Simplexalgorithmus: Unterschied zwischen den Versionen

(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)

Zeile 1:

== Definition ==

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

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.

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)

== ~~Vorgehensweise~~ ==

'''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:

{| class="wikitable" style="text-align:center;"

! 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.''

~~=== 1. Aufstellen der Normalform (Schlupfvariablen) ===~~

* '''Pivot-Spalte''': \(x_2\) (da 12 > 9).

~~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~~.

* '''Pivot-Zeile''': 1. Zeile (Automat I), da hier der kleinste Quotient (80) vorliegt.

* ~~Beispiel~~: ~~Aus \~~(~~2x_1 + x_2 \le 100\~~) ~~wird \~~(~~2x_1 + x_2 + s_1 = 100\~~).

* '''Pivot-Element''': '''4'''.

* ~~Wenn \(s_1 = 0\), liegt ein~~ '''~~Engpass~~''' ~~vor (die Kapazität ist voll ausgeschöpft)~~.

=== 2. ~~Das Simplex-~~Tableau ===

=== 3. Zweites 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\)).

Nach Anwendung des [[Gaußsches Eliminationsverfahren|Gauß-Verfahrens]] (Pivot-Element auf 1 bringen, Rest der Spalte auf 0):

{| class="wikitable" style="text-align:center;"

! Basis !! \(x_1\) !! \(x_2\) !! \(~~s_1~~\) !! \(~~s_2~~\) !! r.S. !! Q

! Basis !! \(x_1\) !! \(x_2\) !! \(u_1\) !! \(u_2\) !! \(u_3\) !! r.S. !! Quotient

|-

| \(~~s_1~~\) || 2 || 1 || 1 || 0 || ~~100~~ || 50

| \(x_2\) || 0,5 || 1 || 0,25 || 0 || 0 || 80 || \(80:0,5 = 160\)

|-

| \(~~s_2~~\) || 1 || 2 || 0 || 1 || 80 || 40

| \(u_2\) || 2 || 0 || -1 || 1 || 0 || 80 || \(80:2 = 40\) (Engpass!)

|-

| style="background:#eee;" | \(z\) || -40 || ~~-50~~ || 0 || 0 || 0 ||

| \(u_3\) || 3 || 0 || -0,5 || 0 || 1 || 200 || \(200:3 \approx 66,7\)

|-

| style="background:#eee;" | \(Z\) || -3 || 0 || 3 || 0 || 0 || 960 ||

|}

~~===~~ 3. ~~Iterationsschritte ===~~

* Die Lösung ist noch nicht optimal, da in der \(Z\)-Zeile bei \(x_1\) noch ein negativer Wert (-3) steht.

* ~~'''~~Pivot-Spalte~~'''~~: ~~Die Spalte mit dem negativsten Wert in der Zielfunktionszeile~~ (~~Indikatorzeile~~)~~. Sie zeigt den größten relativen Zuwachs.~~

* Neue Pivot-Spalte: \(x_1\); Neue Pivot-Zeile: Zeile von \(u_2\) (Quotient 40); Pivot-Element: '''2'''.

* '''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.~~

=== 4. Drittes Tableau (Optimalzustand) ===

Erneute Umformung führt zum Endtableau:

~~Mithilfe des [[Gaußsches Eliminationsverfahren~~|~~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.~~

{| class="wikitable" style="text-align:center;"

! 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'''

|-

| style="background:#eee;" | \(Z\) || 0 || 0 || 1,5 || 1,5 || 0 || '''1080'''

|}

== ~~Ökonomische~~ Interpretation ==

=== Interpretation des Ergebnisses ===

~~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~~.

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

[[Kategorie:Lineare_Optimierung]]

[[Kategorie:AHR_WuV_Mathe_GK]]

@@ Zeile 1: / Zeile 1: @@
 == Definition ==
-Der '''Simplexalgorithmus''' (oder das Simplex-Verfahren) ist ein iteratives numerisches Verfahren zur Lösung von [[Lineares Optimierungsproblem|linearen Optimierungsproblemen]]. Er wird insbesondere dann eingesetzt, wenn mehr als zwei Entscheidungsvariablen vorliegen und eine grafische Lösung nicht mehr möglich ist.
+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.
+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)
-== Vorgehensweise ==
+'''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:
+{| class="wikitable" style="text-align:center;"
+! 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.''
-=== 1. Aufstellen der Normalform (Schlupfvariablen) ===
+* '''Pivot-Spalte''': \(x_2\) (da 12 > 9).
-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.
+* '''Pivot-Zeile''': 1. Zeile (Automat I), da hier der kleinste Quotient (80) vorliegt.
-* Beispiel: Aus \(2x_1 + x_2 \le 100\) wird \(2x_1 + x_2 + s_1 = 100\).
+* '''Pivot-Element''': '''4'''.
-* Wenn \(s_1 = 0\), liegt ein '''Engpass''' vor (die Kapazität ist voll ausgeschöpft).
-=== 2. Das Simplex-Tableau ===
+=== 3. Zweites 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\)).
+Nach Anwendung des [[Gaußsches Eliminationsverfahren|Gauß-Verfahrens]] (Pivot-Element auf 1 bringen, Rest der Spalte auf 0):
 {| class="wikitable" style="text-align:center;"
-! Basis !! \(x_1\) !! \(x_2\) !! \(s_1\) !! \(s_2\) !! r.S. !! Q
+! Basis !! \(x_1\) !! \(x_2\) !! \(u_1\) !! \(u_2\) !! \(u_3\) !! r.S. !! Quotient
 |-
-| \(s_1\) || 2 || 1 || 1 || 0 || 100 || 50
+| \(x_2\) || 0,5 || 1 || 0,25 || 0 || 0 || 80 || \(80:0,5 = 160\)
 |-
-| \(s_2\) || 1 || 2 || 0 || 1 || 80 || 40
+| \(u_2\) || 2 || 0 || -1 || 1 || 0 || 80 || \(80:2 = 40\) (Engpass!)
 |-
-| style="background:#eee;" | \(z\) || -40 || -50 || 0 || 0 || 0 ||
+| \(u_3\) || 3 || 0 || -0,5 || 0 || 1 || 200 || \(200:3 \approx 66,7\)
+|-
+| style="background:#eee;" | \(Z\) || -3 || 0 || 3 || 0 || 0 || 960 ||
 |}
-=== 3. Iterationsschritte ===
+* Die Lösung ist noch nicht optimal, da in der \(Z\)-Zeile bei \(x_1\) noch ein negativer Wert (-3) steht.
-* '''Pivot-Spalte''': Die Spalte mit dem negativsten Wert in der Zielfunktionszeile (Indikatorzeile). Sie zeigt den größten relativen Zuwachs.
+* Neue Pivot-Spalte: \(x_1\); Neue Pivot-Zeile: Zeile von \(u_2\) (Quotient 40); Pivot-Element: '''2'''.
-* '''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.
+=== 4. Drittes Tableau (Optimalzustand) ===
+Erneute Umformung führt zum Endtableau:
-Mithilfe des [[Gaußsches Eliminationsverfahren|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.
+{| class="wikitable" style="text-align:center;"
+! 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'''
+|-
+| style="background:#eee;" | \(Z\) || 0 || 0 || 1,5 || 1,5 || 0 || '''1080'''
+|}
-== Ökonomische Interpretation ==
+=== Interpretation des Ergebnisses ===
-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.
+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\)).
 [[Kategorie:Lineare_Optimierung]]
 [[Kategorie:AHR_WuV_Mathe_GK]]