ZU DEN KURSEN!

Operations Research - Zweiphasenmethode

Kursangebot | Operations Research | Zweiphasenmethode

Operations Research

Zweiphasenmethode

Anzuwenden ist das vorgestellte Simplex-Verfahren für…

  • Maximierungsprobleme,

  • bei positiv stehenden Werten auf der rechten Seite und

  • im Falle dessen, dass eine Ausgangslösung sofort abzulesen ist (Zuverlässigkeit).

Beispiel

Hier klicken zum AusklappenZu begutachten ist dieses Problem:

2x1 + x2 ≥ 8
3x1 + 3x2 ≥ 12
x1 + 3x2 ≥ 6
x1, x2 ≥ 0.

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

Die Lösung ist mit der Zweiphasenmethode zu bestimmen.

Die oben genannten Anforderungen sind bei dem betrachteten Minimierungsproblem nicht gegeben.

Die rechten Seiten sind negativ, wenn die „≥“-Zeichen durch Multiplikation mit –1 zu „≤“ gemacht werden und demnach ein Minimierungsproblem vorliegt. Zudem ist der Nullpunkt x1 = x2 = 0 unzulässig  (z.B. bei 2x1 + x2 = 2·0 + 0 = 0 nicht größer oder gleich 8) und auch wenn keine Ausgangslösung direkt abzulesen ist.

Jedoch bestehen die folgenden Möglichkeiten, damit die Voraussetzungen erfüllt werden:

1. Voraussetzung: Maximierungsproblem

Durch das multiplizieren der Zielfunktion mit -1, wird aus dem Minimierungsproblem ein Maximierungsproblem gemacht. Genauer gesagt wird dann K: 10x1 + 12x2 →  min! zu -K: -10x1 – 12x2  →  max!

Expertentipp

Hier klicken zum AusklappenWenn die Zielfunktion mit „-1“ multipliziert wird, lässt sich daraus immer eine Minimierungsaufgabe bzw. Maximierungsaufgabe erstellen.

2. Voraussetzung: positive rechte Seite

Da die rechten Seiten bei diesem Problem positiv sind, ist dabei nichts zu verändern.

3. Voraussetzung: Zulässigkeit

Weil die Restriktion nicht erfüllt wird, wie es oben exemplarisch ausgerechnet wurde, ist hierbei die Ausgangslösung x1= x2 = 0 nicht zulässig. Wenn eine „≥“-Restriktion vorliegt, wird die Schlupfvariable yi mit einem negativen Vorzeichen eingefügt. Grund dafür ist, dass ebenso für yi die Nichtnegativitätsbedingungen yi ≥ 0 zählen. Demnach ist beispielsweise für die zweite Restriktion 3x1 + 3x2 ≥ 12 die Darstellung in Gleichungsform 3x1 + 3x2 – y2 = 12. Denn wenn y2 ≥ 0 ist, dann gilt – y2 ≤ 0 und es wird von 3x1 + 3x2 (das, was größer oder gleich null ist) ein wenig abgezogen, damit es 12 ergibt.

Expertentipp

Hier klicken zum Ausklappen- die Schlupfvariable ywird bei ≥-Restriktionen mit einem Minus-Zeichen eingeleitet.

- die Schlupfvariable yi wird bei ≤-Restriktionen mit einem Plus-Zeichen eingeleitet.

Demnach 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

Bei diesem Tableau liegt ein Maximierungsproblem vor, in welcher nur positive Elemente auf der rechten Seite vorliegen. Als erfüllt gelten die ersten beiden zuvor erwähnten Voraussetzungen.

Dabei gibt es jedoch Probleme mit der sofortigen Ablesbarkeit. In der ersten Zeile steht (für x1 = x2 = 0 als Ausgangslösung) – y1 = 8, d.h. y1 = -8. Es entspricht jedoch nicht der Nichtnegativitätsbedingung y1 ≥ 8. Aus diesem Grund ist das Tableau nicht zulässig. Eingeführt wurden die künstlichen Variablen kj genau in der Zeile, wo -1 in der Zeile stand, zugunsten der unmittelbaren Ablesbarkeit bzw. Zulässigkeit.

