Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon:

Simplex-Algorithmus

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
Der Simplex-Algorithmus zur Lösung eines linearen Programms

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

modifiziert eine zulässige Basislösung $ x_I$ mit sukzessiven Pivot-Operationen, bis ein optimaler Vektor $ x$ erreicht ist. Ein Schritt

$\displaystyle x_I \rightarrow x_J \,, \quad J= \left\{I \backslash j\right\} \cup k \,, $

der das Simplex-Tableau $ T_I= \left( A_I^{-1},\, x_I \right)$ verwendet, hat die folgende Form:

(i) Zuerst berechnet man mit $ K$, der Komplementärmenge von $ I$,

$\displaystyle d_K^{\operatorname t}= c_K^{\operatorname t} - c_I^{\operatorname t}A_I^{-1} A_K $

und definiert $ k$ als den kleinsten Index, an dem $ d_K$ sein Minimum annimmt. Falls $ d_k \geq 0$, ist die aktuelle Basislösung $ x_I$ optimal und der Algorithmus bricht ab.

(ii) Ist der Hilfsvektor

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

$ \leq 0$, so ist das Infimum der Zielfunktion $ -\infty$, und das lineare Programm hat keine Lösung. Andernfalls wählt man $ j$ als den kleinsten Index, für den der Quotient

$\displaystyle \frac{x_i}{z_i} \,, \quad z_i> 0 \,, \quad i \in I \,, $

minimal ist.

(iii) Das Tableau $ T_I$ wird aktualisiert,

$\displaystyle T_I= \left( A_I^{-1},\, x_I \right) \rightarrow T_J= \left( A_J^{-1},\, y_J \right), $

indem man

$ \bullet$
die Zeile mit Index $ j$ durch $ z_j$ dividiert,
und
$ \bullet$
für jedes $ i \in I \backslash j$ von der Zeile mit Index $ i$ die modifizierte Zeile mit Index $ j$, multipliziert mit $ z_i$, subtrahiert.

Beispiel:

[Downloads] [Verweise]
  automatisch erstellt am 19.  8. 2013