Operations Research

Operations ResearchSonderfälle der Simplexmethode

Gegeben sei folgende LO-Aufgabe:

◦ I Z = 2X1 + X2 max◦ II -X1 + 2X2 12

X1 – 4X2 4-X1 + X2 2

◦ III X1, X2 0

LO-Aufgabe mit unbeschränkten Zielwert

Nach dem Einfügen der drei Schlupfvariablen ergibt sich folgendes Starttableau:

LO-Aufgabe mit unbeschränkten Zielwert

Und folgendes Endtableau:

LO-Aufgabe mit unbeschränkten Zielwert

Steht über einem negativen Zielkoeffizienten kein positiver Koeffizient, so gibt es zulässige Lösungen, aber keinen maximalen Zielwert.

Dies führt zu folgendem allg. Lehrsatz:negativer Zielkoeffizient

Grafisch betrachtet entsteht ein offener Zielbereich:

LO-Aufgabe mit unbeschränkten Zielwert

Zu jeder Maximierungsaufgabe gibt es eine entsprechende Minimierungsaufgabe. Die Lösungen sind ident, nur in ihrem Vorzeichen verschieden.

Minimierungsaufgaben

min3 21 xxZ max3 21* xxZZ

Nebenbedingungen bleiben gleich!

)1(

Beispiel:

Minimierungsaufgaben

14maxmin ZZ

Starttableau

2. Simplextableau

Endtableau

max)1(min3 21 xxZ

Weist eine Nichtbasisvariable den Wert Null auf, gibt es weitere optimale Lösungen.

Mehrfachlösungen

Starttableau

1. Endtableau

X2 weist den Wert Null auf, steht aber nicht in der Basis.

Basis

max2 321 xxxZBsp.:

Mehrfachlösungen

Basis X1 X2 X3 Y1 Y2 Y3 RHS

Y1 -1 0 0 1 4 -3 5

X2 0 1 0 0 2 -1 2

X3 1 0 1 0 -1 1 1

F 1 0 0 0 0 1 4

Wird trotz aller positiver Zielkoeffizienten nach X2 weiteriteriert, kommt man zu einem weitern 2. identen Ergebnis.

4122101 xZProbe durch Einsetzen in die Zielfunktion:

Da Y2 als Nichtbasisvariable wieder den Wert Null aufweist kommt man durch weiteriterieren (Y2 als Pivotspalte) zu einem nächsten optimalen Ergebnis mit dem Wert Z = 4.

Woran erkennt man eine Basisvariable, woran eine Nichtbasisvariable?

Zusammenfassende Fragen:

Basis X1 X2 X3 Y1 Y2 Y3 RHS

Y1 -1 0 0 1 4 -3 5

X2 0 1 0 0 2 -1 2

X3 1 0 1 0 -1 1 1

F 1 0 0 0 0 1 4

Setzen Sie beide Ergebnisse aus dem Unterkapitel Mehrfachlösungen in die Zielfunktion

ein und überprüfen Sie die Lösungen.

max2 321 xxxZ

Basis X1 X2 Y1 Y2 Y3 Y4 RHS QuoteY1 0 0 1 0 -0,2 0,4 2 5

Y2 0 0 0 1 1,6 -0,2 8 +

X2 0 1 0 0 -0,4 -0,2 2 +

X1 1 0 0 0 0,6 -0,2 6 +

Z 0 0 0 0 1 0 4

Auflösung:

Basis X1 X2 Y1 Y2 Y3 Y4 RHSY4 0 0 2,5 0 -0,5 1 5Y2 0 0 -0,5 1 1,6 0 9X2 0 1 -0,5 0 -0,5 0 3X1 1 0 -0,5 0 0,5 0 7Z 0 0 0 0 1 0 4

Z = X1-X2 = 7-3 = 4

Z = X1-X2 = 6-2 = 4

Grafische Darstellung:

Auflösung:

X1

2x

Ist die ursprüngliche LO-Aufgabe lösbar, dann ist auch die entsprechende duale Aufgabe lösbar.

Die Zielwerte der beiden Aufgaben stimmen in diesen Fällen überein.

Die ursprüngliche Maximierungsaufgabe wird primale Aufgabe genannt.

Die zugehörige Minimierungsaufgabe, wird duale Aufgabe genannt.

Dualität der linearen OptimierungZu jeder Maximierungsaufgabe gibt es eine

entsprechende Minimierungsaufgabe!

(I) Z=X1 - X2 - 2X3 max (II) +X1 + X2 - X3 >= 16 2X1 + X2 + X3 <= 30 X1 +X3 >= 10 (III) X1, X2, X3 >= 0

Dualität der linearen OptimierungBeispielaufgabe

Vor der Formulierung der dualen Aufgabe werden alle Restriktionen durch Multiplikation mit (-1) zu Bedingungen umgewandelt.

(II) -X1 - X2 + X3 -16 2X1 + X2 + X3 30 -X1 - X3 -10

Die umformulierte LO-Aufgabe wird in ein abgekürztes Schema geschrieben und anschließend in eine Minimierungsaufgabe umgewandelt:

Dualität der linearen OptimierungBeispielaufgabe

X1 X2 X31 -1 -2 max-1 -1 1 -162 1 1 30-1 0 -1 -10

Die Umformung in eine Minimierungsaufgabe erfolgt durch Tausch der Zielzeile mit der rechten Seite. Anschließend werden die zentralen Variablen spaltenweise transponiert:

Dualität der linearen OptimierungBeispielaufgabe

)1,2 ,1( 12 1

S1 S2 S3

-16 30 -10 min

-1 2 -1 1

-1 1 0 -1

1 1 -1 -2

1-11 0 11-1-21-

Matrix rte tranponie10 11 1 2 1 11

Wieder mit (-1) multiplizieren um nur Bedingungen und die max-Form zu haben.

Dualität der linearen OptimierungBeispielaufgabe

S1 S2 S3

-16 30 -10 min1 -2 1 -11 -1 0 1-1 -1 1 2

Anschließend wird die Starttableau erstellt:

Duale Aufgabe:

Da die rechte Seite neg. ist, weist der tiefste Wert auf die Pivotzeile:

Dualität der linearen OptimierungBeispielaufgabe

Berechnung der Quote:

Zielzeile (F) Pivotzeile 30/-2=15

Niedrigste Wert weist auf die Pivotspalte.

Nach weiteren Iterationen ergibt sich folgendes Endtableau:

Dualität der linearen OptimierungBeispielaufgabe

primal max,dual min,

maxmin

Z

12:undZ

ZZ

Gegeben sei folgende LO-Aufgabe:

◦A.)Lösen Sie diese Aufgabe grafisch und schraffieren Sie den Bereich der zulässigen Lösungen.

