Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online lexicon:

Simplex Algorithm

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview
The simplex algorithm for solving a linear program

$\displaystyle c^{\operatorname t}x \longrightarrow \min \,, \quad Ax = b \,, \quad x \geq 0 \,, $

updates an admissible basic solution $ x_I$ with successive pivot operations until an optimal vector $ x$ is reached. One step

$\displaystyle x_I \rightarrow x_J \,, \quad J= \left\{I \backslash j\right\} \cup k \,, $

which utilizes the simplex tableau $ T_I= \left( A_I^{-1},\, x_I \right)$, has the following form:

(i) First, with $ K$, the complementary set to $ I$, one computes

$\displaystyle d_K^{\operatorname t}= c_K^{\operatorname t} - c_I^{\operatorname t}A_I^{-1} A_K $

and defines $ k$ as the smallest index, where $ d_K$ attains its minimum. If $ d_k \geq 0$, the current basic solution $ x_I$ is optimal and the algorithm terminates.

(ii) If the auxiliary vector

$\displaystyle z_I = A_I^{-1} A_k $

is $ \leq 0$, the infimum of the cost function is $ -\infty$ and the linear program has no solution. Otherwise, $ j$ is the smallest index, for which the quotients

$\displaystyle \frac{x_i}{z_i} \,, \quad z_i> 0 \,, \quad i \in I \,, $

are minimal.

(iii) The tableau $ T_I$ is updated,

$\displaystyle T_I= \left( A_I^{-1},\, x_I \right) \rightarrow T_J= \left( A_J^{-1},\, y_J \right), $

by

$ \bullet$
dividing the row with index $ j$ by $ z_j$ ,
$ \bullet$
subtracting, for each $ i \in I \backslash j$, from the row with index $ i$ the modified row with index $ j$ multiplied by $ z_i$.

(Authors: Höllig/Pfeil/Walter)

see also:

[Downloads] [Examples]
  automatically generated 4/24/2007