Lineare Programmierung & Simplex
Maximiere cT x unter Ax ≤ b, x ≥ 0. Zielfunktion und Restriktionen sind alle linear.
Geometrische Anschauung
Die zulässige Menge ist ein konvexes Polyeder. Das Optimum liegt immer in einer Ecke. Simplex wandert von Ecke zu Ecke entlang verbessernder Kanten.
Simplex-Schritt
- Wähle eine Startecke (Basislösung).
- Berechne reduzierte Kosten — gibt es eine verbessernde Richtung?
- Wenn ja: Tausche eine Variable in die Basis (Pivot).
- Wiederhole, bis keine Verbesserung mehr möglich ist.
Beispiel — Produktion
Max 3x₁ + 2x₂ unter 2x₁ + x₂ ≤ 10, x₁ + 3x₂ ≤ 15, x₁, x₂ ≥ 0.
Ecken: (0, 0), (5, 0), (3, 4), (0, 5). Werte: 0, 15, 17, 10. Optimum (3, 4) mit Wert 17.
Worst Case SimplexTheoretisch exponentiell viele Schritte — praktisch fast immer linear in n+m. Für riesige Probleme: Innere-Punkte-Verfahren mit polynomialer Garantie.