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

Pivot Step for a Linear Program

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
A pivot step for a linear program

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

modifies the index set of an admissible basic solution $ x$,

$\displaystyle I \rightarrow J = ( I \backslash j ) \cup k \,, $

so that $ J$ corresponds to a new basic solution $ y$ with non-increasing value of the cost function:

$\displaystyle c^{\operatorname t} x \geq c^{\operatorname t} y \,. $

The indices $ j$ and $ k$ are determined as follows.

The index $ k$ is an index from the complement $ K$ of $ I$, for which

$\displaystyle d_k=c_k -c_I^{\operatorname t} A_I^{-1} A_k $

is minimal. If $ d_k \geq 0$, then $ x$ is a solution of the linear program.

The index $ j \in I$ is selected so that, with $ z_I=A_I^{-1} A_k$,

$\displaystyle t=\frac{x_j}{z_j} = \min \left\{ \frac{x_i}{z_i}: z_i>0\,,\quad i \in I\right\} $

is minimal.

With these definitions,

$\displaystyle y_I=x_I-t z_I \,, \quad y_k=t\,, $

and

$\displaystyle c^{\operatorname t} y = c^{\operatorname t} x + d_k t. $

(Authors: Höllig/Pfeil/Walter)

Example:

[Annotations] [Links]
  automatically generated 7/ 2/2007