Simplex-Algorithmus

Beispiel: Simplex-Algorithmus anwenden

Es sollen die Daten aus dem Beispiel zur linearen Optimierung verwendet werden. Das lineare Programm war:

Ein Kiosk verkauft zwei Produkte:

• den K-Becher: ein Becher mit Zucker (1 Becher, 2 Zuckerwürfel) für Kaffeetrinker und
• den T-Becher: ein Becher mit mehr Zucker (1 Becher, 4 Zuckerwürfel) für Teetrinker.

Den Kaffee oder Tee müssen die Kunden selbst mitbringen. Der Gewinn je K-Becher sei 2 € und je T-Becher 3 €.

k sei die verkaufte Menge K-Becher, t die verkaufte Menge T-Becher.

Die lineare, zu maximierende Zielfunktion ist:

Z(k, t) = k × 2 € + t × 3 €.

Kapazitätsbeschränkungen (als Nebenbedingungen mit Ungleichungen erfasst):

k × 1 + t × 1 <= 3 (es gibt nur 3 Becher)

k × 2 + t × 4 <= 8 (es gibt nur 8 Zuckerwürfel).

Zudem müssen k und t >= 0 sein (es können keine negativen Mengen hergestellt und verkauft werden).

Schritt 1: Gleichungssystem aufstellen

Das Problem wird in eine Art Matrixform – das Simplex-Tableau – überführt; zunächst werden aus den beiden Ungleichungen mit einem Trick Gleichungen gemacht. Dafür führt man sogenannte Schlupfvariablen s₁ und s₂ ein (wenn eine Ungleichung z. B. 12 + 8 <= 25 lautete, dann wäre für 12 + 8 + s = 25 die Schlupfvariable s = 5):

k × 1 + t × 1 + s₁ = 3

k × 2 + t × 4 + s₂ = 8.

Schritt 2: Simplex-Tableau aufstellen

$$\left[ \begin{array}{c|cccc|c} &k&t&s_1&s_2&E \\ I&1&1&1&0&3 \\ II&2&4&0&1&8 \\ III&-2&-3&0&0&0 \end{array} \right]$$

Die erste Zeile I enthält die 3 Koeffizienten der Nebenbedingung 1 (für k, t und s₁) sowie ganz rechts die 3 (maximale Anzahl der Becher).

Die zweite Zeile II enthält die 3 Koeffizienten der Nebenbedingung 2 (für k, t und s₂) sowie ganz rechts die 8 (maximale Anzahl der Zuckerwürfel).

Die dritte Zeile III enthält die 2 Koeffizienten der Zielfunktion (k, t) als negative Werte.

Die ganz rechte Spalte "E" ist die Ergebnisspalte (in der sich am Schluss die Lösung befindet).

Schritt 3: Simplex-Tableau mehrmals umformen

Pivotelement bestimmen

Die sogenannte Pivotspalte ist die Spalte, bei welcher der Zielfunktionskoeffizient (in der untersten Zeile) am geringsten ist; das ist mit -3 die t-Spalte.

Teilt man die Zeilen I und II der Ergebnisspalte (ganz rechte Spalte) durch die jeweiligen Werte der Pivotspalte, ergibt das 3:1 = 3 für Zeile I und 8:4 = 2 für Zeile II; der kleinste Wert bestimmte die Pivotzeile, hier also Zeile II.

Das Pivotelement ist dann im Kreuzpunkt von Pivotspalte und -zeile, das ist die Zahl 4.

Erste Umformung

Die Pivotzeile wird durch das Pivotelement (also durch 4) geteilt:

$$\left[ \begin{array}{c|cccc|c} &k&t&s_1&s_2&E \\ I&1&1&1&0&3 \\ II&0,5&1&0&0,25&2 \\ III&-2&-3&0&0&0 \end{array} \right]$$

Anschließend bringt man die anderen Koeffizienten der Pivotspalte auf 0, indem man in den Zeilen I und III ein Vielfaches der Pivotzeile addiert oder subtrahiert; hier wird von Zeile I die Pivotzeile II abgezogen und zu Zeile III das Dreifache der Pivotzeile addiert:

$$\left[ \begin{array}{c|cccc|c} &k&t&s_1&s_2&E \\ I&0,5&0&1&-0,25&1 \\ II&0,5&1&0&0,25&2 \\ III&-0,5&0&0&0,75&6 \end{array} \right]$$

Zweite (und letzte) Umformung

Das kleinste Element in der letzten (Zielfunktions)Zeile ist nun -0,5 in der k-Spalte; das ist deshalb die neue Pivotspalte.

Teilt man die Zeilen I und II der Ergebnisspalte (ganz rechte Spalte) wieder durch die jeweiligen Werte der Pivotspalte, ergibt das 1:0,5 = 2 für Zeile I und 2:0,5 = 4 für Zeile II; der kleinste Wert bestimmt wieder die Pivotzeile, hier also Zeile I. Das Pivotelement ist dann wieder im Kreuzpunkt von Pivotspalte und -zeile, das ist die Zahl 0,5.

Die Pivotzeile wird durch das Pivotelement (also durch 0,5) geteilt:

$$\left[ \begin{array}{c|cccc|c} &k&t&s_1&s_2&E \\ I&1&0&2&-0,5&2 \\ II&0,5&1&0&0,25&2 \\ III&-0,5&0&0&0,75&6 \end{array} \right]$$

Anschließend bringt man die anderen Koeffizienten der Pivotspalte wieder auf 0; hier wird von Zeile II das 0,5-fache der Pivotzeile I abgezogen und zu Zeile III wird das 0,5-fache der Pivotzeile addiert:

$$\left[ \begin{array}{c|cccc|c} &k&t&s_1&s_2&E \\ I&1&0&2&-0,5&2 \\ II&0&1&-1&0,5&1 \\ III&0&0&1&0,5&7 \end{array} \right]$$

Die letzte Zeile (Zielfunktion) besteht nur noch aus positiven Werten, deshalb kann der Simplex-Algorithmus beendet werden. Die optimalen Werte können in der rechten Ergebnisspalte abgelesen werden: es werden 2 K-Becher produziert und 1 T-Becher, der Gewinn beträgt 7 (2 K-Becher bringen 2 × 2 € = 4 € Gewinn, 1 T-Becher bringt 3 € Gewinn, in Summe 7 €; das stimmt mit dem Ergebnis bei der linearen Optimierung durch Ausprobieren überein).