Zweiphasenmethode

Da habe ich auch ewig lange für gebraucht, bis ich auf folgendes System gestoßen bin, (von dem ich hoffe, dass es stimmt):

(Was mich vor allem verwirrt hat ist, dass sie die Schlupfvariablen ständig anders benennen.)

Du führst zunächst einmal immer folgende Schlupfvariablen (ich nenne die jetzt einfach mal z) ein:

Für jede Nebenbedingung mit <= führst du ein +z ein
Für jede Nebenbedingung mit >= führst du ein -z ein

Dann stellst du das Tableau auf. Schau dir dann das Tableau an: Es muss für jede zu ermittelnde Variable (x1, x2, x3, ...) eine Startbasis geben. Gemeint ist damit im Tableau eine (1,0,0) oder (0,1,0) oder (0,0,1) (hier jetzt also bezogen auf den Fall, dass es drei zu ermittelnde Variablen gibt (x1,x2,x3)). Zu lesen natürlich von oben nach unten unterhalb des Strichs, nicht von links nach rechts! (Linear unabhängige Spaltenvektoren.)

Sollte es nicht für jede zu ermittelnde Variable so eine Startbasis geben, dann muss sie eben noch eingeführt werden für genau diese Variable(n). Das stellt dann das Hilfsproblem dar, welches in der ersten Phase gelöst wird.

Erstmal danke Nils für deine Hilfe.

Nils Wrase schrieb:

Dann stellst du das Tableau auf. Schau dir dann das Tableau an: Es muss für jede zu ermittelnde Variable (x1, x2, x3, ...) eine Startbasis geben. Gemeint ist damit im Tableau eine (1,0,0) oder (0,1,0) oder (0,0,1) (hier jetzt also bezogen auf den Fall, dass es drei zu ermittelnde Variablen gibt (x1,x2,x3)). Zu lesen natürlich von oben nach unten unterhalb des Strichs, nicht von links nach rechts! (Linear unabhängige Spaltenvektoren.)

Zum Vergrößern anklicken....

Ich beziehe mich jetzt mal auf das Beispiel in KE 7, Seite 344. Diesen Einheitsvektor gibt es für x3 und x5. Für x1, x2 und x4 gibt es das nicht.

Sollte es nicht für jede zu ermittelnde Variable so eine Startbasis geben, dann muss sie eben noch eingeführt werden für genau diese Variable(n). Das stellt dann das Hilfsproblem dar, welches in der ersten Phase gelöst wird.

Zum Vergrößern anklicken....

Wieso werden denn für die Nebenbedingungen 2 und 3 künstliche Schlupfvariablen eingeführt und nicht auch für die 1.? Meine konkrete Frage ist, wie berechne ich oder woran sehe ich, für welche Nebenbedingung ich solch eine künstliche Schlupfvariable einführen muss?

Kiomi schrieb:

Hilft das weiter?
#?t=21223#post327337

Zum Vergrößern anklicken....

Danke für den Link. In dem Beispiel in KE 7 auf Seite 344 sind drei Nebenbedingungen mit = , es werden aber nur zwei künstliche Variablen eingeführt. Woran liegt das? Bestimmt an der Sache mit dem Einheitsvektor. 😉 Nur wieso?

Kiomi schrieb:

Ich habe das so verstanden, dass ich wegen der drei Gleichungen drei Einheitsvektoren brauche. x3 und x5 bilden jeweils einen Einheitsvektor (1,0,0). Welcher gewählt wird, ist egal. Nun braucht es noch zwei Einheitsvektoren, damit das Problem gelöst werden kann. Also werden für die zweite und dritte Zeile die Hilfsvariablen eingesetzt, um die Einheitsvektoren (0,1,0) und (0,0,1) zu erhalten.

Zum Vergrößern anklicken....

Stimmt, wenn ich mir die Aufgabe so anschaue, dann muss es wohl so sein, dass man pro Nebenbedingung eine Startbasis braucht.

Das heißt dann natürlich auch, dass man bei fünf Variablen und nur drei Nebenbedingungen eine Lösung bekommt, bei der zwei Werte Null sein müssen.

Heath schrieb:

