Revised simplex method: Difference between revisions

Revision as of 15:25, 19 August 2014

Latest revision as of 08:04, 11 February 2025

(19 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 11:

\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 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 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 87:

:<math>\frac{\partial (\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x})}{\partial x_q} = s_q,</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},</math>

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 146:

</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 177:

\boldsymbol{s_N} & =

\begin{bmatrix}

2/3 & 11/3 & 4/3

\end{bmatrix}^{\mathrm{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'''''^T'''''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|'''''B'''''}} are present in the revised simplex method:

:<math>

\begin{align}

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

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

\end{align}

</math>

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-TomlinForrest−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]]