Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge

Mathematik-Online-Lexikon:

Pivot-Schritt für ein lineares Programm


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 Übersicht

Ein Pivot-Schritt für ein lineares Programm

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

modifiziert die Indexmenge einer zulässigen Basislösung $ x$,

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

so dass $ J$ einer neuen zulässigen Basislösung $ y$ mit nicht ansteigendem Wert der Zielfunktion entspricht:

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

Die Indizes $ j$ and $ k$ werden folgendermaßen bestimmt.

Der Index $ k$ ist ein Index des Kompliments $ K$ von $ I$, für den

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

minimal ist. Falls $ d_k \geq 0\ \forall k \in K$, dann ist $ x$ eine Lösung des linearen Programms.

Zur Wahl des Index $ j \in I$ wird zunächst der Vektor

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

gebildet. Hat $ z_I$ keine positiven Komponenten, so ist die Zielfunktion nach unten unbeschränkt, das lineare Programm also nicht lösbar. Andernfalls ist $ j \in I$ ein Index, für den der Quotient

$\displaystyle x_i/z_i,\quad z_i>0,\,i\in I
\,,
$

minimal ist, und man setzt $ y_k=x_j/z_j$.

Mit diesen Definitionen ist

$\displaystyle y_I=x_I- z_I y_k,\quad
y_j = 0
\,,
$

und

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

Bei Uneindeutigkeit wird sowohl für $ k$ als auch für $ j$ jeweils der kleinstmögliche Index gewählt.

Beispiel:


[Erläuterungen] [Verweise]

  automatisch erstellt am 19.  8. 2013