Startlösung finden (Phase 1)
Voraussetzung: Hilfszielfunktion
Jetzt läuft die erste Phase, die Eröffnungsphase. Sie hat ein einziges Ziel: einen zulässigen Punkt der ursprünglichen Aufgabe finden, von dem die zweite Phase starten kann. Dazu läuft der gewöhnliche Simplex mit der Hilfszielfunktion \(-T\), bis alle künstlichen Variablen \(0\) sind oder der Simplex nicht weiterkommt. Voraussetzung ist die Hilfszielfunktion.
Du rechnest so:
- Stelle das Tableau auf: die Zeilen der Nebenbedingungen mit Schlupf-, Überschuss- und künstlichen Variablen, die Hilfszeile \(-T\) und die Zeile \(Z\) der ursprünglichen Zielfunktion. Die Zeile \(Z\) wird in der ersten Phase nur mitgeführt.
- Wähle die Pivotspalte in der Hilfszeile: der kleinste, also negativste Eintrag.
- Bilde die Quotienten, wähle die Pivotzeile und pivotiere. Dabei werden alle Zeilen umgerechnet, auch \(Z\).
- Wiederhole, bis die Hilfszeile keinen negativen Eintrag mehr hat.
Danach liest du das Ergebnis am Wert von \(-T\). Ist \(-T=0\), sind alle künstlichen Variablen \(0\), weil eine Summe nichtnegativer Zahlen nur dann \(0\) ist, wenn jede \(0\) ist. Der Punkt erfüllt alle ursprünglichen Nebenbedingungen und ist der Startpunkt für die zweite Phase. Bleibt \(-T<0\), obwohl die Hilfszeile keine negativen Einträge hat, gibt es keinen zulässigen Punkt, und das Problem hat keine Lösung. Die zweite Phase startet dann nicht.
Die Hilfszeile \(-T=-A=-8+x_1-2x_2-S_1\) hat unter \(x_1\) den Eintrag \(-1\), unter \(x_2\) den Eintrag \(2\), unter \(S_1\) den Eintrag \(1\) und rechts den Wert \(-8\). Der einzige negative Eintrag steht unter \(x_1\), die Pivotspalte ist \(x_1\). Die Quotienten sind \(8/1=8\) in der Zeile von \(A\) und \(10/1=10\) in der Zeile von \(S_2\). Die kleinere \(8\) bestimmt die Pivotzeile von \(A\). Nach dem Pivotschritt ist \(x_1=8\), \(A\) hat die Basis verlassen, und \(S_2=2\). Die Hilfszeile hat nur noch die \(1\) unter \(A\), der Wert ist \(-T=0\). Die erste Phase ist zu Ende, der Punkt \((8,0)\) ist zulässig, die Zeile \(Z\) zeigt dort \(Z=24\).
Wenn es keinen zulässigen Punkt gibt
Beispiel: \(x_1+x_2\le 2\) und \(x_1+x_2\ge 5\). Beide Zeilen können nie gleichzeitig gelten. Die erste Phase endet mit einem Wert \(-T=-3\) und ohne negativen Eintrag in der Hilfszeile. Die künstliche Variable bleibt größer als \(0\), nämlich um die Lücke von \(3\) zwischen den beiden Grenzen. Das Problem hat keinen zulässigen Punkt.
Wenn die erste Phase schon das Optimum liefert
Manchmal ist am Ende der ersten Phase die Zeile \(Z\) schon ohne negativen Eintrag. Dann ist der gefundene zulässige Punkt zugleich das Optimum, und die zweite Phase entfällt.