ZU DEN KURSEN!

Operations Research - Zweiphasenmethode

Kursangebot | Operations Research | Zweiphasenmethode

Operations Research

Zweiphasenmethode

Das bisher diskutierte Simplex-Verfahren ist anwendbar

  • für Maximierungsprobleme

  • wenn positive Werte auf der rechten Seite stehen,

  • für den Fall, dass eine Ausgangslösung unmittelbar abgelesen werden kann (= Zulässigkeit).

Beispiel

Hier klicken zum Ausklappen Wir betrachten das Problem
2x1 + x2 ≥ 8
3x1 + 3x2 ≥ 12
x1 + 3x2 ≥ 6
x1, x2 ≥ 0.

Die Zielfunktion ist K: 10x1 + 12x2 →  min!

Bestimme die Lösung mit der Zweiphasenmethode.

Für das betrachtete Minimierungsproblem sind die o.e. Forderungen nicht erfüllt:

Es liegt ein Minimierungsproblem vor, die rechten Seiten sind negativ, wenn die „≥“-Zeichen durch Multiplikation mit –1 zu „≤“ gemacht werden. Da außerdem der Nullpunkt x1 = x2 = 0 unzulässig ist (so ist z.B. 2x1 + x2 = 2·0 + 0 = 0 nicht größer oder gleich 8), ist keine Ausgangslösung unmittelbar ablesbar.

Es gibt aber nun Möglichkeiten, die drei Voraussetzungen zu erfüllen:

1. Voraussetzung ... Maximierungsproblem

Wir machen aus der Minimierungsaufgabe ein Maximierungsproblem, indem die Zielfunktion mit – 1 multipliziert wird: aus K: 10x1 + 12x2 →  min! wird dann -K: -10x1 – 12x2  →  max!

Expertentipp

Hier klicken zum Ausklappen Aus einer Minimierungsaufgabe lässt sich stets eine Maximierungsaufgabe erstellen (und umgekehrt), wenn man die Zielfunktion mit „-1“ multipliziert.

2. Voraussetzung: positive rechte Seite

Die rechten Seiten sind im vorliegenden Problem positiv, deshalb ist hier nichts zu verändern.

3. Voraussetzung: Zulässigkeit

Die Ausgangslösung x1= x2 = 0 ist hier nicht zulässig, da sie die Restriktionen nicht erfüllt (wie oben beispielhaft vorgerechnet). Man fügt die Schlupfvariable yimit negativem Vorzeichen ein, wenn es sich um eine „≥“-Restriktion handelt. Das liegt daran, dass auch für yi die Nichtnegativitätsbedingungen yi ≥ 0 gelten sollen. So ist z.B. für die zweite Restriktion 3x1 + 3x2 ≥ 12 die Darstellung in Gleichungsform 3x1 + 3x2 – y2 = 12, denn wenn y2 ≥ 0 ist, gilt – y2 ≤ 0 und es wird von 3x1 + 3x2 (was größer oder gleich null ist) etwas abgezogen, um auf 12 zu kommen.

Expertentipp

Hier klicken zum Ausklappen - bei ≥-Restriktionen wird die Schlupfvariable ymit einem Minus-Zeichen eingeführt

- bei ≤-Restriktionen bleibt es hingegen bei yi mit einem Plus-Zeichen

Also gilt hier

x1

x2

y1

y2

y3

RS

y1

2

1

-1

0

0

8

y2

3

3

0

-1

0

12

y3

1

3

0

0

-1

6

-10

-12

0

0

0

Tab. 13: Ein unzulässiges Ausgangstableau

Beim vorliegenden Tableau handelt es sich um ein Maximierungsproblem mit rechter Seite, die ausschließlich positive Elemente enthält, die ersten beiden eingangs erwähnten Voraussetzungen sind also erfüllt.

Hingegen gibt es Probleme mit der unmittelbaren Ablesbarkeit. So steht in der ersten Zeile (für x1 = x2 = 0 als Ausgangslösung) – y1 = 8, d.h. y1 = -8. Dies genügt aber nicht der Nichtnegativitätsbedingung y1 ≥ 8. Deshalb ist das Tableau noch unzulässig. Für die unmittelbare Ablesbarkeit (und damit Zulässigkeit) führt man künstliche Variablen kj ein, und zwar genau dort, wo bislang in der Zeile nur – 1 stand.

Hier also in allen drei Zeilen:

x1

x2

y1

y2

y3

k1

k2

k3

RS

k1

2

1

-1

0

0

1

0

0

8

k2

3

3

0

-1

0

0

1

0

12

k3

1

3

0

0

-1

0

0

1

6

-10

-12

0

0

0

0

0

0

Tab. 14: Ein zulässiges Ausgangstableau

