Lineare Optimierung - HTW Berlin · 2017. 2. 23. · Lineare Optimierung Teil 1 • Simplexalgorithmus 1 • Grundlagen • Beispiel Produktionsprogrammplanung • Graphische Lösung

Lineare OptimierungTeil 1

• Simplexalgorithmus

1

• Grundlagen

• Beispiel Produktionsprogrammplanung

• Graphische Lösung

HTW BerlinProf. Dr. F. Hartl

2

Was ist eine Lineare Optimierungsaufgabe?

Eine Standard-Lineare Optimierungsaufgabe (LOA) besteht aus

die lineare Zielfunktion z(x1,…,xn) = c1x1+…+cnxn

einen maximalen Wert z annimmt

und m lineare Nebenbedingungsbeziehungen (NB) in der Form

n nichtnegativen Entscheidungsvariablen x1,…,xn ,

die so zu bestimmen sind, dass

a11x1+ …+a1nxn b1

a11,…, amn, b1,…bm, c1,…,cn sind bekannte Zahlen.

am1x1+ …+amnxn bm

………………………… erfüllt sind.

1.NB:

m.NB:

3

Bearbeitungszeit in

h/ME

Verfügbare

Machinenkapazität in

h/Woche

Maschine P1 P2

M1 2 4 40

M2 3 2 24

M3 1 0 6

Bsp. Produktionsprogrammplanung (PPP) als LOP

• unterschiedlicher zeitlicher Aufwand in Stunden(h) pro Woche für die Fertigung einer Mengeneinheit(ME) eines Produktes

• Fertigung von 2 Produkten P1, P2 mit 3 Maschinen M1, M2 und M3

begrenzter Zeitkapazitäten.

• Deckungsbeitrag für P1 pro ME 500 GE bzw. für P2 pro ME 2000 GE.

ges.: PP (x1,x2) mit max. Gesamtdeckungsbeitrag

4

gesucht:

x1 - von Produktart 1 produzierte und verkaufte Menge

x2 - von Produktart 2 produzierte und verkaufte Menge

Zielfunktion: Z(x1, x2) = 500 x1 + 2000 x2 maximiere

Mathematisches Modell des PPP

NNB: x1 0, x2 0.

NB: M1-Restriktion: 2 x1 + 4 x2 40

M2-Restriktion: 3 x1 + 2 x2 24

M3-Restriktion x1 6

zulässiger Lösungs-bereich X des LOP

wobei

X

Schritt 1: Darstellung des zulässigen Lösungsbereiches X

Nebenbedingungen:


NNB:

x1 0 x2 0 1.Quadrant

grafische Lösung eines LOP mit 2 Entscheidungsvariablen x1 und x2

Der Bereich X wird bestimmt durch die Durchschnittsmenge aller Halbebenen


5

M3-Restriktion: x1 6

6

2x1+4x2 <= 40

3x1+2x2<=24

x1 <= 6

X

Schlussfolgerungen bezüglich des Lösungsgebietes X

• X besitzt endlich viele Ecken, wenn X nichtleer(im Bsp. 5 Ecken ein Pentagon)

P1(0,0), P2(6,0),

• X ist ein konvexesPolyeder der Ebene

• Eckpunkte sind

P3(6,3), P4(2,9), P5(0,10)

Satz: Besitzt LOA eine Optimallösung, kann sie auf Grund der linearen Zielfunktion nur auf dem Rand von X (in Ecken von X) liegen.

Zielfunktion: Z(x1, x2) = 500 x1 + 2000 x2 max

Schritt 2: schnelle Eckpunktsuche mit maximalem Z-Wert

2x1+4x2 <= 40

3x1+2x2<=24

x1 <= 6

X


stets Startpunkt P1(0,0) Z1(0,0) = 0

P2(6,0) Z2(6,0) = 3.000

P3(6,3) Z3(6,3) = 9.000

P4(2,9) Z4(2,9) = 19.000

P5(0,10) Z5(0,10) = 20.000Max

Fasse die Zi-Werte als Höhen von Eckpfeiler auf und legt darauf das Dach (Ebene) Z(x1,x2) . Optimaler Weg: Gehe von P1(0,0) sofort in Richtung positiver x2 Werte. Richtung steilster Anstieg

(0,0)

(0,10)

7

Z(x1, x2) = 500 x1 + 2000 x2 grad Z =

oder mittels Gradienten

2x1+4x2 <= 40

3x1+2x2<=24

x1 <= 6

X


Z(0,10) = 20.000 Max

(0,0)

(0,10)

8

Annahme z = 2000 Z(x1, x2) = 500 x1 + 2000 x2 = 2000

oder durch Einzeichnen einer höchstmöglichen Isolinie

2x1+4x2 <= 40

3x1+2x2<=24

x1 <= 6

