Branch-and-Bound

Anwendung auf Probleme der ganzzahligen linearen Optimierung

Ein einfaches Beispiel

Anhand einer konkreten Aufgabenstellung zeigen wir das Verfahren.

Das Ausgangsproblem lautet:

• Maximiere   G = x₁ + x₂
• mit den Nebenbedingungen

2x₁ + x₂ ≤ 4

x₁ + 2x₂ ≤ 3

x₁, x₂ ≥ 0 ganzzahlig

Wir lassen die Ganzzahligkeitsbedingung weg und finden mit dem Simplex-Verfahren die Lösung

• G = 7/3
• x₁ = 5/3 = 1 2/3
• x₂ = 2/3

Wir fahren fort mit dem Ziel, eine Lösung mit ganzzahligem x₁ zu finden. Dazu bilden wir 2 weitere Optimierungsaufgaben, eine mit der zusätzlichen Nebenbedingung x₁ ≤ 1, die andere mit x₁ ≥ 2.

• P₁₁ – Maximiere   G = x₁ + x₂
• mit den Nebenbedingungen

2x₁ + x₂ ≤ 4

x₁ + 2x₂ ≤ 3

x₁ ≤ 1

x₁, x₂ ≥ 0

• P₁₂ – Maximiere   G = x₁ + x₂
• mit den Nebenbedingungen

2x₁ + x₂ ≤ 4

x₁ + 2x₂ ≤ 3

x₁ ≥ 2

x₁, x₂ ≥ 0

Das Problem P₁₁ hat die Lösung

• G = 2
• x₁ = 1
• x₂ = 1

Da x₁ und x₂ ganzzahlig sind, ist dies eine zulässige Lösung des Ausgangsproblems. Wir wissen aber noch nicht, ob es eine bessere Lösung gibt.

Dazu lösen wir Problem P₁₂ und erhalten:

• G = 2
• x₁ = 2
• x₂ = 0

Auch dies ist wegen der Ganzzahligkeit eine zulässige Lösung. Da sowohl für P₁₁ als auch für P₁₂ die Zielfunktion den Wert G = 2 annimmt, hat das Problem zwei optimale Lösungen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Branch-and-Bound aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung