ZU DEN KURSEN!

Operations Research - Zweitbeste Lösung

Kursangebot | Operations Research | Zweitbeste Lösung

Operations Research

Zweitbeste Lösung

Die beste Lösung – auch Optimallösung genannt – erhält man nach dem beschriebenen Simplex-Verfahren. Zur Erinnerung hier nochmals das Optimaltableau:

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

Mittels Rückwärtsrechnung bestimmen wir nun die zweitbeste Lösung, die eine oder mehrere Ecken „weiter rechts“ oder „weiter links“ liegen kann. Es wird also eine Nichtbasisvariable in die Menge der Basisvariablen aufgenommen.

Dies erfolgt in mehreren Schritten:

Methode

Hier klicken zum Ausklappen KOCHREZEPT ZWEITBESTE LÖSUNG:


 
1. Bestimmung der Schlüsselzahlen in den Spalten der Nichtbasisvariablen

a. dividiere die Werte der rechten Seite durch die positiven Elemente der Spalte der Nichtbasisvariablen

b. der kleinste Quotient heißt Schlüsselzahl

c. markiere diese Schlüsselzahl

2. multipliziere den jeweils kleinsten Quotienten mit dem – negativen – Zielfunktionswert

a. bestimme jene Spalte, die das Minimum enthält

3. nimm die Variable, die man in Schritt 2 erhält, in die Menge der Basisvariablen auf. Wirf dafür jene Variable aus der Menge der Basisvariablen raus, die in der Zeile liegt, aus der die Variable entnommen wurde

4. Rechne mit diesen Informationen einen Simplex-Schritt.

In unserem ersten Beispiel aus Kapitel 1 ("Beste Lösung") bedeutet dies folgendes:

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. Die y1-Spalte wird also ausgewählt.

3. Schritt

Mache daher y1 zur Basisvariable und y4 zur Nichtbasisvariable. Das neue Pivot-Element ist 100.

4. Schritt

Der Simplex-Schritt liefert folgende Tableaus:

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

y4

0

0

1

0

-2,5

0,01

10

0

0

0

0

-337,5

0,45

-18.000

Tab. 12: Zweitbeste Lösung

Also ist die Ecke links von der Optimallösung, d.h. x1 = 50 und x2 = 100, also Punkt (4) in Abb. 4, die zweitbeste.

Merke

Hier klicken zum Ausklappen Im Simplex-Algorithmus durchläuft man nicht notwendig die zweitbeste Lösung im vorletzten Schritt, da die Ecken nicht nach der Reihenfolge der Werte der Zielfunktion abgesucht werden. Vielmehr sucht man – beginnend mit x1 = x2 = 0 die Ecken ab, die jeweils eine Verbesserung des Werts der Zielfunktion ergeben.