Unbeschränkt
Voraussetzung: Pivot und Theta
Nicht jedes Optimierungsproblem hat ein Maximum. Das Skript nennt vier Sonderfälle, in denen der Simplex etwas anderes liefert als eine eindeutige optimale Lösung. Der erste ist das unbeschränkte Problem: Die Zielfunktion lässt sich weiter verbessern, aber nichts hält sie auf. Der Simplex erkennt das im Tableau, und du musst es erkennen und benennen können. Voraussetzung ist der Pivotschritt.
Der Simplex zeigt Unbeschränktheit so an:
- Die Zeile \(Z\) hat noch einen negativen Eintrag, \(Z\) lässt sich also vergrößern. Diese Spalte wäre die Pivotspalte.
- Die Pivotspalte hat in keiner Nebenbedingung einen positiven Eintrag.
- Dann gibt es keinen Quotienten und keine Pivotzeile. Das Problem hat keine endliche optimale Lösung, es ist unbeschränkt.
Der Grund: Ein Quotient Rechte Seite durch Eintrag nennt, wie weit die Variable wachsen darf, bis die Zeile ihre Grenze erreicht. Das gibt es nur, wenn der Eintrag positiv ist, denn nur dann verbraucht die wachsende Variable die rechte Seite. Bei einem negativen Eintrag oder bei \(0\) wird die Zeile nie knapp, die Variable darf beliebig wachsen. Weil dabei \(Z\) steigt, gibt es keinen größten Wert.
Das Starttableau hat die Zeile \(x_1-x_2+S_1=2\) und die Zeile \(Z-2x_1-x_2=0\). Die Pivotspalte ist \(x_1\) mit dem Quotienten \(2/1=2\). Nach dem Schritt ist \(x_1=2+x_2-S_1\), und die Zeile \(Z\) lautet \(Z-3x_2+2S_1=4\). Unter \(x_2\) steht \(-3\), \(Z\) lässt sich also weiter vergrößern. Die Spalte \(x_2\) hat in der Nebenbedingung den Eintrag \(-1\), also keinen positiven. Es gibt keinen Quotienten: Das Problem ist unbeschränkt. Mit \(x_2=t\) ist \(x_1=2+t\) und \(Z=4+3t\), und \(t\) darf jede nichtnegative Zahl sein.
Unbeschränkt ist nicht leer
Bei einem unbeschränkten Problem gibt es zulässige Punkte, in jedem Tableau steht eine zulässige Basislösung. Es gibt nur kein Maximum. Ein leerer Bereich ist etwas anderes: Dort endet schon die erste Phase der Zweiphasenmethode ohne zulässigen Punkt.
Ein zweites Beispiel, wie weit wachsen
Im Beispiel ist \(Z=4+3t\). Soll \(Z\) mindestens \(100\) werden, braucht es \(3t\ge 96\), also \(t\ge 32\). Für jeden gewünschten Wert findest du ein \(t\), nur ist keines das größte.