Danke für den Link. In dem Beispiel in KE 7 auf Seite 344 sind drei Nebenbedingungen mit = , es werden aber nur zwei künstliche Variablen eingeführt. Woran liegt das? Bestimmt an der Sache mit dem Einheitsvektor. 😉 Nur wieso?

Zum Vergrößern anklicken....

Zu dem Link würde ich dementsprechend sagen, dass der dritte Punkt nicht stimmen kann. Das Gleichheitszeichen bedeutet nicht automatisch, dass man eine Schlupfvariable einführen muss.

Bei den Aufgaben des Studientags von Bochum ist bei Thema 8 folgende Aufgabe dabei:

max 2x + y
s.d. x + y <= 16
−3x + y >= 12
5x − 2y >= −38

Das Hilfsproblem in Phase I ist laut der Lösung:
max − w
s.d. x + y + z1 = 16
−3x + y − z2 + w = 12
−5x + 2y + z3 = 38

Nach meinem Verständnis habe ich hier nirgendwo einen Einheitsvektor. Dementsprechend müsste man nach deiner Aussage bei allen drei Nebenbedingungen eine künstliche Variable einführen. Es wurde aber nur ein w eingeführt?!?

Kiomi schrieb:

Durch die Schlupfvariablen z1 und z3 wurden zwei Einheitsvektoren erzeugt. Die Schlupfvariable z2 ist wegen des negativen Vorzeichens kein Einheitsvektor, daher ist die Hilfsvariable w notwendig, um den dritten Einheitsvektor hinzubekommen.

Zum Vergrößern anklicken....

Vielen Dank!!! Irgendwie dachte ich, dass die Schlupfvariablen da nicht mit zu den Einheitsvektoren reinzählen. Nun ist alles klar!

Vielen Dank für eure Hilfe!

Kiomi schrieb:

Durch die Schlupfvariablen z1 und z3 wurden zwei Einheitsvektoren erzeugt. Die Schlupfvariable z2 ist wegen des negativen Vorzeichens kein Einheitsvektor, daher ist die Hilfsvariable w notwendig, um den dritten Einheitsvektor hinzubekommen.

Zum Vergrößern anklicken....

Genau.

Trotz des >= bei der dritten Nebenbedingung wird hier allerdings eine positive Schlupfvariable eingeführt. Muss wohl an dem negativen Wert nach dem >= liegen.

Nils Wrase schrieb:

Genau.

Trotz des >= bei der dritten Nebenbedingung wird hier allerdings eine positive Schlupfvariable eingeführt. Muss wohl an dem negativen Wert nach dem >= liegen.

Zum Vergrößern anklicken....

Ja, sobald das Ergebnis auf der rechten Seite - ist, muss man die ganze Gleichung *(-1) machen und somit dreht sich das >= Zeichen in ein <= Zeichen und es wird nun eine positive Schlupfvariable gebraucht.

Heath schrieb:

Ja, sobald das Ergebnis auf der rechten Seite - ist, muss man die ganze Gleichung *(-1) machen und somit dreht sich das >= Zeichen in ein <= Zeichen und es wird nun eine positive Schlupfvariable gebraucht.

Zum Vergrößern anklicken....

Genau das ist der springende Punkt, diese kleine Falle ist öfter mal dabei. Also wenn die rechte Seite negativ ist, erst alles mit -1 multiplizieren und dabei den Wechsel des Ungleichzeichens nicht vergessen, und dann erst die Hilfsvariable einführen (oder eben auch nicht).

nachdem ich einigermaßen verstanden habe, wann ich noch Hilfsvariablen einfügen muss, fehlt mir noch der entscheidende AHA-Effekt beim Aufstellen des Starttableaus von Phase I.
Ich weiß, dass ich irgendwie die Hilfsvariablen mit verarbeiten muss, meine Frage ist nur wie? Gibt es ein Schema, nachdem ich das Starttableau aufstellen kann? Es wäre echt schön, wenn mir da jemand auf die Sprünge helfen könnte...

Viele Grüße
Kristin

ein "Schema f" gibt es da schon. Ich gehe immer folgendermaßen vor:

Ergänzung: Wenn die Zielfunktion folgendermaßen formuliert ist muss man nichts machen:

max ....

