L4 Sonderfälle
Beim Lösen von Linearen Optimierungsproblemen können einige Sonderfälle auftreten, es ist möglich, dass der Zielwert unendlich ist, es eine Lösung, unendlich viele Lösungen oder gar keine Lösung gibt.
Unbeschränkte Lösung
Betrachten wir folgende Aufgabenstellung:
max z= | 10·x1 | +5·x2 | |
u.d.N. | 6·x1 | -12·x2 | ≤ 60 |
-2·x1 | +2·x2 | ≤ 50 | |
-3·x1 | + x2 | ≤ 15 | |
x1,x2≥0
Übertragen in das Tableau 1
Bei der 1. Iteration ist noch keine Auffälligkeit zu erkennen. Es wird ganz normal die Spalte mit dem kleinsten Koeffizienten in der Zielzeile gewählt. Gemäß der Regel
kommt nur die Zeile der 1. Nebenbedingungen in Frage, da als Pivotelement nur Koeffizienten größer als null gewählt werden dürfen.
Bereits an dieser Stelle sei auf das Phänomen hingewiesen, dass die rechte Seite von Zeilen mit negativem Koeffizienten in der Pivotspalte größer wird.
Tableau 2
⇒Keine Pivotzeile auswählbar, unbeschränkte Lösung
Nach der 1. Iteration ist noch nicht die optimale Lösung gefunden, die x2–Spalte wird als Pivotspalte gewählt. Der Versuch dort ein Pivotelement zu finden scheitert allerdings, da in der gesamten Spalte alle Koeffizienten negativ sind. Die Rechnung bricht an dieser Stelle ab. Das Optimierungsproblem kennt keine Schranken und das Optimum liegt im Unendlichen.
Betrachtung im Detail - Positiver Koeffizient
Um den Unterschied zwischen positiven und negativen Koeffizienten zu erkennen nochmal zurück zum Starttableau. Die Pivotzeile ausgeschrieben bedeutet:
6·x1-12·x2 + x3 =60
Aufgelöst nach x3:
x3 =60 - 6·x1-12·x2
Wird x1 erhöht, wird x3 kleiner. Wegen der Nichtnegativitätsbedingung darf x1 höchstens den Wert x1=10 annehmen, dann ist x3=0.
Eine größere Erhöhung ist nicht möglich. Über die Regel zur Auswahl von Zeilen wird immer die Zeile gesucht, in der zuerst eine andere Variable negativ zu werden droht.
Negativer Koeffizient
Zum Vergleich nun die Betrachtung für eine Zeile mit negativem Koeffizienten. Als Beispiel dient hier die erste Zeile des 2. Tableaus:
1·x1-2·x2 + x3 =60
Aufgelöst nach x1
x1 =10 +12·x2 - x3
Erhöht man x2 wird auch x1 größer.
Da in allen Zeilen negative Koeffizienten in der Pivotspalte sind, ist entsprechendes dort der Fall. Das heißt es gibt keine Nebenbedingung, die x2 einschränkt.
In der zeichnerischen Darstellung ist zu erkennen, dass der Lösungsbereich in Richtung steigender Zielwerte offen ist. So schade man es finden mag, in der Praxis, z.B. bei Gewinnmaximierungsproblemen, können unbeschränkte Lösungen eigentlich nur durch Modellierungsfehler zustande kommen. In diesem Fall empfiehlt es sich besonders zu prüfen, ob nicht wichtige Nebenbedingungen vergessen wurden.