Schlupf und Überschuss
Voraussetzung: Rechte Seite
Der Simplex rechnet mit Gleichungen, nicht mit Ungleichungen. Darum bekommt jede Nebenbedingung eine Variable, die den Unterschied zwischen linker und rechter Seite ausgleicht. Wie diese Variable in die Gleichung eingeht, hängt vom Zeichen ab. Das ist Schritt 4 und 5 der Zweiphasenmethode. Voraussetzung ist die Form aus dem vorigen Schritt: maximieren und jede rechte Seite nichtnegativ.
Du arbeitest mit der Aufgabe aus dem vorigen Schritt weiter: Maximiere \(Z=3x_1+2x_2\) unter \(x_1-2x_2\ge 8\) und \(x_1+3x_2\le 10\) mit \(x_1,x_2\ge 0\).
- Bei \(\le\) liegt die linke Seite unter der rechten. Die Variable füllt auf: \(\ldots+S=\) rechte Seite. Sie heißt Schlupfvariable.
- Bei \(\ge\) liegt die linke Seite über der rechten. Die Variable zieht ab: \(\ldots-S=\) rechte Seite. Sie heißt Überschussvariable.
- Alle diese Variablen sind nichtnegativ, \(S\ge 0\). Das Skript nennt sie alle Schlupfvariablen.
Die Variable misst den Abstand zur Grenze. Bei \(\le\) ist es die ungenutzte Kapazität der Zeile: rechte Seite minus linke Seite. Bei \(\ge\) ist es der Überschuss über die verlangte Menge: linke Seite minus rechte Seite. Ist die Variable \(0\), ist die Zeile genau ausgeschöpft, der Punkt liegt auf der Grenze. Wäre sie negativ, würde der Punkt die Nebenbedingung verletzen.
Die zweite Zeile wird \(x_1+3x_2+S_2=10\), die erste wird \(x_1-2x_2-S_1=8\). Die Namen \(S_1\) und \(S_2\) folgen der Reihenfolge der Zeilen. Im Punkt \((8,0)\) ist die erste Zeile \(8-S_1=8\), also \(S_1=0\): Der Punkt liegt auf der Grenze. Die zweite Zeile ist \(8+S_2=10\), also \(S_2=2\): Von \(10\) sind \(2\) ungenutzt. Am Ursprung dagegen wäre \(0-S_1=8\), und das gäbe \(S_1=-8\). Das ist nicht erlaubt. Der Ursprung ist kein zulässiger Punkt, und darum braucht diese Aufgabe die Zweiphasenmethode.
Warum die Variable nicht negativ sein darf
Eine nichtnegative Variable \(S\) ist die Bedingung dafür, dass die Gleichung dieselben Punkte beschreibt wie die Ungleichung. Gilt \(x_1+3x_2\le 10\), dann ist \(10-x_1-3x_2\ge 0\), und genau das ist \(S_2\). Gäbe es einen Punkt mit \(S_2<0\), wäre die Ungleichung dort verletzt.
Ein zweites Beispiel, zwei Zeilen
Gegeben sind \(2x_1+x_2\le 12\) und \(x_1+x_2\ge 4\). Die Gleichungen lauten \(2x_1+x_2+S_1=12\) und \(x_1+x_2-S_2=4\). Im Punkt \((3,2)\) ist \(S_1=12-(6+2)=4\) und \(S_2=(3+2)-4=1\). Beide sind nichtnegativ, der Punkt ist zulässig.