Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 2

Nachdem im vorherigen Abschnitt das gegebene Minimierungsproblem zunächst unter Vernachlässigung der Ganzzahligkeitsbedingung mittels Simplexalgorithmus gelöst wurde, wird nun das Branch-and-Bound-Verfahren für das ganzzahlige Optimierungsproblem angewandt. Nach Anwendung des Simplexalgorithmus auf das angepasste Problem resultierte die folgende optimale Lösung:

und mit dem Zielfunktionswert:

.

Die untere Schranke für das Problem ist dabei die optimale Lösung des angepassten Problems :

Diese untere Schranke resultierte für nichtganzzahlige Variablen und ist deshalb so nicht zulässig. Das Problem muss demnach verzweigt werden. Die Entscheidung mit welcher Variable begonnen wird in diesem Fall für getroffen, da diese einen größeren Wert aufweist.

Für die Teilprobleme und muss nun wieder für das angepasste Problem und (Vernachlässigung der Ganzzahligkeitsbedingung) die optimale Lösung bestimmt werden. Für muss dabei das Ausgangsproblem betrachtet werden und die Nebenbedingung hinzugefügt werden. Für das angepasste Teilrpoblem wird die Nebenbedingung mit berücksichtigt. 

Verzweigung 1

Für das angepasste Teilproblem gilt (Standardform):

      max!

u.d.N.

(1)   

(2)    

(3)

(4)

Umformen in die Normalform:

      max!

u.d.N.

(1)   

(2)    

(3)

(4)

Es wird nun wieder der duale Simplexalgorithmus angewandt um eine zulässige Lösung zu erhalten und danach der primale Simplexalgorithmus für eine optimale Lösung:

Das duale Simplexverfahren endet hier, da alle Werte auf der rechten Seite positiv sind. Es liegt also eine zulässige Lösung vor, die auch die optimale Lösung darstellt, da die Werte in der Zielfunktionszeile positiv sind. Die optimale Lösung für das angepasste Teilproblem ergibt sich demnach zu:

und mit dem Zielfunktionswert:

.

(Einsetzen der optimalen Lösung in die Zielfunktion des Minimierungsproblems).

Der ermittelte Zielfunktionswert stellt gleichzeitig die untere Schranke des Teilproblems dar. Die optimale Lösung ist nicht ganzzahlig () damit liegt keine zulässige Lösung für das Ausgangsproblem vor. Das Problem muss in jedem Fall noch verzweigt werden, allerdings muss erst die untere Schranke für das Teilproblem bestimmt werden, um herauszufinden, ob eventuell als erstes verzweigt werden muss (oder nicht verzweigt wird). 

Verzweigung 2

Für das Teilproblem gilt (Standardform):

      max!

u.d.N.

(1)   

(2)    

(3)

(4) 

Umformen in die Normalform:

      max!

u.d.N.

(1)   

(2)    

(3)

(4) 

Es kann nun wieder der duale Simplexalgorithmus angewandt um eine zulässige Lösung zu erhalten und danach der primale Simplexalgorithmus für eine optimale Lösung.