Aufgabe B0503 Branch & Bound

Ines,

es wird hier nach einer ganzzahligen optimalen Lösung gesucht.
Knoten 2 hat eine Zielwertschranke von 40,6. Diese ist höher als die Zielwertschranke der ganzzahligen Lösung von Knoten * und muss deshalb weiter aufgespalten werden. Wenn du jetzt den rechten Ast ansiehst wird dieser mit einem Zielwert von 40 von dem Knoten* dominiert, da dieser ebenfalls den Zielwert 40 besitzt aber bereits ganzzahlig ist. Knoten 4 hat einen Zielwert von 40,33 und könnte noch einen Zielwert über 40 erbringen und wird aufgespalten.
Da nun 39,67 und 39 als Zielwerte herauskommen, werden diese wieder von Knoten* dominiert.

Viele Grüße
Berit

Ich habe bei der Aufgabe such so mein Verständnissproblem.

Was ich bisher bei B&B verstanden habe ist, dass ich ganzzahlige Bedingungen suche,
rechnen kann die einzelnen Schritte auch aber ich weiß was ich in welcher Reihenfolge rechnen muss und wieso ich mal ein Ergebniss dominiert wurd und auf der anderen Baumseite nicht.

Ich kann auch die Begriffe wie: terminiert und Schranken Zielwert nicht wirklich fassen.
Dadurch erklären sich die Lösungen sicherlich auch nicht für mich.

Verzweifelte Grüße

Susanne

Susanne,

der Begriff "terminieren" heißt so viel wie "beenden, abschließen" Terminiertheit ? Wikipedia

Die Zielfunktionswertschranke ist einfach dein Bound, also der Wert den die optimale Lösung noch haben könnte.

VG
Stephan

Ok. soweit verstanden.
Wenn ich mir das Beispiel ansehe, weiß ich jedoch nicht was mir das alles sagen soll. Ich schreibe mal auf wie ich den B&B "verstanden" habe und auch meine Fragen

1. P0 wird berechnet (40,75) <soweit o.k.>

2. Verzwiege zu P1 und P2 und berechne diese (mit 3 rein und draußen,da drei nicht ganzzahlig ist) Komme auf die Werte P1 (40,67) und P2 (40,6) <macht für mich auch noch Sinn>

3. Ich mache weiter, da der Zielfunktionswert des LP (hier P0 mit 40,75) nicht schlechter ist wie bei P1 und P2 <wäre wenn das so ist auch verständlich>

4.Ich rechne beide Bäume weiter, jeweils rein und raus den nicht ganzen Wert. <o.K>

5. Bekomme 4 neue Werte raus.
--P3 (40,33) bleibt drin, <Frage : da schlechter wie P0 (40,75) oder schlechter wie P2 (40,6) welcher Wert ist ausschlaggebend?>
--P* (40) zulässig da ganzzahlig, <Frage: rechne ich nicht weiter, weil 14 kg erreicht wurden, oder weil das Ergebnis ganzzahlig ist?>
--P4 (40,33) bleibt, da schlechter <Frage s.o. :wie P0 (40,75) oder P2 (40,33) ???>
--P (40) wird von P* dominiert <Frage: ist das so, weil der Wert 40 auch von einer zulässigen Lösung erreicht wird? >

6. Rechne mit P3 und P4 weiter

7.--P5 wie gehabt
---P (39,4) wird dominiert <Frage : von wem und wieso>
---P (39,67) wird dominiert <Frage : von wem und wieso>
---P (39) wird dominiert <Frage : von wem und wieso>

8. rechne mit 5 weiter, <da ich nur mit nicht dominierten weiterrechne>
P (38) o.k. ganzzahlig
P (37) wird dominiert <Frage : von wem und wieso>


Aus den Werten den optimalen heraussuchen ist auch klar.

Dank und Gruß
Susanne

Susanne151 schrieb:

