Jetzt neu: Steuerrecht online lernen auf steuerkurse.de!
ZU DEN KURSEN!

Operations Research - Zweitbeste Lösung

Kursangebot | Operations Research | Zweitbeste Lösung

Operations Research

Zweitbeste Lösung

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

Hier klicken zum AusklappenSCHEMA ZWEITBESTE LÖSUNG:


 
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

Hier klicken zum AusklappenDie zweitbeste Lösung im Simplex-Algorithmus wird nicht notwenigerweise im vorletzten Schritt durchlaufen, weil die Ecken nicht nach der Reihenfolge der Zielfunktionswerten abgesucht werden. Überprüft werden eher die Ecken, welche mit x1 = x2 = 0 beginnen und jeweils eine Verbesserung des Werts der Zielfunktion bieten.