Simplexalgorithmus

Definition

Der Simplexalgorithmus (oder das Simplex-Verfahren) ist ein iteratives numerisches Verfahren zur Lösung von linearen Optimierungsproblemen. Er wird insbesondere dann eingesetzt, wenn mehr als zwei Entscheidungsvariablen vorliegen und eine grafische Lösung nicht mehr möglich ist.

Vorgehensweise

1. Aufstellen der Normalform (Schlupfvariablen)

Um die Ungleichungen des Bedingungssystems in Gleichungen zu überführen, werden Schlupfvariablen (\(s_1, s_2, ...\)) eingeführt. Diese Variablen füllen die Differenz zwischen der verbrauchten Ressource und der Kapazitätsgrenze auf.

• Beispiel: Aus \(2x_1 + x_2 \le 100\) wird \(2x_1 + x_2 + s_1 = 100\).
• Wenn \(s_1 = 0\), liegt ein Engpass vor (die Kapazität ist voll ausgeschöpft).

2. Das Simplex-Tableau

Die Gleichungen werden in einem speziellen Schema, dem Simplex-Tableau, angeordnet. Die Zielfunktion wird dabei so umgeformt, dass alle Variablen auf einer Seite stehen (meist \(z - c_1x_1 - c_2x_2 ... = 0\)).

Basis	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	r.S.	Q
\(s_1\)	2	1	1	0	100	50
\(s_2\)	1	2	0	1	80	40
\(z\)	-40	-50	0	0	0

3. Iterationsschritte

• Pivot-Spalte: Die Spalte mit dem negativsten Wert in der Zielfunktionszeile (Indikatorzeile). Sie zeigt den größten relativen Zuwachs.
• Pivot-Zeile: Die Zeile mit dem kleinsten positiven Quotienten \(Q\) aus der rechten Seite (r.S.) und dem Wert der Pivot-Spalte. Sie markiert den ersten eintretenden Engpass.
• Pivot-Element: Das Schnittpunkt-Element von Pivot-Spalte und Pivot-Zeile.

Mithilfe des Gaußschen Eliminationsverfahrens wird das Pivot-Element auf 1 und alle anderen Werte in der Pivot-Spalte auf 0 transformiert. Dieser Prozess wird wiederholt, bis keine negativen Werte mehr in der Zielfunktionszeile stehen.

Ökonomische Interpretation

Das Endtableau gibt die optimale Produktionsmenge sowie den maximalen Erfolg (Deckungsbeitrag) an. Schlupfvariablen im Endtableau, die ungleich Null sind, zeigen nicht genutzte Kapazitäten in den jeweiligen Abteilungen an.