Revised simplex method: Difference between revisions

Revision as of 16:59, 12 March 2014

Latest revision as of 08:04, 11 February 2025

(25 intermediate revisions by 16 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 20:

\begin{align}

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

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

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

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

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'''''&ensp; '''''N'''''&#93;]}}. Then {{math|'''''x'''''}} is given by

:<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},

\end{align}

Line 73:

:<math>

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

Line 85:

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

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

i.e., every unit increase in {{math|''x_q''}} will results in a decrease by {{math|−''s_q''}} in {{math|'''''c'''''^T'''''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_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'''''^T'''''x'''''}} 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.

Line 102:

\begin{bmatrix}

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

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

\boldsymbol{A} & =

\begin{bmatrix}

3 & 2 & 1 & 1 & 0 \\

2 & 5 & 3 & 0 & 1

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

\boldsymbol{b} & =

\begin{bmatrix}

10 \\

15

\end{bmatrix}\text{.}

\end{align}

</math>

Line 123:

\begin{bmatrix}

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

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

\boldsymbol{N} & =

\begin{bmatrix}

Line 131:

</math>

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

:<math>

Line 137:

\boldsymbol{\lambda} & =

\begin{bmatrix}

100 & 150

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

\boldsymbol{s_N} & =

\begin{bmatrix}

-622 & -983 & -594

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

\end{align}

</math>

Choose {{math|''q'' {{=}} 3}} as the entering index. Then {{math|'''''d''''' {{=}} &#91;[1&ensp; 3&#93;]^T}}, which means a unit increase in {{math|''x''₃}} will 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,

Line 155:

\begin{bmatrix}

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

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

\boldsymbol{N} & =

\begin{bmatrix}

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

\end{bmatrix}\text{.}

\end{align}

</math>

Line 170:

\begin{bmatrix}

0 & 0 & 5 & 5 & 0

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

\boldsymbol{\lambda} & =

\begin{bmatrix}

0 & -4/3

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

\boldsymbol{s_N} & =

\begin{bmatrix}

2/3 & 11/3 & 4/3

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

\end{align}

</math>

Line 186:

==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 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 237 ⟶ 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 246 ⟶ 248:

[[Category:Exchange algorithms]]

[[Category:Linear programming]]

[[Category:Operations research]]

[[Category:Optimization algorithms and methods]]