ZU DEN KURSEN!

Operations Research 2 - Branch-and-Bound am Minimierungsproblem (optimale Lösung)

Kursangebot | Operations Research 2 | Branch-and-Bound am Minimierungsproblem (optimale Lösung)

Operations Research 2

Branch-and-Bound am Minimierungsproblem (optimale Lösung)

Es soll im folgenden das Branch-and-Bound Verfahren anhand eines ganzzahligen Minimierungsproblems dargestellt werden. Es wird hier zur Festlegung der Schranken nicht das Ausgangsproblem $P_0$ betrachtet, sondern das angepasste Problem $P'_0$. Dazu wird für das gegebene ganzzahlige Minimierungsproblem die Ganzzahligkeitsbedingung vernachlässigt und zunächst mittels Simplex-Algorithmus oder grafisch die optimale Lösung für jedes Teilproblem $P_i$ ermittelt. Diese ermittelte optimale Lösung wird dann in die Zielfunktion eingesetzt und der optimale Zielfunktionswert bestimmt. 

Bestimmung der oberen Schranke für den 0. Ast

Das angepasste Minimierungsproblem muss zunächst in die Standardform (Maximierungsproblem, $\le$-Nebenbedingungen, Nichtnegativitätsbedingung) umgeformt werden. Danach wird es in die Normalform überführt. Sind auf der rechten Seite keine negativen Werte gegeben, so kann sofort der primale Simplexalgorithmus angewandt werden um eine optimale Lösung zu erhalten. Sind negative Werte auf der rechten Seite gegeben, so wird zunächst der duale Simplexalgorithmus angewandt um eine zulässige Lösung zu erhalten. Danach kann der primale Simplexalgorithmus angewandt werden. Die ermittelte optimale Lösung wird dann in die Zielfunktion eingesetzt. 

Merke

Hier klicken zum Ausklappen

Alternativ kann die optimale Lösung auch - ohne Umformung in die Standardform- grafisch ermittelt werden.

Der ermittelte optimale Zielfunktionswert wird dann als untere Schranke $\underline{F}_0$ gewählt. 

Zusätzlich zu der lokalen unteren Schranke muss noch eine obere Schranke für den 0. Ast betrachtet werden, welche nicht überschritten werden darf. Diese ist bei Minimierungsproblemen gegeben durch $\overline{F} = \infty$.

Das Problem wird dann in zwei Teilprobleme $P_1$ und $P_2$ verzweigt. Begonnen wird mit derjenigen Variablen, die den größten optimalen Wert aufweist. 

Die resultierenden Teilprobleme $P_i$ müssen dann separat betrachtet werden und wieder mittels Simplexalgorithmus oder grafisch die optimale Lösung $\underline{F}_i$ unter Vernachlässigung der Ganzzahigkeitsbedingung bestimmt werden, indem die verzweigten Nebenbedingungen eingesetzt werden. Ein Teilproblem braucht nicht weiter betrachtet werden, wenn gilt:

Methode

Hier klicken zum Ausklappen

Fall a: $\underline{F}_i \ge \overline{F}$. Die ermittelte optimale Lösung (durch Simplex bei Weglassen der Ganzzahligkeitsbedingung) ist größer als die beste zulässige ganzzahlige Lösung (obere Schranke des Teilsproblems).

Fall b: $\underline{F}_i < \overline{F}$. Die ermittelte optimale Lösung des Teilproblems ist kleiner als die bereits gefunde beste zulässige ganzzahlige Lösung. Diese Lösung ist zudem ganzzahlig und ebenfalls zulässig. Es wird

$\overline{F} := \underline{F}_i $

gesetzt. Es existiert demnach eine neue obere Schranke, welche die Ganzzahligkeitsbedingung erfüllt und zulässig ist.

Fall c: Es existiert keine zulässige Lösung.

Das Branch-and-Bound-Verfahren wird im folgenden Abschnitt anhand eines Beispiels dargestellt.