Brauche Hilfe zu Branch & Bound

18 Hits und keiner kann helfen? Ich will nicht verrecken 😉 also Bitte ran 🙂

Sonnige Grüsse
puntosoy

Also, ich habe mal versucht, das Tableau aufzustellen, so würde ich das machen, kann natürlich auch Murks sein.
Gerechnet habe ich nicht, denn wer weiß wieviele Simplex-Schritte man da braucht.....


min z = -2y1-y2

in max-Bedingung umgeformt:

max -(-2y1-y2) = 2y1+y2

Zielfunktion:
x0-2y1-y2=0

NB:

y1+y2+x1=5
-y1+y2+x2=0
6y1+2y2+x3=21

Die x1 bis x3 bei den Nebenbedingungen sind - so nehme ich stark an - Hilfsvariablen, die man wegen der Gleichheitszeichen in der Gleichung braucht.

Die Hilfsvariablen sollen sich zu null addieren:
Hilfszielfunktion:
min z = x1+x2+x3 -> überführen in max-Bedingung: max -z: -x1-x2-x3 -> z+x1+x2+x3 = 0. Davon müssen dann noch alle Gleichungen abgezogen, die eine Hilfsvariable enthalten, an Ende kommt raus als Hilfszielfunktion:

z-6y1-4y2=-26

(Ich verwende mal z statt x-1)


Wenn dann noch dabei steht: y1 <= 2, dann muß man wohl eine Schlupfvariable (nenne ich mal s1) einführen:

y1 + s1 = 2

Die Hilfszielfunktion bliebe die gleiche wie oben.


Wenn dabei steht y1 >= 3, dann muß man eine Schlupfvariable abziehen und eine Hilfsvariable (x4) dazupacken:

y1 - s1 + x4 = 3

Da hier eine weitere Hilfsvariable drin ist, wäre die Hilfszielfunktion:

z-7y1-4y2+s1=-29

-----
Kannst Du das insoweit nachvollziehen, und/oder siehst Du da Fehler drin?

Tempo,

vielen Dank für deine Hilfe und Antwort. Werde wenn ich zu Hause bin erstmal durchrechnen und ausprobieren. Auf den ersten Blick sieht es gut aus.

Viele Grüsse
puntosoy

puntosoy schrieb:

Hallo Tempo,

vielen Dank für deine Hilfe und Antwort. Werde wenn ich zu Hause bin erstmal durchrechnen und ausprobieren. Auf den ersten Blick sieht es gut aus.

Viele Grüsse
puntosoy

Zum Vergrößern anklicken....

Äh....Ich hoffe, Du hast das nicht probiert, denn ich habe festgestellt, daß ich doch Murks erzählt habe. 😱😀

Man braucht gar keinen 2-Phasen-Simplex.
Am besten, Du schaust mal - wenn Du es noch nicht gemacht haben solltest - in die Zusammenfassung von Cordula (übrigens vielen vielen Dank nochmal für die Mühe an dieser Stelle🙂) rein (bei "kostenlose Skripte"), da ist unter Branch-and-Bound zumindestens der Fall hier ohne die Bedingung y1<=2 exakt dargestellt.

Egal, auch dann braucht man keinen 2-Phasen-Simplex, da auch in dem Fall die Zahl der Einheitsvektoren mit der Zahl der Zeilen übereinstimmt (<- Das entscheidet darüber, ob 2-Phasen oder eine Phase, worauf ich nicht geachtet hatte und deshalb natürlich totalen Unsinn erzählt habe).

Mit der weiteren NB y1<=2: Das Gleiche wie in der Zusammenfassung von Cordula, und
y1<=2 wird zusätzlich so umgeformt: y1+x4=2 und dem Tableau hinzugefügt. Acuh dann stimmt die Zahl der Eingeitsvektoren mit der Zeilenzahl überein.

Analoges gilt für y1>=3, nur dann halt x4 abziehen: y1-x4=3.

Tempo,

nochmals vielen Dank!

Habe s noch nicht probiert, da ich just PET beiseite gelegt hatte und meinen "Kampf" mit ProKO aufgenommen habe. Nächste Woche ist Steuern dran. Dann wieder PET und werde dann sofort probieren ob es passt. Ich weiss nur noch das in der PET Zusammenfassung die Lösung zu den Ausgangsdaten waren. Als "fleissiger" Klausurvorbereiter wollte ich prüfen ob ich auch zu dem Ergebniss komme, indem ich das einfach mal durchrechne.

Viele Grüsse

Puntosoy

puntosoy schrieb:

Hallo Tempo,

nochmals vielen Dank!

Habe s noch nicht probiert, da ich just PET beiseite gelegt hatte und meinen "Kampf" mit ProKO aufgenommen habe. Nächste Woche ist Steuern dran. Dann wieder PET und werde dann sofort probieren ob es passt. Ich weiss nur noch das in der PET Zusammenfassung die Lösung zu den Ausgangsdaten waren. Als "fleissiger" Klausurvorbereiter wollte ich prüfen ob ich auch zu dem Ergebniss komme, indem ich das einfach mal durchrechne.

Viele Grüsse

Puntosoy

Zum Vergrößern anklicken....

Nix zu danken, im Grunde habe ich zu danken, ich hätte den eigenen Bockmist sonst gar nicht erkannt und womöglich mit in die Klausur getragen....😀

Was Proko angeht, bin ich derzeit auch am kämpfen, zwar schon recht fit in den Grunddisziplinen, aber ich stelle anhand alter Klausuraufgaben fest, daß Prof. Fandel einige davon recht tricky (a.k.a. "nervig") formulieren kann....😱

Steuern/Konzernrechnungslegung scheint mir von allen Fächern noch das "verlässlichste" zu sein; Marketing und Ufü habe ich bis jetzt sehr stiefmütterlich behandelt, weil ich eigentlich keine Lust drauf habe, und last but not least InFi - Bohren interessanter, aber dicker Bretter....dennoch sehe ich langsam Land, äh, bzw. fische ersten Seetang und rieche Festland....🙄

Grüsse,
Tempo