FLBK-Wiki

Simplexalgorithmus: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.097 Bearbeitungen
VisuellWikitext
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
 
Zeile 1: Zeile 1:


== Definition ==
== Definition ==
Der '''Simplexalgorithmus''' ist ein '''numerisches Verfahren''' zur Lösung '''linearer Optimierungsprobleme''' mit mehr als zwei 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 ersetzt die grafische Lösung durch eine '''systematische Verbesserung von Eckpunkten''' des zulässigen Bereichs.


Der Algorithmus wird im Grundkurs zur Lösung von '''Maximierungsproblemen''' verwendet, bei denen:
Für die Anwendung des regulären Simplexalgorithmus müssen zwei Voraussetzungen erfüllt sein:
* alle Nebenbedingungen Ungleichungen vom Typ ≤ sind,
# Die '''Nulllösung''' (alle Problemvariablen sind Null) muss eine zulässige Lösung sein.
* alle Variablen der '''Nichtnegativitätsbedingung''' genügen,
# Es muss sich um ein '''Maximierungsproblem''' handeln.
* eine '''Startlösung (Nullösung)''' existiert.


== Beispiel (Produktionsplanung) ==
== Mathematische Grundlagen und Begriffe ==
In einer Fabrik werden die Produkte '''A''' und '''B''' auf drei Automaten hergestellt.


{| class="wikitable"
=== 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.
! Automat !! Zeit für A (min) !! Zeit für B (min) !! Maximale Nutzungszeit (min)
 
|-
=== Basis- und Nichtbasisvariablen ===
| I || 2 || 4 || 320
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.
| II || 4 || 4 || 400
* Die Schlupfvariablen bilden die erste Basis.
|-
| III || 4 || 2 || 360
|}


Gewinn:
=== Pivot-Element, -Zeile und -Spalte ===
* Produkt A: 9 €
* '''Pivot-Spalte''': Die Spalte der Nichtbasisvariablen, die den größten positiven Beitrag zur Steigerung der Zielgröße \(Z\) liefert.
* Produkt B: 12 €
* '''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.


== Mathematisches Modell ==
== Beispiel: Gewinnmaximum ermitteln ==
=== Entscheidungsvariablen ===
In einer Fabrik werden die Produkte A und B auf den Automaten I, II und III hergestellt.
* <math>x_1</math>: Stückzahl von Produkt A
* <math>x_2</math>: Stückzahl von Produkt B


=== Nebenbedingungen ===
=== 1. Aufstellen des mathematischen Modells ===
<math>
Basierend auf den Bearbeitungszeiten und Kapazitäten ergibt sich folgendes Modell:
\begin{aligned}
2x_1 + 4x_2 &\le 320 \quad &(\text{Automat I})\\
4x_1 + 4x_2 &\le 400 \quad &(\text{Automat II})\\
4x_1 + 2x_2 &\le 360 \quad &(\text{Automat III})\\
x_1, x_2 &\ge 0
\end{aligned}
</math>


=== Zielfunktion ===
'''Variablen:'''
<math>
* \(x_1\): Stückzahl Produkt A (Gewinn: 9 GE/Stück)
Z = 9x_1 + 12x_2 \rightarrow \max
* \(x_2\): Stückzahl Produkt B (Gewinn: 12 GE/Stück)
</math>


== Umformung in ein Gleichungssystem ==
'''Bedingungssystem:'''
Zur Anwendung des Simplexalgorithmus werden '''Schlupfvariablen''' eingeführt:
* 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\)


<math>
'''Zielgleichung:'''
\begin{aligned}
* \(Z = 9x_1 + 12x_2 \rightarrow \text{max!}\)
2x_1 + 4x_2 + u_1 &= 320\\
4x_1 + 4x_2 + u_2 &= 400\\
4x_1 + 2x_2 + u_3 &= 360
\end{aligned}
</math>


* <math>u_1, u_2, u_3</math> beschreiben '''freie Kapazitäten'''
=== 2. Das erste Simplex-Tableau (Startlösung) ===
* Anfangs sind <math>x_1 = x_2 = 0</math> ('''Nullö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:


== Erstes Simplex-Tableau ==
{| class="wikitable" style="text-align:center;"
{| class="wikitable"
! Basis !! \(x_1\) !! \(x_2\) !! \(u_1\) !! \(u_2\) !! \(u_3\) !! r.S. !! Quotient (Engpass)
|-
! Basis !! x₁ !! x₂ !! u₁ !! u₂ !! u₃ !! b
|-
|-
| u₁ || 2 || 4 || 1 || 0 || 0 || 320
| \(u_1\) || 2 || 4 || 1 || 0 || 0 || 320 || \(320:4 = 80\) (Engpass!)
|-
|-
| u₂ || 4 || 4 || 0 || 1 || 0 || 400
| \(u_2\) || 4 || 4 || 0 || 1 || 0 || 400 || \(400:4 = 100\)
|-
|-
| u₃ || 4 || 2 || 0 || 0 || 1 || 360
| \(u_3\) || 4 || 2 || 0 || 0 || 1 || 360 || \(360:2 = 180\)
|-
|-
| Z || -9 || -12 || 0 || 0 || 0 || 0
| style="background:#eee;" | \(Z\) || -9 || -12 || 0 || 0 || 0 || 0 ||
|}
|}
''Anmerkung: Im Tableau werden oft die negativen Koeffizienten der umgeformten Zielgleichung verwendet.''


