Aufgabe B0501 851

Aufgabe B0501 (851)

Hallochen,
ich über gerade fleissig und stolpere soeben über o.g. Aufgabe. Dabei stellt sich mir die Frage wie man auf das Starttableau kommt.
mein Ansatz ist das LOP in eine Max Aufgabe "umzuwandeln" durch multiplikation mit -1.
Soweit stimmt das ja noch mit deren Zielfunktion offensichtlich überein. Aber warum werden die Restriktionen nicht wie zB im Skript bei Beispiel 5.6 auch mit -1 multipliziert?
wenn ich das nämlich mache, brauche ich zwei Hilfsvariablen und nicht nur eine wie beschrieben😕
Über einen Denkanstoß würde ich mich freuen

Die 2. Nebenbedingung könnte man mit -1 multipliziert, um aus dem >= ein <= zu machen. Allerdings müsste man dann einen dualen Simplexalg. verwenden, da die rechte Seite ja negativ wäre.

Müsste aber doch genauso gehen. Schon probiert?

Bei dem Lösungsweg lt. Übungsaufgabe wird eben die Hilfsvariable für die >= Bedingung benötigt. (-s, +h)

Ob ich Dir damit geholfen habe?🙄😕

Gehen müsste beides - entweder die >= Bedingungen über Hilfsvariablen bzw. die Multiplikation mit -1 und dafür evtl. duale Simplexschritte - vielleicht einfach eine Frage des Aufwandes?

Zumindest habe ich das so verstanden....

Yvonne,

überlege mal, warum der duale Simplex in dieser Situation nicht anwendbar ist. Es reicht nicht, wenn die Lösung unzulässig ist.

Tip: Wie sieht die "Delta zj-Zeile" aus?

Gruß
loddar

Da steht noch ein negativer Wert in der Zielfunktionszeile....?😱

yvonne schrieb:

da steht noch ein negativer Wert in der Zielfunktionszeile....?😱😀

Zum Vergrößern anklicken....

Stört das denn? 😕
Ich habe mit 2 dualen Simplexschritten das angegebene Tableau errechnet - zwar etwas durcheinandergewürfelt, durch eine abweichende Aufnahmefolge von x1 und x2 in die Basis, aber bei näherem Vergleich identisch.

Letztlich erhalte ich ja immer einen negativen Zielfunktionswert im Endtableau bei Mininmierungsproblemen.

Hallochen,
was für eine blöde Aufgabe, und dabei sieht sie doch so harmlos aus.
also ich habs jetzt mal ohne Hilfvariablen gemacht (ich nehm mal an so wie du Angela) und hab dann folgendes Starttableau:
x0 x1 x2 x3 s1 s2 s3 RHS
1 6 2 -1 0 0 0 0
0 2 1 1 1 0 0 60
0 -2 -1 -2 0 1 0 -40
0 2 0 1 0 0 1 25

allerdings komm ich ständig auf irgendein anderes Ergebnis. Welches Element ist denn dein Pivotelement?
Oder um es allgemein zu fragen? Was macht man denn , wenn in Zielfunktionszeile und RHS eine negantive Zahl stehen?
Ich hab die 1 in der letzten Zeile von x3 genommen und hab nach einem Schritt ein Optimaltableau. Das weicht aber größenmäßig sehr von der Lösung ab.

1) Suche neg. RHS-Wert: s2=-40 -> s2 fliegt aus der Basis

2) Suche in dieser Zeile negative Werte und bilde für diese Quotienten aus Zielfunktionswert und "Zeilenwert" (hier -3 und -2). Das Maximum (oder das Minimum des Betrages) wähle ich als Pivotelement, also x2 wird in die Basis aufgenommen.

Im 2. Pivotschritt ist s3x1=-4 mein Pivotelement.

Das heißt also, neg. RHS hat Vorrang vor negativer Zielfunktionszeile?

ChristianeH schrieb:

Aber warum werden die Restriktionen nicht wie zB im Skript bei Beispiel 5.6 auch mit -1 multipliziert?

Zum Vergrößern anklicken....

Bei der Maximierung sollten alle Restriktionen <= sein.

In Uebungsaufgabe 3.3 wird ein Minimierungsproblem in ein Maximierungsproblem umgewandelt. Im Prinzip wird hier auch nur die Zielfunktionszeile durch Multiplikation mit-1 in ein Maximierungsproblem ueberfuehrt. Da die Restriktionen durch s1 und s2 in Gleichungen ueberfuehrt werden, sind sie offensichtlich nicht relevant dafuer, ob ein Minimierung oder Maximierungsproblem vorliegt.

