Simplex algorithm: Difference between revisions

Revision as of 01:26, 24 March 2014

Revision as of 20:18, 28 March 2014

Line 26:

::<math>\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 0</math>

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 subset of column vectors <math>\scriptstyle A_i</math>, wherecorresponding to the nonzero entries of ''x'' (<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 is a finite number of extreme points, but the number of extreme points is unmanageably large for all but the smallest linear programs.<ref>{{harvtxt|Murty|1983|loc=Section 3.13|p=143}}</ref>