1939, the Soviet mathematician лв Kantorovich put forward the linear programming problem in the book Mathematical Methods in Production Organization and Planning, which also did not attract attention.
1947, American mathematician G.B.Dantzing put forward the simplex method for solving linear programming, which laid the foundation of this subject.
1947, American mathematician J.von Neumann put forward duality theory, which opened up many new research fields of linear programming and expanded its application scope and problem-solving ability.
195 1 year, American economist T.C. Kupmans applied linear programming to the economic field, for which he and Kantrovich jointly won the 1975 Nobel Prize in Economics.
Since 1950s, people have done a lot of theoretical research on linear programming, and a large number of new algorithms have emerged. For example, 1954 C. Lemcke proposed the dual simplex method, 1954 S. Gass and T. Sadie solved the sensitivity analysis and parametric programming problem of linear programming, 1956 A. Tucker proposed the complementary relaxation theorem, 1960 G. B. Danzig and.
The research results of linear programming also directly promote the algorithm research of other mathematical programming problems, including integer programming, stochastic programming and nonlinear programming. With the development of digital computer, many linear programming softwares have appeared, such as MPSX, OPHEIE, predictor and so on. Can easily solve the linear programming problem of thousands of variables.
1979, the Soviet mathematician L. G. Khachian proposed an ellipsoid algorithm for solving linear programming problems, and proved that it is a polynomial time algorithm.
1984, N. Kamaka, an Indian mathematician at Bell Telephone Laboratory in the United States, proposed a new polynomial time algorithm for solving linear programming problems. When the number of variables is 5000, only 1/50 of the simplex method time is needed to solve the linear programming problem. The polynomial algorithm theory of linear programming has been formed. Since 1950s, the application scope of linear programming has been expanding. Method of establishing linear programming model