X


Z(0,10) = 20.000 Max

(0,0)

(0,10)

9

10

Rechnerische Bestimmung der Eckpunktlösungen mittels Simplexverfahren

• Suche von dieser Ecke aus eine benachbarte zulässige Ecke mit größerem Z-Wert.

• Bestimme über ein LGS eine zulässige Ecke und berechne den zugehörigen Zielfunktionswert Z.

• Gibt es keine solche zulässige Ecke mehr, dann ist die optimale Ecke erreicht (es werden also nicht alle zulässigen Ecken benötigt).

G. B. Dantzig, 1947

11

2 x1 + 4 x2 + 1y1 = 40

3 x1 + 2 x2 +1y2 = 24

1 x1 + 0 x2 +1y3 = 6

2 x1 + 4 x2 40

3 x1 + 2 x2 24

1 x1 + 0 x2 6

Die Entscheidungsvariablen x1, x2 und die Schlupfvariablen y1, y2 , y3 sind nichtnegativ.

Die Schlupfvariablen stehen für die freie Kapazität der jeweiligen Nebenbedingung.

Ungleichungs-form

erweiterte Gleichungsform durch Einfügen von Schlupfvariablen

1. Schritt: Überführung des Ungleichungssystems in die erweiterte Gleichungsform

12

2. Schritt: Überführung der Gleichungsform in die Tabellenform

BV: Basisvariable=Variable mit Faktor 1 und nur in einer Zeile vorhanden.

BV x1 [ME] x2 [ME] y1 [M1 h] y2 [M2 h] y3 [M3 h] z b

y1 2 4 1 0 0 0 40

y3 1 0 0 0 1 0 6

Z -500 -2000 0 0 0 1 0

y2 3 2 0 1 0 0 24

Gleichungsform

Tabellenform

2 x1 + 4 x2 +1y1 = 40

3 x1 + 2 x2 +1y2 = 24

1 x1 +1y3 = 6

-500 x1 - 2000 x2 + z = 0

z = 500 x1 + 2000 x2

so umformen, dass alle Variablen links von = stehen.

13

Auswertung der Ausgangstabelle

BV x1 x2 y1 y2 y3 z b

y1 2 4 1 0 0 0 40

y2 3 2 0 1 0 0 24

y3 1 0 0 0 1 0 6

Z -500 -2000 0 0 0 1 0

Da ein Eckpunkt in der Ebene jeweils ein Schnittpunkt zweier Begrenzungsgeradenist, müssen die zwei frei wählbaren Variablen x1 und x2 gleich Null gesetzt werden.

m=3 Variable sind bestimmbar, wenn jeweils 2 von den insgesamt 5 Variablen (die sogenannten Nichtbasisvariablen (NBV)) frei gewählt werden.

x1=0,

Das LGS hat m=3 Gleichungen, n= 2 Entscheidungsvariable und insgesamt n+ m=5 Variable ist unterbestimmt.

m=3

n+m = 2+ 3= 5 Variablex1 = 0 x2 = 0

y1 = 40

y2 = 24

y3 = 6

Z = 0

Die 1. Basislösung lautet:

z= 0x2=0, y1=40, y2=24, y3=6,

14

Suche die benachbarte Ecke mit höchstmöglichem Zielwert?

Auswahlregel für neue BV

Wähle eine derjenigen NBV als BV aus, deren Zielzeilenkoeffizient am „negativsten“ ist.


y1 2 4 1 0 0 0 40

y2 3 2 0 1 0 0 24

y3 1 0 0 0 1 0 6

Z -500 -2000 0 0 0 1 0

Wähle eine NBV als neue BV aus, also x1 oder x2. Um am schnellsten zum hohen Z Wert zu gelangen, wird x2 neue BV. (siehe z = 500x1+2000x2)

Die Variable x1 bleibt NBV- also x1=0 - ,sonst kommt man nicht zum benachbarten Eckpunkt.

Da die z-Funktion umgestellt wurde, um sie in die Tabelle zu übertragen, beachte:

Die zugehörige Spalte wird als Pivotspalte (PS) bezeichnet.

x1=0

Welche BV muss der neuen BV x2 weichen?

PS

15

Quotientenbestimmung Q = bi/ aiPS

PZ

Ist die neue BV ausgewählt, so muss ermittelt werden, um wie viel diese Variable von ihrem bisherigen Wert 0 aus maximal erhöht werden darf, ohne dass der zulässige Bereich verlassen wird.

Q

40/4

24/2

-

minimaler

Quotient


y1 2 4 1 0 0 0 40

y2 3 2 0 1 0 0 24

y3 1 0 0 0 1 0 6

Z -500 -2000 0 0 0 1 0


y1 2 4 1 0 0 0 40

y2 3 2 0 1 0 0 24

y3 1 0 0 0 1 0 6

Z -500 -2000 0 0 0 1 0

PS

Pivotzeile (PZ) – Regel:

Wähle diejenige Zeile als PZ, bei der der zeilenweise gebildete Quotient aus dem absoluten Glied bi und dem Element aiPS der PS, sofern positiv, minimal ist.

PS

Nun muss eine Basistransformation mit den NBV x1=0,y1=0 und den BV x2, y2, y3

erfolgen.

Neue BV = x2

Neue NBV ?

1000

16


y1 2 4 1 0 0 0 40

y2 3 2 0 1 0 0 24

y3 1 0 0 0 1 0 6

Z -500 -2000 0 0 0 1 0

Basistransformation: y1,y2,y3 x2,y2,y3

mittels erweitertem Eliminationsverfahren von Gauß

PZ

PS


PE PZ/PE

2.Zeile - 2* PZ/PE

Z-Zeile - (-2000)* PZ/PE

Wenn x2 BV sein soll, muss im neuen Tableau in der x2 Spalte zuerst eine 1 und dann Nullen stehen.

Dies gelingt, wenn:

x1 =0 x3 =0

x2 = 10

y2 = 4

y3 = 6

Z = 20.000

2. Eckpunktlösung

x2y2

y3Z

0100

0010

0001

2/4 1/4 40/4

3-2*2/4=2 0-1*2/4=-1/2 24-40*2/4=4

1 0 6 -500-2*(-2000)/4=

500 0-1*(-2000)/4=

500 0-40*(-2000)/4=

20000

17

Optimalitätsüberprüfung der 2. Tabelle

• Wenn alle Werte in der Z-Zeile nichtnegativ sind, hat die

Zielfunktion stets ihr Extremum erreicht.


x2 1/2 1 1/4 0 0 0 10

y2 2 0 - 1/2 1 0 0 4

y3 1 0 0 0 1 0 6

Z 500 0 500 0 0 1 20.000

• Beweis: wenn x1>0 und/oder y1 >0 , dann wird z < 20.000 ,

da jetzt Z = 20.000- 500x1-500y1

x1 = 0 y1 = 0

18

x2 = 10 – 1/2 x1 – 1/4 y1

y2 = 4 – 2 x1 + 1/2 y1

y3 = 6 – 1 x1 - 0 y1

z = 20.000 – 500x1 – 500 y1

Entscheidungsvariable : x1 , x2 Optimale Produktionsmengen: x1 = 0 , x2 = 10

Schlupfvariable y1 y2 y3 geben Kapazitätsauslastung an:

y1 = 0, Maschine 1 hat 0 Stunden freie Kapazität, ist somit ausgelastet,

maximaler Zielfunktionswert: z(0,10) = 20.000 GE

y2 = 4, Maschine 2 hat 4 Stunden freie Kapazität.

y3 = 6, Maschine 3 hat 6 Stunden freie Kapazität, wird also nicht eingesetzt.

Auswertung des optimalen Tableaus

Tabellenform


x2 1/2 1 1/4 0 0 0 10

y2 2 0 - 1/2 1 0 0 4

y3 1 0 0 0 1 0 6

Z 500 0 500 0 0 1 20.000

x1 = 0 y1 = 0

Lösungs-Gleichungsform

Basisvariable : x2 , y2 , y3

Nichtbasisvariable : x1 , y1 , werden stets Null gesetzt

19

x2 = 10 – 1/2 x1 – 1/4 y1

y2 = 4 – 2 x1 + 1/2 y1

y3 = 6 – 1 x1 - 0 y1

z = 20000 – 500x1 – 500 y1

Was wäre, wenn von dem optimalen Produktionsprogramm abgewichen wird und die Menge x1 (bisher x1=0) vom Produkt P1 auf x1 = 1 gesetzt wird (weiterhin y1=0) ?

Der Zielfunktionswert vermindert sich um 500 GE.

Die freie Kapazität der Maschine M2 vermindert sich um 2 h/Woche.

Die Produktmenge x2 von P2 vermindert sich um 1/2 ME.

Die freie Kapazität Maschine M3 vermindert sich um 1 h/Woche.

x1 = 1 Produktmenge von P1

= Opportunitätskosten

20

x2 = 10 – 1/2 x1 – 1/4 y1

y2 = 4 – 2 x1 + 1/2 y1

y3 = 6 – 1 x1 - 0 y1

z = 20000 – 500x1 – 500 y1

Was wäre, wenn von dem optimalen Produktionsprogramm abgewichen wird und die freie Kapazität y1 (bisher y1=0) der Maschine M1 auf y1=1 gesetzt wird (weiterhin x1=0) ?

y1 = 1 freie Kapazität auf M1

= Opportunitätskosten

Der Zielfunktionswert vermindert sich um 500 GE.

Die freie Kapazität von M2 erhöht sich um ½ h/Woche.

Die Produktmenge x2 von P2 vermindert sich um ¼ ME.

Die freie Kapazität von M3 bleibt unverändert 6 h/Woche.

21

Jede Iteration besteht aus folgenden drei Schritten:

Zusammenfassung:Primaler Simplex-Algorithmus

Schritt 3: Austausch einer BV gegen eine NBV nach den Regeln der

elementaren Basistransformation

so gelangen wir stets von einer zulässigen zu einer anderen

zulässigen Basislösung mit größerem oder gleichem Zielfunktionswert.

Schritt 2:Wahl der Basisvariablen, die in eine Nichtbasisvariable umgewandelt werden soll ( Pivotzeile ) Suche den minimalen Quotienten aus den Werten der b-Spalte sowie den zugehörigen positiven Werten der Pivotspalte.Das Element aPZ PS heißt Pivotelement.

Schritt 1:

Wahl der Nichtbasisvariablen , die in eine Basisvariable umgewandelt werden soll ( Pivotspalte )Suche in der Z-Zeile den „negativsten“ Koeffizienten.

22

Zusammenfassung des Simplex Algorithmus

23

Vorgehensweise zur Lösung eines Standardmaximierungsproblems

B. Auer, F. Seitz, Grundkurs Wirtschaftsmathematik, DOI 10.1007/978-3-658-02734-6_22,© Springer Fachmedien Wiesbaden 2013

24

Bearbeitungszeit in

h/ME

Machinenkapazität in

h/Woche

Maschine P1 [t] P2 [t]

M1 2 4 40

M2 3 2 24

M3 1 0 6

Übung PPP-2

Zur Fertigung von P1 und P2 werden die drei Maschinen M1, M2 und M3 eingesetzt.

Die Deckungsbeiträge betragen sowohl für P1 als auch für P2 pro Tonne 500 €.

Die pro Woche verfügbare Maschinenkapazität in Stunden (h) sowie die Bearbeitungszeiten in Stunden [h] je Tonne durch die jeweilige Maschine sind der folgenden Tabelle zu entnehmen.

ges.: PP (x1,x2) mit max. Gesamtdeckungsbeitrag

25

rechnerische Lösung

BV x1 x2 y1 y2 y3 b

y1 2 4 1 0 0 40

y2 3 2 0 1 0 24

y3 1 0 0 0 1 6

Z -500 -500 0 0 0 0

y3 0 0 1/4 -1/2 1 4

x2 0 1 3/8 -1/4 0 9

x1 1 0 -1/4 1/2 0 2

Z 0 0 125/2 125 0 5500

Q

20

8

6

7

3

-

4

-

6

Zulässige Eckpunktlösungen

6

24

40

0

0

3

2

1

2

1

y

y

yx

x

0

6

280

6

y

y

yx

x

3

2

1

2

1

0

0

163

6

y

y

yx

x

3

2

1

2

1

4

0

09

2

y

y

yx

x

3

2

1

2

1

y1 0 0 1 -2 4 16

x2 0 1 0 1/2 -3/2 3

x1 1 0 0 0 1 6

Z 0 0 0 250 -250 4500

zulässige und optimale

Eckpunktlösung mit z=5.500 GE

y1 0 4 1 0 -2 28

y2 0 2 0 1 -3 6

x1 1 0 0 0 1 6

Z 0 -500 0 0 500 3000

2 x1 + 4 x2 +1y1 = 40

3 x1 + 2 x2 +1y2 = 24

1 x1 +1y3 = 6

-500 x1 - 500 x2 + z = 0

Hinweis:Da zwei

gleichgroße negative Werte in z-Zeile den erstenWert auswählen.

Opt.PP

26

Grafische Auswertung

Das optimale PP ist x1= 2 ME und x2 = 9 ME

Der Gesamt-deckungsbetrag ist Z(2,9) = 500*2+500*9 = 5.500 GE

Hinweis: um vom Startpunkt (0,0) über die benachbarten Punkte zum Punkt (2,9) zu gelangen, gibt es zwei Wege: entweder (0,0)-(6,0)-(6,3)-(2,9) oder (0,0)-(0,10)-(2,9). Bei der rechnerischen Lösung sind wir den ersten Weg gegangen mit notwendig 4 Tabellen.

(1.) (2.)

(3.)

(4)

Eine Tabelle hätten wir beim zweiten Weg weniger, was aber bei den zwei gleichen negativen Werte in der Z-Zeile nicht unmittelbar vorhersagbar war.

Documents

Lineare Optimierung - HTW Berlin · 2017. 2. 23. · Lineare Optimierung Teil 1 • Simplexalgorithmus 1 • Grundlagen • Beispiel Produktionsprogrammplanung • Graphische Lösung