5. Метод ветвей и границ
 

Алгоритм метода ветвей и границ похож на алгоритм с возвратом, он также использует дерево решений и применим для широкого круга дискретных комбинаторных задач. Если алгоритм с возвратом направлен на нахождение одного или нескольких решений, удовлетворяющих определённым условиям, то алгоритмы ветвей и границ ориентированны преимущественно на оптимизацию.

В дереве решений для каждого узла (вершины) определяется некоторая функция стоимости. Цель – найти конфигурацию, на которой функция стоимости дос-тигает максимального или минимального значения. Алгоритмы ветвей и границ, как правило, довольно сложны. Для сокращения процесса поиска оптимального решения используется метод поиска, основанный на правилах вычёркивания ветвей. Сущность метода ветвей и границ рассмотрим на примере решения задачи бивалентного линейного программирования.
Пример.

Имеются единичные ресурсы х₁, х₂,…х_n. Применение каждого ресурса х_i даёт прибыль с_j. Необходимо выбрать такие ресурсы хi, которые обеспечивают наибольшую прибыль
maxP=max∑c_jx_j при ограничениях
∑a_ijx_j ≤b_i, i=1,2,…m и x_j=0 или 1, j=1,2,…n.

Построим двоичное дерево решений следующим образом. Ветви, отходящие от корня (узла нулевого уровня), будут соответствовать выбору ресурса x₁: левая ветвь — ресурс выбран (x₁ = 1), правая ветвь — ресурс не выбран (x₁ = 0). Аналогично левые ветви, исходящие из узлов (к - 1)-го уровня, соответствуют выбору ресурса Х_k (х_k = 1), к = 1,2,...,n, а правые — (х_k = 0). В результате получаем идеально сбалансированное дерево высоты n с 2ⁿ листьями.

Поиск оптимального решения осуществляется обходом дерева. Для конкретности рассмотрения примем порядок левого нисходящего обхода Preorder. Это означает, что сначала двигаемся по левым поддеревьям вниз до конца, затем возвращаемся на предыдущий уровень и двигаемся по правым поддеревьям. Каждому узлу к-го уровня (к = 0,1,2,...,n) соответствует некоторый k-мерный вектор с нуль-единичными элементами, который позволяет однозначно вычислить значение прибыли для этого узла
P_k= ∑c_jx_j
и определить, удовлетворяются ли условия
∑a_ijx_j≤b_i , i=1,2,…m.

Корню дерева (к = 0) соответствуют отсутствие ресурсов и нулевая прибыль Р = 0. При обходе по мере посещения узлов дерева, удовлетворяющих нашим ус-ловиям, выбирается максимальное текущее значение прибыли Р_i, и запоминается соответствующий ей к-мерный вектор Х_k.

Пусть мы находимся в некотором промежуточном узле к-го уровня, в котором удовлетворяются наши условия. Прибыль в этом узле составляет:
P_k=∑c_jx_j
что соответствует выбранной комбинации ресурсов х₁,х₂,…х_k.

Целесообразно ли двигаться дальше вниз от этого узла? Поскольку движение по правой ветви вниз на один уровень не приводит к выбору нового ресурса (х_k+1=0), то и значение прибыли не изменяется. Поэтому вопрос касается только движения вниз по левой ветви.

Если бы теперь мы выбрали все оставшиеся ресурсы (х_k+1 = 1, …,х_n=1), т.е. двигались бы до конца по левым ветвям, то прибыль увеличилась бы и составила:
P_k+m=∑c_jx_j+∑c_m

Это максимально возможное значение прибыли при движении от рассматриваемого узла. Поэтому движение вниз от этого узла имеет смысл только тогда, когда Р_k+m > Р_t , в противном случае необходимо возвращаться назад.

Таким образом, текущее максимальное значение прибыли P_t он деляет границу движения вниз от данного узла, и ветви рассматриваемого узла вычеркиваются, т.е. от дальнейшего обхода исключаются все узлы-потомки.

Если же Р_k+m> Р_t, то обход дерева по левым поддеревьям продолжается. Придя в следующий узел, т.е. выбрав х_k+1=1, проверяем, удовлетворяются ли условия
∑a_ijx_j≤b_i , i=1,2,…m.

Если да, то вычисляем новое значение прибыли, при необходимости обновляем текущее максимальное значение прибыли Р_t, и продолжаем движение вниз по левым поддеревьям по рассмотренному алгоритму. Если эти условия не удовлетворяются или мы уже обработали конечный узел (лист) поддерева, то возвращаемся назад на один или несколько уровней и начинаем обход правого поддерева. Нужно отметить, что движение по правой ветви вниз на один уровень всегда осуществляется безусловно, так как при этом значение прибыли не изменяется и не нарушаются наши условия.

По завершении обхода как результат получаем искомое максимальное значение прибыли max Р = Р_t, и оптимальный вектор X^*, у которого единичные элементы соответствуют выбранным ресурсам.