[BWL] [QM] Verständnisfrage zu Aufgabe 27 (B&B)

[Johannes]

Hallo!

Ich rechne gerade die Übungsblätter von QM durch und verstehe die Lösung von Aufgabe 27 (Übungsblatt 8 ) nicht. Dort soll man für den gegebenen Entscheidungsbaum angeben, ob die Teilprobleme terminieren dürfen, oder ob man sie weiter untersuchen muss. Dabei habe ich in der Lösungsmitschrift stehen, dass terminieren und gebrancht werden müssen. Ich kann leider überhaupt nicht nachvollziehen wieso das so ist.
Wäre super, wenn mir da jemand weiterhelfen kann!
Danke!

Johannes

[Vion]

Wichtig ist erst einmal, dass man sich die Aufgabe genau durchliest. Oft geht es in diesen Aufgaben um ein Maximierungsproblem.
Hier ist es jedoch ein Minimierungsproblem.
Es wird also die kleinste Zahl gesucht.

Wenn ich es richtig in Erinnerung habe gilt die folgende Begründung:
Zulässige Lösungen terminieren immer. Also terminiert auch P4,P5 und P7.

Die unzulässige Lösung P8 (320) kann die kleinste zulässige Lösung P1 (270) nicht mehr unterbieten. Also kann dieser Knoten auch terminieren, da er uns nicht weiter bringt. Die Knoten P6 und P9 sind kleiner als die kleinste zulässige Lösung P1. Hier besteht also die Möglichkeit, dass hier per Branch eine zulässige Lösung gefunden wird die kleiner als P1 (270) ist.

Dies führt also dazu dass nur P6 und P9 weiter verzweigt werden müssen.

Gruß Vion

[Johannes]

Jetzt hab ich es verstanden!
Danke!

[Johannes]

Ich hätte noch eine Frage zu der Branch & Bound Aufgabe danach (Aufgabe 28).
Aus welchem Grund werden in der Lösung die Zielfunktionswerte immer abgerundet?
Zum Beispiel hat die LP-Relaxation des ursprünglichen Problems den Zielwert 25,75. Die Upperbound wird aber auf 25 gesetzt.

[Martin]

Zum Beispiel hat die LP-Relaxation des ursprünglichen Problems den Zielwert 25,75. Die Upperbound wird aber auf 25 gesetzt.

Aus der Erinnerung (das ist bei mir schon was her): Da es sich um ein ganzzahliges Problem handelt, wird mit der gegebenen Zielfunktion eine zulässige Lösung nur ganzzahlig sein können. Eine Lösung kann nicht besser sein als die (optimale) Lösung der Relaxation. Also kann der bestmögliche Wert nur der abgerundete Zielfunktionswert der optimalen Lösung der Relaxation sein.

[Johannes]

Das macht Sinn!
Aber das geht auch nur solange die Koeffizienten in der Zielfunktion auch ganzzahlig sind. Aber dann weiß ich ja worauf ich achten müss
Danke!