Simplexalgorithmus: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Zur Navigation springen Zur Suche springen
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.097 Bearbeitungen
VisuellWikitext
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Zeile 1: Zeile 1:
= Simplexalgorithmus =
== Definition ==
== 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}
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>


== Algorithmus ==
=== Zielfunktion ===
1. Aufstellen des Simplex-Tableaus
<math>
2. Bestimmung der Pivot-Spalte
Z = 9x_1 + 12x_2 \rightarrow \max
3. Bestimmung der Pivot-Zeile
</math>
4. Pivotisierung
5. 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}
\begin{aligned}
x + y &\le 4\\
2x_1 + 4x_2 + u_1 &= 320\\
2x + y &\le 5\\
4x_1 + 4x_2 + u_2 &= 400\\
x,y &\ge 0
4x_1 + 2x_2 + u_3 &= 360
\end{aligned}
\end{aligned}
</math>
</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 ==
== Zusammenhang ==
* Grafische Lösung: [[Eckpunktberechnungsmethode]]
* Grafische Lösung: [[Eckpunktberechnungsmethode]]
* Lineare Gleichungssysteme: [[Gaußsches Eliminationsverfahren]]
* Lineare Gleichungssysteme: [[Lineares Gleichungssystem]]
* Matrizenrechnung: [[Matrix]]


[[Kategorie:Lineare_Optimierung]]
[[Kategorie:Lineare_Optimierung]]
[[Kategorie:AHR_WuV_Mathe_GK]]
[[Kategorie:AHR_WuV_Mathe_GK]]

Version vom 6. Februar 2026, 09:58 Uhr

Simplexalgorithmus

Definition

Der Simplexalgorithmus ist ein numerisches Verfahren zur Lösung linearer Optimierungsprobleme mit mehr als zwei Variablen. 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:

  • alle Nebenbedingungen Ungleichungen vom Typ ≤ sind,
  • alle Variablen der Nichtnegativitätsbedingung genügen,
  • eine Startlösung (Nullösung) existiert.

Beispiel (Produktionsplanung)

In einer Fabrik werden die Produkte A und B auf drei Automaten hergestellt.

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

Gewinn:

  • Produkt A: 9 €
  • Produkt B: 12 €

Mathematisches Modell

Entscheidungsvariablen

  • [math]\displaystyle{ x_1 }[/math]: Stückzahl von Produkt A
  • [math]\displaystyle{ x_2 }[/math]: Stückzahl von Produkt B

Nebenbedingungen

[math]\displaystyle{ \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

[math]\displaystyle{ Z = 9x_1 + 12x_2 \rightarrow \max }[/math]

Umformung in ein Gleichungssystem

Zur Anwendung des Simplexalgorithmus werden Schlupfvariablen eingeführt:

[math]\displaystyle{ \begin{aligned} 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]\displaystyle{ u_1, u_2, u_3 }[/math] beschreiben freie Kapazitäten
  • Anfangs sind [math]\displaystyle{ x_1 = x_2 = 0 }[/math] (Nullösung)

Erstes Simplex-Tableau

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]\displaystyle{ x_2 }[/math], da −12 < −9.

Pivot-Zeile (Engpass)

Die Pivot-Zeile wird durch den Minimumquotienten bestimmt: [math]\displaystyle{ \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

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]\displaystyle{ x_1 = 40 }[/math]
  • [math]\displaystyle{ x_2 = 60 }[/math]
  • Maximaler Gewinn:

[math]\displaystyle{ Z = 9 \cdot 40 + 12 \cdot 60 = 1080 }[/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

Abgerufen von „https://wiki.flbk-hamm.de/index.php?title=Simplexalgorithmus&oldid=2667“