Simplexalgorithmus: Unterschied zwischen den Versionen

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

Der '''Simplexalgorithmus''' ist ein numerisches Verfahren zur Lösung '''linearer Optimierungsprobleme''' mit mehreren Variablen.

Er eignet sich insbesondere für Probleme im '''ℝ³ oder höher'''.

== ~~Vorgehensweise~~ ==

== Voraussetzungen ==

* Lineares Standard-Maximumproblem

* Nebenbedingungen als Gleichungen

* Alle Variablen ≥ 0

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

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

Ungleichungen werden durch '''Schlupfvariablen''' in Gleichungen überführt:

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

:<math>a_1x + a_2y \le b \;\Rightarrow\; a_1x + a_2y + s = b</math>

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

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

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

Das Optimierungsproblem wird in Tabellenform dargestellt (vgl. [[Matrix]]).

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

=== Begriffe ===

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

* '''Pivot-Spalte''': Variable mit größtem Zielfunktionskoeffizienten

|-

* '''Pivot-Zeile''': Engpass (Minimumquotient)

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

* '''Pivot-Element''': Schnittpunkt von Pivot-Zeile und Pivot-Spalte

|-

* '''Engpass''': begrenzende Nebenbedingung

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

|-

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

|}

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

== Algorithmus ==

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

1. Aufstellen des Simplex-Tableaus

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

2. Bestimmung der Pivot-Spalte

* '''Pivot-Element''': Das Schnittpunkt-Element von Pivot-Spalte und Pivot-Zeile.

3. Bestimmung der Pivot-Zeile

4. Pivotisierung

5. Abbruch, wenn keine Verbesserung möglich ist

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.

== Beispiel ==

Maximiere:

:<math>Z = 3x + 2y</math>

== ~~Ökonomische Interpretation~~ ==

unter:

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

:<math>

\begin{aligned}

x + y &\le 4\\

2x + 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.

== Hilfsmittel ==

* CAS

* Tabellenkalkulation (z. B. Excel)

== Zusammenhang ==

* Grafische Lösung: [[Eckpunktberechnungsmethode]]

* Lineare Gleichungssysteme: [[Gaußsches Eliminationsverfahren]]

[[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.
+Der '''Simplexalgorithmus''' ist ein numerisches Verfahren zur Lösung '''linearer Optimierungsprobleme''' mit mehreren Variablen.
+Er eignet sich insbesondere für Probleme im '''ℝ³ oder höher'''.
-== Vorgehensweise ==
+== Voraussetzungen ==
+* Lineares Standard-Maximumproblem
+* Nebenbedingungen als Gleichungen
+* Alle Variablen ≥ 0
-=== 1. Aufstellen der Normalform (Schlupfvariablen) ===
+== 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.
+Ungleichungen werden durch '''Schlupfvariablen''' in Gleichungen überführt:
-* Beispiel: Aus \(2x_1 + x_2 \le 100\) wird \(2x_1 + x_2 + s_1 = 100\).
+:<math>a_1x + a_2y \le b \;\Rightarrow\; a_1x + a_2y + s = b</math>
-* Wenn \(s_1 = 0\), liegt ein '''Engpass''' vor (die Kapazität ist voll ausgeschöpft).
-=== 2. Das Simplex-Tableau ===
+== 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\)).
+Das Optimierungsproblem wird in Tabellenform dargestellt (vgl. [[Matrix]]).
-{| class="wikitable" style="text-align:center;"
+=== Begriffe ===
-! Basis !! \(x_1\) !! \(x_2\) !! \(s_1\) !! \(s_2\) !! r.S. !! Q
+* '''Pivot-Spalte''': Variable mit größtem Zielfunktionskoeffizienten
-|-
+* '''Pivot-Zeile''': Engpass (Minimumquotient)
-| \(s_1\) || 2 || 1 || 1 || 0 || 100 || 50
+* '''Pivot-Element''': Schnittpunkt von Pivot-Zeile und Pivot-Spalte
-|-
+* '''Engpass''': begrenzende Nebenbedingung
-| \(s_2\) || 1 || 2 || 0 || 1 || 80 || 40
-|-
-| style="background:#eee;" | \(z\) || -40 || -50 || 0 || 0 || 0 ||
-|}
-=== 3. Iterationsschritte ===
+== Algorithmus ==
-* '''Pivot-Spalte''': Die Spalte mit dem negativsten Wert in der Zielfunktionszeile (Indikatorzeile). Sie zeigt den größten relativen Zuwachs.
+. Aufstellen des Simplex-Tableaus
-* '''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.
+. Bestimmung der Pivot-Spalte
-* '''Pivot-Element''': Das Schnittpunkt-Element von Pivot-Spalte und Pivot-Zeile.
+. Bestimmung der Pivot-Zeile
+. Pivotisierung
+. Abbruch, wenn keine Verbesserung möglich ist
-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.
+== Beispiel ==
+Maximiere:
+:<math>Z = 3x + 2y</math>
-== Ökonomische Interpretation ==
+unter:
-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.
+:<math>
+\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.
+== Hilfsmittel ==
+* CAS
+* Tabellenkalkulation (z. B. Excel)
+== Zusammenhang ==
+* Grafische Lösung: [[Eckpunktberechnungsmethode]]
+* Lineare Gleichungssysteme: [[Gaußsches Eliminationsverfahren]]
 [[Kategorie:Lineare_Optimierung]]
 [[Kategorie:AHR_WuV_Mathe_GK]]