In den folgenden Abschnitten werden zwei unterschiedliche Branch-and-Bound Verfahren zur Bestimmung der besten Lösung bei ganzzahligen Minimierungsproblemen aufgezeigt. Dabei werden die folgenden beiden Verfahren unterschieden:
- Branch-and-Bound am Ausgangsproblem. Hier wird von vornherein das ganzzahlige Minimierungsproblem (=Ausgangsproblem) betrachtet und anhand dessen die oberen und unteren Schranken aufgestellt.
- Branch-and-Bound am angepassten Problem. Hier wird zunächst für das angepasste Problem die Optimallösung mittels Simplexalgorithmus oder grafisch ermittelt, indem die Ganzzahligkeitsbedingung vernachlässigt wird. Dieses Ergebnis dient dann der Bestimmung der besten Lösung im Entscheidungsbaum für das Ausgangsproblem.
Weitere interessante Inhalte zum Thema
-
Branch-and-Bound: Maximierungsprobleme
Vielleicht ist für Sie auch das Thema Branch-and-Bound: Maximierungsprobleme (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Beispiel: Branch and Bound am Maximierungsproblem (optimale Lösung)
Vielleicht ist für Sie auch das Thema Beispiel: Branch and Bound am Maximierungsproblem (optimale Lösung) (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.