Simplexalgorithmus: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Zur Navigation springen Zur Suche springen
Zum nächsten Versionsunterschied →
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.097 Bearbeitungen
VisuellWikitext
Die Seite wurde neu angelegt: „== Definition == Der '''Simplexalgorithmus''' (oder das Simplex-Verfahren) ist ein iteratives numerisches Verfahren zur Lösung von linearen Optimierungsproblemen. Er wird insbesondere dann eingesetzt, wenn mehr als zwei Entscheidungsvariablen vorliegen und eine grafische Lösung nicht mehr möglich ist. == Vorgehensweise == === 1. Aufstellen der Normalform (Schlupfvariablen) === Um die Ungleichungen des Bedingungssystem…“
 
Keine Bearbeitungszusammenfassung
Zeile 1: Zeile 1:
== Definition ==
== 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:Lineare_Optimierung]]
[[Kategorie:AHR_WuV_Mathe_GK]]
[[Kategorie:AHR_WuV_Mathe_GK]]

Version vom 6. Februar 2026, 09:23 Uhr

Definition

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.

Voraussetzungen

  • Lineares Standard-Maximumproblem
  • Nebenbedingungen als Gleichungen
  • Alle Variablen ≥ 0

Schlupfvariablen

Ungleichungen werden durch Schlupfvariablen in Gleichungen überführt:

[math]\displaystyle{ a_1x + a_2y \le b \;\Rightarrow\; a_1x + a_2y + s = b }[/math]

Simplex-Tableau

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

Begriffe

  • Pivot-Spalte: Variable mit größtem Zielfunktionskoeffizienten
  • Pivot-Zeile: Engpass (Minimumquotient)
  • Pivot-Element: Schnittpunkt von Pivot-Zeile und Pivot-Spalte
  • Engpass: begrenzende Nebenbedingung

Algorithmus

1. Aufstellen des Simplex-Tableaus 2. Bestimmung der Pivot-Spalte 3. Bestimmung der Pivot-Zeile 4. Pivotisierung 5. Abbruch, wenn keine Verbesserung möglich ist

Beispiel

Maximiere:

[math]\displaystyle{ Z = 3x + 2y }[/math]

unter:

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

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