Übungsbeispiel 1

0, x)(4 x

3 2046x )(

max4x5 Z)(

21

21

2

21

21

xIIIx

xxIIxI

Lösung 1

Z=5x1 + 4x2 = 5 x 2 + 4 x 2 = 18

Gegeben sei folgende LO-Aufgabe:

◦A.)Lösen Sie diese Aufgabe grafisch und schraffieren Sie den Bereich der zulässigen Lösungen.

◦ Zeichnen Sie den Vertreter der Zielgeradenschar ein und benennen Sie ihn mit a.

Übungsbeispiel 2

0, x)(1832x

4 x 22x

10 x)(maxx2 Z)(

21

21

21

21

21

21

xIIIxxxxIIxI

Lösung 2A

B.) Benennen Sie in der Zeichnung die Eckpunkte mit A, B, … und geben Sie die entsprechenden Koordinaten an.

Wie lautet die Optimallösung und der maximale Zielwert.

Übungsbeispiel 2b

Lösung B

C.) Wie lautet Ihre Lösung falls die Zielfunktion Z = x1-x2max lautet?

Tragen Sie in Ihr Diagramm einen Vertreter der neuen Zielgeradenschar ein und benennen Sie Ihn mit dem Buchstaben b.

Übungsbeispiel 2c

Lösung CFür Z=0 (Vertreter der Geradenschar)x1=x2

Alle Punkte der Strecke BC führen zum maximalen Z

(C)Somit ergibt sich Zmax=7-3=4(B) Zmax=6-2=4

D.)Wie verändert sich die Lösbarkeit wenn Sie die Restriktion x1 + x2 <= 10 unter (II) weglassen?

Übungsbeispiel 2d

0, x)(1832x

4 x 22x

10 x)(maxx2 Z)(

21

21

21

21

21

21

xIIIxxxxIIxI

Lösung D D.)Es existieren Lösungen, aber keine mit einem maximalen

Ziel. Durch den Wegfall der Geraden CD ist der Zielraum offen.

E.)Formulieren Sie die duale Aufgabe unter Verwendung der zugehörigen echten Variablen.

Übungsbeispiel 2e

0, x)(1832x

4 x 22x

10 x)(maxx2 Z)(

21

21

21

21

21

21

xIIIxxxxIIxI

Lösung E E.) Umwandeln zu <= und spaltenweises

transponieren:X1 X22 1 max

1 1 10

-2 1 -2

1 -1 4

-2 -3 -18

S1 S2 S3 S410 -2 4 -18 min

1 -2 1 -2 2

1 1 -1 -3 1

0,,,s )(13s

222s )(min1842s10 Z)(

:

4321

4321

4321

4321

sssIIIssssssII

sssIbeDualeAufga