|
It this paper the evolution of methods for the linear programming problem (LPP) and their influence on mathematics development is studied. The core problem, connecting many researches, was the polynomial and effective LPP solving method search. We analyze the contributions of Levin A.Y. (Levin-Newman method of central sections), Nemirovskii A.S. (ellipsoid method), L.G. Khachiyan (LPP polynomial-time solvability proof by introducing the innovational approach). The paper also considers the influence of N. Karmarkar's ‒ the author of algorithm, converging to the solution by cutting through the feasible polyhedron instead of going along its boundary, as well as the contributions of Levin L.A., who investigated the universal problems, complexity and reducibility.
Keywords:Linear programming, optimization, Levin-Newman method of central sections, ellipsoid method, polynomial-time solvability, Levin, Nemirovskii, Khachiyan, Karmarkar.
|