weiß jemand nach welcher Regel beim B&B Verfahren die Reihenfolge der zu bearbeitenden Knoten bestimmt wird?
Im Skript [S. 88] steht ja, man solle "das freie Ende des Baumes mit dem minimalen Zielwert" wählen. Wenn ich nun aber bei P0 anfange, dann habe ich ja erst mal nur einen Zielwert den man mittels Simplex als erste zulässige Lösung ermittelt hat. Dann wähle ich beliebig eine der nicht geraden Variablen, z. b. x1 = 9,23 , und spalte in eine linke und eine rechte Hälfte. Hier wäre es also <= 9 und >=10.
1) Welche Seite muss nun aber zuerst bearbeitet werden? Irgendwer meinte mal, die mit der größeren Schranke, hier also die >= 10 Seite. Stimmt das?
2) Angenommen man habe sich in 1) für die >=10 Seite entschieden. Wird diese Seite dann zuerst fertig bearbeitet, so dass ich auf dieser Seite dann also die Knoten P1, P2, P3, usw. stehen habe und wechsle erst danach auf die andere Seite?
Wäre sehr dankbar wenn mir jemand weiterhelfen kann.
Grüße,
Florian
Comments
Amber-Ann
Contributions on this page: 1
View profileSchau dir mal die Animation zu B&B auf der CD an. War ganz hilfreich. Kann ich nur empfehlen. Und dann versteht man den ganzen Vorgang.
Da ist ein Beispiel zu B&B und auch erklärt, wie man beim Aufspalten vorgeht. Manchmal muss man eine Seite gar nicht weiter aufspalten, weil sich dadurch das Ergebnis, was man der anderen Seite schon raushat und eine Möglichkeit wäre, dadurch nicht mehr verbessern könnte, sondern nur verschlechtern und dann kann man sich den ganzen Zweig sparen.
cako
Contributions on this page: 1
View profileverrückten:):D, die abwl am 3.9.08 schreiben!
zu branch bound habe ich eine Frage (übungsaufgabe von Lehrstuhl: B507):
kann mir jemand konkret das ausgangstableau für den simplex-algorithmus für Z=71,4 mit (10,2,0) mitteilen.
verzweigen würde ich hier auf x1>=11 und x1<=10 (siehe lösung)
komme einfach nicht auf die lösung. Oder ist hier einfach x1=10 und x2=0 in maximierungsbedingung einzusetzen?
gruß carsten
Winnie84
Contributions on this page: 2
View profileWoher hast du denn die Lösung dazu??? Das Ausgangstableau ist doch gar nicht zum Aufstellen...
Winnie84
Contributions on this page: 2
View profileAber wenn du ein Ausgangstableau aufstellen möchstest würd ich folgendes vorschlagen:
MAx 7x1+3x2
u.d.N.
5x1+2x2 <=51
2x1+6x2<=33
x1>=10
x2<=0
Und dann ganz normal die Schlupf-und Hilfsvariablen etc dazu machen. Ich denke, dass man bei x2 rein theoretisch auch =0 nehmen kann, da ja nicht mehr geht als nichts einsetzen...