Simplexalgorithmus
Definition
Die Simplexmethode ist ein algebraisches Verfahren zur Lösung von linearen Optimierungsproblemen mit beliebig vielen Variablen. Während grafische Verfahren meist auf zwei (maximal drei) Variablen beschränkt sind, ermöglicht der Simplexalgorithmus die systematische Suche nach dem optimalen Eckpunkt in einem hochdimensionalen Planungspolyeder.
Für die Anwendung des regulären Simplexalgorithmus müssen zwei Voraussetzungen erfüllt sein:
- Die Nulllösung (alle Problemvariablen sind Null) muss eine zulässige Lösung sein.
- Es muss sich um ein Maximierungsproblem handeln.
Mathematische Grundlagen und Begriffe
Schlupfvariablen
Um ein Ungleichungssystem in ein Lineares Gleichungssystem zu überführen, wird für jede Restriktion eine zusätzliche Variable eingeführt, die den vorhandenen „Spielraum“ (die Differenz zwischen Ressourcenverbrauch und Kapazität) auffüllt. Diese werden als Schlupfvariablen (hier: \(u_1, u_2, u_3\)) bezeichnet. Sie übernehmen mathematisch die Restkapazität der jeweiligen Produktionseinheit.
Basis- und Nichtbasisvariablen
In einem System mit \(n\) Variablen und \(m\) Gleichungen können \(m\) Variablen als Basisvariablen (BV) ausgedrückt werden, während die restlichen \(n-m\) Variablen als Nichtbasisvariablen (NBV) den Wert Null erhalten.
- In der Startlösung sind die Problemvariablen (\(x_1, x_2\)) die NBV.
- Die Schlupfvariablen bilden die erste Basis.
Pivot-Element, -Zeile und -Spalte
- Pivot-Spalte: Die Spalte der Nichtbasisvariablen, die den größten positiven Beitrag zur Steigerung der Zielgröße \(Z\) liefert.
- Pivot-Zeile: Die Zeile, die den engsten Engpass darstellt. Man ermittelt sie, indem man die Kapazitäten (rechte Seite) durch die Koeffizienten der Pivot-Spalte teilt; der kleinste positive Quotient markiert die Pivot-Zeile.
- Pivot-Element: Das Schnittpunkt-Element von Pivot-Spalte und Pivot-Zeile.
Beispiel: Gewinnmaximum ermitteln
In einer Fabrik werden die Produkte A und B auf den Automaten I, II und III hergestellt.
1. Aufstellen des mathematischen Modells
Basierend auf den Bearbeitungszeiten und Kapazitäten ergibt sich folgendes Modell:
Variablen:
- \(x_1\): Stückzahl Produkt A (Gewinn: 9 GE/Stück)
- \(x_2\): Stückzahl Produkt B (Gewinn: 12 GE/Stück)
Bedingungssystem:
- Automat I: \(2x_1 + 4x_2 \le 320\)
- Automat II: \(4x_1 + 4x_2 \le 400\)
- Automat III: \(4x_1 + 2x_2 \le 360\)
- Nichtnegativitätsbedingungen: \(x_1, x_2 \ge 0\)
Zielgleichung:
- \(Z = 9x_1 + 12x_2 \rightarrow \text{max!}\)
2. Das erste Simplex-Tableau (Startlösung)
Nach Einführung der Schlupfvariablen \(u_1, u_2, u_3\) und Umformung der Zielgleichung in die Form \(Z - 9x_1 - 12x_2 = 0\) ergibt sich das Starttableau:
| Basis | \(x_1\) | \(x_2\) | \(u_1\) | \(u_2\) | \(u_3\) | r.S. | Quotient (Engpass) |
|---|---|---|---|---|---|---|---|
| \(u_1\) | 2 | 4 | 1 | 0 | 0 | 320 | \(320:4 = 80\) (Engpass!) |
| \(u_2\) | 4 | 4 | 0 | 1 | 0 | 400 | \(400:4 = 100\) |
| \(u_3\) | 4 | 2 | 0 | 0 | 1 | 360 | \(360:2 = 180\) |
| \(Z\) | -9 | -12 | 0 | 0 | 0 | 0 |
Anmerkung: Im Tableau werden oft die negativen Koeffizienten der umgeformten Zielgleichung verwendet.
- Pivot-Spalte: \(x_2\) (da 12 > 9).
- Pivot-Zeile: 1. Zeile (Automat I), da hier der kleinste Quotient (80) vorliegt.
- Pivot-Element: 4.
3. Zweites Tableau
Nach Anwendung des Gauß-Verfahrens (Pivot-Element auf 1 bringen, Rest der Spalte auf 0):
| Basis | \(x_1\) | \(x_2\) | \(u_1\) | \(u_2\) | \(u_3\) | r.S. | Quotient |
|---|---|---|---|---|---|---|---|
| \(x_2\) | 0,5 | 1 | 0,25 | 0 | 0 | 80 | \(80:0,5 = 160\) |
| \(u_2\) | 2 | 0 | -1 | 1 | 0 | 80 | \(80:2 = 40\) (Engpass!) |
| \(u_3\) | 3 | 0 | -0,5 | 0 | 1 | 200 | \(200:3 \approx 66,7\) |
| \(Z\) | -3 | 0 | 3 | 0 | 0 | 960 |
- Die Lösung ist noch nicht optimal, da in der \(Z\)-Zeile bei \(x_1\) noch ein negativer Wert (-3) steht.
- Neue Pivot-Spalte: \(x_1\); Neue Pivot-Zeile: Zeile von \(u_2\) (Quotient 40); Pivot-Element: 2.
4. Drittes Tableau (Optimalzustand)
Erneute Umformung führt zum Endtableau:
| Basis | \(x_1\) | \(x_2\) | \(u_1\) | \(u_2\) | \(u_3\) | r.S. |
|---|---|---|---|---|---|---|
| \(x_2\) | 0 | 1 | 0,5 | -0,25 | 0 | 60 |
| \(x_1\) | 1 | 0 | -0,5 | 0,5 | 0 | 40 |
| \(u_3\) | 0 | 0 | 1 | -1,5 | 1 | 80 |
| \(Z\) | 0 | 0 | 1,5 | 1,5 | 0 | 1080 |
Interpretation des Ergebnisses
Da kein Koeffizient in der Zielgleichungszeile mehr positiv (bzw. bei dieser Tabellenform negativ) ist, wurde das Optimum erreicht:
- Es sollten 40 Einheiten von Produkt A (\(x_1\)) und 60 Einheiten von Produkt B (\(x_2\)) hergestellt werden.
- Der maximale Gewinn beträgt 1080 GE.
- Die Automaten I und II sind voll ausgelastet (\(u_1=0, u_2=0\)).
- Automat III hat eine **freie Kapazität** von 80 Minuten (\(u_3=80\)).