Branch and bound in operations research?
Hallo, kann man mir bei der beantwortung der 2 teilaufgaben helfen? siehe bild
ich verstehe nicht wie man draufkommen sollte, was die obere schranke oder untere schranke sein sollte. Muss nicht vorher ein Zielfunktionswert angegeben werden?
Mein Prof meinte anscheinend wäre die beste obere schranke die 31, aber ich versteh nicht wieso.
Die obere schranke meines wissens ergibt die beste lösung oder? und die untere schranke, die momentan beste lösung sobald sie von einem wert der oberen schranke überschritten wird.
ich bedanke mich im voraus für die antwort.
ich verstehe dieses thema echt nicht.
1 Antwort
Mein Prof meinte anscheinend wäre die beste obere schranke die 31, aber ich versteh nicht wieso.
Die beste ub ist die kleinste ub, damit also 31 und nicht 32 oder inf.
Die obere schranke meines wissens ergibt die beste lösung oder?
Die kleinste obere Schranke ist die beste bisher gefundene gültige Lösung.
und die untere schranke, die momentan beste lösung sobald sie von einem wert der oberen schranke überschritten wird.
Ehm... diese Aussage verstehe ich nicht. Die untere Schranke gibt an, wie klein die Zielfunktion in diesem Ast im besten Fall werden kann. Falls ein Ast im besten Fall noch immer nicht besser als die beste bisher gefundene gültige Lösung ist, kann er abgeschnitten werden.
Hast du mal selbst von Hand so einen Optimierungsproblem gelöst und einen Baum dazu erstellt?
Sorry, aber das ist echt nicht zu lesen. Verwende Absätze, achte auf deine Rechtschreibung und schau dir am Besten nochmal irgendwo im Internet ein Video dazu an.
Ein paar Tipps:
- Es handelt sich um eine Minimierung
- Die untere Schranke bezieht dich auf den gesamten folgenden Ast
- Die Nummern geben an, in welcher Reihenfolge der Baum berechnet wird
- Die kleinste obere Schranke ist die beste bereits gefundene, gültige Lösung, aber nicht zwangsläufig die global beste Lösung. Lösungen darüber sind schlechter und somit wertlos.
- Die untere Schranke sagt aus, wie gut eine Lösung in dem Ast bestenfalls werden kann. Lösungen darunter sind in dem Ast unmöglich.
Wenn jetzt also die untere Schranke eines Astes über der kleinsten oberen Schranke liegt, dann sind alle (potentiellen) Lösungen in dem Ast wertlos und er kann abgeschnitten werden.
Ich bedanke mich nochmal für die Antwort. Ich habe deine tipps durchgelesen.
Ich habe auch videos angeschaut und verstanden, wie man mit einem aufgeschriebenen Maximierungs/Minimierungsproblem den baum lösen kann. Dennoch so sehr ich es versuche, verstehe ich nicht den richtigen unterschied zur oberen und unteren schranke.
- bezüglich der aufgabe (also die des Bildes) ist die obere schranke bei einem Minimierungsproblem: 31, weil es den kleinsten wert annehmen muss.
- die beste untere schranke ist die 35 oder? da sie den größten wert annehmen muss (also größer als die 31 oder?) oder ist es 31?
wäre bei einem MAXIMALEN optmierungsproblem die beste untere schranke die 25 und die beste obere schranke die 32?
also MEINES WISSEN JETZT ZU OBER UND UNTERSCHRANKE:
- untere schranke: bei einem ast: wenn ich da die beste MOMENTANE lösung habe die dem Zielfunktionswert nähert, ist das meine beste untere schranke. Außer ich finde einen anderen Ast, der größer als dieser momentane optimale wert ist und das ist meine NEUE untere Schranke mit der optimalen Lösung (Maximierungsproblem), oder?
- obere schranke: Als obere schranke dient eine vorerst optimale zulässige Lösung ist ja der höchste wert der angenommen werden kann. Also, wenn die untere schranke die obere schranke vom wert höher ist, kann es abgeschnitten werden?
Ist es beim MINIMIERUNGSproblem einfach umgekehrt?
-> obere schranke Zielfunktionswert bspweise 10, dh man sucht den kleinsten. Das wäre bspweise 5.
-> untere schranke darf nicht die 10 überschreiten, aber größer als die obere schranke sein. Die beste untere schranke, wäre der größte wert vom ganzen baum oder?
Ich bedanke mich, falls du darauf antworten sollest im Voraus und ich hoffe, dass ich etwas verstanden habe. Hoffentlich verstehe ich den unterschied zu ober und unterschranke.
Und das du das dann auch lesen kannst.
bezüglich der aufgabe (also die des Bildes) ist die obere schranke bei einem Minimierungsproblem: 31, weil es den kleinsten wert annehmen muss.
31 ist die beste obere Schranke. 32 ist auch eine obere Schranke, aber da minimiert werden soll, ist kleiner = besser.
die beste untere schranke ist die 35 oder? da sie den größten wert annehmen muss (also größer als die 31 oder?) oder ist es 31?
Nein. Die beste (kleinste) untere Schranke ist zu dem Zeitpunkt 27, weil man da noch Hoffnung auf die kleinste Lösung hat.
wäre bei einem MAXIMALEN optmierungsproblem die beste untere schranke die 25 und die beste obere schranke die 32?
Nein, und da das ein Minimierungsproblem ist, ist es an dem Beispiel auch schwer zu machen. Bleib lieber erstmal bei der Minimierung, du bringst das sonst durcheinander, so wie hier:
untere schranke: bei einem ast: wenn ich da die beste MOMENTANE lösung habe die dem Zielfunktionswert nähert, ist das meine beste untere schranke. Außer ich finde einen anderen Ast, der größer als dieser momentane optimale wert ist und das ist meine NEUE untere Schranke mit der optimalen Lösung (Maximierungsproblem), oder?
wenn ich da die beste MOMENTANE lösung habe die dem Zielfunktionswert nähert
Was meinst du überhaupt hiermit?
nochmals danke für die Antwort und tut mir sehr leid für die ganzen Fragen.
Also ist bei einem Minimierungsproblem die beste untere schranke: die kleinste untere Schranke die aktuell gefunden wurde?
Warum ist es nicht bei der Nr 2 die untere Schranke: 26 oder bei der 1 die untere Schranke 27 als beste Lösung? Liegt es daran, weil sie in der Mitte der Verzeweigung liegen?
Du meintest "weil man da noch Hoffnung auf die kleinste Lösung hat". Ist das auf die obere Schranke bezogen? Das die Lösung kleiner als die 31 wird?
Nt 6 wird doch nicht weitergemacht, weil die 35 größer als die lösung von obere schranke: 31 ist und auch die von der Nr: 5 mit 27, oder?
- Was ich im unteren Absatz, bezüglich eines Maximierungsproblems verstanden habe war:
- obere Schranke hat bspweise den Zielfunktionswert 7,5. Also stellt die obere schranke als den besten zielfunktionswert der bekannten lösung dar mit 7,5
- die untere schranke (bei einer ganzzahligkeitsbedingung): überprüft bei jedem ast, welche dem zielfunktionswert annähert? wenn man bspweise auf einem pfadweg die 6 als beste Lösung, welches der 7,5 nähert raushat. Ist das die beste untere Schranke oder? Aber, wenn man auf einem anderen Pfad weitermacht und dort die 7 rauskommt, ist das die beste untere Schranke und die vorherige wird verworfen?
Nochmals vielen lieben Dank!
Erstmal möchte ich mich vielmals bei dir bedanken, dass du mir darauf geantwortet hast. Ich habe schon ein zwei Optimierungsprobleme versucht zu lösen und dadurch auch ein Baum erstellt gehabt. Dennoch verwirren mich die erklärungen so sehr, da es zum beispiel ja auch das rucksackproblem auch als baum darzustellen ist und es dort wiederrum etwas anders verläuft (falls ich es so richtig verstanden habe). Mein prof hat nur 2 beispiele zum branch and bound gemacht (also inkl das bild) und das hilft mir auch nicht viel weiter. Bezüglich deiner Antwort: also ist 31, der best upper bound weil es den kleinsten wert entspricht? okay, aber woher weiss ich dass ich "weitermachen" muss? also am anfang ist ja lower bound 25, und upper bound infinity. und dann gehe ich einfach so in den ast weiter (weil es so vorgegeben ist?) rechts bei der nummer 2 ist ja die obere schranke 32 und die untere 26. mache den ast weiter, weil ich weiss dass die untere schranke kleiner ist als die obere und man deswegen noch nicht die optimale lösung gefunden hat? oder was ist der grund? dabei ergibt sich bei der 5 lower bound: 27 und die 6 mit lower bound 35. Hört man hier auf, weil man erreicht hat dass lower bound die 32 (oder muss es die 31 sein?) größer ist? also eigentlich ist doch der best lower bound die 35 oder, also der größte wert vom ganzen baum, und es keinen wert gibt, der besser ist? bei der linken seite hat man bei nr 3 und nr 4 28 und 30 als lower bound - und man macht weiter, weil diese nicht größer als der upper bound ist? und wie du es dann gesagt hast ist der beste upper bound 31. woher weiss man dass man nicht weitermachen muss (also abgesehen davon dass es nicht auf dem bild weitergeht), weil die 31 steht ja jetzt als momentan optimale lösung da. ich hoffe dass ich es einigermassen verstanden habe. es tut mir leid, falls ich da voll viel geschrieben habe ><