L5 Bemerkungen

In den vorangegangenen Kapiteln wurde der Simplexalgorithmus beschrieben. In diesem Kapitel werden abschließend noch einige ergänzende Aspekte beleuchtet. Zunächst wird die Idee des Simplex algorithmuses anhand der Analogie einer Wanderung durch eine Welt mit durchaus einigen Besonderheiten beschrieben. Darauf folgen eine Diskussion der Auswahlregeln und schließlich noch eine Erörterung, warum bei Linearen Problemen ein lokales Optimum immer auch ein globales Optimum ist. Zu guter Letzt wird der Frage nachgegangen, mit welchem Aufwand das Lösen von Problemen mit dem Simplexalgorithmus verbunden ist.

Eine Analogie: Wanderung durch die lineare Welt

Man kann das Vorgehen bei der Optimierung als „Weg auf den Gipfel eines Berges“ betrachten. Die Wahl des Pivotelements ist die Entscheidung für einen bestimmten Weg zur nächsten Kreuzung. So kommt man von Basislösung zu Basislösung, in dem Sinnbild von Kreuzung zu Kreuzung. Ein Teil der Kreuzungen liegt allerdings auf verbotenem Gelände.

Zu Beginn ist man möglicherweise auf einem verbotenen Teil des Wegenetzes. In der 1. Phase wird versucht, so schnell wie möglich auf erlaubtes Gebiet zu gelangen.

An jeder Kreuzung ist in Form des Zielzeilenkoeffizienten eine Information gegeben, welche Steigung der nächste Wegabschnitt hat. Allerdings gibt es keine Information, bis auf welche Höhe der nächste Wegabschnitt führt.

Es wird immer der Weg mit der steilsten Steigung gewählt. Dass die nächste Kreuzung diejenige mit dem höchsten Zugewinn an Höhenmetern ist, ist aber keineswegs klar. Der Weg kann kurz und steil sein, während ein anderer flacherer aber länger ist und die nächste Kreuzung auf einem höheren Niveau liegt. Schließlich wird der Gipfel erreicht, dort führen alle Wege nur noch nach unten.

Dazu sollte man sagen, dass das Gelände eine recht spezielle Topografie hat. Es gibt nur einen Gipfel. Das heißt, nach oben gehen ist immer richtig und es gibt auch keine Sackgassen. Ist ein Punkt erreicht, an dem alle Wege nur noch nach unten führen, muss der Gipfel erreicht sein.

Bezüglich der Wanderung gibt es noch einige Besonderheiten. Einem eingeschlagenen Weg wird konsequent bis zur nächsten Kreuzung gefolgt. Es wird auch nicht querfeldein gegangen, selbst wenn es erlaubt ist.