Simplexalgorithmus: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

VisuellWikitext

@@ Zeile 1: / Zeile 1: @@
+= Simplexalgorithmus =
 == Definition ==
-Der '''Simplexalgorithmus''' ist ein numerisches Verfahren zur Lösung '''linearer Optimierungsprobleme''' mit mehreren Variablen.
+Der '''Simplexalgorithmus''' ist ein '''numerisches Verfahren''' zur Lösung '''linearer Optimierungsprobleme''' mit mehr als zwei Variablen.
-Er eignet sich insbesondere für Probleme im '''ℝ³ oder höher'''.
+Er ersetzt die grafische Lösung durch eine '''systematische Verbesserung von Eckpunkten''' des zulässigen Bereichs.
-== Voraussetzungen ==
+Der Algorithmus wird im Grundkurs zur Lösung von '''Maximierungsproblemen''' verwendet, bei denen:
-* Lineares Standard-Maximumproblem
+* alle Nebenbedingungen Ungleichungen vom Typ ≤ sind,
-* Nebenbedingungen als Gleichungen
+* alle Variablen der '''Nichtnegativitätsbedingung''' genügen,
-* Alle Variablen ≥ 0
+* eine '''Startlösung (Nullösung)''' existiert.
-== Schlupfvariablen ==
+== Beispiel (Produktionsplanung) ==
-Ungleichungen werden durch '''Schlupfvariablen''' in Gleichungen überführt:
+In einer Fabrik werden die Produkte '''A''' und '''B''' auf drei Automaten hergestellt.
-:<math>a_1x + a_2y \le b \;\Rightarrow\; a_1x + a_2y + s = b</math>
-== Simplex-Tableau ==
+{| class="wikitable"
-Das Optimierungsproblem wird in Tabellenform dargestellt (vgl. [[Matrix]]).
+|-
+! Automat !! Zeit für A (min) !! Zeit für B (min) !! Maximale Nutzungszeit (min)
+|-
+| I || 2 || 4 || 320
+|-
+| II || 4 || 4 || 400
+|-
+| III || 4 || 2 || 360
+|}
-=== Begriffe ===
+Gewinn:
-* '''Pivot-Spalte''': Variable mit größtem Zielfunktionskoeffizienten
+* Produkt A: 9 €
-* '''Pivot-Zeile''': Engpass (Minimumquotient)
+* Produkt B: 12 €
-* '''Pivot-Element''': Schnittpunkt von Pivot-Zeile und Pivot-Spalte
-* '''Engpass''': begrenzende Nebenbedingung
+== Mathematisches Modell ==
+=== Entscheidungsvariablen ===
+* <math>x_1</math>: Stückzahl von Produkt A
+* <math>x_2</math>: Stückzahl von Produkt B
+=== Nebenbedingungen ===
+<math>
+\begin{aligned}
+x_1 + 4x_2 &\le 320 \quad &(\text{Automat I})\\
+x_1 + 4x_2 &\le 400 \quad &(\text{Automat II})\\
+x_1 + 2x_2 &\le 360 \quad &(\text{Automat III})\\
+x_1, x_2 &\ge 0
+\end{aligned}
+</math>
-== Algorithmus ==
+=== Zielfunktion ===
-. Aufstellen des Simplex-Tableaus
+<math>
-. Bestimmung der Pivot-Spalte
+Z = 9x_1 + 12x_2 \rightarrow \max
-. Bestimmung der Pivot-Zeile
+</math>
-. Pivotisierung
-. Abbruch, wenn keine Verbesserung möglich ist
-== Beispiel ==
+== Umformung in ein Gleichungssystem ==
-Maximiere:
+Zur Anwendung des Simplexalgorithmus werden '''Schlupfvariablen''' eingeführt:
-:<math>Z = 3x + 2y</math>
-unter:
+<math>
-:<math>
 \begin{aligned}