Ok. soweit verstanden.
Wenn ich mir das Beispiel ansehe, weiß ich jedoch nicht was mir das alles sagen soll. Ich schreibe mal auf wie ich den B&B "verstanden" habe und auch meine Fragen

1. P0 wird berechnet (40,75) <soweit o.k.>

2. Verzwiege zu P1 und P2 und berechne diese (mit 3 rein und draußen,da drei nicht ganzzahlig ist) Komme auf die Werte P1 (40,67) und P2 (40,6) <macht für mich auch noch Sinn>

3. Ich mache weiter, da der Zielfunktionswert des LP (hier P0 mit 40,75) nicht schlechter ist wie bei P1 und P2 <wäre wenn das so ist auch verständlich>

Falsch, der Grund weshalb du weiter machst, ist dass du keine optimale zulässige Lösung gefunden hast. Der Knoten P0 interessiert hier nicht mehr, weil du den schon aufgespalten hast.

4.Ich rechne beide Bäume weiter, jeweils rein und raus den nicht ganzen Wert. <o.K>

5. Bekomme 4 neue Werte raus.
--P3 (40,33) bleibt drin, <Frage : da schlechter wie P0 (40,75) oder schlechter wie P2 (40,6) welcher Wert ist ausschlaggebend?>
P0 interessiert nicht mehr, an dieser Stelle ist die Zielfunktionswertschranke 40,6 (von P2).
--P* (40) zulässig da ganzzahlig, <Frage: rechne ich nicht weiter, weil 14 kg erreicht wurden, oder weil das Ergebnis ganzzahlig ist?>
Weil das Ergebnis ganzzahlig ist.
--P4 (40,33) bleibt, da schlechter <Frage s.o. :wie P0 (40,75) oder P2 (40,33) ???>
An dieser Stelle interessiert P2 nicht mehr, da der aufgespalten wurde.
--P (40) wird von P* dominiert <Frage: ist das so, weil der Wert 40 auch von einer zulässigen Lösung erreicht wird? >
ja

6. Rechne mit P3 und P4 weiter

7.--P5 wie gehabt
---P (39,4) wird dominiert <Frage : von wem und wieso>
---P (39,67) wird dominiert <Frage : von wem und wieso>
---P (39) wird dominiert <Frage : von wem und wieso>
P* dominiert mit seinem Zielfunktionswert von 40.

8. rechne mit 5 weiter, <da ich nur mit nicht dominierten weiterrechne>
P (38) o.k. ganzzahlig richtig (aber nicht optimal, die 40 von P* ist besser)
P (37) wird dominiert <Frage : von wem und wieso>
P* dominiert mit seinem Zielfunktionswert von 40.


Aus den Werten den optimalen heraussuchen ist auch klar.

Dank und Gruß
Susanne

Zum Vergrößern anklicken....

Zum B&B-Prinzip:
Das B&B-Verfahren ist ein Suchverfahren. D.h. du sucht eine optimale zulässige Lösung.

Du startest immer mit einer optimalen Lösung (die des relaxierten Problems), die leider in den allermeißten Fällen nicht zulässig ist.

Jetzt hast du zwei Richtungen in denen du eine zulässige Lösung finden könntest zur Auswahl - dies ist das Verzweigen oder Aufspalten des Knotens. Dabei geht dir salopp gesagt etwas von deinem Zielfunktionswert flöten, d.h. du entfernst dich ein Stück von der optimalen relaxierten Lösung.

Bei jedem Knoten steht immer eins fest: Besser wird's nicht mehr; d.h. nach dem Aufspalten wird der Zielfunktionswert immer schlechter (theoretisch kann er noch gleich bleiben).

Der nicht-verzweigte Knoten mit dem höchsten Zielfunktionswert gibt immer deine Schranke vor (besser wird's nicht), wenn dieser Knoten jetzt noch eine zulässige Lösung ist, ist es auch eine optimale Lösung der gesamten Aufgabe, weil: Besser wird's nicht!

Jetzt ok?

nochmal,[/COLOR]
hab mal in blau ein paar Sachen in deinem Text ergänzt....[/COLOR]

1. P0 wird berechnet (40,75) <soweit o.k.>

2. Verzwiege zu P1 und P2 und berechne diese (mit 3 rein und draußen,da drei nicht ganzzahlig ist) Komme auf die Werte P1 (40,67) und P2 (40,6) <macht für mich auch noch Sinn> =>ok[/COLOR]

3. Ich mache weiter, da der Zielfunktionswert des LP (hier P0 mit 40,75) nicht schlechter ist wie bei P1 und P2 <wäre wenn das so ist auch verständlich> => nein, du machst weiter, weil du noch kein ganzzahliges Ergebnis hast[/COLOR]

4.Ich rechne beide Bäume weiter, jeweils rein und raus den nicht ganzen Wert. <o.K> =>ok aber du rechnest immer zuerst den Zweig weiter, bei dem du den größten Zielwert errechnet hast, hier ausgehend von P1, da 40,67 > 40,6. Der Zielwert stellt ja deinen gesamten Nutzen aller mitgenommenen Teile im Rucksack dar. Du beginnst mit den Teilen, die den größten Nutzen erbringen. Aus diesem Grund wird der Zielwert unter jeder Verzweigung geringer.[/COLOR]

5. Bekomme 4 neue Werte raus.
--P3 (40,33) bleibt drin, <Frage : da schlechter wie P0 (40,75) oder schlechter wie P2 (40,6) welcher Wert ist ausschlaggebend? => [/COLOR]nein, da díe mitgenommenen Gegenstände noch nicht ganzzahlig sind[/COLOR]

--P* (40) zulässig da ganzzahlig, <Frage: rechne ich nicht weiter, weil 14 kg erreicht wurden, oder weil das Ergebnis ganzzahlig ist?>
=> nein, da jede weitere Verzweigung einen geringeren Zielwert bringen würde, und wir wollen hier den Nutzen maximieren ( siehe auch meine Erklärung zu 4) Du würdest ja sonst nur prüfen ob der Tausch eines Gegenstandes mit großem Nutzen durch einen Gegenstand mit kleinerem Nutzen einen höheren Zielwert=Gesamtnutzen ergibt und das ist nicht möglich.😉[/COLOR]
--P4 (40,33) bleibt, da schlechter <Frage s.o. :wie P0 (40,75) oder P2 (40,33) ???>=> falsch siehe oben[/COLOR]
--P (40) wird von P* dominiert <Frage: ist das so, weil der Wert 40 auch von einer zulässigen Lösung erreicht wird? > => ja genau![/COLOR]

6. Rechne mit P3 und P4 weiter

7.--P5 wie gehabt
---P (39,4) wird dominiert <Frage : von wem und wieso> => von P* da ganze Gegenstände und höherer Gesamtnutzen[/COLOR]
---P (39,67) wird dominiert <Frage : von wem und wieso>=> von P* da ganze Gegenstände und höherer Gesamtnutzen
---P (39) wird dominiert <Frage : von wem und wieso>=> von P* da ganze Gegenstände und höherer Gesamtnutzen

8. rechne mit 5 weiter, <da ich nur mit nicht dominierten weiterrechne>
P (38) o.k. ganzzahlig
P (37) wird dominiert <Frage : von wem und wieso>=> von P* da ganze Gegenstände und höherer Gesamtnutzen ( und auch von 38, aber 40 bleibt optimal, da hier der höchste Gesamtnutzen)

Hoffe meine Erklärung ist so einigermaßen verständlich, [/COLOR]
sonst melde dich[/COLOR]🙂

Gruß Berit[/COLOR]

Oh, da haben sich unsere Lösungen wohl überschnitten.
Naja, doppelt hält ( oder versteht es sich) besser

Ich glaub jetzt ist es o.k.
Trinke einen kaffee und werde dann mal eine andere Aufgabe rechnen. Und hofffentlich die gleichen Ergebnisse wie der Lehrstuhl haben.

Susanne