Bei diesem Problem können wir nicht wie gewohnt den Simplex-Algorithmus mit dem Ursprung als zulässige Basislösung starten. Wir wenden deshalb die 2-Phasen-Methode an um zunächst eine zulässige Basislösung zu finden, mit der dann der eigentliche Simplex-Algorithmus gestartet wird.
Wir fuhren dafür die künstliche Variablen z ein und erhalten das Ausgangstableau mit den Basisvariablen s1, z.
| BV | x1 | x2 | s1 | s2 | z | RS |
| s1 | 2 | 3 | 1 | 0 | 0 | 24 |
| z | -1 | 1 | 0 | -1 | 1 | 3 |
|
|
|
|
|
|
|
| -ZF | 0 | 0 | 0 | 0 | 1 | 0 |
Wir maximieren nun die Hilfszielfunktion ZF = -z.
Da diese aber noch von den Basisvariable z abhängt, eliminieren wir die Einträge in der Zielfunktionszeile durch geeignete Zeilenoperationen und erhalten:
z-Zeile - (-ZF)-Zeile :
| BV | x1 | x2 | s1 | s2 | z | RS |
| s1 | 2 | 3 | 1 | 0 | 0 | 24 |
| z | -1 | 1 | 0 | -1 | 1 | 3 |
| -ZF | -1 | 1 | 0 | -1 | 0 | 3 |
Wir maximieren jetzt die Hilfszielfunktion ZF mit dem üblichen Simplex-Algorithmus.
Nachdem wir zulässige Basislösung gefunden haben, sind wir in der Lage den Simplex-Algorithmus fur die ursprüngliche Zielfunktion 2x1+x2 ausgehend von dieser Basislösung durchzuführen. Wir streichen die künstlichen Variablen.
Falls die Zielfunktion noch von den Basisvariablen x1 und x2 abhängt, führen wir wieder geeignete Zeilenumformung durch. Dann führen wir erneut den Simplex-Algorithmus durch. Im letzten Tableau lesen wir dann die optimale Basislösung.
