Mehrere Optima
Voraussetzung: Optimum ablesen
Ein Problem kann mehr als eine optimale Lösung haben. Der Simplex endet dann bei einer optimalen Ecke und zeigt im Tableau, dass es weitere gibt. Das ist der zweite Sonderfall des Skripts, die mehrdeutige Lösung. Du erkennst den Hinweis an einem einzigen Zeichen und prüfst dann, ob der nächste Pivotschritt eine weitere Ecke liefert. Voraussetzung ist das Ablesen am optimalen Tableau.
Das Zeichen: Das Tableau ist optimal, die Zeile \(Z\) hat also keinen negativen Eintrag. Steht in der Zeile \(Z\) aber unter einer Nichtbasisvariable eine \(0\), gibt es eine weitere optimale Basislösung mit demselben Wert von \(Z\). Das Skript sagt es so: Wenn der Simplex Optimalität anzeigt und in der Zielzeile mehr als nur die Basisvariablen \(0\) sind, ist die Lösung mehrdeutig.
- Unter den Basisvariablen steht in der Zeile \(Z\) immer eine \(0\). Das zählt nicht.
- Unter einer Nichtbasisvariable zeigt eine \(0\) an, dass sie in die Basis dürfte, ohne dass sich \(Z\) ändert.
- Ein weiterer Pivotschritt in dieser Spalte liefert eine optimale Basislösung mit demselben Wert von \(Z\). Ist der kleinste Quotient größer als \(0\), ist das eine zweite optimale Ecke.
Warum \(Z\) gleich bleibt: Im Pivotschritt steigt \(Z\) um den Betrag des Eintrags in der Zeile \(Z\) mal den Quotienten. Ist der Eintrag \(0\), ist der Zuwachs \(0\), egal wie groß der Quotient ist. Der Zielwert bleibt, aber die Ecke wechselt.
Das Starttableau hat die Zeile \(x_1+3x_2+S_1=9\) und \(Z-2x_1-6x_2=0\). Die Pivotspalte ist \(x_2\), der Quotient \(9/3=3\), die Pivotzeile die von \(S_1\). Nach dem Schritt ist \(x_2=3\) und die Zeile \(Z\) lautet \(Z+0\cdot x_1+2S_1=18\). Kein Eintrag ist negativ, das Optimum \(Z=18\) im Punkt \((0,3)\) ist erreicht. Aber unter der Nichtbasisvariable \(x_1\) steht eine \(0\). Pivotiert man in der Spalte \(x_1\), bekommt man den Punkt \((9,0)\), und auch dort ist \(Z=2\cdot 9=18\). Es gibt mehrere optimale Lösungen.
Das Bild dazu
Zeichnest du das Problem, ist die Höhenlinie von \(Z\) parallel zu einer Kante des Bereichs. Hier haben \(Z=2x_1+6x_2\) und die Grenze \(x_1+3x_2\le 9\) dieselben Koeffizienten bis auf den Faktor \(2\). Beim Verschieben der Höhenlinie berührt sie zuletzt nicht eine Ecke, sondern die ganze Kante zwischen \((9,0)\) und \((0,3)\). Jeder Punkt dieser Kante hat \(Z=18\).
Wann die Null keine zweite Ecke liefert
Die Null ist ein Hinweis, kein Beweis für eine zweite Ecke. Es gibt zwei Ausnahmen. Ist die rechte Seite der Pivotzeile \(0\), also eine Basisvariable schon \(0\), ist der Quotient \(0\). Die Basis wechselt, aber der Punkt in der Ebene bleibt derselbe (Degeneration, siehe die letzte Karte dieser Reihe). Hat die Spalte unter der Nichtbasisvariable keinen positiven Eintrag, gibt es keinen Quotienten und keine Pivotzeile. Dann bleibt \(Z\) gleich, während die Variable beliebig wächst, und die optimalen Punkte bilden einen Strahl ohne Ende statt einer Kante.
Ein zweites Beispiel, ein Punkt abseits
Der Punkt \((3,0)\) liegt nicht auf der Kante, denn \(3+3\cdot 0=3\) ist kleiner als \(9\). Dort ist \(Z=6\), und das ist nicht optimal. Mehrdeutig heißt nicht, dass jeder Punkt gut ist, sondern dass die ganze Kante gleich gut ist.