Revised simplex method: Difference between revisions

Revision as of 15:41, 12 March 2014

Latest revision as of 08:04, 11 February 2025

(31 intermediate revisions by 17 users not shown)

Line 1:

In [[mathematical optimization]], the '''revised simplex method''' is ana 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 (linear algebra)|basis]] of the [[Matrix (mathematics)|matrix]] representing the constraints. The matrix-oriented approach allows for greater computational efficiency by enabling sparse matrix operations.{{sfn|Morgan|1997|loc=§2}}

Line 8:

\begin{array}{rl}

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

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

\end{array}

</math>

where {{math|'''''A''''' ∈ '''R'''ℝ^''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.

==Algorithmic description==

Line 19:

:<math>

\begin{align}

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

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

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

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

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

\end{align}

Line 29:

where {{math|'''''λ'''''}} and {{math|'''''s'''''}} are the [[Lagrange multiplier]]s associated with the constraints {{math|'''''Ax''''' {{=}} '''''b'''''}} and {{math|'''''x''''' ≥ '''0'''}}, respectively.{{sfn|Nocedal|Wright|2006|p=358|loc=Eq.&nbsp;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 bebeing 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&nbsp;13.2}}}} Since {{math|'''''A'''''}} has full rank, {{math|'''''B'''''}} is nonsingular. Without loss of generality, assume that {{math|'''''A''''' {{=}} &#91;['''''B''''' '''''N'''''&#93;]}}. Then {{math|'''''x'''''}} is given by

:<math>

Line 51:

\boldsymbol{c_B} \\

\boldsymbol{c_N}

\end{bmatrix}\text{,} \\

\boldsymbol{s} & =

\begin{bmatrix}

\boldsymbol{s_B} \\

\boldsymbol{s_N}

\end{bmatrix}\text{.}

\end{align}

</math>

Line 64:

:<math>

\begin{align}

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

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

\end{align}

</math>

Line 73:

:<math>

\begin{align}

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

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

\end{align}

</math>

Line 81:

===Pivot operation===

If the KKT conditions are violated, a ''pivot operation'' consisting of introducing a column of <{{math>\boldsymbol{|'''''N'''''}}</math> into the basis at the expense of an existing column in <math>\boldsymbol{{math|'''''B'''''}}</math> is performed. In the absence of [[Degeneracy (mathematics)|degeneracy]], a pivot operation always results in a strict decrease in {{math|'''''c'''''<mathsup>\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x}</mathsup>'''''x'''''}}. 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&nbsp;13.4}}

Select an index <{{math>|''m'' < ''q'' \le≤ ''n</math>''}} such that <{{math|''s_{s_qq}'' < 0</math>}} as the ''entering index''. The corresponding column of <math>\boldsymbol{{math|'''''A'''''}}</math>, <math>\boldsymbol{{math|'''''A}_q'''<sub>q</mathsub>''}}, will be moved into the basis, and <{{math|''x<sub>x_qq</mathsub>''}} will be allowed to increase from zero. It can be shown that

:<math>\frac{\partial (\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x})}{\partial x_q} = s_q\text{,}</math>

i.e., every unit increase in <{{math|''x<sub>x_qq</mathsub> will''}} results in a decrease by <{{math|−''s<sub>-s_qq</mathsub>''}} in <math>\boldsymbol{c}^{\mathrm{math|'''''c'''''<sup>T}} \boldsymbol{x}</mathsup>'''''x'''''}}.{{sfn|Nocedal|Wright|2006|p=369|loc=Eq.&nbsp;13.24}} Since

:<math>\boldsymbol{B x_B} + \boldsymbol{A}_q x_q = \boldsymbol{b}\text{,}</math>

<{{math|'''''x<sub>\boldsymbol{x_B}B</mathsub>'''''}} must be correspondingly decreased by <{{math|Δ'''''x_\DeltaB''''' \boldsymbol{x_B} {= \boldsymbol{B}^{-1} \boldsymbol{'''''B'''''⁻¹'''''A}_q x_q'''<sub>q</mathsub>x_q''}} subject to <{{math|'''''x_{\boldsymbol{x_B}B}''''' -− \DeltaΔ'''''x_B''''' \boldsymbol{x_B}≥ \ge \boldsymbol{'''0'''}}</math>. Let <math>\boldsymbol{{math|'''''d}''''' = \boldsymbol{B{=}^{-1} \boldsymbol{'''''B'''''⁻¹'''''A}_q'''<sub>q</mathsub>''}}. If <math>\boldsymbol{{math|'''''d}''''' \le≤ \boldsymbol{'''0'''}}</math>, no matter how much <{{math|''x<sub>x_qq</mathsub>''}} is increased, <{{math|'''''x_{\boldsymbol{x_B}B}''''' -− \Delta \boldsymbol{x_B}Δ'''''x<sub>B</mathsub>'''''}} will stay nonnegative. Hence, <math>\boldsymbol{c}^{\mathrm{math|'''''c'''''<sup>T}} \boldsymbol{x}</mathsup>'''''x'''''}} can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index <{{math>|''p'' = \operatorname{argmin}_{1 \le=}} argmin_{1≤''i \le ''≤''m}''} \{x_i {(}}''x_i''/''d_i'' d_i \mathop{|{!}} d_i''d_i'' > 0\{{)}}}}</math> as the ''leaving index''. This choice effectively increases <{{math|''x<sub>x_qq</mathsub>''}} from zero until <{{math|''x<sub>x_pp</mathsub>''}} is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing <math>\boldsymbol{{math|'''''A}_p'''<sub>p</mathsub>''}} with <math>\boldsymbol{{math|'''''A}_q'''<sub>q</mathsub>''}} in the basis.

==Numerical example==

{{seealso|Simplex method#Example}}

Consider a linear program where

:<math>

\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}

</math>

Let

:<math>

\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}

</math>

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

:<math>

\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}

</math>

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,

:<math>

\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}

</math>

Correspondingly,

:<math>

\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}

</math>

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

==Practical issues==

===Degeneracy===

{{seealso|Simplex method#Degeneracy: Stallingstalling 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 resultsresult in a decrease in {{math|'''''c'''''<mathsup>\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x}</mathsup>'''''x'''''}}, 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}}

===Basis representation===

Two types of [[System of linear equations|linear systems]] involving <math>\boldsymbol{{math|'''''B'''''}}</math> are present in the revised simplex method:

:<math>

\begin{align}

\boldsymbol{B x_Bz} & = \boldsymbol{by}\text{,} \\

\boldsymbol{B}^{\mathrm{T}} \boldsymbol{\lambdaz} & = \boldsymbol{c_By}\text{.}

\end{align}

</math>

Instead of refactorizing <math>\boldsymbol{{math|'''''B'''''}}</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 methodmethods. 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}}

==Notes and references==

Line 129 ⟶ 218:

|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

|ref=harv}}

|archive-date=7 August 2011

}}

* {{cite book

|last1=Nocedal

Line 148 ⟶ 239:

|___location=New York, NY, USA

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

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

}}

|ref=harv}}

{{refend}}

Line 157 ⟶ 248:

[[Category:Exchange algorithms]]

[[Category:Linear programming]]

[[Category:Operations research]]

[[Category:Optimization algorithms and methods]]