Simplex-Algorithmus

Eine der wichtigsten mathematischen Methoden zur Unterstützung von Entscheidungen ist der Simplex-Algorithmus. Er kommt zur Anwendung wenn es mehrere Engpässe für eine Produktion gibt.

Erster Schritt: Ein lineares Programm schreiben
Als erstes muss man das lineare Gleichungssystem aufschreiben, d.h. Zielfunktion und Nebenbedingungen.

Die Zielfunktion ist der kumulierte Deckungsbeitrag und soll maximiert werden.
Wenn ich als ein Produkt x habe und ein Produkt y, die jeweils einen DB von 7 bzw 10 € haben, entsteht folgene Zielfunktion:
7*x+10*y -> max
Produkt x und y brauchen allerdings Ressourcen:x braucht 5 mal Rohstoff A und 10 mal B.
y hingegen brauch 10 A und 5 B.

Sowohl von A als auch von B gibt es aber nur 100 Stück. Wir haben also eine Produktion mit zwei Engpässen.

Diese Nebenbedingungen schreiben wir in Gleichungsform:
Für A: 5*x+10*y<=100
Für B: 10*x+5*y <=100

Dies sind Ungleichungen. Wir wollen aber Gleichungen haben, also fügen wir noch „Schlupfvariablen“  ein (a und b) die den Unterschiedsbetrag abbilden. Für die Zielfunktion ist dieser Parameter Z und wird von der rechten auf die linke Seite gebracht (deswegen minus Z).

5x +10y +1a + 0b = 100
10x +5y +0a +1b = 100
7x +10y +0   + 0 – Z= 0

Zweiter Schritt: Pivotisierung und Gleichungsumformungen
Wir haben nun ein Gleichungssystem (-Matrix) mit 3 Zeilen und 5 Spalten. Nun suchen wir als erstes die größte Zahl in der Zielfunktion. Diese ist 10 in der y-Spalte. Dies ist unsere Pivotspalte. Nun dividieren wir die rechten Seiten durch den Wert in der y-Spalte in der jeweiligen Zeile(allerdings nur für alle nicht Zielfunktions-Gleichungen:
5x +10y +1a + 0b = 100  I 100/10=10
10x +5y +0a +1b = 100   I100/5 =20
7x +10y +0   + 0 – Z= 0

 

Diese Zahl beschreibt die Kapazität die das Produkt bietet. Von Produkt A aus können also 10 mal y und von Produkt B 20 mal y produziert werden. Da für Produkt A der engere Engpass vorherrscht, ist dies nun unsere Pivotzeile. TReffpunkt von Pivotspalte und Pivotzeile ist das Pivotelement. In diesem Fall 10y.

Nun formen für die Pivotzeile um, sodass das Pivotelement 1 ergibt,d.h. wir teilen durch 10:
0,5x +1y +0,1a +0b = 10

Die anderen beiden Zeilen müssen jetzt so umgeformt werden, dass alle anderen Werte in der Pivotspalte 0 sind. Also die zweite Zeile minus 5 mal unsere neue Zeile 1 und die dritte Zeile minus 10 mal unsere neue Zeile 1.

Unser neues Gleichungssystem ergibt sich als:
0,5x +1y +0,1a +0b = 10
7,5x +0y -0,5a +1b = 50
2x +0y     -1a   + 0 – Z= -100

Dieser zweite Schritt muss jetzt noch wiederholt werden. Ich lasse euch dies einmal probieren und löse im nächsten Blogpost auf und verrate dann noch wie das Ergebniss zu interpretieren ist.

Dies könnt ihr hier nachlesen:
http://derbwler.de/2012/02/simplex-algorithmus-teil-2/

You may also like...

1 Response

  1. 6. Februar 2012

    […] schon im vorherigen Artikel (http://derbwler.de/2012/02/simplex-algorithmus)beschrieben, möchte ich jetzt die die Auflösung und die Interpretation des Beispiels […]

Schreib einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *