Branch-and-Bound am Maximierungsproblem

Es wird zunächst das Branch-and-Bound Verfahren für ein Maximierungsproblem aufgezeigt, wobei das gegebene ganzzahlige Maximierungsproblem betrachtet wird. Es wird also bei dem in den nächsten 3 Abschnitten vorgestellten Branch-and-Bound Verfahren vorher keine Optimallösung ermittelt. Im Abschnitt Branch-and-Bound am angepassten Problem (optimale Lösung) wird dann gezeigt, wie das Branch-and-Bound Verfahren durchgeführt wird, wenn zunächst eine optimale Lösung (mittels Simplexalgorithmus bzw. grafischem Verfahren) ermittelt wird und anhand dieses Ergebnisses der Entscheidungsbaum aufgestellt wird. Beide hier vorgestellen Verfahren führen zum selben Ergebnis.