Revised simplex method

In mathematical optimization, the revised simplex method is a variant of George Dantzig's simplex method for linear programming.

The revised simplex method is mathematically equivalent to the standard simplex method but differs in implementation. Instead of maintaining a tableau which explicitly represents the constraints adjusted to a set of basic variables, it maintains a representation of a basis of the matrix representing the constraints. The matrix-oriented approach allows for greater computational efficiency by enabling sparse matrix operations.Template:Sfn

Problem formulation

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

$\begin{array}{cc}\text{minimize}& {𝒄}^{\mathrm{T}}𝒙\\ \text{subject to}& 𝑨𝒙=𝒃,𝒙\ge 0\end{array}$

where Template:Math. Without loss of generality, it is assumed that the constraint matrix Template:Math has full row rank and that the problem is feasible, i.e., there is at least one Template:Math such that Template:Math. If Template:Math is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.

Algorithmic description

Optimality conditions

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{array}{cc}𝑨𝒙& =𝒃,\\ {𝑨}^{\mathrm{T}}\mathit{\lambda }+𝒔& =𝒄,\\ 𝒙& \ge 0,\\ 𝒔& \ge 0,\\ {𝒔}^{\mathrm{T}}𝒙& =0\end{array}$

where Template:Math and Template:Math are the Lagrange multipliers associated with the constraints Template:Math and Template:Math, respectively.Template:Sfn The last condition, which is equivalent to Template:Math for all Template:Math, is called the complementary slackness condition.

By what is sometimes known as the fundamental theorem of linear programming, a vertex Template:Math of the feasible polytope can be identified by being a basis Template:Math of Template:Math chosen from the latter's columns.Template:Efn Since Template:Math has full rank, Template:Math is nonsingular. Without loss of generality, assume that Template:Math. Then Template:Math is given by

$𝒙=\left[\begin{array}{c}{𝒙}_{𝑩}\\ {𝒙}_{𝑵}\end{array}\right]=\left[\begin{array}{c}{𝑩}^{-1}𝒃\\ 0\end{array}\right]$

where Template:Math. Partition Template:Math and Template:Math accordingly into

$\begin{array}{cc}𝒄& =\left[\begin{array}{c}{𝒄}_{𝑩}\\ {𝒄}_{𝑵}\end{array}\right],\\ 𝒔& =\left[\begin{array}{c}{𝒔}_{𝑩}\\ {𝒔}_{𝑵}\end{array}\right].\end{array}$

To satisfy the complementary slackness condition, let Template:Math. It follows that

$\begin{array}{cc}{𝑩}^{\mathrm{T}}\mathit{\lambda }& ={𝒄}_{𝑩},\\ {𝑵}^{\mathrm{T}}\mathit{\lambda }+{𝒔}_{𝑵}& ={𝒄}_{𝑵},\end{array}$

which implies that

$\begin{array}{cc}\mathit{\lambda }& =({𝑩}^{\mathrm{T}}{)}^{-1}{𝒄}_{𝑩},\\ {𝒔}_{𝑵}& ={𝒄}_{𝑵}-{𝑵}^{\mathrm{T}}\mathit{\lambda }.\end{array}$

If Template:Math at this point, the KKT conditions are satisfied, and thus Template:Math is optimal.

Pivot operation

If the KKT conditions are violated, a pivot operation consisting of introducing a column of Template:Math into the basis at the expense of an existing column in Template:Math is performed. In the absence of degeneracy, a pivot operation always results in a strict decrease in Template:Math. 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.Template:Sfn

Select an index Template:Math such that Template:Math as the entering index. The corresponding column of Template:Math, Template:Math, will be moved into the basis, and Template:Math will be allowed to increase from zero. It can be shown that

$\frac{\partial ({𝒄}^{\mathrm{T}}𝒙)}{\partial x_q}=s_q,$

i.e., every unit increase in Template:Math results in a decrease by Template:Math in Template:Math.Template:Sfn Since

$𝑩{𝒙}_{𝑩}+{𝑨}_q{x}_q=𝒃,$

Template:Math must be correspondingly decreased by Template:Math subject to Template:Math. Let Template:Math. If Template:Math, no matter how much Template:Math is increased, Template:Math will stay nonnegative. Hence, Template:Math can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index Template:Math as the leaving index. This choice effectively increases Template:Math from zero until Template:Math is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing Template:Math with Template:Math in the basis.

Numerical example

Template:Seealso Consider a linear program where

$\begin{array}{cc}𝒄& ={\left[\begin{array}{ccccc}-2& -3& -4& 0& 0\end{array}\right]}^{\mathrm{T}},\\ 𝑨& =\left[\begin{array}{ccccc}3& 2& 1& 1& 0\\ 2& 5& 3& 0& 1\end{array}\right],\\ 𝒃& =\left[\begin{array}{c}10\\ 15\end{array}\right].\end{array}$

Let

$\begin{array}{cc}𝑩& =\left[\begin{array}{cc}{𝑨}_4& {𝑨}_5\end{array}\right],\\ 𝑵& =\left[\begin{array}{ccc}{𝑨}_1& {𝑨}_2& {𝑨}_3\end{array}\right]\end{array}$

initially, which corresponds to a feasible vertex Template:Math. At this moment,

$\begin{array}{cc}\mathit{\lambda }& ={\left[\begin{array}{cc}0& 0\end{array}\right]}^{\mathrm{T}},\\ {𝒔}_{𝑵}& ={\left[\begin{array}{ccc}-2& -3& -4\end{array}\right]}^{\mathrm{T}}.\end{array}$

Choose Template:Math as the entering index. Then Template:Math, which means a unit increase in Template:Math results in Template:Math and Template:Math being decreased by Template:Math and Template:Math, respectively. Therefore, Template:Math is increased to Template:Math, at which point Template:Math is reduced to zero, and Template:Math becomes the leaving index.

After the pivot operation,

$\begin{array}{cc}𝑩& =\left[\begin{array}{cc}{𝑨}_3& {𝑨}_4\end{array}\right],\\ 𝑵& =\left[\begin{array}{ccc}{𝑨}_1& {𝑨}_2& {𝑨}_5\end{array}\right].\end{array}$

Correspondingly,

$\begin{array}{cc}𝒙& ={\left[\begin{array}{ccccc}0& 0& 5& 5& 0\end{array}\right]}^{\mathrm{T}},\\ \mathit{\lambda }& ={\left[\begin{array}{cc}0& -4/3\end{array}\right]}^{\mathrm{T}},\\ {𝒔}_{𝑵}& ={\left[\begin{array}{ccc}2/3& 11/3& 4/3\end{array}\right]}^{\mathrm{T}}.\end{array}$

A positive Template:Math indicates that Template:Math is now optimal.

Practical issues

Degeneracy

Template:Seealso 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 Template:Math, 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.Template:Sfn

Basis representation

Two types of linear systems involving Template:Math are present in the revised simplex method:

$\begin{array}{cc}𝑩𝒛& =𝒚,\\ {𝑩}^{\mathrm{T}}𝒛& =𝒚.\end{array}$

Instead of refactorizing Template:Math, 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.Template:SfnTemplate:Sfn

Notes and references

Bibliography

• Template:Cite thesis
• Template:Cite book