== Zentrale Begriffe ==
* '''Pivot-Spalte''': \(x_2\) (da 12 > 9).
=== Pivot-Spalte ===
* '''Pivot-Zeile''': 1. Zeile (Automat I), da hier der kleinste Quotient (80) vorliegt.
Die '''Pivot-Spalte''' ist die Spalte mit dem '''stärksten negativen Koeffizienten''' in der Zielfunktionszeile. 
* '''Pivot-Element''': '''4'''.
→ Sie zeigt, welche Variable den Gewinn am stärksten erhöht.


Hier: <math>x_2</math>, da −12 < −9.
=== 3. Zweites Tableau ===
Nach Anwendung des [[Gaußsches Eliminationsverfahren|Gauß-Verfahrens]] (Pivot-Element auf 1 bringen, Rest der Spalte auf 0):


=== Pivot-Zeile (Engpass) ===
{| class="wikitable" style="text-align:center;"
Die '''Pivot-Zeile''' wird durch den '''Minimumquotienten''' bestimmt:
! Basis !! \(x_1\) !! \(x_2\) !! \(u_1\) !! \(u_2\) !! \(u_3\) !! r.S. !! Quotient
<math>
|-
\frac{b}{\text{Koeffizient der Pivot-Spalte}}
| \(x_2\) || 0,5 || 1 || 0,25 || 0 || 0 || 80 || \(80:0,5 = 160\)
</math>
|-
 
| \(u_2\) || 2 || 0 || -1 || 1 || 0 || 80 || \(80:2 = 40\) (Engpass!)
Nur positive Koeffizienten werden berücksichtigt. 
|-
Die Pivot-Zeile beschreibt die '''engste Nebenbedingung''' (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 ||
|}


=== Pivot-Element ===
* Die Lösung ist noch nicht optimal, da in der \(Z\)-Zeile bei \(x_1\) noch ein negativer Wert (-3) steht.
Das '''Pivot-Element''' ist das Element am Schnittpunkt von Pivot-Spalte und Pivot-Zeile. 
* Neue Pivot-Spalte: \(x_1\); Neue Pivot-Zeile: Zeile von \(u_2\) (Quotient 40); Pivot-Element: '''2'''.
Es wird im nächsten Schritt auf 1 normiert.


== Iterationen ==
=== 4. Drittes Tableau (Optimalzustand) ===
Nach sukzessiver Anwendung des Gaußschen Eliminationsverfahrens (vgl. [[Gaußsches Eliminationsverfahren]]) erhält man das optimale Tableau.
Erneute Umformung führt zum Endtableau:


== Optimales Tableau ==
{| class="wikitable" style="text-align:center;"
{| class="wikitable"
! Basis !! \(x_1\) !! \(x_2\) !! \(u_1\) !! \(u_2\) !! \(u_3\) !! r.S.
|-
! Basis !! x₁ !! x₂ !! u₁ !! u₂ !! u₃ !! b
|-
|-
| x₂ || 0 || 1 || 0,5 || -0,25 || 0 || 60
| \(x_2\) || 0 || 1 || 0,5 || -0,25 || 0 || '''60'''
|-
|-
| x₁ || 1 || 0 || -0,5 || 0,5 || 0 || 40
| \(x_1\) || 1 || 0 || -0,5 || 0,5 || 0 || '''40'''
|-
|-
| u₃ || 0 || 0 || 1 || -1,5 || 1 || 80
| \(u_3\) || 0 || 0 || 1 || -1,5 || 1 || '''80'''
|-
|-
| Z || 0 || 0 || -1,5 || -1,5 || 0 || 1080
| style="background:#eee;" | \(Z\) || 0 || 0 || 1,5 || 1,5 || 0 || '''1080'''
|}
|}


== Optimale Lösung ==
=== Interpretation des Ergebnisses ===
* <math>x_1 = 40</math>
Da kein Koeffizient in der Zielgleichungszeile mehr positiv (bzw. bei dieser Tabellenform negativ) ist, wurde das Optimum erreicht:
* <math>x_2 = 60</math>
* Es sollten '''40 Einheiten von Produkt A''' (\(x_1\)) und '''60 Einheiten von Produkt B''' (\(x_2\)) hergestellt werden.
* Maximaler Gewinn:
* Der maximale Gewinn beträgt '''1080 GE'''.
<math>
* Die Automaten I und II sind voll ausgelastet (\(u_1=0, u_2=0\)).
Z = 9 \cdot 40 + 12 \cdot 60 = 1080
* Automat III hat eine **freie Kapazität** von '''80 Minuten''' (\(u_3=80\)).
</math>
 
Automat III besitzt noch 80 Minuten freie Kapazität, Automaten I und II sind ausgelastet.
 
== Einordnung ==
* Der Simplexalgorithmus liefert dasselbe Ergebnis wie die grafische Lösung
* Er ist auf Probleme mit vielen Variablen übertragbar
* Tabellenkalkulationen oder CAS erleichtern die Berechnung
 
== Zusammenhang ==
* Grafische Lösung: [[Eckpunktberechnungsmethode]]
* Lineare Gleichungssysteme: [[Lineares Gleichungssystem]]
* Matrizenrechnung: [[Matrix]]


[[Kategorie:Lineare_Optimierung]]
[[Kategorie:Lineare_Optimierung]]
[[Kategorie:AHR_WuV_Mathe_GK]]
[[Kategorie:AHR_WuV_Mathe_GK]]
Abgerufen von „https://wiki.flbk-hamm.de/Simplexalgorithmus“