Simplex algorithm: Difference between revisions

Revision as of 11:52, 18 May 2015

Revision as of 12:01, 18 May 2015

Line 35:

== History ==

George Dantzig worked on planning methods for US Air Force during World War II using desk calculator. During 1946 his colleague challenged him to mechanize the planning process in order to entice him into not taking another job. Dantzig formulated the problem as linear inequalities inspired by the work of [[Wassily Leontief]] however at that time he didn't included objective as part of his formulation. Without objective, vast number of solutions can be feasible and therefore to find the "best" feasible solution military specified "ground rules" that described how goal can be achieved as opposed to specifying goal itself. Dantzig's core insight was to realize that most such ground rules can be translated in to linear objective function that needs to be maximized.<ref>{{Cite journal|url = http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|title = Reminiscences about the origins of linear programming|last = |first = |date = April, 1982|journal = Operations Research Letter|doi = 10.1016/0167-6377(82)90043-8|pmid = |access-date = |volume = 1|issue = 2}}</ref> Development of simplex method was evolutionary and happened over a period of about a year.<ref>{{Cite journal|url = http://www.phpsimplex.com/en/Dantzig_interview.htm|title = An Interview with George B. Dantzig: The Father of Linear Programming|last = Albers and Reid|first = |date = 1986|journal = College Mathematics Journal|doi = |pmid = |access-date = |pages = 292–314}}</ref>

After Dantzig included objective function as part of his formulation during mid-1947, the problem was mathematically more tractable. Dantzig realized that one of the unsolved problems that [[George Dantzig#Urban Legend|he mistook]] as homework in his professor [[Jerzy Neyman]]'s class and actually solved it was applicable to finding algorithm for linear programs. This problem involved finding existence of Lagrange multipliers for general linear program over a continuum of variables each bounded between zero and one and satisfying linear constraints expressed in the form of Lebesgue integrals. Dantzig later published his "homework" as thesis to earn his doctorate. The column geometry used in this thesis gave Dantzig insight that made him believe that Simplex method would be very efficient.<ref>{{Cite journal|url = http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|title = Origins of the simplex method|last = Dantzig|first = George|date = May 1987|journal = A history of scientific computing|doi = 10.1145/87252.88081|pmid = |access-date = |isbn = 0-201-50814-1}}</ref>