ZU DEN KURSEN!

Operations Research 2 - Branch-and-Bound: Maximierungsprobleme

Kursangebot | Operations Research 2 | Branch-and-Bound: Maximierungsprobleme

Operations Research 2

Branch-and-Bound: Maximierungsprobleme

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.