Nun sind alle formalen Forderungen erfüllt. Die rechte Seite ist positiv, es handelt sich um eine Maximierungsaufgabe und es ist – weil in jeder Zeile eine +1 steht – eine Lösung unmittelbar abzulesen.

Merke

Hier klicken zum Ausklappen Die künstlichen Variablen kj sind dazu da, um die Zulässigkeit herzustellen
• sie sind ablesbar als zulässige Ausgangslösung
• sie werden ausschließlich aus rechentechnischen Gründen eingeführt
• sie sind aber nicht interpretierbar, haben also keine inhaltliche Bedeutung
• sie sollten deswegen stets Nichtbasisvariablen werden.


Der letzte Punkt ist entscheidend für die Zwei-Phasen-Methode. Um die kj zu Nichtbasisvariablen zu machen, muß man sie zu null kriegen. Dies eröffnet die Möglichkeit, sich auf das Tableau zu beschränken, das lediglich x1, x2, y1, y2, y3 enthält.

Wie macht man eine Variable möglichst schnell zu einer Nichtbasisvariablen?

Die Antwort ist klar, wenn man sich anschaut, wie man eine Variable umgekehrt zu einer Basisvariablen macht: nämlich dadurch, dass ihr Zielfunktionskoeffizient möglichst groß ist und es sich deshalb lohnt, sie ins Programm reinzunehmen. Dadurch wird sie größer als null und also Basisvariable.

Deswegen führt man eine zusätzliche (fiktive) Zielfunktion K´ ein, in der die künstlichen Variablen kj möglichst niedrig bewertet werden. Dies lässt sich dadurch erreichen, dass man folgende Funktion betrachtet:

K´: k1 + k2+ k3 → min!   -K´: - k1 – k2 – k3 → max.

Die übrigen Variablen gehen mit null ein und werden also nicht berührt. Man erhält das Tableau

x1

x2

y1

y2

y3

k1

k2

k3

RS

k1

2

1

-1

0

0

1

0

0

8

k2

3

3

0

-1

0

0

1

0

12

k3

1

3

0

0

-1

0

0

1

6

K

-10

-12

0

0

0

0

0

0

0

0

0

0

0

0

-1

-1

-1

0

Tab. 15: Zweiphasenmethode mit Hilfszielfunktion

Die Idee ist nun, die künstlichen Variablen k1, k2, k3 möglichst schnell zu eliminieren. Wir betrachten deswegen zunächst die Zielfunktion K´ statt K und versuchen, die hinteren Zahlen –1 zu 0 zu kriegen. Dies macht man, indem man die –1 mit den +1 oben bei kj verrechnet, hier also die jeweiligen Zeilen addiert. Da man dies für alle Spalten macht, auch und gerade für x1, x2, y1, y2, y3, resultiert

x1

x2

y1

y2

y3

k1

k2

k3

RS

k1

2

1

-1

0

0

1

0

0

8

k2

3

3

0

-1

0

0

1

0

12

k3

1

3

0

0

-1

0

0

1

6

K

-10

-12

0

0

0

0

0

0

0

K´*

6

7

-1

-1

-1

0

0

0

26

Tab. 16: Künstliche Variablen sind eliminiert

So erhält man z.B. die Zahl 7 durch die Elemente der x2-Spalte: 1 + 3 + 3 = 7. Ebenso rechnet man 6 = 2 + 3 + 1 in der x1-Spalte und 7 = 1 + 3 + 3 in der x2-Spalte usw.

Entscheidend ist, dass die kj nun eine null in der Zielfunktionszeile haben. Dadurch erst ist die Zulässigkeit gewährleistet. Das vorliegende Tableau ist damit das Ausgangstableau der Zwei-Phasen-Methode.

Methode

Hier klicken zum Ausklappen

KOCHREZEPT ZWEI-PHASEN-METHODE:


Vorbereitung
- füge künstliche Variablen kj ein
- füge eine zusätzliche (fiktive) Zielfunktion K´ ein

- erzeuge Nullen unter den künstlichen Variablen kjin dieser zusätzlichen Zielfunktion

- erhalte damit eine „neue“ Zielfunktion K´*

Erste Phase

- benutze ausschließlich K´* als Zielfunktion

- mache die künstlichen Variablen kjdurch Simplex-Schritte zu Nichtbasisvariablen

-die ursprüngliche Zielfunktion K ist von der Wahl als Pivot-Zeile hierbei ausgeschlossen

Zweite Phase

- wenn dies erreicht ist, streiche die künstlichen Variablen kjund die zusätzliche (fiktive) Zielfunktion K´*

-führe weitere Simplex-Schritte durch unter Verwendung der (bis hierher mitgeführten) ursprünglichen Zielfunktion K

- erhalte die optimale Lösung, sobald das reduzierte Tableau nur noch negative Zahlen oder Nullen in der Zielfunktionszeile K stehen hat.