ZU DEN KURSEN!

Operations Research - Simplex-Austausch-Schritt

Kursangebot | Operations Research | Simplex-Austausch-Schritt

Operations Research

Simplex-Austausch-Schritt

Zunächst versuchen wir, das

  • Kalkül des Simplex-Algorithmus, danach

  • die Zahlen der Tableaus

zu verstehen.

Methode

KOCHREZEPT SIMPLEX-ALGORITHMUS: 


 1. Bestimme die Pivot-Spalte
Suche hierzu die Spalte mit dem größten Zielfunktionskoeffizienten

2. Bestimme die Pivot-Zeile

•teile alle Elemente der rechten Seite durch die – streng positiven – Elemente der Pivot-Spalte

•nimm das Minimum der Zahlen aus a.

3. Bestimme das Pivot-Element

Dies befindet sich im Schnittpunkt aus Pivotspalte und Pivotzeile

4. Dividiere die Elemente der Pivotzeile durch das Pivotelement

Dadurch wird das Pivotelement zu eins

5. Mache alle Elemente der Pivotspalte – mit Ausnahme des Pivotelements selbst – zu null

Subtrahiere geeignete Vielfache der Pivotzeile von den jeweiligen Zeilen des Tableaus. 

In unserem ersten Beispiel aus dem Kapitel "Beste Lösung" ist die Pivotspalte bei x1, da der Zielfunktionswert mit 270 maximal ist.

Merke

x1 wird dadurch von einer Nichtbasisvariable (mit Wert null) zu einer Basisvariable (mit Wert größer null). Man spricht deshalb bei einem Simplex-Schritt auch von einem Basis-Tausch. Gut 1 wird produziert, Produkt 2 nicht (x1 = 60, x2 = 0 im Punkt (E)).

Dann sucht man die Pivotzeile. Die Elemente der rechten Seite, dividiert durch die Pivotspalte, liefern Quotienten, die ganz rechts eingetragen werden:

x1

x2

y1

y2

y3

y4

RS

Divisionen

y1

1

0

1

0

0

0

60

60 : 1 = 60

y2

0

1

0

1

0

0

150

-

y3

1

0,2

0

0

1

0

70

70 : 1

y4

150

50

0

0

0

1

12.500

12.500 : 150 = 83,33

ZF

270

45

0

0

0

0

0

Tab. 2: Suche nach der Pivotzeile und dem Pivotelement

Minimal ist die Zahl 60, so dass die erste Zeile zur Pivotzeile wird. Das Pivotelement liegt im Drehkreuz aus Pivotspalte und Pivotzeile und ist hier also 1. Der vierte Schritt des obigen Kochrezepts entfällt, da das Pivotelement bereits gleich 1 ist. Mache danach die einzelnen Elemente der Pivotspalte zu null. In der zweiten Zeile rechnet man nichts, da der Eintrag bereits null ist.

  • In der dritten Zeile

    • rechnet man III – I = IIIneu

  • Für die vierte Zeile

    • kalkuliert man –150·I + IV = IVneu

  • In der Zielfunktionszeile

    • rechnet man ZF – 270·I =ZFneu

Nach diesem Simplex-Schritt erhält man folgendes Tableau:

x1

x2

y1

y2

y3

y4

RS

x1

1

0

1

0

0

0

60

y2

0

1

0

1

0

0

150

y3

0

0,2

-1

0

1

0

10

y4

0

50

-150

0

0

1

3.500

0

45

-270

0

0

0

-16.200
Tab. 3: Simplextableau nach erstem Austauschschritt

Zum tiefergehenden Verständnis sind noch einige Erklärungen notwendig:

Wir befinden uns im Punkt (E) der Abb. 4, denn es ist x1= 60 und x2= 0.

x1 ist nun Basisvariable, nicht mehr Nichtbasisvariable wie vorher. Auf deutsch: Gut 1 wird produziert, das Gut 2 nicht (x2 ist also weiterhin Nichtbasisvariable). x1 steht deshalb nun am linken Rand des Tableaus, nicht mehr lediglich oben.

y1 ist nicht mehr Basis-, sondern Nichtbasisvariable. Es wird also der Wert y1 = 0 zugewiesen. Wenn x1 = 60 ist, dann ist die Absatzkapazität komplett ausgereizt. Mehr Absatz ist beim ersten Produkt nicht möglich.

Bei einer Menge von x1= 60 ME und x2= 0 ME ist der Gewinn G = 270·60 + 45·0 = 16.200 €. Der Wert in der rechten unteren Ecke des Tableaus ist also der Gewinn, der bei Betrachtung der jeweiligen Ecke entsteht.

Methode

Das Minus-Zeichen bedeutet nicht, dass der Gewinn negativ ist!

Zu den restlichen Werten der rechten Seite:

  • y2= 150

    • die zweite Absatzkapazität ist noch komplett unausgelastet,

    • es ist also noch Platz für 150 zu produzierende Mengeneinheiten

  • y3= 10

    • auf der Maschine beträgt die Restkapazität noch 10 Minuten

    • wegen 1·60 + 0,2·0 = 60, und dies liegt 10 Minuten unter der maximalen Kapazität von 70

  • y4= 3.500

    • es sind noch 3.500 Arbeitsstunden unausgenutzt

    • wegen 150.60 + 50·0 = 9.000,

    • und dies liegt 3.500 Stunden unter der maximalen Kapazität von 12.500.

Auch die restlichen Zahlen sind interpretierbar. Hierum kümmern wir uns jedoch erst im Optimaltableau (was allerdings in jedem anderen Tableau auch geht).