Content deleted Content added
→Overview: again: maximization, not minimization. |
Added history section describing how simplex method was developed |
||
Line 32:
It can also be shown that if an extreme point is not a maximum point of the objective function then there is an edge containing the point so that the objective function is strictly increasing on the edge moving away from the point.<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> If the edge is finite then the edge connects to another extreme point where the objective function has a greater value, otherwise the objective function is unbounded above on the edge and the linear program has no solution. The simplex algorithm applies this insight by walking along edges of the polytope to extreme points with greater and greater objective values. This continues until the maximum value is reached or an unbounded edge is visited, concluding that the problem has no solution. The algorithm always terminates because the number of vertices in the polytope is finite; moreover since we jump between vertices always in the same direction (that of the objective function), we hope that the number of vertices visited will be small.<ref name="Murty137"/>
The solution of a linear program is accomplished in two steps. In the first step, known as Phase I, a starting extreme point is found. Depending on the nature of the program this may be trivial, but in general it can be solved by applying the simplex algorithm to a modified version of the original program. The possible results of Phase I are either a basic feasible solution is found or that the feasible region is empty. In the latter case the linear program is called ''infeasible''. In the second step, Phase II, the simplex algorithm is applied using the basic feasible solution found in Phase I as a starting point. The possible results from Phase II are either an optimum basic feasible solution or an infinite edge on which the objective function is unbounded below.<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Vanderbei"
== 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>
==Standard form==
| |||