Die Optimallösung, welche gleichzeitig die beste Lösung ist, bekommt man durch das vorgestellte Simplex-Verfahren. Das Optimaltableau dient hier nochmals als Erinnerung:
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 0 | 60 |
y2 | 0 | 0 | 5 | 1 | -5 | 0 | 100 |
x2 | 0 | 1 | -5 | 0 | 5 | 0 | 50 |
y4 | 0 | 0 | 100 | 0 | -250 | 1 | 1.000 |
0 | 0 | -45 | 0 | -225 | 0 | -18.450 |
Tab. 9: Optimaltableau zur Vorbereitung der zweitbesten Lösung
Die zweitbeste Lösung kann durch die Rückwärtsrechnung ermittelt werden, welche sich ein oder mehrere Ecken „rechts“ oder „weiter links“ befinden kann. Somit wird eine Nichtbasisvariable in die Menge der Basisvariablen aufgenommen.
Dies geschieht in mehreren Schritten:
Methode
1. zu bestimmen sind die Schlüsselzahlen in den Spalten der Nichtbasisvariablen.
a. die Werte der rechten Seite sind durch die positiven Elemente der Spalte der Nichtbasisvariablen zu dividieren.
b. den kleinsten Quotient nennt man Schlüsselzahl.
c. die Schlüsselzahl ist zu markieren.
2. der jeweils kleinste Quotient mit einem negativen Zielfunktionswert ist zu multiplizieren.
a. jene Spalte, welche das Minimum enthält, ist zu bestimmen.
3. die Variable, welche aus Schritt 2 einhergeht, ist in die Menge der Basisvariablen aufzunehmen. Dafür ist die Variable aus der Menge der Basisvariablen rauszuwerfen, welche in der Zeile liegt, aus welcher die Variable herausgenommen wurde.
4. die Rechnung des Simplex-Schritts kann mit diesen Informationen vorgenommen werden.
Für unser erstes Beispiel aus Kapitel 1 ("Beste Lösung") bedeutet es:
1. Schritt
Spalte y1: 60: 1 = 60, 100: 5 = 20, 1000: 100 = 10 (*)
Spalte y3: 50: 5 = 10 (*).
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 0 | 60 |
y2 | 0 | 0 | 5 | 1 | -5 | 0 | 100 |
x2 | 0 | 1 | -5 | 0 | 5* | 0 | 50 |
y4 | 0 | 0 | 100* | 0 | -250 | 1 | 1.000 |
0 | 0 | -45 | 0 | -225 | 0 | -18.450 |
Tab. 10: Suche nach Schlüsselzahlen
2. Schritt
10·45 = 450 ... Minimum, 10·225 = 2.250. Ausgewählt wird demnach die y1-Spalte.
3. Schritt
y1 ist in eine Basisvariable zu transformieren und y4 zu einer Nichtbasisvariablen. Das neue Pivot-Element ist 100.
4. Schritt
Folgende Tableaus werden von dem Simplex-Schritt geliefert:
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 1 | 0 | 0 | 0 | 60 |
y2 | 0 | 0 | 5 | 1 | -5 | 0 | 100 |
x2 | 0 | 1 | -5 | 0 | 5 | 0 | 50 |
y4 | 0 | 0 | 1 | 0 | -2,5 | 0,01 | 10 |
0 | 0 | -45 | 0 | -225 | 0 | -18.450 |
Tab. 11: Vorbereitung für Pivotschritt
x1 | x2 | y1 | y2 | y3 | y4 | RS | |
x1 | 1 | 0 | 0 | 0 | 2,5 | -0,01 | 50 |
y2 | 0 | 0 | 0 | 1 | 7,5 | -0,05 | 50 |
x2 | 0 | 1 | 0 | 0 | -7,5 | 0,05 | 100 |
y1 | 0 | 0 | 1 | 0 | -2,5 | 0,01 | 10 |
0 | 0 | 0 | 0 | -337,5 | 0,45 | -18.000 |
Tab. 12: Zweitbeste Lösung
Die zweitbeste Lösung befindet sich in der Ecke links von der Optimallösung, demnach in Punkt (4) x1 = 50 und x2 = 100 (s. Abb. 4).
Merke
Weitere interessante Inhalte zum Thema
-
Lineare Programmierung
Vielleicht ist für Sie auch das Thema Lineare Programmierung aus unserem Online-Kurs Operations Research interessant.
