Definition
Der Simplex-Algorithmus löst lineare Optimierungsprobleme.
Algorithmus bedeutet, dass man (Mensch oder Computer / Programm) bestimmte Schritte in einer bestimmten Reihenfolge abarbeiten muss.
Für das Simplex-Verfahren werden Umformungen vorgenommen, wie man sie vom Gauß-Algorithmus aus der Matrizenrechnung bzw. dem Lösen linearer Gleichungssysteme kennt.
Alternative Begriffe: Simplexalgorithmus, Simplexmethode, Simplex-Methode, Simplex-Verfahren, Simplexverfahren.
Beispiel
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).
Simplex-Algorithmus anwenden
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 s1 und s2 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 + s1 = 3
k × 2 + t × 4 + s2 = 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 s1) 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 s2) 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.
Ergebnis
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.
Fazit
- Simplex-Algorithmus: iteratives Tableau-Verfahren zur Lösung linearer Optimierungsprobleme – geht vom zulässigen Anfangseckpunkt schrittweise zum optimalen Eckpunkt.
- Schlupfvariablen s1, s2, … wandeln ≤-Ungleichungen in Gleichungen um und ermöglichen so die Tableau-Darstellung.
- Pivotspalte: negativster Wert in der Zielfunktionszeile (Z-Zeile); Pivotzeile: Minimum der Quotienten (Ergebnisspalte ÷ Pivotspaltenkoeffizient); Pivotelement: Kreuzpunkt beider.
- Abbruch: sobald alle Werte der Z-Zeile ≥ 0 – das globale Optimum ist erreicht; die Lösung steht in der Ergebnisspalte.
Selbsttest: Simplex-Algorithmus
Aufgabe: Simplex-Algorithmus
Lösen Sie das folgende lineare Optimierungsproblem mit dem Simplex-Algorithmus:
Maximieren Sie Z = 2x1 + 3x2
Nebenbedingungen:
x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1, x2 ≥ 0
Stellen Sie (a) das Anfangstableau auf (mit Schlupfvariablen s1, s2) und bestimmen Sie (b) das erste Pivotelement.
(a) Schlupfvariablen einführen: x1 + x2 + s1 = 4 und x1 + 2x2 + s2 = 6
Anfangstableau:
| x1 | x2 | s1 | s2 | b | |
|---|---|---|---|---|---|
| I | 1 | 1 | 1 | 0 | 4 |
| II | 1 | 2 | 0 | 1 | 6 |
| Z | −2 | −3 | 0 | 0 | 0 |
(b) Pivotelement: Pivotspalte = x2 (negativster Z-Wert: −3). Quotienten: 4 ÷ 1 = 4 (Zeile I), 6 ÷ 2 = 3 (Zeile II) → Pivotzeile II. Pivotelement = 2.
1. Tableau-Umformung (Zeile II ÷ 2, dann andere Zeilen anpassen):
| x1 | x2 | s1 | s2 | b | |
|---|---|---|---|---|---|
| I | 0,5 | 0 | 1 | −0,5 | 1 |
| II | 0,5 | 1 | 0 | 0,5 | 3 |
| Z | −0,5 | 0 | 0 | 1,5 | 9 |
Neues Pivotelement: x1-Spalte (−0,5), Quotienten: 1 ÷ 0,5 = 2, 3 ÷ 0,5 = 6 → Pivotzeile I, Pivotelement 0,5.
2. Tableau-Umformung (Zeile I ÷ 0,5, dann andere Zeilen anpassen):
| x1 | x2 | s1 | s2 | b | |
|---|---|---|---|---|---|
| I | 1 | 0 | 2 | −1 | 2 |
| II | 0 | 1 | −1 | 1 | 2 |
| Z | 0 | 0 | 1 | 1 | 10 |
Alle Werte der Z-Zeile ≥ 0 → Optimum erreicht: x1 = 2, x2 = 2, Z = 10.