wiwiweb
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research
Den Kurs kaufen für:
einmalig 29,00 €
Zur Kasse
Minimierungsprobleme > Zweiphasenmethode:

Zweiphasenmethode

WebinarTerminankündigung aus unserem Online-Kurs Volks- und Betriebswirtschaft:
 Am 12.01.2017 (ab 18:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar Grundbegriffe der Bilanzierung
- In diesem 60-minütigen Gratis-Webinar gibt Daniel Lambert einen Überblick über die zentralen Begriffe der Bilanzierung - hier im Besonderen dem Bilanzausweis.
[weitere Informationen] [Terminübersicht]

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

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!

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.

- 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

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

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.

Multiple-Choice

Welche der folgenden Aussagen ist richtig?

0/0
Lösen

Hinweis:

Bitte kreuzen Sie die richtigen Aussagen an. Es können auch mehrere Aussagen richtig oder alle falsch sein. Nur wenn alle richtigen Aussagen angekreuzt und alle falschen Aussagen nicht angekreuzt wurden, ist die Aufgabe erfolgreich gelöst.

Bild von Autor Daniel Lambert

Autor: Daniel Lambert

Dieses Dokument Zweiphasenmethode ist Teil eines interaktiven Online-Kurses zum Thema Operations Research.

Dipl.-Math. Dipl.-Kfm. Daniel Lambert gibt seit vielen Jahren Kurse zur Prüfungsvorbereitung. Er unterrichtet stets orientiert an alten Prüfungen und weiß aus langjähriger Erfahrung, wie sich komplexe Sachverhalte am besten aufbereiten und vermitteln lassen. Daniel Lambert ist Repetitor aus Leidenschaft seit nunmehr 20 Jahren.
Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research

wiwiweb - Interaktive Online-Kurse (wiwiweb.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
  • Maximierungsprobleme
    • Einleitung zu Maximierungsprobleme
  • Beste Lösung, Graphische Lösung
    • Aufstellen des Problems
    • Graphische Darstellung des Maximierungsproblems
  • Analytische Lösung
    • Vorbereitung
    • Schlupfvariablen
    • Aufstellen des Ausgangstableaus
    • Der Simplex-Algorithmus
    • Simplex-Austausch-Schritt
    • Weiterer Simplex-Schritt und Interpretation des Optimaltableaus
  • Entartung
    • Mehrdeutigkeit
    • Degeneration
  • Sensitivitätsanalyse
    • Schwankungen Deckungsbeitragskoeffizienten
    • Änderungen der Restriktionen
  • Zweitbeste Lösung
    • Zweitbeste Lösung
  • Minimierungsprobleme
    • Einleitung zu Minimierungsprobleme
    • Zweiphasenmethode
      • Zweiphasenmethode
      • Beginn erste Phase
      • Beginn zweite Phase
      • Dualität
      • Dualer Simplex-Algorithmus
  • Transportproblem
    • Nordwest-Ecken-Methode
    • Matrix-Minimum-Methode
    • Stepping-Stone-Methode
  • 24
  • 18
  • 56
  • 6
einmalig 29,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research

    Ein Kursnutzer am 16.03.2015:
    "alles top"

  • Gute Bewertung für Operations Research

    Ein Kursnutzer am 02.12.2014:
    "Super Erklärungen in den Videos!"

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen