Simplexmethode

Die Simplexmethode dient in ihrer ursprünglichen Form (reguläre Simplexmethode) als Verfahren zur Lösung von linearen Optimierungsmodellen, die aus einer zu maximierenden linearen Zielfunktion und einem Block linearer Nebenbedingungen (estriktionen) sowie Nichtnegativitätsbedingungen für die Problemvariablen (x) bestehen (vgl. beispielsweise die Problemstellung der Produktionsprogrammplanung; Operations Research). Das System der Nebenbedingungen (Gleichungssystem mit sog. Schlupfvariablen) wird ebenso wie die Zielfunktion in ein Simplextableau überführt, in dessen Randspalte sich der aktuelle Lösungswert der am Kopf der Zeile stehenden Basisvariablen sowie in der letzten Zeile der Zielfunktionswert ablesen lassen. Innerhalb des Tableaus sind die Restriktionskoeffizienten (a,) der jeweils am Kopf der Spalte stehenden Variablen abzulesen, und die letzte Zeile (Zielzeile) enthält die jeweiligen Zielfunktionskoeffizienten (c). Nachfolgend ist die Struktur eines solchen Ausgangstableaus dargestellt:

Mit Hilfe sog. Basistransformationen werden beginnend mit dem oben aufgeführten Ausgangstableau im Laufe des Verfahrens verschiedene Lösungen erzeugt, die dadurch gekennzeichnet sind, dass sie aus J Basisvariablen bestehen und sich ihr Zielfunktionswert im Laufe der Iterationen nicht verschlechtert. Lässt sich keine Lösung mehr finden, die einen besseren Ziel funktionswert aufweist, so ist die Optimallösung erreicht, und das Verfahren ist beendet. Im Optimaltableau enthält die Zielzeile, in der negative Elemente auf eine Möglichkeit der Verbesserung hindeuten, nur Werte größer oder gleich null, und der Zielfunktionswert ist maximal. Veranschaulicht man sich die Vorgehensweise anhand einer Graphik, so werden im Rahmen der Simplexmethode ausgehend vom Ursprung des Koordinatenkreuzes Eckpunkte des Beschränkungspolyeders, der durch die Restriktionen festgelegt wird, auf ihre Optimalität untersucht, und nach jeder neuen Tableautransformation ist ein besserer Eckpunkt erreicht. Für mögliche Sonderfälle, wie Degeneration, Mehrdeutigkeit, Unzulässigkeit des Nullpunktes, Ganzzahligkeit der Problemvariablen u. Ä., sind Vorgehensweisen im Rahmen der Simplexmethode, Modifikationen des Verfahrens (z. B. Zwei Phasen implexmethode) oder sogar neue Verfahren, die die Simplexmethode als Ausgangspunkt verwenden (Verfahren von Dakin oder Gomory), entwickelt worden, so dass dieses Verfahren der linearen Optimierung einen zentralen Lösungsansatz darstellt. Darüber hinaus lässt sich bei weiter gehenden Fragestellungen wie denen von Sensitivitätsanalysen auf den Ergebnissen der Simplexmethode aufbauen.