ChristianeH schrieb:

Das heißt also, neg. RHS hat Vorrang vor negativer Zielfunktionszeile?

Zum Vergrößern anklicken....

Wenn ein negatives RHS vorliegt, muss man einen dualen Simplexschritt im primalen Tableau machen. Und der sollte zuerst gemacht werden.
Gruss,
Ulrike

ChristianeH schrieb:

Das heißt also, neg. RHS hat Vorrang vor negativer Zielfunktionszeile?

Zum Vergrößern anklicken....

Ja, so habe ich es verstanden.

Cobra schrieb:

Bei der Maximierung sollten alle Restriktionen <= sein.

In Uebungsaufgabe 3.3 wird ein Minimierungsproblem in ein Maximierungsproblem umgewandelt. Im Prinzip wird hier auch nur die Zielfunktionszeile durch Multiplikation mit-1 in ein Maximierungsproblem ueberfuehrt. Da die Restriktionen durch s1 und s2 in Gleichungen ueberfuehrt werden, sind sie offensichtlich nicht relevant dafuer, ob ein Minimierung oder Maximierungsproblem vorliegt.

Zum Vergrößern anklicken....

Ist es nicht so, dass das Problem weiterhin ein Minimierungsproblem bleibt, aber da der Simplex nur maximieren kann, nähere ich mich der Null eben von der negativen Seite.
Hätte ich ein Maximierungsproblem, würde ich nach max +x0 suchen.

AngelaA schrieb:

Ist es nicht so, dass das Problem weiterhin ein Minimierungsproblem bleibt, aber da der Simplex nur maximieren kann, nähere ich mich der Null eben von der negativen Seite.
Hätte ich ein Maximierungsproblem, würde ich nach max +x0 suchen.

Zum Vergrößern anklicken....

Ich glaube Du hast Recht.
Gruss,
Ulrike

Ist zwar schon paar Tage her, ich antworte aber auch noch mal....

Geht man bei der Aufgabe rein algorithmisch vor, so ist der Zweiphasen-Simplex nötig und damit die Einführung der Hilfsvariablen zu NB Nr. 2 (Und wahrscheinlich wurde deswegen die Variable auch h2 genannt.)

Es führen jedoch auch andere Wege zum Ziel. Dazu zitiere ich einmal den Lehrstuhl: "Sieht der erfahrene LP-Fachmann eine solche Lösung"[/COLOR] (gemeint war eine zulässige Ausgangslösung) "so kann er auf die Hilfsvariablen und damit auf die erste Phase verzichten. ... Man pivotisiert unter Missachtung zwischenzeitlicher Unzulässigkeiten (!) geradewegs nach den erkannten Basisvariablen."[/COLOR] (Musterlösung zu PET-Klausur März 02 Aufgabe 3f)

Das bedeutet also, man ignoriert erst einmal die NNB. Damit erstreckt sich graphisch gesehen der Lösungsraum auch auf den 2./3./4. Quadranten, wird aber nach wie vor von den Restriktionsgeraden beschränkt. Der Simplex errechnet (nach wie vor) Schnittpunkte der Restriktionsgeraden und ein Basistausch (ein Pivotschritt) führt zu einem weiteren Schnittpunkt. In unserem Fall multipliziert man also die 2. NB mit (-1) und pivotisiert "drauf los."

Hat man Glück und pivotisiert "richtig herum" kommt man nach wenigen Schritten zu einer Ecke, die (primal oder dual) zulässig ist, ab da kann man dann den entsprechenden "richtigen" Algorithmus anwenden.

Man kann auch wild durcheinander duale/primale Simplexschritte anwenden, muss nur darauf achten, immer eine neue Ecke auszurechnen. Allerdings muss man, wenn man Pech hat, alle Basislösungen errechnen, um die optimale zu finden. Dies hängt entscheidend von der Lage der Restriktionsgeraden und der Reihenfolge der gewählten Basen ab.

Lange Rede kurzer Sinn:
Die Algorithmen versuchen durch systematische Suche benachbarter Ecken die optimale Lösung iterativ zu bestimmen. Damit kommt man nach einer endlichen Anzahl von Schritten auf jeden Fall zum Ziel.

Beim pivotisieren nach Gefühl kann es schneller gehen, man kann sich aber auch total verrennen.

MfG
Thomas