Die Regeln des Simplexalgorithmuses zu beherrschen ist gut. An dieser Stelle wird die dahinter stehende Idee genauer erläutert und die Regeln werden kritisch hinterfragt.

Auswahl der Pivotzeile im Detail

Steilster Anstieg (Steepest Ascent)

Über die bekannte Auswahlregel der Pivotspalte wird sichergestellt, dass der Zielwert steigt, und zwar möglichst schnell.

Sicher ist, dass der Zielwert steigt, wenn man eine Spalte mit negativen Koeffizienten wählt. Dass man am schnellsten zum Optimum gelangt, wenn man den kleinsten Koeffizienten wählt, ist aber nur eine plausible Verfahrens­anweisung, die sich in der Praxis als sinnvoll erwiesen hat und mit wenig Arbeit verbunden ist.

Beliebiger negativer Koeffizient

Ebenso würde man früher oder später das Optimum auffinden, wenn man eine beliebige Spalte mit negativem Koeffizient auswählt. Dann hätte man sich das Durchsehen der gesamten Zielzeile gespart und müsste dafür durchschnittlich ein paar mehr Iterationen rechnen. Vergleicht man den gesparten Aufwand bei der Auswahl der Pivotspalte mit dem Aufwand zur Berechnung der zusätzlichen Tableaus wird schnell klar, dass es keine gute Idee ist.

Größte Zielwertveränderung (Greatest Change)

Ebenso könnte man noch weitere Berechnungen vor der Auswahl der Pivot spalte anstellen. Zum Beispiel könnte man die Spalte auswählen, bei der sich im nächsten Schritt der Ziel wert größt­möglich verbessert.

Dazu muss für jede Spalte mit negativem Ziel­zeilen­koeffizienten die sich bei Wahl dieser Spalte ergebende Pivotzeile gesucht werden und aus gerechnet werden, wie stark der Zielwert steigen würde:

Dank des zusätzlichen Aufwands für die Beschaffung von Informationen bei der Auswahl des Pivot­elements könnten vermutlich im Durchschnitt einige Iterationen eingespart werden. Dass das Optimum über diese Strategie am schnellsten erreicht wird, ist aber auch nicht sicher.

Im Detail, die Auswahl der Pivotzeile

Grundidee des Simplexalgorithmuses ist, dass der zulässige Bereich, wenn er einmal erreicht ist, nicht mehr verlassen wird. Das wird über die Auswahl der Pivotzeile sichergestellt. Ein Verstoß gegen diese Regel ist ein gravierender Verstoß gegen die Prinzipien des Simplexalgorithmuses und das Optimum wird nie oder bestenfalls zufällig gefunden.

Natürlich könnte man vorübergehend Unzulässigkeiten akzeptieren und am Ende wieder eine 1. Phase anschließen. Dabei würde aber das optimale Ergebnis verloren gehen was eine erneute 2. Phase erforderlich macht und so weiter. Das ganze Verfahren würde unsystematisch werden.

Es ist aber möglich, die Phasen konsequent zu vertauschen. Die Umsetzung ist allerdings etwas komplizierter. Stichwort hierzu ist „Lösen des Dualen Problems“, auf eine Beschreibung an dieser Stelle wird verzichtet.

Der schnellste Weg bei bekannter Lösung

Wenn schon bekannt ist, welche Variablen in der Basis der optimalen Lösung sind, kann mit vergleichsweise wenigen Basistäuschen die gewünschte Basislösung hergestellt werden. Besonders elegant ist, dass sich das Ganze auf das Bilden einer Inverse und eine Matrixmultiplikation reduziert aufschreiben lässt.

Dieser schnellste Weg führt möglicherweise durch unzulässige Bereiche oder der Zielwert verschlechtert sich eventuell zwischenzeitlich.

Der Simplexalgorithmus ist ein Verfahren zum Auffinden der optimalen Lösung. Ist diese schon bekannt, braucht er nicht angewendet werden und es ist empfehlenswert den direkten Weg zu gehen.

Vorzeitiger Abbruch der Rechnung

Sobald die 1. Phase abgeschlossen ist, liegt bekanntlich eine zulässige Lösung vor und alle nach&sbsp;folgenden Lösungen sind ebenfalls zulässig. Wenn aus Zeitmangel oder welchen Gründen auch immer die Rechnung abgebrochen wird, bevor das Optimum aufgefunden wurde, kann die bis dahin vorliegende Lösung verwendet werden.

Da bei jeder Iteration eine Verbesserung des Zielwerts stattfindet, ist die gefundene Lösung auch eine gute Lösung und die Mühen, die bisher in die Optimierung gesteckt wurden, waren nicht vergeblich. Es gibt sogar Verfahren, die allerdings auch mit etwas Aufwand verbunden sind, mit denen ein Höchstwert für den Abstand der aktuell gefundenen Lösung zur optimalen Lösung angeben werden kann.