Simplex-Verfahren

Das Simplex-Verfahren (auch Simplex-Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer Optimierungsprobleme. Es löst ein solches Problem nach endlich vielen Schritten exakt oder stellt dessen Unlösbarkeit oder Unbeschränktheit fest. Die Grundidee des Simplex-Verfahrens wurde 1947 von George Dantzig vorgestellt. Seitdem hat es sich durch zahlreiche Verbesserungen zum wichtigsten Lösungsverfahren der linearen Optimierung in der Praxis entwickelt. Das Simplex-Verfahren ist ein Pivotverfahren.

Obwohl bisher für jede Variante des Verfahrens ein Beispiel konstruiert werden konnte, bei dem der Algorithmus exponentielle Laufzeit benötigt, läuft der Simplex-Algorithmus in der Praxis meist schneller als andere Verfahren. Zwar gibt es zur Lösung einzelner linearer Programme auch andere konkurrenzfähige Methoden, z. B. Innere-Punkte-Verfahren. Der große Vorteil des Simplex-Algorithmus liegt jedoch darin, dass er bei leichter Veränderung des Problems - beispielsweise dem Hinzufügen einer zusätzlichen Bedingung - einen "Warmstart" von der letzten verwendeten Lösung durchführen kann und daher meist nur wenige Iterationen zur erneuten Lösung benötigt, während andere Verfahren von vorne beginnen müssen. Darüber hinaus nutzt das Simplex-Verfahren die engen Zusammenhänge zwischen einem linearen Programm (LP) und seinem dualen LP aus und löst grundsätzlich beide Probleme gleichzeitig. Beide Eigenschaften sind in der nichtlinearen oder ganzzahligen linearen Optimierung von Bedeutung, wo sehr viele ähnliche LPs in Folge gelöst werden müssen.

Die geometrische Grundidee des Algorithmus besteht darin, von einer beliebigen Ecke des Polyeders, das durch das lineare Programm definiert wird, entlang seiner Kanten zu einer optimalen Ecke zu laufen. Der Name des Verfahrens rührt daher, dass die nichtnegativen Linearkombinationen der Basisspalten in jeder Iteration einen simplizialen Kegel beschreiben. Ein Namensvetter dieses Verfahrens namens Downhill-Simplex-Verfahren (Nelder und Mead 1965) basiert ebenfalls auf einem Simplex, ist aber ein iteratives Verfahren zur nichtlinearen Optimierung.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Simplex-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren