revised simplex method

For the rest of the discussion, it is assumed that a linear programming problem has been converted into the following standard form:

:$$

\begin{array}{rl}

\text{minimize} & \boldsymbol{c}^{\mathrm{T}} \boldsymbol{x} \\

\text{subject to} & \boldsymbol{Ax} = \boldsymbol{b}, \boldsymbol{x} \ge \boldsymbol{0}

\end{array}

where {{math|A ∈ ℝ^m×n}}. Without loss of generality, it is assumed that the constraint matrix {{math|A}} has full row rank and that the problem is feasible, i.e., there is at least one {{math|x ≥ 0}} such that {{math|Ax {{=}} b}}. If {{math|A}} is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.

For linear programming, the Karush–Kuhn–Tucker conditions are both necessary and sufficient for optimality. The KKT conditions of a linear programming problem in the standard form is

:$$

\begin{align}

\boldsymbol{Ax} & = \boldsymbol{b}, \\

\boldsymbol{A}^{\mathrm{T}} \boldsymbol{\lambda} + \boldsymbol{s} & = \boldsymbol{c}, \\

\boldsymbol{x} & \ge \boldsymbol{0}, \\

\boldsymbol{s} & \ge \boldsymbol{0}, \\

\boldsymbol{s}^{\mathrm{T}} \boldsymbol{x} & = 0

\end{align}

where {{math|λ}} and {{math|s}} are the Lagrange multipliers associated with the constraints {{math|Ax {{=}} b}} and {{math|x ≥ 0}}, respectively.{{sfn|Nocedal|Wright|2006|p=358|loc=Eq. 13.4}} The last condition, which is equivalent to {{math|s_ix_i {{=}} 0}} for all {{math|1 < i < n}}, is called the complementary slackness condition.

By what is sometimes known as the fundamental theorem of linear programming, a vertex {{math|x}} of the feasible polytope can be identified by being a basis {{math|B}} of {{math|A}} chosen from the latter's columns.{{efn|The same theorem also states that the feasible polytope has at least one vertex and that there is at least one vertex which is optimal.{{sfn|Nocedal|Wright|2006|p=363|loc=Theorem 13.2}}}} Since {{math|A}} has full rank, {{math|B}} is nonsingular. Without loss of generality, assume that {{math|A {{=}} [B N]}}. Then {{math|x}} is given by

:$$

\boldsymbol{x} =

\begin{bmatrix}

\boldsymbol{x_B} \\

\boldsymbol{x_N}

\end{bmatrix} =

\begin{bmatrix}

\boldsymbol{B}^{-1} \boldsymbol{b} \\

\boldsymbol{0}

\end{bmatrix}

where {{math|x_B ≥ 0}}. Partition {{math|c}} and {{math|s}} accordingly into

:$$

\begin{align}

\boldsymbol{c} & =

\begin{bmatrix}

\boldsymbol{c_B} \\

\boldsymbol{c_N}

\end{bmatrix}, \\

\boldsymbol{s} & =

\begin{bmatrix}

\boldsymbol{s_B} \\

\boldsymbol{s_N}

\end{bmatrix}.

\end{align}

To satisfy the complementary slackness condition, let {{math|s_B {{=}} 0}}. It follows that

:$$

\begin{align}

\boldsymbol{B}^{\mathrm{T}} \boldsymbol{\lambda} & = \boldsymbol{c_B}, \\

\boldsymbol{N}^{\mathrm{T}} \boldsymbol{\lambda} + \boldsymbol{s_N} & = \boldsymbol{c_N},

\end{align}

which implies that

:$$

\begin{align}

\boldsymbol{\lambda} & = (\boldsymbol{B}^{\mathrm{T}})^{-1} \boldsymbol{c_B}, \\

\boldsymbol{s_N} & = \boldsymbol{c_N} - \boldsymbol{N}^{\mathrm{T}} \boldsymbol{\lambda}.

\end{align}

If {{math|s_N ≥ 0}} at this point, the KKT conditions are satisfied, and thus {{math|x}} is optimal.

If the KKT conditions are violated, a pivot operation consisting of introducing a column of {{math|N}} into the basis at the expense of an existing column in {{math|B}} is performed. In the absence of degeneracy, a pivot operation always results in a strict decrease in {{math|c^Tx}}. Therefore, if the problem is bounded, the revised simplex method must terminate at an optimal vertex after repeated pivot operations because there are only a finite number of vertices.{{sfn|Nocedal|Wright|2006|p=370|loc=Theorem 13.4}}

Select an index {{math|m < q ≤ n}} such that {{math|s_q < 0}} as the entering index. The corresponding column of {{math|A}}, {{math|A_q}}, will be moved into the basis, and {{math|x_q}} will be allowed to increase from zero. It can be shown that

:$\backslash frac\{\backslash partial\; (\backslash boldsymbol\{c\}^\{\backslash mathrm\{T\}\}\; \backslash boldsymbol\{x\})\}\{\backslash partial\; x\_q\}\; =\; s\_q,$

i.e., every unit increase in {{math|x_q}} results in a decrease by {{math|−s_q}} in {{math|c^Tx}}.{{sfn|Nocedal|Wright|2006|p=369|loc=Eq. 13.24}} Since

:$\backslash boldsymbol\{B\; x\_B\}\; +\; \backslash boldsymbol\{A\}\_q\; x\_q\; =\; \backslash boldsymbol\{b\},$

