Ganzer Simplex-Lauf
Voraussetzung: Optimum ablesen
Wenn zwei Variablen und zwei Nebenbedingungen vorliegen, kannst du graphisch lösen. Bei drei Variablen geht das nicht mehr, und in Klausuren wird der Simplex-Algorithmus verlangt. Er besteht aus den Teilen, die du einzeln geübt hast: Schlupfvariablen, Pivotspalte, Pivotzeile, Pivotschritt und Ablesen. Diese Karte führt sie zu einem ganzen Lauf zusammen. Voraussetzung sind die vier Karten zur Optimierung, vor allem zu Pivot und Theta.
Der Lauf in der Reihenfolge des Skripts:
- Jede Nebenbedingung bekommt eine Schlupfvariable. Die Zielfunktion wird zu \(Z-c_1x_1-\dots-c_nx_n=0\).
- Starttableau aufstellen: Die Schlupfvariablen sind die Basisvariablen.
- Hat die Zeile \(Z\) keinen negativen Eintrag, ist der Lauf zu Ende. Sonst ist die Spalte mit dem kleinsten Eintrag die Pivotspalte.
- \(\Theta\) für jede Zeile mit positivem Eintrag in der Pivotspalte bilden. Das kleinste \(\Theta\) gibt die Pivotzeile.
- Pivotzeile durch das Pivotelement teilen, mit ihr die übrigen Einträge der Pivotspalte nullen und die Variablen in der Basis tauschen. Dann zurück zu 3.
Jeder Pivotschritt führt zu einer anderen Ecke des erlaubten Bereichs, und der Zielwert wird nie kleiner. Nach endlich vielen Schritten ist die beste Ecke erreicht. Wie viele Schritte nötig sind, hängt vom Problem ab: Nach einem Schritt kann noch ein negativer Eintrag in der Zeile \(Z\) stehen, dann folgt der nächste.
\[ \begin{array}{c|cccc|c}\text{BV}&x_1&x_2&S_1&S_2&b\\\hline S_1&3&1&1&0&24\\S_2&1&1&0&1&14\\\hline Z&-4&-3&0&0&0\end{array} \]
Pivotspalte ist \(x_1\) (Eintrag \(-4\)). Es ist \(\Theta_1=\frac{24}{3}=8\) und \(\Theta_2=\frac{14}{1}=14\), also ist \(S_1\) die Pivotzeile. Nach dem Teilen durch \(3\) und dem Nullen entsteht
\[ \begin{array}{c|cccc|c}\text{BV}&x_1&x_2&S_1&S_2&b\\\hline x_1&1&\tfrac13&\tfrac13&0&8\\S_2&0&\tfrac23&-\tfrac13&1&6\\\hline Z&0&-\tfrac53&\tfrac43&0&32\end{array} \]
In der Zeile \(Z\) steht unter \(x_2\) noch \(-\frac53\). Die Pivotspalte ist \(x_2\), es ist \(\Theta_1=8:\frac13=24\) und \(\Theta_2=6:\frac23=9\), die Pivotzeile ist \(S_2\). Der zweite Schritt liefert
\[ \begin{array}{c|cccc|c}\text{BV}&x_1&x_2&S_1&S_2&b\\\hline x_1&1&0&\tfrac12&-\tfrac12&5\\x_2&0&1&-\tfrac12&\tfrac32&9\\\hline Z&0&0&\tfrac12&\tfrac52&47\end{array} \]
Kein Eintrag in \(Z\) ist negativ. Das Optimum liegt bei \(x_1=5\), \(x_2=9\), \(S_1=S_2=0\) mit \(Z=47\).
Die Probe mit dem graphischen Verfahren
Das Beispiel hat die Ecken \((0,0)\), \((8,0)\), \((5,9)\) und \((0,14)\) mit den Werten \(Z=0\), \(32\), \(47\) und \(42\). Der größte Wert \(47\) liegt in \((5,9)\), und genau dort endet der Simplex-Lauf. Der erste Schritt führte vom Ursprung zur Ecke \((8,0)\) mit \(Z=32\), der zweite von dort zur Ecke \((5,9)\). Bei zwei Variablen siehst du den Weg im Bild, bei mehr Variablen verlässt du dich auf die Rechnung.
Ein zweites Beispiel, was die Einträge der Zeile Z am Ende bedeuten
Die Einträge \(\frac12\) und \(\frac52\) unter den Schlupfvariablen im Endtableau sind nicht negativ. Sie sagen, wie viel \(Z\) etwa wächst, wenn eine Kapazität um eine Einheit größer wäre: um \(\frac12\) bei der ersten und um \(\frac52\) bei der zweiten Nebenbedingung. Diese Deutung der Kapazitäten folgt in einer eigenen Karte.