Lösen mit der Simplexmethode

Die Simplexmethode ist ein allgemeiner Ansatz zur Lösung mehrdimensionaler linearer Optimierungsaufgaben. Ähnlich wie beim Gauss'schen Eliminationsalgorithmus wird auch hier eine Pivotisierung vorgenommen, die der geometrischen Operation der Bewegung von einem Eckpunkt des zulässigen Bereichs zu einem anderen entspricht, auf der Suche nach einer Lösung unter Verbesserung des Zielfunktionswertes.

Der Name der Simplexmethode entspringt der Bezeichnung des zulässigen Bereichs als Simplex, die Methode wurde anfang der 50er Jahre von Kantorowitsch entwickelt.

Das Verfahren beruht auf der Tatsache der Konvexität linearer Optimierungsprobleme. Damit ist gegeben, dass die Zielfunktion einen optimalen Wert in einem Eckpunkt des zulässigen Bereichs annimmt.

Um die Simplexmethode auf lineare Optimierungsprobleme anwenden zu können, müssen diese erst in eine standardisierte Form überführt werden, in die Zweite Normalform eines linearen Optimierungsproblems. Dies erreicht man unter anderem durch Durchsetzung der Nichtnegativität, durch Einführung von Schlupfvariablen und weitere Umformungen. Mitunter kann es dadurch zu einer gewaltigen Aufblähung des Problems kommen. Unter gewissen Voraussetzungen, z.B. der Beschränktheit des zulässigen Bereichs, ist die Simplexmethode jedoch sehr leistungsfähig.

Aufgrund ihrer algorithmischen Struktur gibt es einfach verständliche Rechnerimplementationen der Simplexmethode, worauf hier jedoch nicht weiter eingegangen werden soll.