Inhaltsverzeichnis
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
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
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
Das Problem wird dann in zwei Teilprobleme
Die resultierenden Teilprobleme
Methode
Fall a:
Fall b:
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.
Weitere interessante Inhalte zum Thema
-
Branch-and-Bound: Maximierungsprobleme
Vielleicht ist für Sie auch das Thema Branch-and-Bound: Maximierungsprobleme (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Dualer Simplexalgorithmus
Vielleicht ist für Sie auch das Thema Dualer Simplexalgorithmus (Grundlagen des Operations Research 1) aus unserem Online-Kurs Operations Research 2 interessant.