Rechte Seite
Voraussetzung: Optimum ablesen
Der einfache Simplex startet im Ursprung. Das geht nur, wenn die Nebenbedingungen alle \(\le\) mit nichtnegativer rechter Seite sind. Sonst ist der Ursprung kein zulässiger Punkt, und du suchst erst einen zulässigen Startpunkt. Dafür gibt es die Zweiphasenmethode, und sie beginnt damit, das Problem in die richtige Form zu bringen. Dieser Schritt ist der Anfang. Voraussetzung ist die Normalform aus dem Simplex.
Dieselbe Aufgabe läuft durch alle sechs Schritte dieser Sektion: Maximiere \(Z=3x_1+2x_2\) unter \(-x_1+2x_2\le -8\), \(x_1+3x_2\le 10\) und \(x_1,x_2\ge 0\).
Die Zweiphasenmethode verlangt, dass drei Dinge erfüllt sind. Du prüfst sie in dieser Reihenfolge.
- Es wird maximiert. Ein Minimum wird zum Maximum, indem du die Zielfunktion mit \(-1\) multiplizierst, also \(Z'=-Z\) maximierst.
- Jede rechte Seite ist nichtnegativ. Eine Zeile mit negativer rechter Seite multiplizierst du mit \(-1\).
- Jede Variable erfüllt \(x\ge 0\). Eine Variable ohne Vorzeichenbeschränkung ersetzt du durch zwei nichtnegative, \(x=x'-x''\).
Beim Multiplizieren mit \(-1\) gilt die Regel für Ungleichungen: Mit einer negativen Zahl multipliziert dreht sich das Zeichen. Aus \(\le\) wird \(\ge\), aus \(\ge\) wird \(\le\). Alle Zahlen der Zeile wechseln das Vorzeichen, auch die auf der linken Seite. Das Maximum von \(Z'=-Z\) ist das Negative des Minimums von \(Z\): Liefert der Simplex für \(Z'\) den Wert \(-12\), ist das Minimum von \(Z\) gleich \(12\).
Aus \(-x_1+2x_2\le -8\) wird durch Multiplizieren mit \(-1\) die Zeile \(x_1-2x_2\ge 8\). Die zweite Zeile \(x_1+3x_2\le 10\) hat eine nichtnegative rechte Seite und bleibt. Danach lautet das Problem: Maximiere \(Z=3x_1+2x_2\) unter \(x_1-2x_2\ge 8\) und \(x_1+3x_2\le 10\). Die Zeile mit \(\ge\) heißt später, dass der Ursprung nicht zulässig ist, denn dort wäre \(0\ge 8\) falsch.
Eine Variable ohne Vorzeichenbeschränkung
Ist \(x_j\) beliebig, setzt du \(x_j=x_j'-x_j''\) mit \(x_j'\ge 0\) und \(x_j''\ge 0\). Jede Zahl lässt sich so schreiben: eine positive als \(x'\) mit \(x''=0\), eine negative als \(x''\) mit \(x'=0\). Ist die Variable von vornherein nichtpositiv, \(x_j\le 0\), genügt \(x_j=-x_j^*\) mit \(x_j^*\ge 0\). In der Aufgabe oben kommt das nicht vor, weil alle Variablen die Nichtnegativität erfüllen.
Ein zweites Beispiel, ein Minimum
Minimiere \(K=2x_1+x_2\) unter \(x_1+x_2\ge 6\) und \(-x_1+2x_2\le -3\). Du maximierst \(Z'=-K=-2x_1-x_2\). Die erste Zeile hat die rechte Seite \(6\), sie bleibt. Die zweite hat \(-3\), also wird sie mit \(-1\) multipliziert: \(x_1-2x_2\ge 3\). Der Simplex liefert für \(Z'\) den Wert \(-11\), im Punkt \((5,1)\). Das Minimum der Kosten ist deshalb \(K=11\), und zur Probe ist \(2\cdot 5+1=11\).