Editing Linear programming (section)

== History ==
[[File:Leonid Kantorovich 1975.jpg|thumb|[[Leonid Kantorovich]]]]
[[File:JohnvonNeumann-LosAlamos.gif|thumb|[[John von Neumann]]]]

The problem of solving a system of linear inequalities dates back at least as far as [[Joseph Fourier|Fourier]], who in 1827 published a method for solving them,<ref name="SierksmaZwols2015">{{cite book|author1=Gerard Sierksma|author2=Yori Zwols|title=Linear and Integer Optimization: Theory and Practice|edition=3rd|year=2015|publisher=CRC Press|isbn=978-1498710169|page=1}}</ref> and after whom the method of [[Fourier–Motzkin elimination]] is named.

In the late 1930s, Soviet mathematician [[Leonid Kantorovich]] and American economist [[Wassily Leontief]] independently delved into the practical applications of linear programming. Kantorovich focused on manufacturing schedules, while Leontief explored economic applications. Their groundbreaking work was largely overlooked for decades.

The turning point came during World War II when linear programming emerged as a vital tool. It found extensive use in addressing complex wartime challenges, including transportation logistics, scheduling, and resource allocation. Linear programming proved invaluable in optimizing these processes while considering critical constraints such as costs and resource availability.

Despite its initial obscurity, the wartime successes propelled linear programming into the spotlight. Post-WWII, the method gained widespread recognition and became a cornerstone in various fields, from operations research to economics. The overlooked contributions of Kantorovich and Leontief in the late 1930s eventually became foundational to the broader acceptance and utilization of linear programming in optimizing decision-making processes.<ref>{{Cite web |title=Linear programming {{!}} Definition & Facts {{!}} Britannica |url=https://www.britannica.com/science/linear-programming-mathematics |access-date=2023-11-20 |website=www.britannica.com |language=en}}</ref>

Kantorovich's work was initially neglected in the [[USSR]].<ref name="dantzig1982">{{cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = Reminiscences about the origins of linear programming|author=George B. Dantzig|date = April 1982|journal = Operations Research Letters|volume = 1|issue = 2|pages = 43–48|doi = 10.1016/0167-6377(82)90043-8}}</ref> About the same time as Kantorovich, the Dutch-American economist [[Tjalling Koopmans|T. C. Koopmans]] formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975 [[Nobel Memorial Prize in Economic Sciences]].<ref name="SierksmaZwols2015" /> In 1941, [[Frank Lauren Hitchcock]] also formulated transportation problems as linear programs and gave a solution very similar to the later [[simplex method]].<ref name="Schrijver1998">{{cite book |author=Alexander Schrijver |title=Theory of Linear and Integer Programming |publisher=John Wiley & Sons |year=1998 |isbn=978-0-471-98232-6 |pages=221–222}}</ref> Hitchcock had died in 1957, and the Nobel Memorial Prize is not awarded posthumously.

From 1946 to 1947 [[George Dantzig|George B. Dantzig]] independently developed general linear programming formulation to use for planning problems in the US Air Force.<ref name=":0">{{Cite book|title=Linear programming|last1=Dantzig|first1=George B.|last2=Thapa|first2=Mukund Narain|date=1997|publisher=Springer|isbn=0387948333|location=New York|page=xxvii|oclc=35318475}}</ref> In 1947, Dantzig also invented the [[Simplex algorithm|simplex method]] that, for the first time efficiently, tackled the linear programming problem in most cases.<ref name=":0" /> When Dantzig arranged a meeting with [[John von Neumann]] to discuss his simplex method, von Neumann immediately conjectured the theory of [[#Duality|duality]] by realizing that the problem he had been working in [[game theory]] was equivalent.<ref name=":0" /> Dantzig provided formal proof in an unpublished report "A Theorem on Linear Inequalities" on January 5, 1948.<ref name="dantzig1982"/> Dantzig's work was made available to public in 1951. 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 [[Abundance of the chemical elements|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,<ref name = "khachiyan79">{{cite journal|title = A Polynomial Algorithm for Linear Programming|author = Leonid Khachiyan|date = 1979|journal = Doklady Akademii Nauk SSSR|volume=224|issue=5|pages=1093–1096}}</ref> 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.<ref name = "karmarkar84" >{{cite journal|title = A New Polynomial-Time Algorithm for Linear Programming|author = Narendra Karmarkar|date = 1984|journal = Combinatorica|volume=4|issue = 4|pages=373–395|doi = 10.1007/BF02579150|s2cid = 7257867}}</ref>