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:
“It is my conviction that women are the natural orators of the race.”
—Eliza Archard Connor, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 9, by Susan B. Anthony and Ida Husted Harper (1902)
“The second day of July 1776, will be the most memorable epoch in the history of America. I am apt to believe that it will be celebrated by succeeding generations as the great anniversary festival. It ought to be commemorated, as the day of deliverance, by solemn acts of devotion to God Almighty. It ought to be solemnized with pomp and parade, with shows, games, sports, guns, bells, bonfires and illuminations, from one end of this continent to the other, from this time forward forever more”
—John Adams (1735–1826)
“The history of all Magazines shows plainly that those which have attained celebrity were indebted for it to articles similar in natureto Berenice—although, I grant you, far superior in style and execution. I say similar in nature. You ask me in what does this nature consist? In the ludicrous heightened into the grotesque: the fearful coloured into the horrible: the witty exaggerated into the burlesque: the singular wrought out into the strange and mystical.”
—Edgar Allan Poe (1809–1849)