Simplexalgorithmus
Simplexalgorithmus
Definition
Der Simplexalgorithmus ist ein numerisches Verfahren zur Lösung linearer Optimierungsprobleme mit mehr als zwei Variablen. Er ersetzt die grafische Lösung durch eine systematische Verbesserung von Eckpunkten des zulässigen Bereichs.
Der Algorithmus wird im Grundkurs zur Lösung von Maximierungsproblemen verwendet, bei denen:
- alle Nebenbedingungen Ungleichungen vom Typ ≤ sind,
- alle Variablen der Nichtnegativitätsbedingung genügen,
- eine Startlösung (Nullösung) existiert.
Beispiel (Produktionsplanung)
In einer Fabrik werden die Produkte A und B auf drei Automaten hergestellt.
| Automat | Zeit für A (min) | Zeit für B (min) | Maximale Nutzungszeit (min) |
|---|---|---|---|
| I | 2 | 4 | 320 |
| II | 4 | 4 | 400 |
| III | 4 | 2 | 360 |
Gewinn:
- Produkt A: 9 €
- Produkt B: 12 €
Mathematisches Modell
Entscheidungsvariablen
- [math]\displaystyle{ x_1 }[/math]: Stückzahl von Produkt A
- [math]\displaystyle{ x_2 }[/math]: Stückzahl von Produkt B
Nebenbedingungen
[math]\displaystyle{ \begin{aligned} 2x_1 + 4x_2 &\le 320 \quad &(\text{Automat I})\\ 4x_1 + 4x_2 &\le 400 \quad &(\text{Automat II})\\ 4x_1 + 2x_2 &\le 360 \quad &(\text{Automat III})\\ x_1, x_2 &\ge 0 \end{aligned} }[/math]
Zielfunktion
[math]\displaystyle{ Z = 9x_1 + 12x_2 \rightarrow \max }[/math]
Umformung in ein Gleichungssystem
Zur Anwendung des Simplexalgorithmus werden Schlupfvariablen eingeführt:
[math]\displaystyle{ \begin{aligned} 2x_1 + 4x_2 + u_1 &= 320\\ 4x_1 + 4x_2 + u_2 &= 400\\ 4x_1 + 2x_2 + u_3 &= 360 \end{aligned} }[/math]
- [math]\displaystyle{ u_1, u_2, u_3 }[/math] beschreiben freie Kapazitäten
- Anfangs sind [math]\displaystyle{ x_1 = x_2 = 0 }[/math] (Nullösung)
Erstes Simplex-Tableau
| Basis | x₁ | x₂ | u₁ | u₂ | u₃ | b |
|---|---|---|---|---|---|---|
| u₁ | 2 | 4 | 1 | 0 | 0 | 320 |
| u₂ | 4 | 4 | 0 | 1 | 0 | 400 |
| u₃ | 4 | 2 | 0 | 0 | 1 | 360 |
| Z | -9 | -12 | 0 | 0 | 0 | 0 |
Zentrale Begriffe
Pivot-Spalte
Die Pivot-Spalte ist die Spalte mit dem stärksten negativen Koeffizienten in der Zielfunktionszeile. → Sie zeigt, welche Variable den Gewinn am stärksten erhöht.
Hier: [math]\displaystyle{ x_2 }[/math], da −12 < −9.
Pivot-Zeile (Engpass)
Die Pivot-Zeile wird durch den Minimumquotienten bestimmt: [math]\displaystyle{ \frac{b}{\text{Koeffizient der Pivot-Spalte}} }[/math]
Nur positive Koeffizienten werden berücksichtigt. Die Pivot-Zeile beschreibt die engste Nebenbedingung (Engpass).
Pivot-Element
Das Pivot-Element ist das Element am Schnittpunkt von Pivot-Spalte und Pivot-Zeile. Es wird im nächsten Schritt auf 1 normiert.
Iterationen
Nach sukzessiver Anwendung des Gaußschen Eliminationsverfahrens (vgl. Gaußsches Eliminationsverfahren) erhält man das optimale Tableau.
Optimales Tableau
| Basis | x₁ | x₂ | u₁ | u₂ | u₃ | b |
|---|---|---|---|---|---|---|
| x₂ | 0 | 1 | 0,5 | -0,25 | 0 | 60 |
| x₁ | 1 | 0 | -0,5 | 0,5 | 0 | 40 |
| u₃ | 0 | 0 | 1 | -1,5 | 1 | 80 |
| Z | 0 | 0 | -1,5 | -1,5 | 0 | 1080 |
Optimale Lösung
- [math]\displaystyle{ x_1 = 40 }[/math]
- [math]\displaystyle{ x_2 = 60 }[/math]
- Maximaler Gewinn:
[math]\displaystyle{ Z = 9 \cdot 40 + 12 \cdot 60 = 1080 }[/math]
Automat III besitzt noch 80 Minuten freie Kapazität, Automaten I und II sind ausgelastet.
Einordnung
- Der Simplexalgorithmus liefert dasselbe Ergebnis wie die grafische Lösung
- Er ist auf Probleme mit vielen Variablen übertragbar
- Tabellenkalkulationen oder CAS erleichtern die Berechnung
Zusammenhang
- Grafische Lösung: Eckpunktberechnungsmethode
- Lineare Gleichungssysteme: Lineares Gleichungssystem
- Matrizenrechnung: Matrix