Wenn da aber steht:

min ...

muss man alles mit -1 multiplizieren um daraus ein

max ...

zu machen.

Erstmal die Aufgabe anschauen. Wenn z.B. eine der Ungleichungen folgendermaßen aussieht

-x + y >= -1

erstmal mit -1 multiplizieren. Dann dreht es das >= Zeichen um. Also hast du dann =<

Als nächsten Schritt musst du bei allen Gleichungen mit >= oder =< eine Schlupfvariable ergänzen. Damit erreicht du aus einer Ungleichung eine Gleichung wird. Kleines Beispiel:

x + y =< 5

Nun egal welchen Wert x und y haben (das wissen wir ja nicht) zusammen ist es nicht mehr als 5. Also ergänze ich eine Schlupfvariabel s, wobei s>=0. Diese ergänzt dann die Summe von x und y um aus der Ungleichung eine Gleichung zu machen. Also:

x + y + s = 5

Meistens bekommt man jetzt eine gültige Startbasis für die Phase II zusammen. Also kleines Beispiel:

max x + y
unter x - y + s_1 = 5
2x + 3y + s_2 = 7

Es kann aber auch passieren, dass ich eine Ungleichung habe die so aussieht:

x + y >= 5

Dann kann ich nicht sagen

x + y + s = 5

weil die Summe von x und y offensichtlich schon größer als 5 ist. Dann muss ich folgendes machen

x + y - s = 5

wobei s >= 0 ist. Das Problem hier ist dann nur, dass ich dann folgendes habe

max 3x + y
unter x - y + s_1 = 3
x + y - s_2 = 5

Da meine zweite Schlupfvariabel (s_2) negativ ist habe ich keine gültige Startbasis für Phase I. Die Lösung ist hier eine sog. künstliche Schlupfvariable (w) zu ergänzen. Also

max 3x + y
unter x - y + s_1 = 3
x + y - s_2 + w = 5

Jetzt habe ich aber das Problem, dass ich w ja auch wieder weghaben will. Dafür muss aber irgendwo auch - w stehen sonst funktioniert das in dem Tableau ja nicht. Also

max - w
unter x - y + s_1 = 3
x + y - s_2 + w = 5

Man sieht die ursprüngliche Zielfunktion ist durch eine Hilfsfunktion ersetzt. Eine gültige Startbasis für die Phase I habe ich auch und jetzt lässt sich einfach das Tableau erstellen:

0 0 0 0 -1 0
3 1 0 0 0 0
1 -1 1 0 0 3
1 1 0 -1 1 5

Die erste Zeile ist die Hilfszielfunktion (die mit -w). Dann kommt die eigentliche Zielfunktioin und die letzten beiden Zeilen sind die Nebenbedingungen.

Im Prinzip ist das die Vorgehensweise und somit auch das "Schema f" wenn du so willst.

Mfg Frank

hey, super...danke. Das probier ich gleich mal aus

Hm, jetzt muss ich doch noch was fragen:

Wenn ich dann Phase I gemacht hab und auch mit Phase II fertig bin (in der Zielfunktionszeile sind alle Werte negativ), kann ich ja die Werte dann ablesen.

wenn ich jetzt z.B. raus habe (Zielfunktion lasse ich mal weg):
x1 x2 z1 z2 -ZF
1 0 2 1 5
0 1 1 2 2

dann wäre ja x1=5 und x2=2. Was ist aber wenn, dort wo jetzt Nullen stehen dann Zahlen rauskommen?

z.B. so:

x1 x2 x3 x4
0 0 1 1
0 1 1 -1
0 -1 -1 -1
1 0 0 1

Wie komme ich in so einem Fall auf die gesuchten Werte?

Danke schonmal.

Viele Grüße
Kristin

die Werte der Variablen bei deinem ersten Beispiel wären:

(x1, x2, z1, z2) = (5,2,0,0)

Bei deinem zweiten Beispiel:

(x1, x2, x3, x4) = (die Zeile fehlt leider, 0,0,0)

Schau dir mal die Lösungen der alten Klausuren an. Du erkennst sicher wie dass funktioniert (speziell die Probeklausur 1142KP07, Aufgabe 11).


Mfg Frank