Simplex algorithm: Difference between revisions

Revision as of 17:10, 4 February 2019

Revision as of 17:17, 4 February 2019

Line 21:

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

In geometric terms, the [[feasible region]] defined by all values of <math>\mathbf{x}</math> such that <math display="inline">A\mathbf{x} \le \mathbf{b}</math> and <math>\forall i, x_i \ge 0 </math> is a (possibly unbounded) [[convex polytope]]. There is a simple characterization of theAn extreme pointspoint or verticesvertex of this polytope, namely an element <math> \mathbf{x} = (x_1,\, \dots,\, x_n)</math> of the feasible region is an extreme point if and only if the subset of column vectors <math>A_i</math> corresponding to the nonzero entries of <math>\mathbf{x}</math> <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>