previous up next contents index
previous: Das Standard-Minimierungsproblem up: Lineare Optimierung next: Spezialfälle

2-Phasen-Simplex-Algorithmus  



\begin{displaymath}
\begin{array}
{rcl}
 z(x_1,x_2)=11\,x_1+8\,x_2 &\longrightar...
 ... + 4\,x_2 &\leq& 60\\ [0.5ex]
 x_1,\,x_2 &\geq& 0\\ \end{array}\end{displaymath}

Aus dem Anfangs-Simplex-Tableau

\begin{displaymath}
\begin{array}
{c\vert cccccc\vert c}
 z & x_1 & x_2 & s_1 & ...
 ... 60 \\  \hline
 1 & -11 & -8 & 0 & 0 & 0 & 0 & 0 \\ \end{array}\end{displaymath}

erhalten wir die nicht zulässige Basislösung $(0,0;-12,-12,-10,60)$.


\begin{figure}
\setlength {\unitlength}{0.7mm}
 
\begin{picture}
(225,170)
 
\th...
 ...8,\footnotesize 10,\footnotesize 12,\footnotesize $14$}\end{picture}\end{figure}



$\Rightarrow\quad$ 2-Phasen-Simplex-Algorithmus

1. Phase:
Suchen zulässige Basislösung mit Hilfe des Simplex-Algorithmus und einer Hilfszielfunktion.
2. Phase:
Berechnen des Optimums mit Hilfe des
Standard-Verfahrens.



1. Phase:
Die Suche nach einem Startpunkt

(1)
Aufstellen des Anfangs-Simplex-Tableaus.
In jeder Zeile, in der wir eine Schlupfvariable subtrahieren, addieren wir zusätzlich eine Hilfsvariable $a_i$.


(2)
Ersetzen die Zielfunktion durch die Summe aller Hilfsvariablen $z^\ast = a_1 + a_2 + \cdots$ .


(3)
Durch Addition aller Zeilen, die eine Hilfsvariable enthalten, zur Zielfunktionszeile bringen wir alle Einträge der Hilfsvariablen $a_i$ in der Zielfunktionszeile auf Null.


(4)
Minimieren diese Hilfszielfunktion $z^\ast$ mit dem Standardverfahren.

(5)
Im Minimum von $z^\ast$ gibt es drei Möglichkeiten:
(a)
$z^\ast_{\min} = 0$ und keine Hilfsvariable ist Basisvariable
$\Rightarrow$
gehe zu Punkt (6).
(b)
$z^\ast_{\min} = 0$ und eine Hilfsvariable ist Basisvariable
$\Rightarrow$
Durch geeignete Pivotschritte, die $z^\ast$ unverändert lassen, können alle Hilfsvariablen zu Nichtbasisvariablen gemacht werden.
Anschließend gehe zu Punkt (6).
(c)
$z^\ast_{\min} \gt 0$ $\quad\Rightarrow\quad$ zulässiger Bereich \fbox {\textbf{leer}}


(6)
Streiche die Spalten der Hilfsvariablen aus dem Tableau und setze wieder die ursprüngliche Zielfunktion $z$ ein.


(7)
Durch Addition eines Vielfachen von geeigneten Zeilen zur Zielfunktionszeile bringen wir alle Einträge der Basisvariablen in der Zielfunktionszeile auf Null.




2. Phase:
Lösen des Optimierungsproblems

(8)
Löse das lineare Optimierungsproblem mit dem Standardverfahren.



BEISPIEL FORTSETZUNG
1. Phase:

\begin{displaymath}
\begin{array}
{c\vert ccccccccc\vert c}
 z^\ast & x_1 & x_2 ...
 ...
 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & -1 & 0 \\  \end{array} \end{displaymath}

Wenn wir $s_4$, $a_1$, $a_2$ und $a_3$ als Basisvariable wählen, erhalten wir die zulässige Basislösung

$(x_1,x_2;s_1,s_2,s_3,s_3,s_4;a_1,a_2,a_3)$ $=(0,0;0,0,0,60;12,12,10)$

\begin{displaymath}
ZFZ\leftarrow ZFZ + Z1 + Z2 + Z3 \end{displaymath}

\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
\setlength {\arraycolsep}{0.5em...
 ... & 4 & 4 & -1 & -1 & -1 & 0 & 0 & 0 & 0 & 34 & \\  \end{array} \end{displaymath}

Minimieren der Hilfszielfunktion:

\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
\setlength {\arraycolsep}{0.3em...
 ... & 0 & 2 & 1 & -1& -1& 0 & -2 & 0 & 0 & 10 & \\  
 \end{array} \end{displaymath}

\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
 
\setlength {\arraycolsep}{0.3...
 ...}& -1& 0 &-\frac{4}{3}&-\frac{4}{3}& 0 & 2 & \\  
 \end{array} \end{displaymath}

\begin{displaymath}
\setlength {\arraycolsep}{0.3em}
 \begin{array}
{c\vert cccc...
 ...
 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & -1 & 0 \\  \end{array} \end{displaymath}

Wir haben $z^\ast_{\min} = 0$ erreicht, und die drei Hilfsvariablen $a_1$, $a_2$ und $a_3$ sind keine Basisvariablen mehr.

Die (zulässige) Basislösung lautet

$(x_1,x_2;s_1,s_2,s_3,s_3,s_4;a_1,a_2,a_3)
 =(8,2;6,0,0,28;0,0,0)$.




2. Phase:

Wir setzen jetzt wieder die ursprüngliche Zielfunktion in unser Tableau ein:

\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
 \begin{array}
{c\vert cccccc\v...
 ...8 \\  \hline
 1 & -11 & -8 & 0 & 0 & 0 & 0 & 0 \\  \end{array} \end{displaymath}

Wir müssen die ZFZ umformen, da $z$ durch die zwei Basisvariablen $x_1$ und $x_2$ ausgedrückt wird.

\begin{displaymath}
\textstyle ZFZ \leftarrow ZFZ + 11\times Z1 + 8\times Z2 \end{displaymath}

\begin{displaymath}
\setlength {\fboxsep}{2mm}
 
 \begin{array}
{c\vert cccccc\v...
 ...28\\  \hline
 1 & 0 & 0 & 0 & 3 & -14 & 0 &104 \\  \end{array} \end{displaymath}

Können nun das Minimierungsproblem mit dem Standardverfahren lösen:

\begin{displaymath}
\begin{array}
{c\vert cccccc\vert c}
 z & x_1 & x_2 & s_1 & ...
 ...2 \\  \hline
 1 & 0 & 0 & -3 & 0 & -5 & 0 & 86 \\  \end{array} \end{displaymath}

Die optimale zulässige Basislösung ist

$(x_1,x_2;s_1,s_2,s_3,s_4)=(2,8;0,6,0,22)$,

d.h. das Minimum liegt im Punkt $(2,8)$. Der minimale Zielfunktionswert ist $z_{\min}=86$.


previous up next contents index

© 1997, Josef Leydold
Abteilung für angewandte Statistik und Datenverarbeitung