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