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

Simplex Tableau

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
For a linear program

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

a pivot step

$\displaystyle I \rightarrow J = \left\{I \backslash j \right\} \cup k $

can be carried out with the aid of the tableau

$\displaystyle T_I = \left( A_I^{-1} , \, x_I \right). $

To obtain the tableau $ T_J= \left( A_J^{-1} , \, y_J \right)$, the matrix $ T_I$ is modified as follows:
(i)
We compute $ z_I = A_I^{-1} A_k$.

(ii)
The row with index $ j$ of $ T_I$ is divided by $ z_j$.

(iii)
For all $ i \in I \backslash j$, the row with index $ j$ is multiplied by $ z_i$ and subtracted from the row with index $ i$.

We note that matrices and vectors are indexed according to the index sets $ I$ and $ J$, i.e., if $ i$ is the $ \ell$-th index in $ I$, then the $ \ell$-th row of $ T_I$ is referred to as row with index $ i$, etc.

(Authors: Höllig/Pfeil/Walter)

Example:

[Annotations] [Links]
  automatically generated 4/24/2007