Question

"linear programming". Find out a little more about the history of how and when this method was developed and in what kinds of settings it is used. Remember to cite your sources.

Answer 1

The linear programming problem was developed between    (1827-1984)

The problem of solving a system of linear inequalities dates back at least as far as Fourier, who in 1827 published a method for solving them, and after whom the method of Fourier– Motzkin elimination is named.

In 1939 a linear programming formulation of a problem that is equivalent to the general linear programming problem was given by the Soviet economist Leonid Kantorovich , who also proposed a method for solving it. It is a way he developed, during World War II, to plan expenditures and returns in order to reduce costs of the army and to increase losses imposed on the enemy. Kantorovich's work was initially neglected in the USSR. About the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975 Nobel prize in economics.In 1941, Frank Lauren Hitchcock also formulated transportation problems as linear programs and gave a solution very similar to the later simplex method. Hitchcock had died in 1957 and the Nobel prize is not awarded posthumously.

During 1946–1947, George B. Dantzig independently developed general linear programming formulation to use for planning problems in US Air Force^[4]. In 1947, Dantzig also invented the simplex method that for the first time efficiently tackled the linear programming problem in most cases. When Dantzig arranged a meeting with John von Neumann to discuss his simplex method, Neumann immediately conjectured the theory of duality by realizing that the problem he had been working in game theory was equivalent. Dantzig provided formal proof in an unpublished report "A Theorem on Linear Inequalities" on January 5, 1948. In the post-war years, many industries applied it in their daily planning.

Dantzig's original example was to find the best assignment of 70 people to 70 jobs. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the observable universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm. The theory behind linear programming drastically reduces the number of possible solutions that must be checked.

The linear programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior-point method for solving linear-programming problems.

how did linear programming first developed?

During 1946-1947 George B. Dantzig independently developed general linear programming formulation to use for planning

problem in US Air Force in 1947.

A linear programming problems are defined as the maximizing or minimizing a linear function subject to linear constraints.The constraints may be equalities or inequalities.