Lineare Optimierung mit dem Simplexverfahren
OPERATIONS RESEARCH
Marc Schwärzli SS 2013
Konvex - Konkav• Eine Funktion heißt konvex, wenn die
Funktionswerte zwischen 2 Punkten unter einer Verbindungsgeraden liegen. F(x) = x²
Konvex - Konkav• Eine Funktion heißt konkav, wenn die
Funktionswerte zwischen 2 Punkten über einer Verbindungsgeraden liegen.
• F(x) = -x²
Eine Konvexe Punktmenge
Alle Punkte auf einer Verbindungsgeraden zwischen zwei Punkten liegen innerhalb der Zielmenge.
Lineare Optimierung (LO)• Eine lineare Optimierungsaufgabe besteht aus
einer Zielfunktion, die unter bestimmten Nebenbedingungen zu maxi- bzw. minimieren ist.
• Eine LO-Aufgabe kann entweder grafisch durch Schneiden der Nebenbedingungen oder mit dem Simplexverfahren gelöst werden.
Bei der grafischen Lösung werden die Nebenbedingungen als Geraden dargestellt.
Beispiel: Gewinnmaximierung
• Der Fabrikant Hugo V. stellt auf seinen Maschinen 2 verschiedene Stoffe her (Umrüstzeiten sind zu vernachlässigen):– Pro Minute können 8m Baumwolle oder 4m Seide auf
Maschine 1 hergestellt werden.– Auf der 2. Maschine könne höchstens 6m/ Minute Stoff
bedruckt werden.– Arbeiter Manfred verpackt 5m Baumwolle pro Minute
und Arbeiter Herfried 3m Seide pro Minute. – Der Gewinn je Meter Baumwolle beträgt € 9 und je
Meter Seide € 14.
Ableiten der Gleichungen aus dem Text:
• Maschine 1:
• Maschine 2:
• Manfred: • Herfried:
• Nichtnegativbedingung:
• Zielfunktion:
82 )(148 21
21 xxgMeterxx
Meterxx
166
21
Meterx
15
1
Meterx
13
2
0,0 21 xx
max149),( 2121 xxxxZ
6 )( 21 xxg
5 )( 1 xg
3 )( 2 xg
Als Gerade:
Grafische Lösung einer LO-Aufgabe• Die Nebenbedingung wird als
Gerade konstruiert:82 )( 21 xxg
40 : 211 xxP
80 : 122 xxP
1P
2P
Grafische Lösung einer LO-Aufgabe• Nebenbedingung 6 )( 21 xxg
Grafische Lösung einer LO-Aufgabe• Nebenbedingungen und : 5 )( 1 xg 3 )( 2 xg
Grafische Lösung einer LO-Aufgabe• Bestimmung des Maximalen Gesamtgewinns
durch Erstellung der Isogewinngeraden:– Zielfunktion = 9X1 + 14X2 Maximum – Die Ziefunktion wird nach X2 = kX1 + d umgeformt,
damit das k ablesbar ist. – d = 0, da die Gerade durch (0/0) Ursprung geht.– X2 = kX1
– 14X2 = -9X1
– X2 = -9/14 X1 k ist als -9/14 erkennbar.
Grafische Lösung einer LO-Aufgabe• Konstruktion der Isogewinngeraden mit der
Steigung k = -9/14 durch den Ursprung:
X1
X2
k
Steigung1
114
9
Grafische Lösung einer LO-Aufgabe• Durch Parallelverschieben der Isogewinngeraden
zum äußersten Punkt kommt man zum Punkt mit dem maximalen Gewinn:
Grafische Lösung einer LO-Aufgabe• 4m Baumwolle und 2m Seide stellen das
optimale Produktionsprogramm dar.• Durch Einsetzen des Punktes in die
Zielfunktion 9X1 + 14X2 ergibt sich der Gewinn für das optimale Produktionsprogramm mit €64
• Der Bereich der zulässigen Lösungen bildet stets eine konvexe Punktmenge. (Schraffierter Bereich)
Rechnerische Lösung einer LO-Aufgabe nach dem Simplexverfahren
• Transformation der Ungleichungen in Gleichungen mithilfe von Schlupfvariablen:
– X1 + X2 + S1 = 8– X1 + X2 +S2 = 6– X1 +S3 = 5– X2 +S4 = 3
Basisvariablen Nichtbasis=variablen
Allgemeines zum Simplexverfahren
• Ein Gleichungssystem heißt von kanonischer Form, wenn es in jeder Gleichung eine Unbekannte gibt, die nur in dieser vorkommt und dort den Koeffizienten Eins besitzt.
• Diese Unbekannten bezeichnet man als Basisvariablen (BV), die übrigen als Nichtbasisvariablen (NBV)
Das Simplexverfahren
Erstellen der Standardform• Maschine 1: x1 + 2x2 <= 8 Meter• Maschine 2: x1 + x2 <= 6 Meter• Manfred: x1 <= 5 Meter• Herfried x2 <= 3 Meter• Nichtnegativbedingung: x1 >= 0; x2 >= 0• Zielfunktion: Z(x1, x2) = 9 x1 + 14 x2 -> max.
Das Simplexverfahren
Erstellen der Standardform• Die rechte Seite (RHS) einer Restriktion
(Nebenbedingung) darf nicht negativ sein.• Einführung der Schlupfvariablen (Y1-4)• Zielfunktion (F) ist mit (-1) multipliziert (optional).
Das Simplexverfahren
Erstellen der Standardform Basisvariablen
Nichtbasis=variablen
Basisvariablen
Das Simplexverfahren
Bestimmen der Pivotspalte• Der erste kleinste Zielfunktionskoeffizient
weist auf die Pivotspalte:
Das Simplexverfahren
Berechnung der Pivotzeile• Die Quote (Q) wird durch Division der rechten
Seite (RHS) durch die Pivotspalte bestimmt (Zeilenweise). RHS/Pivotspalte
Das Simplexverfahren
Berechnung der Pivotzeile• Die Zeile mit der niedrigsten positive Quote bildet die
Pivotzeile (hier 3).• Bei gleichen Werten wird die erste Schlupvariable
durch die Pivotspalte dividiert(Y1/ Pivotspalte) . Das niedrigere Ergebnis weist auf die Pivotzeile. (S. 29 Studienbrief oben)
Das Simplexverfahren
Bestimmung des Pivotelements• Im Schnittpunkt der Pivotzeile und der
Pivotspalte befindet sich das Pivotelement.
Das Simplexverfahren
Berechnung der 2. Simplextabelle• Da X2 den maximal möglichen Wert 3 annehmen soll,
kommt X2 in die Basis und Y4 wird Nichtbasisvariable.
Basis X1 X2 Y1 Y2 Y3 Y4 RHS
Y1 0Y2 0Y3 0Y4 1F 0
Inhalt der Y4-Spalte
Das Simplexverfahren
Berechnung der 2. Simplextabelle• Bestimmung der restlichen Elemente der
Pivotzeile inkl. RHS.Basis X1 X2 Y1 Y2 Y3 Y4 RHS
Y1 0Y2 0Y3 0X2 1F 0
Das Simplexverfahren
Berechnung der 2. Simplextabelle
Neubrechnung der Pivotzeile: Wert/ Pivotelement 0/1; 0/1; 0/1; 1/1; 3/1
Basis X1 X2 Y1 Y2 Y3 Y4 RHS
Y1 0
Y2 0
Y3 0
X2 0 1 0 0 0 1 3
F 0
Das Simplexverfahren
Berechnung der 2. Simplextabelle
Neuberechnung der restlichen Werte nach Schema: Wert – (Zeilenwert x Spaltenwert / Pivotelement) -9 – (0 x -14 : 1)
Basis X1 X2 Y1 Y2 Y3 Y4 RHS
Y1 0Y2 0Y3 0X2 0 1 0 0 0 1 3F -9 0
Das Simplexverfahren
Berechnung der 2. Simplextabelle
Umrechnung der restlichen Werte nach Schema: Wert – (Zeilenwert x Spaltenwert / Pivotelement) 8 – (3 x 2 : 1)
Basis X1 X2 Y1 Y2 Y3 Y4 RHS
Y1 0 2Y2 0Y3 0X2 0 1 0 0 0 1 3F -9 0
Das Simplexverfahren
Berechnung der 2. SimplextabelleNach Berechnung der restlichen Werte ergibt sich das
2. Simplextableau mit dem Zielwert 42
Basis X1 X2 Y1 Y2 Y3 Y4 RHS
Y1 1 0 1 0 0 -2 2Y2 1 0 0 1 0 -1 3Y3 1 0 0 0 1 0 5X2 0 1 0 0 0 1 3F -9 0 0 0 0 14 42
Das Simplexverfahren
Berechnung der 3. SimplextabelleDie Iterationsschritte werden solange fortgesetzt bis alle
Werte der Zielzeile positiv sind, dann ist keine weitere Verbesserung des Zielwertes mehr möglich.
Bestimmung des Pivotelements
Das Simplexverfahren
Berechnung der 3. Simplextabelle
• Pivotelement zur 4. Simplextabelle:
3. Tabelle
Das Simplexverfahren
Berechnung der 4. Simplextabelle
Erst mit der 4. Tabelle ist die Lösung mit Z = 64 erreicht:
Alle Nichtbasisvariablen in der Z-Zeile (hier F) haben einen positiven Koeffizienten Optimalitätskriterium
Z
BasIs
(Wurde eingangs nicht mit -1 multipliziert müssen alle Koeffizienten negativ sein)
Übungsaufgabe grafisch• Eine Studentin gründet eine Gesellschaft zur Produktion von Computerchips.• Sie hat die Möglichkeit monatlich bis zu 200 kg Silizium, 40 kg Kupfer, 20 kg Aluminium
zuzukaufen.• Die Entwicklungsabteilung entwirft 2 verschiedene Chip-Architekturen, deren Verkauf
vielversprechend erscheint.• Die Herstellungskosten sind für beide Bauarten gleich, so daß lediglich das Material den
Unterschied ausmacht.
• Die Marktanalyse ergibt einen erwarteten Gewinn von 400 € je kg Giga und 250 € je kg Nano.
• Welche Menge sollte sie monatlich herstellen und verkaufen um einen größtmöglichen Gewinn zu erwirtschaften.
• Stellen Sie das mathematische Modell auf und lösen Sie die Aufgabe grafisch.
Silizium Kupfer Aluminium
Chip Giga 75% 25% -
Chip Nano 75% - 25%
Lösung
• €400 x 160kg + €250 x 80kg = € 84.000.-0, )3(
80
160
80033 )2(
max250400)1(
21
2
1
21
21
xx
x
x
xx
xxZ Silizium Kupfer Aluminium
Chip Giga 75% 25% -Chip Nano 75% - 25%
Übungsaufgabe Simplex• Eine Studentin gründet eine Gesellschaft zur Produktion von Computerchips.• Sie hat die Möglichkeit monatlich bis zu 200 kg Silizium, 40 kg Kupfer, 20 kg Aluminium
zuzukaufen.• Die Entwicklungsabteilung entwirft 2 verschiedene Chip-Architekturen deren Verkauf
vielversprechend erscheint.• Die Herstellungskosten sind für beide Bauarten gleich, so daß lediglich die Materialkosten
den Unterschied ausmachen.
• Die Marktanalyse ergibt einen erwarteten Gewinn von 400 € je kg Giga und 250 € je kg Nano.
• Welche Menge sollte sie monatlich herstellen und verkaufen um einen größtmöglichen Gewinn zu erwirtschaften.
• Stellen Sie das mathematische Modell auf und lösen Sie die Aufgabe mit dem Simplexverfahren.
Silizium Kupfer Aluminium
Chip Giga 75% 25% -
Chip Nano 75% - 25%
Lösung
0, )3(
80
160
80033 )2(
max250400)1(
21
2
1
21
21
xx
x
x
xx
xxZSilizium Kupfer Aluminium
Chip Giga 75% 25% -Chip Nano 75% - 25%
Lösung
Das SimplexverfahrenDie Zweiphasenmethode
• Diese bisherige Form der Lösung eines Ungleichungssystems ist nur möglich wenn für alle Ungleichungen gilt.
• Kommen auch Bedingungen vor, so ist die Aufgabe nur mit der Zweiphasenmethode zu lösen.
• Gegeben sei folgende LO-Aufgabe mit einer
Restriktion (negative rechte Seite)
• I Z = 2X1 + X2 +2X3 max• II 2X1 - X2 4
X2 + 2X3 15 X1 + X3 = 8
• III X1, X2, X3 0
Die Zweiphasenmethode
• Umwandeln in Gleichungen durch das Einführen von nichtnegativen Schlupfvariablen.
• Umwandeln in ein Gleichungssystem von kanonischer Form durch Einführung künstlicher Variablen k1 - …. kn.
Leitfaden zur Zweiphasenmethode
Umformen
• Künstliche Variablen K gegen Null minimieren (Zk=-k1 … -kn;). Addition von Zk mit k-Restriktionen. Daraus entsteht eine neu Zielfunktion Zneu.
• Die neue Zielfunktion wird gemeinsam mit den Restriktionen nach der Umformung (Kanonische Form) in eine Simplextabelle übergeführt.
• Lösen des Simplexalgorithmus.• Weglassen der Spalten mit einem k, Z sollte null
sein.
Leitfaden zur ZweiphasenmethodeErste Phase
• Die verbleibenden Gleichungen (Restriktionen) werden jetzt mit der Zielfunktion aus der Angabe, ZOriginal. , harmonisiert.
• Elimination der Basisvariablen aus der Zielfunktion durch Subtraktion des x-fachen Wertes der Restriktionen, die diese Basisvariablen enthalten.
• Dadurch ergibt sich eine neue Zielzeile, Z2. Phase.
• Die verbleibenden Gleichungen (Restriktionen) werden jetzt mit Z2. Phase in einem weiteren Simplextableau verbunden.
• Das Lösen des Simplexalgorithmus bringt das Ergebnis
Leitfaden zur ZweiphasenmethodeZweite Phase
• Durch Multiplikation mit -1 wäre die negative rechte Seite erkennbar:
• Umformen der in Bedingung zur Lösung!
• I Z = 2X1 + X2 +2X3 max• II -2X1 + X2 -4
X2 + 2X3 15 X1 + X3 = 8
• III X1, X2, X3 0
Die Zweiphasenmethode
Negative rechte Seite nach Umformung
• Umwandeln in Gleichungen durch das Einführen von nichtnegativen Schlupfvariablen S (auch in der Zielfunktion).
• I Z = 2X1 + X2 +2X3 + 0S1 + 0S2 max• II 2X1 - X2 -S1 = 4
X2 + 2X3 +S2 = 15 X1 + X3 = 8
• III X1, X2, X3 , S1, S2 0
Die Zweiphasenmethode
• Ein Gleichungssystem heißt von kanonischer Form, wenn es in jeder Gleichung eine Unbekannte gibt, die nur in dieser vorkommt und dort den Koeffizienten plus Eins besitzt (nur S2 erfüllt dies):
• I Z = 2X1 + X2 +2X3 + 0S1 + 0S2 max• II 2X1 - X2 -S1 = 4
X2 + 2X3 +S2 = 15 X1 + X3 = 8
• III X1, X2, X3 , S1, S2 0
Die Zweiphasenmethode
Koeffizient -1
Kein S3
• Umwandeln in ein Gleichungssystem von kanonischer Form durch Einführung künstlicher Variablen k:• II 2X1 - X2 -S1 +k1 = 4
X2 + 2X3 +S2 = 15 X1 + X3 +k2 = 8
• III X1, X2, X3 , S1, S2 0
Die Zweiphasenmethode
Die ZweiphasenmethodeEin Gleichungssystem heißt von kanonischer Form, wenn es in jeder Gleichung eine Unbekannte gibt, die nur in dieser vorkommt und dort den Koeffizienten Eins besitzt.Diese Unbekannten bezeichnet man als Basisvariablen (BV), die übrigen als Nichtbasisvariablen (NBV).• II 2X1 - X2 -S1 +k1 = 4
X2 + 2X3 +S2 = 15 X1 + X3 +k2 = 8
• III X1, X2, X3 , S1, S2 0
• So stellt das Gleichungssystem ein äquivalentes Gleichungssystem kanonischer Form dar, deren künstliche Nichtbasisvariablen k den Wert Null aufweisen.
• Damit dem so ist, sollten die künstlichen Variable möglichst nahe bei Null sein.
• Einführung einer neuen Zielfunktion (minimiere K):
Die Zweiphasenmethode
Z = k1 + k2 min entspricht: `Z = -Z=-k1-k2max
• Die erste Phase der Hilfsaufgabe dient dazu eine kanonische Form und eine erste Basislösung zu gewinnen.
• I `Z = - k1 – k2 max
• II 2X1 - X2 -S1 +k1 = 4 X2 + 2X3 +S2 = 15
X1 + X3 +k2 = 8• III X1, X2, X3 , S1, S2 0
Die Zweiphasenmethode
• Elimination der Basisvariablen (k) aus der Zielfunktion durch Addition der Gleichungen in II zur Zielfunktion, die ein k beinhalten:
• I `Z = - k1 – k2 max • II 2X1 - X2 -S1 +k1 = 4
X2 + 2X3 +S2 = 15
X1 + X3 +k2 = 8• III X1, X2, X3 , S1, S2 0
Die Zweiphasenmethode
Die Zweiphasenmethode
X1 X2 X3 S1 S2 k1 k2 r.S. Quot.
0 0 0 0 0 -1 -1 0
2+1+0=3
0-1+0=-1
1+0+0=1
0-1+0=-1
0+0+0=0
0+1-1=0
1+0-1=0
8+4+0=12
2 -1 0 -1 0 1 0 4 2
0 1 2 0 1 0 0 15
1 0 1 0 0 0 1 8 8
• Nebenrechnung in einer Tabelle: Zeile 1 (Z‘) + Zeile 3 + Zeile 5 ergibt die neue Zielfunktion Z.
`Z +
+
+
Zneu
Die Zweiphasenmethode
X1 X2 X3 S1 S2 k1 k2 r.S. Quot.
0 0 0 0 0 -1 -1 0
3 -1 1 -1 0 0 0 12
2 -1 0 -1 0 1 0 4 2
0 1 2 0 1 0 0 15
1 0 1 0 0 0 1 8 8
• Zur besseren Übersicht sind im ersten Simplextableu zwei Zielfunktionen abgebildet.• Die untere Zielfunktionszeile stellt das Ergebnis der Addition dar.
`Z +
+
+
Zneu
X1 X2 X3 S1 S2 k1 k2 r.S. Quot.
Z 3 -1 1 -1 0 0 0 12
k1 2 -1 0 -1 0 1 0 4 2
S2 0 1 2 0 1 0 0 15k2 1 0 1 0 0 0 1 8 8
Lösen des Simplextableaus in der ersten Phase um eine erste zulässige Basislösung zu gewinnen. Achtung S1 ist keine Basisvariable.
Ordnen der Basisvarialen:X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 3 -1 1 -1 0 0 0 12
k1 2 -1 0 -1 1 0 0 4 2
S2 0 1 2 0 0 1 0 15
k2 1 0 1 0 0 0 1 8 8
Bestimmen einer neuen Basisvariablen:X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 3 -1 1 -1 0 0 0 12
k1 2 -1 0 -1 1 0 0 4 2
S2 0 1 2 0 0 1 0 15
k2 1 0 1 0 0 0 1 8 8
X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 0
X1 1 -0,5 0 -0,5 0,5 0 0 2
S2 0
k2 0
X1 wird neue Basisvariable dann folgt die Umrechnung der Pivotzeile: Wert/ Pivotelement:
Ausfüllen der restlichen Werte:X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 3 -1 1 -1 0 0 0 12
k1 2 -1 0 -1 1 0 0 4 2
S2 0 1 2 0 0 1 0 15
k2 1 0 1 0 0 0 1 8 8
X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 0 0,5 1 0,5 -1,5 0 0 6
X1 1 -0,5 0 -0,5 0,5 0 0 2
S2 0 1 2 0 0 1 0 15
k2 0 0,5 1 0,5 -0,5 0 1 6
Wert – (Zeilenwert x Spaltenwert / Pivotelement):
2. Iteration:X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 0 0,5 1 0,5 -1,5 0 0 6
X1 1 -0,5 0 -0,5 0,5 0 0 2 -
S2 0 1 2 0 0 1 0 15 7,5
k2 0 0,5 1 0,5 -0,5 0 1 6 6
X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 0
X1 0
S2 0
X3 1
Bestimmen einer neuen Basisvariablen:
2. Iteration:X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 0 0,5 1 0,5 -1,5 0 0 6
X1 1 -0,5 0 -0,5 0,5 0 0 2 -
S2 0 1 2 0 0 1 0 15 7,5
k2 0 0,5 1 0,5 -0,5 0 1 6 6
X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 0 0 0 0 -1 0 -1 0
X1 1 -0,5 0 -0,5 0,5 0 0 2
S2 0 0 0 -1 1 1 -2 3
X3 0 0,5 1 0,5 -0,5 0 1 6
Bestimmen der restliche Werte:
Durch Weglassen der Spalten mit den künstlichen Variablen k, kommt man zu einem Gleichungssystem von kanonischer Form:
X1 X2 X3 S1 k1 S2 k2 r.S. Quot.
Z 0 0 0 0 -1 0 -1 0
X1 1 -0,5 0 -0,5 0,5 0 0 2
S2 0 0 0 -1 1 1 -2 3
X3 0 0,5 1 0,5 -0,5 0 1 6
6 5,0 0,5X
3S-
2 5,0 0,5X - X II
132
21
121
SX
S
SBasisvariablen:
• Aufbauend auf dieses Gleichungssystem, wird nun die ursprüngliche Aufgabe gelöst:
• Die ursprüngliche ZielfunktionZ = 2X1 + X2 + 2X3
soll nur durch die Nichtbasisvariablen ausgedrückt werden. (in diesem Fall X2)
Die Zweiphasenmethode
• Dies wird durch Elimination der Basisvariablen X1 und X3 aus der Zielfunktion erreicht.
Die Zweiphasenmethode
6 5,0 0,5X
3S-
2 5,0 0,5X - X II
max2 2X I
132
21
121
321
SX
S
S
XX
Subtraktion des 2-fachen der 1. wie des 2-fachen der 3. Zeile von der Zielzeile:
Nebenrechnung:
6 5,0 0,5X
3S-
2 5,0 0,5X - X II
max2 2X I
132
21
121
321
SX
S
S
XX
NebenrechnungX1 X2 X3 S1 S2
Z 2 1 2 0 0 0- 2 -1 -1 0 4- 0 1 2 1 0 12
0 1 0 0 0 -16
|2x
Neue Zielzeile:
|2x
Neues Starttableau:X1 X2 X3 S1 S2 r.S. Quot.
Z 0 1 0 0 0 -16
X1 1 -0,5 0 -0,5 0 2
S2 0 0 0 -1 1 3
X3 0 0,5 1 0,5 0 6
Ordnen nach Basisvarialen:
X2 S1 X1 S2 X3 r.S. Quot.
Z 1 0 0 0 0 -16
X1 -0,5 -0,5 1 0 0 2 -
S2 0 -1 0 1 0 3 -
X3 0,5 0,5 0 0 1 6 12
Neues Starttableau:Bestimmen des Pivotelements:
X2 S1 X1 S2 X3 r.S. Quot.
Z 1 0 0 0 0 -16
X1 -0,5 -0,5 1 0 0 2 -
S2 0 -1 0 1 0 3 -
X3 0,5 0,5 0 0 1 6 12
X2 S1 X1 S2 X3 r.S. Quot.
Z 0 -1 0 0 -2 -28
X1 0 8
S2 0 3
X2 1 1 0 0 2 12
Ergebnistableau mit Z = 28, X1 = 8, X2 = 12, S2 = 3:
Beispiel Übungsklausur zur Zweiphasenmethode:
0,,,X
10 X
4 X-
82X
max2425 Z
4321
431
21
4321
4321
XXXIII
XX
X
XXXII
XXXXI