FLBK-Wiki

Simplexalgorithmus: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied

Flbkwikiadmin (Diskussion | Beiträge)

3 Benutzergruppen
2.255 Bearbeitungen
VisuellWikitext
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
 
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
== Definition ==
== 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 ===
1. Aufstellen des Simplex-Tableaus
Nach Anwendung des [[Gaußsches Eliminationsverfahren|Gauß-Verfahrens]] (Pivot-Element auf 1 bringen, Rest der Spalte auf 0):
2. Bestimmung der Pivot-Spalte
3. Bestimmung der Pivot-Zeile
4. Pivotisierung
5. 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\\
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.
=== 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:Lineare_Optimierung]]
[[Kategorie:AHR_WuV_Mathe_GK]]
[[Kategorie:AHR_WuV_Mathe_GK]]
Abgerufen von „https://wiki.flbk-hamm.de/Simplexalgorithmus“