Simplex-Verfahren

Ein Simplex-Verfahren (auch Simplex-Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer Optimierungsprobleme, auch als Lineare Programme (LP) bezeichnet. Es löst ein solches Problem nach endlich vielen Schritten exakt oder stellt dessen Unlösbarkeit oder Unbeschränktheit fest. Die Grundidee der Simplex-Verfahren wurde 1947 von George Dantzig vorgestellt; seitdem haben sie sich durch zahlreiche Verbesserungen zu den wichtigsten Lösungsverfahren der linearen Optimierung in der Praxis entwickelt. Simplex-Verfahren sind Pivotverfahren.

Obwohl bisher für jede Variante des Verfahrens ein Beispiel konstruiert werden konnte, bei dem der Algorithmus exponentielle Laufzeit benötigt, läuft ein Simplex-Algorithmus in der Praxis meist schneller als andere Verfahren, obwohl es zur Lösung einzelner linearer Programme auch andere konkurrenzfähige Methoden gibt, wie z. B. Innere-Punkte-Verfahren. Der große Vorteil eines 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 ein Simplex-Verfahren die engen Zusammenhänge zwischen einer linearen Optimierungsaufgabe und seiner dualen Aufgabe aus und löst grundsätzlich beide Probleme gleichzeitig. Beide Eigenschaften sind in der ganzzahligen linearen oder auch nichtlinearen Optimierung dort von Bedeutung, wo sehr viele ähnliche lineare Aufgaben in Folge gelöst werden müssen.

Die geometrische Grundidee des Algorithmus besteht darin, von einer beliebigen Ecke eines Polytops, das durch die lineare Optimierungsaufgabe 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^[1]) basiert ebenfalls auf einem Simplex, ist aber ein iteratives Verfahren zur nichtlinearen Optimierung.

1. ↑ John A. Nelder & R. Mead: A simplex method for function minimization. In: Computer Journal. Band 7, 1965, S. 308–313, doi:10.1093/comjnl/7.4.308.