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

Operations Research - Simplex-Austausch-Schritt

Kursangebot | Operations Research | Simplex-Austausch-Schritt

Operations Research

Simplex-Austausch-Schritt

Zu Beginn ist es wichtig, erst das Kalkül des Simplex-Algorithmus und danach die Zahlen der Tableaus

zu verstehen.

Methode

Hier klicken zum AusklappenSCHEMA SIMPLEX-ALGORITHMUS: 

 
1. zu bestimmen ist die Pivot-Spalte. Dafür ist die Spalte mit dem größten Zielfunktionskoeffizienten zu suchen.

2. ... danach die Pivot-Zeile.

• alle Elemente der rechten Seite sind durch die streng positiven Elemente der Pivot-Spalte zu teilen.

• das Minimum der Zahlen aus a ist zu nehmen.

3. ... das Pivot-Element, welches sich im Schnittpunkt aus Pivotspalte und Pivotzeile befindet, ist zu entnehmen.

4. Elemente der Pivotzeile sind durch das Pivotelement zu dividieren, wodurch das Pivotelement zu einem wird.

5. alle Elemente der Pivotspalte – mit Ausnahme des Pivotelements selbst – sind auf null zu setzen.


Das geeignete Vielfache der Pivotzeile von den entsprechenden Zeilen des Tableaus sind zu subtrahieren. 

Die Pivotspalte liegt im ersten Beispiel aus dem Kapitel "Beste Lösung"  bei x1, aufgrund des maximalen Zielfunktionswertes von 270.

Merke

Hier klicken zum AusklappenDer Wert von x1 wird von einer Nichtbasisvariablen (Wert=0) zu einer Basisvariablen (Wert > null). Aus dem Grund wird beim Simplex-Schritt auch von einem Basis-Tausch gesprochen. Das Produkt a wird im Gegensatz zu Produkt b produziert (x1 = 60, x2 = 0 im Punkt (E).

Im nächsten Schritt wird die Pivotzeile ermittelt. Dividiert werden die Elemente der rechten Seite durch die Pivotspalte. Daraus ergeben sich die Quotienten, die ganz rechts einzutragen sind.

 

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

Die Zahl 60 ist minimal, sodass die erste Zeile zur Pivotzeile wird. Das Pivotelement liegt im Drehkreuz aus Pivotspalte und Pivotzeile und ist hierbei 1. Die einzelnen Elemente der Pivotspalte sind auf null zu bringen. Da der Eintrag in der zweiten Zeile bereits null beträgt, ist hierbei nichts zu berechnen.

  • In der dritten Zeile ist zu rechnen: III – I = IIIneu

  • In der vierteln Zeile ist zu kalkulieren: –150·I + IV = IVneu

  • In der Zielfunktionszeile ist zu rechnen: ZF – 270·I =ZFneu

Aus dem Simplex-Schritt resultiert 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: Simplex-Tableau nach erstem Austauschschritt

Zum besseren Verständnis sind noch weitere Erklärungen nötig:

Wir befinden uns bei Punkt E (x1= 60 und x2= 0) in Abb. 4.

Bei x1 handelt es sich nicht mehr um eine Nichtbasisvariable, sondern nun um eine Baisvariable. Demnach wird das Produkt a produziert und das Produkt b nicht, da x2 weiterhin eine Nichtbasisvariable bleibt. Aus diesem Grund steht x2 nicht mehr nur am oberen Rand des Tableaus, sondern auch am linken Rand.

y1 ist von einer Basis- zur Nichtbasisvariablen geworden. Dieser wird der Wert  y1 = 0 zugewiesen. Die Absatzkapazität ist im Falle von x1 = 60 gänzlich ausgereizt. Daher kann kein höherer Absatz beim ersten Produkt hervorgehen.

Ausgehend von einer Menge von x1= 60 ME und x2= 0 ME beträgt der Gewinn G = 270·60 + 45·0 = 16.200 €. Der Wert in der rechten unteren Ecke des Tableaus ist demnach der Gewinn, welcher bei der Betrachtung der entsprechenden Ecke resultiert.

Merke

Hier klicken zum Ausklappen

Ein Minus-Zeichen muss auf keinen negativen Gewinn hindeuten!

Zu den restlichen Werten der rechten Seite:

  • y2= 150

    • die zweite Absatzkapazität ist noch nicht gänzlich ausgelastet,

    • es besteht noch Platz für 150 zu produzierende Mengeneinheiten

  • y3= 10

    • die Restkapazität beträgt bei den Maschinen noch 10 Minuten

    • die verwendete Kapazität (1·60 + 0,2·0 = 60) liegt 10 Minuten unter der maximalen Kapazität von 70

  • y4= 3.500

    • 3.500 Arbeitsstunden sind nicht gänzlich ausgelastet.

    • die genutzten Arbeitsstunden sind 150·60 + 50·0 = 9.000,

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

Die restlichen Zahlen können ebenso gedeutet werden. Damit beschäftigen wir uns allerdings erst im Optimaltableau (was jedoch in jedem anderen Tableau auch möglich ist).