In den folgenden Abschnitten werden zwei unterschiedliche Branch-and-Bound Verfahren zur Bestimmung der besten Lösung bei ganzzahligen Maximierungsproblemen aufgezeigt. Dabei werden die folgenden beiden Verfahren unterschieden:
- Branch-and-Bound am Ausgangsproblem. Hier wird von vornherein das ganzzahlige Maximierungsproblem (=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: Minimierungsprobleme
Vielleicht ist für Sie auch das Thema Branch-and-Bound: Minimierungsprobleme (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Brainstorming
Vielleicht ist für Sie auch das Thema Brainstorming (Lösungsverfahren für technische Probleme) aus unserem Online-Kurs Methodische Produktentwicklung interessant.