ZU DEN KURSEN!

Operations Research 2 - Branch-and-Bound: Minimierungsprobleme

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

Operations Research 2

Branch-and-Bound: Minimierungsprobleme

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.