Content deleted Content added
No edit summary |
|||
Line 27:
is a (possibly unbounded) [[convex polytope]]. There is a simple characterization of the extreme points or vertices of this polytope, namely <math>\scriptstyle x \;=\; (x_1,\, \dots,\, x_n)</math> is an extreme point if and only if the column vectors <math>\scriptstyle A_i</math>, where <math>\scriptstyle x_i \,\ne\, 0</math>, are [[Linear independence|linearly independent]].<ref>{{harvtxt|Murty|1983|loc=Theorem 3.1}}</ref> In this context such a point is known as a ''basic feasible solution'' (BFS).
It can be shown that for a linear program in standard form, if the objective function has a minimum value on the feasible region then it has this value on (at least) one of the extreme points.<ref>{{harvtxt|Murty|1983|loc=Theorem 3.3}}</ref> This in itself reduces the problem to a finite computation since there are finite number of extreme points, but the number of extreme points is [[http://en.wikipedia.org/wiki/Observable_universe#Matter_content|unmanageably large]] for all but the smallest linear programs.<ref>{{harvtxt|Murty|1983|loc=Section 3.13|p=143}}</ref>
It can also be shown that if an extreme point is not a minimum point of the objective function then there is an edge containing the point so that the objective function is strictly decreasing 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 smaller value, otherwise the objective function is unbounded below 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 lower and lower objective values. This continues until the minimum 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"/>
| |||