Simplexalgorithmus

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

• Grafische Lösung: Eckpunktberechnungsmethode
• Lineare Gleichungssysteme: Gaußsches Eliminationsverfahren