Die Simplex-Methode ist ein klassisches Verfahren der linearen Optimierung. Gegeben sind eine lineare Zielfunktion und lineare Nebenbedingungen. Gesucht wird eine zulässige Lösung, die den Zielfunktionswert maximiert oder minimiert.

Bei einer üblichen geometrischen Interpretation liegt ein Optimum – sofern es existiert – an einer Ecke des zulässigen Bereichs. Das Simplex-Verfahren untersucht nicht einfach sämtliche Ecken, sondern bewegt sich nach festgelegten Pivotregeln von einer zulässigen Basislösung zu einer benachbarten, besseren Lösung, bis ein Abbruchkriterium erfüllt ist.

Der zulässige Bereich kann leer oder unbeschränkt sein; dann gibt es keine endliche optimale Lösung. In degenerierten Fällen können Pivotregeln wichtig sein, um Zyklen zu vermeiden. Die Simplex-Methode ist in der Praxis oft effizient, besitzt aber im ungünstigsten Fall exponentielle Laufzeit.

Quellen und Prüfstand

Inhaltlich überarbeitet am 2026-10-13. Algorithmus, Voraussetzungen und Laufzeitgrenze präzisiert.