Simplex-Verfahren: Eckenwandern zur optimalen Lösung

Das Simplex-Verfahren ist der klassische Algorithmus der Linearen Optimierung. George Dantzig entwickelte es 1947, um lineare Optimierungsprobleme — also eine lineare Zielfunktion unter linearen Nebenbedingungen — effizient zu lösen. Bis heute ist es das meistverwendete Verfahren für diese Problemklasse.

Die Grundidee

Ein lineares Optimierungsproblem hat die Form

maximiere c · x
unter  A · x ≤ b,  x ≥ 0

Die Nebenbedingungen begrenzen den zulässigen Bereich zu einem konvexen Polyeder (Polytop). Eine zentrale Erkenntnis der linearen Optimierung: Wenn eine optimale Lösung existiert, dann liegt sie in einer Ecke des Polytops. Das Simplex-Verfahren nutzt das aus, indem es von Ecke zu Ecke wandert.

Ablauf des Verfahrens

  1. Startecke finden: Eine zulässige Ecke wird als Ausgangspunkt bestimmt, zum Beispiel durch Einführen von Schlupfvariablen.
  2. Pivot-Schritt: Das Verfahren prüft, ob eine benachbarte Ecke über eine Kante einen besseren Zielfunktionswert liefert. Ist das der Fall, wechselt es dorthin.
  3. Abbruchkriterium: Gibt es keine benachbarte Ecke mehr mit besserem Zielfunktionswert, ist die aktuelle Ecke optimal.

Rechnerisch arbeitet das Verfahren mit einem Tableau aus Gleichungen; die Schlupfvariablen machen aus Ungleichungen Gleichungen. Die Bewegung ist damit verwandt mit der lokalen Suche des Hill-Climbing — mit dem entscheidenden Unterschied, dass das Simplex-Verfahren bei linearen Problemen das globale Optimum garantiert findet.

Laufzeit und Alternativen

Im worst case ist das Simplex-Verfahren exponentiell langsam — es gibt konstruierte Beispiele, in denen es viele Ecken durchläuft. In der Praxis ist es jedoch außergewöhnlich schnell. Für eine garantiert polynomiale Laufzeit existieren seit 1984 die Inneren-Punkte-Verfahren, die sich dem Optimum durch das Innere des Polytops nähern statt über Ecken zu wandern.

Wichtig für die Einordnung: Das lineare Optimierungsproblem selbst ist polynomial lösbar. Wird dagegen Ganzzahligkeit verlangt (ganzzahlige Lineare Optimierung), wird das Problem NP-vollständig und das Simplex-Verfahren nicht mehr direkt anwendbar.

Anwendungen

  • Produktionsplanung: optimale Mischung von Rohstoffen und Maschinenkapazitäten
  • Transport- und Zuordnungsprobleme in der Logistik
  • Mischungsprobleme (etwa Futter- oder Kraftstoffmischungen)
  • Netzwerkfluss- und Planungsprobleme

Verwandte Begriffe