-x + y &\le 4\\
+x_1 + 4x_2 + u_1 &= 320\\
-x + y &\le 5\\
+x_1 + 4x_2 + u_2 &= 400\\
-x,y &\ge 0
+x_1 + 2x_2 + u_3 &= 360
 \end{aligned}
 </math>
-Nach Einführung der Schlupfvariablen entsteht ein Simplex-Tableau, aus dem iterativ die optimale Lösung abgelesen wird.
+* <math>u_1, u_2, u_3</math> beschreiben '''freie Kapazitäten'''
+* Anfangs sind <math>x_1 = x_2 = 0</math> ('''Nullösung''')
+== Erstes Simplex-Tableau ==
+{| class="wikitable"
+|-
+! Basis !! x₁ !! x₂ !! u₁ !! u₂ !! u₃ !! b
+|-
+| u₁ || 2 || 4 || 1 || 0 || 0 || 320
+|-
+| u₂ || 4 || 4 || 0 || 1 || 0 || 400
+|-
+| u₃ || 4 || 2 || 0 || 0 || 1 || 360
+|-
+| Z || -9 || -12 || 0 || 0 || 0 || 0
+|}
+== Zentrale Begriffe ==
+=== Pivot-Spalte ===
+Die '''Pivot-Spalte''' ist die Spalte mit dem '''stärksten negativen Koeffizienten''' in der Zielfunktionszeile.
+→ Sie zeigt, welche Variable den Gewinn am stärksten erhöht.
+Hier: <math>x_2</math>, da −12 < −9.
+=== Pivot-Zeile (Engpass) ===
+Die '''Pivot-Zeile''' wird durch den '''Minimumquotienten''' bestimmt:
+<math>
+\frac{b}{\text{Koeffizient der Pivot-Spalte}}
+</math>
+Nur positive Koeffizienten werden berücksichtigt.
+Die Pivot-Zeile beschreibt die '''engste Nebenbedingung''' (Engpass).
+=== Pivot-Element ===
+Das '''Pivot-Element''' ist das Element am Schnittpunkt von Pivot-Spalte und Pivot-Zeile.
+Es wird im nächsten Schritt auf 1 normiert.
+== Iterationen ==
+Nach sukzessiver Anwendung des Gaußschen Eliminationsverfahrens (vgl. [[Gaußsches Eliminationsverfahren]]) erhält man das optimale Tableau.
+== Optimales Tableau ==
+{| class="wikitable"
+|-
+! Basis !! x₁ !! x₂ !! u₁ !! u₂ !! u₃ !! b
+|-
+| x₂ || 0 || 1 || 0,5 || -0,25 || 0 || 60
+|-
+| x₁ || 1 || 0 || -0,5 || 0,5 || 0 || 40
+|-
+| u₃ || 0 || 0 || 1 || -1,5 || 1 || 80
+|-
+| Z || 0 || 0 || -1,5 || -1,5 || 0 || 1080
+|}
+== Optimale Lösung ==
+* <math>x_1 = 40</math>
+* <math>x_2 = 60</math>
+* Maximaler Gewinn:
+<math>
+Z = 9 \cdot 40 + 12 \cdot 60 = 1080
+</math>
+Automat III besitzt noch 80 Minuten freie Kapazität, Automaten I und II sind ausgelastet.
-== Hilfsmittel ==
+== Einordnung ==
-* CAS
+* Der Simplexalgorithmus liefert dasselbe Ergebnis wie die grafische Lösung
-* Tabellenkalkulation (z. B. Excel)
+* Er ist auf Probleme mit vielen Variablen übertragbar
+* Tabellenkalkulationen oder CAS erleichtern die Berechnung
 == Zusammenhang ==
 * Grafische Lösung: [[Eckpunktberechnungsmethode]]
-* Lineare Gleichungssysteme: [[Gaußsches Eliminationsverfahren]]
+* Lineare Gleichungssysteme: [[Lineares Gleichungssystem]]
+* Matrizenrechnung: [[Matrix]]
 [[Kategorie:Lineare_Optimierung]]
 [[Kategorie:AHR_WuV_Mathe_GK]]