History
The problem of solving a system of linear inequalities dates back at least as far as Fourier, after whom the method of Fourier-Motzkin elimination is named. The earliest linear programming was first developed by Leonid Kantorovich in 1939. Leonid Kantorovich developed the earliest linear programming problems in 1939 for use during World War II to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. The method was kept secret until 1947 when George B. Dantzig published the simplex method and John von Neumann developed the theory of duality as a linear optimization solution, and applied it in the field of game theory. Postwar, many industries found its use in their daily planning.
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.
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 optimal solutions that must be checked.
Read more about this topic: Linear Programming
Famous quotes containing the word history:
“The history of American politics is littered with bodies of people who took so pure a position that they had no clout at all.”
—Ben C. Bradlee (b. 1921)
“Racism is an ism to which everyone in the world today is exposed; for or against, we must take sides. And the history of the future will differ according to the decision which we make.”
—Ruth Benedict (1887–1948)
“The principle that human nature, in its psychological aspects, is nothing more than a product of history and given social relations removes all barriers to coercion and manipulation by the powerful.”
—Noam Chomsky (b. 1928)