Vorliegend 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

An diesem Punkt sind nun alle formalen Forderungen erfüllt. Eine Lösung ist auch hier unmittelbar abzulesen, da es sich aufgrund der rechten positiven Seite und dem +1 in jeder Zeile um eine Maximierungsaufgabe handelt.

Merke

Hier klicken zum AusklappenDie Zulässigkeit wird durch die künstlichen Variablen kj hergestellt

• in dem sie als zulässige Ausgangslösung abzulesen sind
• in dem sie nur aus rechentechnischen Gründen eingeführt werden
• in dem sie keine inhaltliche Bedeutung haben und nicht interpretierbar sind
• in dem sie deshalb stets zu Nichtbasisvariablen werden

Für die Zweiphasenmethode ist der letzte Punkt entscheidend. Die künstlichen Variablen kj müssen auf null bekommen werden, um sie zu einer Nichtbasisvariablen zu machen. Dadurch ist es möglich, sich nur auf das Tableau zu fokussieren, welches lediglich x1, x2, y1, y2, y3 enthält.

Wie ist eine Variable zügig in eine Nichtbasisvariable umzuwandeln?

Bei der Betrachtung dessen, wie in umgekehrter Weise eine Variable zu einer Basisvariablen wird, ist die Antwort naheliegend: Der Zielfunktionskoeffizient ist möglichst groß, weswegen sich dieser nicht lohnt ins Programm aufgenommen zu werden. Auf diesem Weg wird sie größer als null und daher zu einer Basisvariablen.

Daher wird eine zusätzliche (fiktive) Zielfunktion K´ eingeführt. Die künstlichen Variablen kj sind daher so niedrig wie möglich zu bewerten. Erfolgen kann dies durch die Betrachtung der folgenden Funktion:

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

Alle übrig gebliebenen Variablen gehen mit null ein und bleiben unberührt. Dadurch kommt das Tableau zustande:

 

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

Im Fokus steht dabei die künstlichen Variablen k1, k2, k3 so schnell wie möglich zu „vernichten“.
Wir schauen uns zu Beginn die Zielfunktion K´ statt K an, um die hinteren Zahlen –1 zu 0 zu bekommen. Dies geschieht dadurch, dass die  –1 mit den +1 oben bei kj verrechnet wird, sprich die entsprechenden Zeilen werden addiert.
Weil dieses Vorgehen für jede Spalte einzeln vorgenommen wird und besonders für x1, x2, y1, y2, y1 ergibt sich:

 

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

Demnach ergibt sich beispielsweise die Zahl 7, resultierend aus den Elementen der x2-Spalte: 1 + 3 + 3 = 7. Gleichermaßen wird 6 = 2 + 3 + 1 in der x1-Spalte und 7 = 1 + 3 + 3 in der x2-Spalte usw. gerechnet.

Wichtig dabei ist, dass die künstlichen Variablen kj dadurch über eine null in der Zielfunktionszeile verfügen. Die Zulässigkeit ist erst dann gewährleistet. Bei dem vorliegenden Tableau handelt es sich somit um ein Ausgangstableau der Zwei-Phasen-Methode.

Methode

Hier klicken zum Ausklappen

SCHEMA ZWEI-PHASEN-METHODE:

Vorbereitung

-  eine künstliche Variablen kj wird eingefügt

- eine zusätzliche (fiktive) Zielfunktion K´ wird eingefügt

- unter den künstlichen Variablen kj in der vorliegenden Zielfunktion werden Nullen erzeugt

- eine „neue“ Zielfunktion K´* kommt dadurch einher

Erste Phase

- ausschließlich K´* wird als Zielfunktion verwendet

- die künstlichen Variablen kj werden durch Simplex-Schritte zu Nichtbasisvariablen

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

Zweite Phase

- beim erreichen der zweiten Phase werden die künstlichen Variablen kj und die zusätzliche (fiktive) Zielfunktion K´* gestrichen

- unter der Verwendung der (noch verfügbaren) ursprünglichen Zielfunktion K werden weitere Simplex-Schritte  durchgeführt

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