Logo

Simplex-Verfahren

Artikel #11976, »Simplex-Verfahren«, geschrieben von: Wolfgang Keller(Red.) (100 %)

Beim Simplex-Verfahren handelt es sich um einen durch Dantzig entwickelten Algorithmus zur Lösung linearer Optimierungsprobleme.

Anzeigen

Obgleich sie im Gegensatz zu Elipsoid-Methode und Innere-Punkte-Verfahren im Worst-Case einen exponentiellen Aufwand besitzt, so wird sie doch häufig in der Praxis sehr häufig eingesetzt, da sie in der Praxis häufig deutlich schneller als die - im wesentlichen theoretisch interessante - Ellipsoid-Methode ist.

Der Vorteil gegenüber den Innere-Punkte-Verfahren liegt in besonderem Maße darin, dass nach bisherigen Erkenntnissen beim Simplex-Verfahren zusätzliche Nebenbedingungen sehr einfach nachträglich eingeführt werden können ohne den Algorithmus von Grunde auf neu berechnen zu lassen.

Dieses Merkmal ist besonders für Branch-and-Bound-Verfahren, sowie Branch-and-Cut-Verfahren zur Lösung ganzzaliger Optimierungsprobleme von hoher praktischer Wichtigkeit.

Anzeigen