{{math|x_B}} must be correspondingly decreased by {{math|Δx_B {{=}} B⁻¹A_qx_q}} subject to {{math|x_B − Δx_B ≥ 0}}. Let {{math|d {{=}} B⁻¹A_q}}. If {{math|d ≤ 0}}, no matter how much {{math|x_q}} is increased, {{math|x_B − Δx_B}} will stay nonnegative. Hence, {{math|c^Tx}} can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index {{math|p {{=}} argmin_1≤i≤m {{(}}x_i/d_i {{!}} d_i > 0{{)}}}} as the leaving index. This choice effectively increases {{math|x_q}} from zero until {{math|x_p}} is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing {{math|A_p}} with {{math|A_q}} in the basis.

{{seealso|Simplex method#Example}}

Consider a linear program where

:$$

\begin{align}

\boldsymbol{c} & =

\begin{bmatrix}

-2 & -3 & -4 & 0 & 0

\end{bmatrix}^{\mathrm{T}}, \\

\boldsymbol{A} & =

\begin{bmatrix}

3 & 2 & 1 & 1 & 0 \\

2 & 5 & 3 & 0 & 1

\end{bmatrix}, \\

\boldsymbol{b} & =

\begin{bmatrix}

10 \\

15

\end{bmatrix}.

\end{align}

Let

:$$

\begin{align}

\boldsymbol{B} & =

\begin{bmatrix}

\boldsymbol{A}_4 & \boldsymbol{A}_5

\end{bmatrix}, \\

\boldsymbol{N} & =

\begin{bmatrix}

\boldsymbol{A}_1 & \boldsymbol{A}_2 & \boldsymbol{A}_3

\end{bmatrix}

\end{align}

initially, which corresponds to a feasible vertex {{math|x {{=}} [0 0 0 10 15]^T}}. At this moment,

:$$

\begin{align}

\boldsymbol{\lambda} & =

\begin{bmatrix}

0 & 0

\end{bmatrix}^{\mathrm{T}}, \\

\boldsymbol{s_N} & =

\begin{bmatrix}

-2 & -3 & -4

\end{bmatrix}^{\mathrm{T}}.

\end{align}

Choose {{math|q {{=}} 3}} as the entering index. Then {{math|d {{=}} [1 3]^T}}, which means a unit increase in {{math|x₃}} results in {{math|x₄}} and {{math|x₅}} being decreased by {{math|1}} and {{math|3}}, respectively. Therefore, {{math|x₃}} is increased to {{math|5}}, at which point {{math|x₅}} is reduced to zero, and {{math|p {{=}} 5}} becomes the leaving index.

After the pivot operation,

:$$

\begin{align}

\boldsymbol{B} & =

\begin{bmatrix}

\boldsymbol{A}_3 & \boldsymbol{A}_4

\end{bmatrix}, \\

\boldsymbol{N} & =

\begin{bmatrix}

\boldsymbol{A}_1 & \boldsymbol{A}_2 & \boldsymbol{A}_5

\end{bmatrix}.

\end{align}

Correspondingly,

:$$

\begin{align}

\boldsymbol{x} & =

\begin{bmatrix}

0 & 0 & 5 & 5 & 0

\end{bmatrix}^{\mathrm{T}}, \\

\boldsymbol{\lambda} & =

\begin{bmatrix}

0 & -4/3

\end{bmatrix}^{\mathrm{T}}, \\

\boldsymbol{s_N} & =

\begin{bmatrix}

2/3 & 11/3 & 4/3

\end{bmatrix}^{\mathrm{T}}.

\end{align}

A positive {{math|s_N}} indicates that {{math|x}} is now optimal.

{{seealso|Simplex method#Degeneracy: stalling and cycling}}

Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not result in a decrease in {{math|c^Tx}}, and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.{{sfn|Nocedal|Wright|2006|p=381|loc=§13.5}}

Two types of linear systems involving {{math|B}} are present in the revised simplex method:

:$$

\begin{align}

\boldsymbol{B z} & = \boldsymbol{y}, \\

\boldsymbol{B}^{\mathrm{T}} \boldsymbol{z} & = \boldsymbol{y}.

\end{align}

Instead of refactorizing {{math|B}}, usually an LU factorization is directly updated after each pivot operation, for which purpose there exist several strategies such as the Forrest−Tomlin and Bartels−Golub methods. However, the amount of data representing the updates as well as numerical errors builds up over time and makes periodic refactorization necessary.{{sfn|Morgan|1997|loc=§2}}{{sfn|Nocedal|Wright|2006|p=372|loc=§13.4}}

{{notelist}}

{{reflist|2}}

{{refbegin}}

• {{cite thesis

|last=Morgan

|first=S. S.

|degree=MSc

|title=A Comparison of Simplex Method Algorithms

|publisher=University of Florida

|year=1997

|url=http://www.cise.ufl.edu/research/sparse/Morgan/index.htm

|archive-url=https://web.archive.org/web/20110807134509/http://www.cise.ufl.edu/research/sparse/Morgan/index.htm

|archive-date=7 August 2011

}}

• {{cite book

|last1=Nocedal

|first1=J.

|last2=Wright

|first2=S. J.

|editor1-last=Mikosch

|editor1-first=T. V.

|editor2-last=Resnick

|editor2-first=S. I.

|editor3-last=Robinson

|editor3-first=S. M.

|title=Numerical Optimization

|edition=2nd

|year=2006

|series=Springer Series in Operations Research and Financial Engineering

|publisher=Springer

|location=New York, NY, USA

|isbn=978-0-387-30303-1

|url=https://www.springer.com/mathematics/book/978-0-387-30303-1

}}

{{refend}}

{{Optimization algorithms|convex}}

{{Mathematical programming}}

Category:Exchange algorithms

Category:Linear programming