Simplexalgorithmus: Unterschied zwischen den Versionen

Aktuelle Version vom 6. Februar 2026, 10:05 Uhr

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\)).

@@ Zeile 1: / Zeile 1: @@
 == Definition ==
-Der '''Simplexalgorithmus''' ist ein numerisches Verfahren zur Lösung '''linearer Optimierungsprobleme''' mit mehreren Variablen.
+Die '''Simplexmethode''' ist ein algebraisches Verfahren zur Lösung von [[Lineares Optimierungsproblem|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.
-Er eignet sich insbesondere für Probleme im '''ℝ³ oder höher'''.
+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\)
-== Voraussetzungen ==
+'''Zielgleichung:'''
-* Lineares Standard-Maximumproblem
+* \(Z = 9x_1 + 12x_2 \rightarrow \text{max!}\)
-* Nebenbedingungen als Gleichungen
-* Alle Variablen ≥ 0
-== Schlupfvariablen ==
+=== 2. Das erste Simplex-Tableau (Startlösung) ===
-Ungleichungen werden durch '''Schlupfvariablen''' in Gleichungen überführt:
+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:
-:<math>a_1x + a_2y \le b \;\Rightarrow\; a_1x + a_2y + s = b</math>
-== Simplex-Tableau ==
+{| class="wikitable" style="text-align:center;"
-Das Optimierungsproblem wird in Tabellenform dargestellt (vgl. [[Matrix]]).
+! 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\)
+|-
+| style="background:#eee;" | \(Z\) || -9 || -12 || 0 || 0 || 0 || 0 ||
+|}
+''Anmerkung: Im Tableau werden oft die negativen Koeffizienten der umgeformten Zielgleichung verwendet.''
-=== Begriffe ===
+* '''Pivot-Spalte''': \(x_2\) (da 12 > 9).
-* '''Pivot-Spalte''': Variable mit größtem Zielfunktionskoeffizienten
+* '''Pivot-Zeile''': 1. Zeile (Automat I), da hier der kleinste Quotient (80) vorliegt.
-* '''Pivot-Zeile''': Engpass (Minimumquotient)
+* '''Pivot-Element''': '''4'''.
-* '''Pivot-Element''': Schnittpunkt von Pivot-Zeile und Pivot-Spalte
-* '''Engpass''': begrenzende Nebenbedingung
-== Algorithmus ==
+=== 3. Zweites Tableau ===
-. Aufstellen des Simplex-Tableaus
+Nach Anwendung des [[Gaußsches Eliminationsverfahren|Gauß-Verfahrens]] (Pivot-Element auf 1 bringen, Rest der Spalte auf 0):
-. Bestimmung der Pivot-Spalte
-. Bestimmung der Pivot-Zeile
-. Pivotisierung
-. Abbruch, wenn keine Verbesserung möglich ist
-== Beispiel ==
+{| class="wikitable" style="text-align:center;"
-Maximiere:
+! Basis !! \(x_1\) !! \(x_2\) !! \(u_1\) !! \(u_2\) !! \(u_3\) !! r.S. !! Quotient
-:<math>Z = 3x + 2y</math>
+|-
+| \(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\)
+|-
+| style="background:#eee;" | \(Z\) || -3 || 0 || 3 || 0 || 0 || 960 ||
+|}
-unter:
+* Die Lösung ist noch nicht optimal, da in der \(Z\)-Zeile bei \(x_1\) noch ein negativer Wert (-3) steht.
-:<math>
+* Neue Pivot-Spalte: \(x_1\); Neue Pivot-Zeile: Zeile von \(u_2\) (Quotient 40); Pivot-Element: '''2'''.
-\begin{aligned}
-x + y &\le 4\\
-x + y &\le 5\\
-x,y &\ge 0
-\end{aligned}
-</math>
-Nach Einführung der Schlupfvariablen entsteht ein Simplex-Tableau, aus dem iterativ die optimale Lösung abgelesen wird.
+=== 4. Drittes Tableau (Optimalzustand) ===
+Erneute Umformung führt zum Endtableau:
-== Hilfsmittel ==
+{| class="wikitable" style="text-align:center;"
-* CAS
+! Basis !! \(x_1\) !! \(x_2\) !! \(u_1\) !! \(u_2\) !! \(u_3\) !! r.S.
-* Tabellenkalkulation (z. B. Excel)
+|-
+| \(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'''
+|-
+| style="background:#eee;" | \(Z\) || 0 || 0 || 1,5 || 1,5 || 0 || '''1080'''
+|}
-== Zusammenhang ==
+=== Interpretation des Ergebnisses ===
-* Grafische Lösung: [[Eckpunktberechnungsmethode]]
+Da kein Koeffizient in der Zielgleichungszeile mehr positiv (bzw. bei dieser Tabellenform negativ) ist, wurde das Optimum erreicht:
-* Lineare Gleichungssysteme: [[Gaußsches Eliminationsverfahren]]
+* 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\)).
 [[Kategorie:Lineare_Optimierung]]
 [[Kategorie:AHR_WuV_Mathe_GK]]