Simplex algorithm: Difference between revisions

Revision as of 17:48, 9 February 2021

Revision as of 22:22, 12 February 2021

Line 21:

The simplex algorithm operates on linear programs in the [[canonical form]]

:maximize <math display="inline">\mathbf{c}^\topT} \mathbf{x}</math>

:subject to <math>A\mathbf{x} \leq \mathbf{b}</math> and <math>\mathbf{x} \ge 0</math>

with <math>\mathbf{c} = (c_1,\, \dots,\, c_n)</math> the coefficients of the objective function, <math>(\cdot)^\topmathrm{T}</math> is the [[matrix transpose]], and <math> \mathbf{x} = (x_1,\, \dots,\, x_n)</math> are the variables of the problem, {{mvar|<math>A}}</math> is a ''p''×''n'' matrix, and <math> \mathbf{b} = (b_1,\, \dots,\, b_p)</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{{math|'''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]]. An extreme point or vertex of this polytope is known as ''[[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>

Line 33:

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 that 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 above.<ref name="DantzigThapa1">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="NeringTucker"/><ref name="Vanderbei">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. {{isbn|978-0-387-74387-5}}. <!-- (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.) --></ref>

==Standard form==

Line 75 ⟶ 76:

:<math>

\begin{bmatrix}

1 & -\mathbf{c}^\topT & 0 \\

0 & \mathbf{A} & \mathbf{b}

\end{bmatrix}

</math>

The first row defines the objective function and the remaining rows specify the constraints. The zero in the first column represents the zero vector of the same dimension as vector ''b''. (Different authors use different conventions as to the exact layout). If the columns of A can be rearranged so that it contains the [[identity matrix]] of order ''p'' (the number of rows in A) then the tableau is said to be in ''canonical form''.<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> The variables corresponding to the columns of the identity matrix are called ''basic variables'' while the remaining variables are called ''nonbasic'' or ''free variables''. If the values of the nonbasic variables are set to 0, then the values of the basic variables are easily obtained as entries in ''b'' and this solution is a basic feasible solution. The algebraic interpretation here is that the coefficients of the linear equation represented by each row are either {{<math|>0}}</math>, {{<math|>1}}</math>, or some other number. Each row will have {{<math|>1}}</math> column with value {{<math|>1}}</math>, {{<math|''>p'' − -1}}</math> columns with coefficients {{<math|>0}}</math>, and the remaining columns with some other coefficients (these other variables represent our non-basic variables). By setting the values of the non-basic variables to zero we ensure in each row that the value of the variable represented by a {{<math|>1}}</math> in its column is equal to the {{mvar|<math>b}}</math> value at that row.

Conversely, given a basic feasible solution, the columns corresponding to the nonzero variables can be expanded to a nonsingular matrix. If the corresponding tableau is multiplied by the inverse of this matrix then the result is a tableau in canonical form.<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>

Line 87 ⟶ 88:

:<math>

\begin{bmatrix}

1 & -\mathbf{c}^\top_BT_B & -\mathbf{c}^\top_DT_D & 0 \\

0 & I & \mathbf{D} & \mathbf{b}

\end{bmatrix}

Line 95 ⟶ 96:

:<math>

\begin{bmatrix}

1 & 0 & -\bar{\mathbf{c}}^\top_DT_D & z_B \\

0 & I & \mathbf{D} & \mathbf{b}

\end{bmatrix}