ZU DEN KURSEN!

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

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

Operations Research 2

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

In diesem Abschnitt wird das Branch-and-Bound Verfahren für ein ganzzahliges Maximierungsproblem dargestellt. Die obere Schranke wird für das hier vorgestellte Verfahren aber nicht anhand des Ausgangsproblems $P_0$ ermittelt, sondern anhand des angepassten Problems $P'_0$. Für das angepasste Problem wird die Ganzzahligkeitsbedingung vernachlässigt und zunächst mittels Simplex-Algorithmus (oder grafisch) für jeden Ast und seine Teilprobleme $P_i$ die optimale Lösung 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 Maximierungsproblem muss -falls nicht vorhanden- in die Normalform umgeformt werden. 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.

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

Zusätzlich zu der lokalen oberen Schranke muss noch eine untere Schranke für den 0. Ast betrachtet werden, welche nicht unterschritten werden darf. Diese ist bei Maximierungsprobleme häufig durch die Nichtnegativitätsbedingung gegeben. Die Variablen dürfen keine negativen Werte annehmen. Die Grenze ist also $x_j = 0$. Das bedeutet die untere globale Schranke liegt bei einem Zielfunktionswert von $\underline{F} = 0$. 

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

Die resultierenden Teilprobleme $P_i$ müssen dann separat betrachtet werden und wieder mittels Simplexalgorithmus oder grafisch die optimale Lösung $\overline{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: $\overline{F}_i \le \underline{F}$. Die ermittelte optimale Lösung (durch Simplex bei Weglassen der Ganzzahligkeitsbedingung) ist kleiner als die beste zulässige ganzzahlige Lösung (untere Schranke des Teilsproblems).

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

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

gesetzt. Es existiert demnach eine neue untere 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.