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