Revised simplex method: Difference between revisions

Revision as of 08:49, 11 March 2014

Revision as of 09:14, 11 March 2014

Line 94:

== Practical issues ==

=== Degeneracy ===

Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not results in a decrease in <math>\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x}</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.{{sfn|Nocedal|Wright|2006|p=372381|loc=§13.45}}

=== Basis representation ===

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

:<math>

\begin{align}

\boldsymbol{B x_B} & = \boldsymbol{b}\text{,} \\

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

\end{align}

</math>

Instead of refactorizing <math>\boldsymbol{B}</math> after each pivot operation, usually an [[LU factorization]] is maintained, for which purpose there exist several strategies.{{sfn|Morgan|1997|loc=§2}}{{sfn|Nocedal|Wright|2006|p=372|loc=§13.4}}

== Notes and references ==