Zwei-Phasen Lösung eines LP

Zwei-Phasen Lösung eines LP

Hallo!

Kann mir vielleicht jemand erklären, warum ich im Beispiel Seite 54 Kurs 512 die vierte Zeile im oberen Tableau nicht aufgrund von Transformationsregel 2 mit (-1) multiplizieren muss?? Beide Bedingungen sind doch erfüllt, b > 0 und die Zeile enthält die -1 eines negativen Einheitsvektors?
Habe ich da was falsch verstanden?

Sabine

Sabine,

bin mir nicht ganz sicher, ob ich deine Frage richtig verstanden habe, aber ich geb einfach mal meinen Senf dazu: Wenn du die vierte Zeile mit -1 multiplizierst, dann willst du das bestimmt machen, damit du in der Spalte x5 den Einheitsvektor bekommst. In dem Fall müsstest du aber ja die ganze vierte Zeile mit -1 multiplizieren und du hättest auf der rechten Seite -2, d.h. dann wäre nicht mehr b>0. Ich hoffe, das klärt deine Frage.

rianja2000

Erst mal danke für Deine Antwort.
Was spricht aber dagegen, dass b dann negativ ist? Ich verstehe die Transformationsregel 2 von Seite 49 so, dass ich diese Zeile mit -1 multiplizieren MUSS. Etwas weiter oben heißt es darüberhinaus:

"Ferner wird auch dann eine Zeile i mit nichtnegativer RHS (also b) multipliziert, falls sie bereits die -1 eines negativen Einheitsvektors ... enthält. man gewinnt einen positiven Einheitsvektor auf Kosten einer negativen RHS."

Hm, ich werde wohl mal den Mentor am Freitag fragen, weil ich ja scheinbar irgend etwas grundsätzliches dabei nicht verstehe.

LG

Sabine

Sabine,

bei dem Satz, den du zitierst, lässt du den wichtigsten Teil weg:

"Ferner wird auch dann eine Zeile i mit nichtnegativer RHS (also b) multipliziert, falls sie bereits die -1 eines negativen Einheitsvektors zu einer freien (vorzeichenunbeschränkten) Variablen enthält. Man gewinnt einen positiven Einheitsvektor auf Kosten einer negativen RHS."

Zum Vergrößern anklicken....

Ich versuch aber auch noch eine andere Möglichkeit um zu erklären, warum b>0 sein muss: Ich versuch es mal mit einem Beispiel:
Es gibt zwei Nebenbedingungen: x1 + x2 <= 10 und 3x1 + x2 <= 5
Mit Schlupfvariablen ist das x1+x2 + x3 = 10 und 3x1 +x2 +x4 =5
Im Tableau (ohne Zfkt) bedeutet das
1 1 1 0 | 10
3 1 0 1 | 5

Man hat zwei Einheitsvektoren, nämlich bei x3 und x4. Das heißt die hier vorliegende Lösung ist x1=0 , x2=0 , x3= 10 und x4=5. Wenn man diese Werte für x1 und x2 oben in die Nebenbedingungen einsetzt, sieht man auch, dass sie erfüllt sind. Wenn aber b<0 dann wären die Nebenbedingungen nicht mehr erfüllt (x3 und x4 müssten negativ sein; aber Schlupfvariablen sollen ja immer positiv sein).

Eine ganz offensichtliche Startlösung (nämlich ausschließlich die Schlupfvariablen >0 und die "echten" Variablen = 0) funktioniert nur bei b>0. Ansonsten braucht man ebend diese erste Phase.

So, ich hoffe, ich habe dich nicht noch mehr verwirrt. Ansonsten kriegst du ja Freitag Unterstützung. Gruß

rianja

rianja!

Also, grundsätzlich habe ich das jetzt kapiert, nur: woran erkenne ich denn, ob die Variable, zu der der negative Einheitsvektor gehört, frei bzw. vorzeichenunabhängig ist?
Gruß,

Sabine

wenn du die Nichtnegativitätsbedingung x1 >= 0 hast, dass ist x1 nicht vorzeichenunabhängig. Wenn du aber für eine Variable keine solche Bedingung hast, dann ist sie vorzeichenunabhängig (das kommt in der Praxis allerdings eher selten vor).

VG

rianja

Das war ja eine schnelle Antwort!
Danke noch mal für Deine Mühe, jetzt habe ich es verstanden.
Manchmal sieht man den Wald vor Bäumen nicht.

LG

Sabine

Danke noch mal für Deine Mühe

Zum Vergrößern anklicken....

absolut :gerngesch. Wenn man Sachen zu erklären versucht, werden sie einem selbst noch klarer. Ich war mir z.B. zunächst auch nicht bewusst, was vorzeichenunabhängig bedeutet. Aber wenn das jetzt in der Klausur dran kommt: :daumen:

Also, immer her mit Fragen....

Gruß

rianja