Simplex algorithm: Difference between revisions

Revision as of 22:33, 7 July 2016

Revision as of 09:59, 8 July 2016

Line 21:

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

with <math>x = (x_1,\, \dots,\, x_n)</math> the variables of the problem, '''c''' <math>c = (c_1,\, \dots,\, c_n)</math> are the coefficients of the objective function, '''A''' is a ''p×n'' matrix, and '''b''' <math>b = (b_1,\, \dots,\, b_p)</math> constants with <math>b_j\geq 0</math>. There is a straightforward process to convert any linear program into one in standard form so this results in no loss of generality.

In geometric terms, the [[feasible region]] defined by all values of <math>\mathbf{x}</math> such that

::<math>\mathbf{A}\mathbf{x} \le \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 '''x''' <math>x = (x_1,\, \dots,\, x_n)</math> is an extreme point if and only if the subset of column vectors <math>A_i</math> corresponding to the nonzero entries of '''x''' (<math>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 maximum 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>