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

2-Phasen-Simplex-Algorithmus  

$$\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}$$

Aus dem Anfangs-Simplex-Tableau

$$\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}$$

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

$\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

(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{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}$$

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)$

$$ZFZ\leftarrow ZFZ + Z1 + Z2 + Z3$$

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

Minimieren der Hilfszielfunktion:

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

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

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

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:

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

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

$$\textstyle ZFZ \leftarrow ZFZ + 11\times Z1 + 8\times Z2$$

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

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

$$\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}$$

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$.