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:
“While the Republic has already acquired a history world-wide, America is still unsettled and unexplored. Like the English in New Holland, we live only on the shores of a continent even yet, and hardly know where the rivers come from which float our navy.”
—Henry David Thoreau (1817–1862)
“In every election in American history both parties have their clichés. The party that has the clichés that ring true wins.”
—Newt Gingrich (b. 1943)
“It is the true office of history to represent the events themselves, together with the counsels, and to leave the observations and conclusions thereupon to the liberty and faculty of every man’s judgement.”
—Francis Bacon (1561–1626)