Optimum bestimmen (Phase 2)
Voraussetzung: Startlösung finden (Phase 1)
Die erste Phase hat einen zulässigen Punkt geliefert. In der zweiten Phase, der Optimierungsphase, geht es um das eigentliche Ziel: die ursprüngliche Zielfunktion \(Z\) so groß wie möglich zu machen. Dazu läuft der gewöhnliche Simplex von diesem Punkt aus weiter. Voraussetzung ist die erste Phase mit \(-T=0\).
Der Übergang und der Ablauf:
- Streiche die Spalten der künstlichen Variablen und die Hilfszeile, wenn keine künstliche Variable mehr in der Basis steht (sonst siehe unten). Sie haben ihre Aufgabe erfüllt, und die künstlichen Variablen dürfen nicht wieder positiv werden.
- Die Zeile \(Z\) bleibt, sie wurde in der ersten Phase mitgeführt. Wähle die Pivotspalte dort: der negativste Eintrag.
- Rechne Quotienten, pivotiere und wiederhole, bis die Zeile \(Z\) keinen negativen Eintrag mehr hat.
- Lies den Wert von \(Z\) rechts in der Zeile \(Z\) ab.
Pro Pivotschritt wächst die Pivotvariable um den kleinsten Quotienten \(\theta\), und \(Z\) steigt um den Betrag des Eintrags in der Zeile \(Z\) mal \(\theta\). Der Eintrag nennt, um wie viel \(Z\) je Einheit wächst, \(\theta\) nennt, wie viele Einheiten es sind. Weil alle Pivotspalten einen negativen Eintrag in der Zeile \(Z\) haben, steigt \(Z\) in jedem Schritt, oder bleibt gleich, wenn \(\theta=0\) ist.
Die Zeile \(Z\) lautet jetzt \(Z-8x_2-3S_1=24\). Der negativste Eintrag steht unter \(x_2\), die Pivotspalte ist \(x_2\). Die Zeile von \(x_1\) hat dort einen negativen Eintrag und scheidet aus, die Zeile von \(S_2\) hat \(5\) bei der rechten Seite \(2\). Der Quotient ist \(\frac{2}{5}\), und \(Z\) steigt um \(8\cdot\frac{2}{5}\) auf \(27{,}2\). In der neuen Zeile \(Z\) steht noch \(-\frac{7}{5}\) unter \(S_1\). Die Pivotspalte ist \(S_1\), der Quotient der Zeile von \(x_2\) ist \(2\), und \(Z\) steigt um \(\frac{7}{5}\cdot 2=\frac{14}{5}\) auf \(30\). Jetzt hat die Zeile \(Z\) nur noch die Einträge \(7\) und \(3\) unter \(x_2\) und \(S_2\), kein negativer Eintrag bleibt. Das Optimum ist \(Z=30\) im Punkt \((10,0)\).
Wenn das Problem ein Minimum war
Wurde \(Z'=-K\) maximiert, steht rechts in der Zeile \(Z'\) der Wert \(-K\). Das Minimum von \(K\) ist das Negative davon. Im zweiten Beispiel der ersten Schritte, Minimiere \(K=2x_1+x_2\) unter \(x_1+x_2\ge 6\) und \(x_1-2x_2\ge 3\), endet die zweite Phase mit \(Z'=-11\), also ist das Minimum der Kosten \(K=11\).
Eine künstliche Variable steht noch in der Basis
Ist die erste Phase bei \(-T=0\) beendet, kann eine künstliche Variable mit dem Wert \(0\) noch in der Basis stehen. Dann streichst du ihre Spalte nicht einfach. Suche in ihrer Zeile einen Eintrag ungleich \(0\) unter einer echten Variable (Entscheidungs-, Schlupf- oder Überschussvariable) und pivotiere dort. Weil die rechte Seite \(0\) ist, ändert das keinen Wert, und die künstliche Variable verlässt die Basis. Stehen in der Zeile unter allen echten Variablen nur Nullen, ist die Zeile überflüssig, und du streichst sie.
Wenn die zweite Phase entfällt
Hat die Zeile \(Z\) schon am Ende der ersten Phase keinen negativen Eintrag, ist der gefundene Punkt bereits optimal. Dann liest du \(Z\) dort ab, und die zweite Phase ist leer.