Beispiel: Revidierter Simplex-Algorithmus

Das Optimierungsproblem aus dem Abschnitt Beispiel: Vielzahl an beschränkten Variablen, welches mit dem Algorithmus für die oberen Schranken gelöst worden ist, kann auch einfach und schnell mit dem revidierten Simplexalgorithmus gelöst werden. 

Gegeben sei das folgende Optimierungsproblem:

   max!

u.d.N.

Die Anzahl der Nebenbedingungen ist größer als die Anzahl der Variablen. Der primale Simplexalgorithmus kann hier natürlich auch angewandt werden, allerdings würde die Bestimmung der optimalen Lösung sehr rechenaufwendig sein. Mittels des Algorithmus der oberen Schranken ist das Problem bereits im oben genannten Abschnitt bestimmt worden. Es soll nun der revidierte Simplex-Algorithmus angewandt werden, um das Problem zu lösen. 

Das Problem wird zunächst auf die Normalform gebracht, indem die Schlupfvariablen eingefügt werden:

   max!

u.d.N.

Vorgehensweise revidierte Simplexmethode

Bevor mit der Berechnung begonnen wird, werden die Koeffizienten in Matrizen geschrieben und die Basis- und Nichtbasisvariablen wie folgt festgelegt:

Es werden ebenfalls die Schlupvariablen in den Matrizen mitberücksichtigt. In die Zielfunktion gehen diese mit dem Wert null ein, weshalb dort für alle 6 Schlupfvariablen am Ende eine Null steht.

Es wird nun die Matrix (nur Werte der Nebenbedingungen der Basisvariablen bis plus Einheitsvektor) aufgestellt:

Zu Beginn sind die Basisvariablen die Schlupfvariablen bis . Es werden alle Werte der Nebenbedingungen für die Basisvariablen, ohne die rechte Seite berücksichtigt. Die Zielfunktionswerte für die Basisvariablen werden in die letzte Zeile der Matrix geschrieben. Für die Basisvariablen sind die Zielfunktionswerte alle Null. Außerdem wird noch ein Einheitsvektor (mit der in der letzten Zeile) berücksichtigt.

Die Matrix (nur Werte der Nichtbasisvariablen) wird ebenfalls benötigt:

Zu Beginn sind die Nichtbasisvariablen die Variablen der Zielfunktion , , und a_2bx_8NNx_{10}$:

Da sich verändert hat, muss die Inverse neu berechnet werden:

5. Iteration

1. Schritt: Auswahl der Pivotspalte.

Es wird nun die Zielfunktionszeile der Inversen mit multipliziert:

Da keine negativen Werte mehr vorhanden sind, ist die Lösung optimal.

Optimale Lösung

Man betrachtet die letzte Matrix und dort die Spalten. Diese gleicht man mit der zu Beginn aufgestellten Matrix ab. Man sieht deutlich, dass die Variablen (der Reihenfolge in der sie in der Matrix auftreten nach) (plus Einheitsvektor) in der Basis befinden. Für diese Variablen müssen die dazugehörigen Werte berechnet werden. Diese werden bestimmt, indem die Inverse mit der rechten Seite multipliziert wird:

Die Werte für die Basisvariablen ergeben sich durch Multiplikation der Inversen mit der rechten Seite :

Dabei gilt , , , , und . Der Zielfunktionswert kann in der Ergebnismatrix in der unteresten Zeile abgelesen werden .