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