Simplex-Verfahren

Das Simplex-Verfahren ist eine Methode, Probleme der linearen Planungsrechnung (siehe lineare Planungsrechnung) zu lösen. Das Simplex-Verfahren untersucht ausgehend vom Ursprung die Eckpunkte des zulässigen Lösungsraums, um das Maximum der Zielfunktion zu bestimmen.


Beispiel

Zu maximieren ist z mit z + (-300) x1 + (-500) x2 = 0 unter den Nebenbedingungen:

x1 + 2 x2 <= 170,
x1 + x2 <= 150,
x2 <= 180,
x1 >= 0 und
x2 >= 0.

Die ersten drei Nebenbedingungen werden unter Einführen von Schlupfvariablen in Gleichungen umgeformt:

x1 + 2 x2 + y1 = 170,
x1 + x2 + y2 = 150 und
x2 + y3 = 180.

Die yi müssen grösser gleich Null sein.


Terminologie

Strukturvariable - sind die Variablen, deren Werte eine Lösung ausmachen (im Beispiel x1 und x2),
Schlupfvariable - sind Variablen, die bei der Umformung der Nebenbedingungen eingeführt werden (y1, y2 und y3),
Nicht-Basisvariable - werden Null gesetzt, um die Basisvariablen zu bestimmen.


Formelzeichen

n - Anzahl der Nicht-Basisvariablen (im Beispiel 2),
m - Anzahl der Basisvariablen (3),
a[0,1], ... a[0,n] - Koeffizienten der Zielfunktion (-300, -500),
a[1,0], ..., a[m,0] - rechte Seiten der Restriktionen (170, 150, 180),
a[1,1], ... a[m,n] - Koeffizienten der Restriktionen ((1, 2), (1, 1), (0, 1)),
a*[i,j] - Koeffizienten nach dem Simplex-Schritt.

 
Simplex-Schritt (Steepest Unit Ascent)

1. Bestimme s so, dass a[0,s] die kleinste Zahl der a[0,j] (1 <= j <= n) ist.
2. Ist a[0,s] >= 0, ist die Lösung gefunden. Ist die Wahl nicht eindeutig, so liegt eine duale Entartung vor. Man wählt dann eine der Möglichkeiten aus.
3. Bestimme r so, dass a[r,0] / a[r,s] die kleinste positive Zahl der a[i,0] / a[i,s] (1 <= i <= m) ist.
4. Sind alle Quotienten kleiner oder gleich Null, existiert keine Lösung (primale Entartung). Ist die Wahl nicht eindeutig, wählt man zufällig unter den Möglichkeiten aus (primale Entartung).
5. Berechne die neuen Koeffizienten:
• a*[r,s] = 1 / a[r,s] (Pivotelement),
• a*[i,s] = - a[i,s] / a[r,s] (Pivotspalte ausser Pivotelement, also für i <> r),
• a*[r,j] =  a[r,j] / a[r,s] (Pivotzeile ausser Pivotelement, also für j <> s),
• a*[i,j] = a[i,j] - a[i,s] a[r,j] / a[r,s] (alle anderen Elemente, also i <> r und j <> s).
6. Vertausche die r-te Basisvariable mit der s-ten Nicht-Basisvariable.

Bei der Greatest Change-Variante des Simplex-Verfahrens wird die Pivotspalte für die a[r,0] / a[r,s] * a[0,s] maximal ist (r wird in Abhängigkeit von s so wie in 3. gewählt).


Gleichungen als Restriktionen

Gleichungen als Restriktionen werden zunächst wie Ungleichungen behandelt (Einfügen einer Schlupfvariablen). Die zugehörige Schlupfvariable wird jedoch als gesperrt vermerkt, sie darf nicht in die Basis (da sie Null bleiben muss).


Fehlende Nichtnegativitätsbedingungen

Gilt für eine Variable v nicht die Bedingung v >= 0, nennt man diese Variable frei. Freie Variablen sind in die Basis zu bringen.


Unzulässige Ausgangslösung

Weil vor dem ersten Simplex-Schritt die Struktur- mit den Nicht-Basisvariablen identisch sind, werden die Strukturvariablen gleich Null. Wenn dieses Wertetupel nicht zu den möglichen Lösungen gehört, spricht man von einer unzulässigen Ausgangslösung. Das ist immer dann der Fall, wenn Restriktionsgleichungen mit einem >= vorliegen (negative rechte Seite). Die betroffene Zeile wird dann als Pivotzeile ausgewählt.


Entartung

Ist die Wahl der Pivotspalte nicht eindeutig, spricht man von dualer Entartung. Ist die Wahl der Pivotzeile nicht eindeutig, oder nicht möglich, spricht man von primaler Entartung.