Revised simplex method: Difference between revisions

Revision as of 06:55, 11 March 2014

Revision as of 07:26, 11 March 2014

Line 34:

\boldsymbol{x} =

\begin{bmatrix}

\boldsymbol{xx_B}_{ \\
\boldsymbol{Bx_N}} \\

\boldsymbol{x}_{\boldsymbol{N}}

\end{bmatrix} =

\begin{bmatrix}

Line 43:

</math>

where <math>\boldsymbol{x}_{\boldsymbol{B}x_B} \ge \boldsymbol{0}</math>. Partition <math>\boldsymbol{c}</math> and <math>\boldsymbol{s}</math> accordingly into

:<math>

Line 49:

\boldsymbol{c} & =

\begin{bmatrix}

\boldsymbol{cc_B}_{ \\
\boldsymbol{Bc_N}} \\

\boldsymbol{c}_{\boldsymbol{N}}

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

\boldsymbol{s} & =

\begin{bmatrix}

\boldsymbol{ss_B}_{ \\
\boldsymbol{Bs_N}} \\

\boldsymbol{s}_{\boldsymbol{N}}

\end{bmatrix}\text{.}

\end{align}

</math>

To satisfy the complementary slackness condition, let <math>\boldsymbol{s}_{\boldsymbol{B}s_B} = \boldsymbol{0}</math>. It follows that

:<math>

\begin{align}

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

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

\end{align}

</math>

Line 73:

:<math>

\begin{align}

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

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

\end{align}

</math>

If <math>\boldsymbol{s}_{\boldsymbol{N}s_N} \ge \boldsymbol{0}</math> at this point, the KKT conditions are satisfied, and thus <math>\boldsymbol{x}</math> is optimal.

=== Pivot operation ===