Simplexmethode

Siehe
>>> Simplex-Methode.

auch Simplex-Algorithmus, mathematisches Lösungsverfahren von Problemen der linearen Programmierung. Dabei geht man von der Zielfunktion aus, unter der Annahme, daß die Restriktionen nicht von einander abhängig sind und sich nicht widersprechen. Weiterhin kann vorausgesetzt werden, daß die Zahl der Restriktionen kleiner ist als die Zahl der Variablen. Der Wert der Zielfunktion ist zu maximieren bzw. zu minimieren.

Das Universalverfahren der linearen Programmierung ist die von Dantzig entwickelte Simplexmethode. Die Simplexmethode verdankt ihren Namen dem Aussehen des Polyeders, der die optimale Lösung enthält. Das Simplexverfahren ist dadurch gekennzeichnet, daß es die optimale Lösung schrittweise, also in Iterationen, sucht, indem es, ausgehend von der Nullösung, am Rand des Polyeders von Eckpunkt zu Eckpunkt fortschreitet, bis die beste Lösung gefunden ist. Die Simplexmethode baut auf Verfahren zur Lösung linearer Gleichungssysteme auf, die in Matrizenform dargestellt und durch Simplexregeln umgeformt werden.

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.

<< vorhergehender Begriff

nächster Begriff >>

Simplexkriterium

Simplexregel