LP Simplex Aufgabenbeispiel kommentiert
- Autor:
- hawe
- Thema:
- Lineare Optimierung
Aufgabe
3 Produkte werden auf 3 Maschinen M1, M2 und M3 hergestellt.
Die Belegungszeiten der Produkte auf der Maschine M1 betragen 2 Minuten für P1, 4 Minuten für P2 und 3 Minuten für P3; M1 besitzt eine freie Kapazität von 1.050 Minuten.
Alle Produkte belegen die Maschine M2 mit je einer Minute; die Kapazität dieser Maschine beträgt noch 450 Minuten.
Auf der dritten Maschine M3 kann nur P2 gefertigt werden; sie besitzt noch eine Kapazität von 150 Minuten. Die Belegungszeit von P2 auf M3 beträgt 1 Minute.
Der Deckungsbeitrag je Stück der 3 Produkte beträgt 50 € , 80 € bzw. 60 €.
a) Welche Stückzahlen sind jeweils herzustellen, damit der Gesamtdeckungsbeitrag maximal wird?
b) Wie groß ist der optimale Gesamtdeckungsbeitrag und wie hoch sind die freien Kapazitäten der drei Maschinen im Optimum? "
Simplex-Applet (Simplex-Rechner)
Simplex-Applet (Simplex-Rechner)Modelierung der Aufgabenstellung
1. 0 LP Max Ungleichungen
1.1 LP Max Gleichungen mit Schlupfvariablen
Die Zielfunktion trage ich negativ ein.
Der Algorithmus endet dann, wenn alle Koeffizienten der Zielfunktion positiv sind!
1.2 LP Max Matrixgleichung A x = b aus 1.1
Aus der Matrixgleichung 1.2 entwickle ich das Starttableau 1.4.
1.3 LP Überlegungen zur Matrixgleichung 1.2
Als Versuch betrachte ich das LP mit p1=160, p2=150, p3=50 und erhalte mit 1.2:
Der Vektor x=(160,150,50,0,0,0)^T ist keine Lösung des GLS 1.2, weil der Ergebnisvektor b=(1050,450,150,0) nicht erreicht wird. Mit den passenden Schlupfvaribalen kann eine Lösung konstruiert werden:
p1=160, p2=150, p3=50 ===> 1.1 ===> s1=..., s2=..., s2=... ===>
Die Lösung x=(160,150,50,-20,90,0)^T erfüllt zwar das GLS 1.2 ist aber ungültig, d.h. erfüllt nicht die Ungleichungen 1.0, weil eine Schlupfvariable negativ wird (Kapazitätsüberschreitung von M1). Nicht Negativitätsbedingung verletzt! Sie Schlupfvariablen stehen für die Ressourcen, die das LP übrig läßt!
Übertragen wir die Matrixgleichung in ein Tableau.
Gültige Lösungen
1.4 LP Max Starttableau
In jeder Zeile gibt es nur eine Variable, die ungleich Null ist.
Diese werden als Basisvariablen des Programms bezeichnet und in Spalte BV notiert.
Das Starttableau 1.4 beschreibt den Zustand des LP, wenn nicht produziert wird
p1=p2=p3=0, s1=1050, s2=450, s3=150 (keine Ressourcen verbraucht):
Konstruieren wir eine gültige Lösung des GLS 1.2.
Die Gleichungen 1.1 kann ich als Ebenen im Raum interpretieren (bei 2 Maschinen p1,p2 würden wir Geraden betrachten). Wo sich zwei der Ebenen (Geraden) schneiden sind die betreffenden Schlupfvariablen verschwunden (=0), d.h. die Maschinenkapazitäten werden voll ausgenutzt.
Ich konstruiere eine Lösung für s1=0 und s3=0 mit GLS 1.1:
Wegen s3=0 folgt p2=150
Eingesetzt in die beiden ersten Gleichungen erhalte ich
2 p1 + 3 p3 = 450, p1 + p3 + s2 = 300 => p1 = -3 s2 + 450, p3 = 2 * s2 - 150}
Für s2=75 wäre p3=0 und p1=225 und das GLS 1.2 lautet dann
Was eine gültige Lösung des GLS 1.2 darstellt!
Um diese Schritte s3=0 p2=150 auf dem Starttableau anzuwenden würde ich als Pivotzeile=3 und Pivotspalte=2 wählen und damit einen Gaussschritt auf Starttableau 1.4 anwenden - Zeile s3 so zu allen anderen Zeilen addieren damit in Spalte 2 0en entstehen. Pivotelement Zeile 3,Spalte 2 auf 1 setzen (ohne Rechnung da das der Startwert ist). Basiswechsel s3<<>>p2:
Der Schritt s1=0 legt Pivotzeile 1 fest und wenn p1 berechnet werden soll ist die Pivotspalte 1 zu nehmen. Pivotelement Zeile 1,Spalte1 auf 1 setzen (Zeile s1' = Zeile s1/2). Zeile s1' so zu allen anderen Zeile addieren damit in Spalte 1 0en entstehen. Basiswechsel s1<<>>p1:
Eine LP Varaible (p1,p2,p3) in der Basis (d.h. alle anderen Variablen in der Zeile sind 0) gibt im b-Vektor den Wert für die LP Variable (p1=225, p2=150) an.
Eine Schlupfvariable in der Basis gibt den Kapazitätsrest (s2=75 Restkapazität für M2) im b-Vektor an!
Der Deckungsbeitrag beläuft sich für diesen Fall auf 23250.
Was aber noch keine maximale Lösung ist, da in der Zeile der Zielfunktion noch ein negativer Wert steht, der einen Basiswechsel von s2<<>>s3 verlangt.
Simplex Algorithmus
Es wird Zeit systematischer Vorzugehen.
Zur Festlegung des Pivotelements nehmen wir die Pivot-Spalte mit dem kleinsten negativen Wert (das ist der größte positive Koeffizient der Zielfunktion 1.0 der den größten Effekt auf die Maximierung verspricht).
Im Starttableau ist das Spalte p2 - Pivot-Spalte. Die Pivot-Zeile bestimmen wir durch den kleinsten positiven Quotienten der Werte aus b dividiert durch p2 (komponetenweise) - Zeile s3 ist Pivotzeile, weil 150 der kleinste positive Wert ist. Das Pivotelement ZS(3,2)=(s3,p2) = 1 muss ggf. durch Division der Zeile durch ZS(3,2) auf 1 gebracht werden (hier nicht notwendig) weil wir p2 als neue Basisvariable festlegen, sie damit berechnen (alle anderen Variablen in der Zeile sind dann 0). In einem Gaussschritt addieren wir Zeile s3 so, dass in der Pivot-Spalte 0en erzeugt werden :
Alle Koeffizienten der Zielfunktion Z positiv - Stopp Simplex - Maximum bei
p1=375, p2=75, p3=0 - Restkapazität M3 mit s3=75.
| |
| | |
| | A x = b |
Matrix_Simplex_LP_Tableau 3 Produkte
- X0:={x1,x2,x3} Variablen festlegen
- Übertrage NB mit Schlupfvariablen nach A
- Rechte Seite der NB nach b
- Zielfunktion nach Z
- (7) Xi Liste der Schlupfvariablen (nicht Basisvariablen): setze 2 Schlupfvariablen=0 - die anderen=1
- (9) Eckensuche A X0 - b=0: LS die betroffenen NB.
- (10) ggf. abhängige Variable = 0 setzen: x3=0 ==> xi Lösungsvektor für Basisvariablen Um ein bestimmtes Programm zu rechnen überschreibe Basisvariablen in xi:={365,80,5} Ressourcen s1 nicht ausreichend - Nichtnegativitätsbedigung nicht erfüllt
- (11) ergänzen mit den berechneten Schlupfvariablen: Basisvektor X >= 0 ==> gültige Lösung
- (12) Tableau und Zielfunktion berechnen