6. Общая схема метода ветвей и границ .

Впервые метод ветвей и границ был предложен в 1960 году в работе Лэнд и Дойг применительно к задаче целочисленного линейного программирования. Дальнейшее развитие этого метода было выполнено в 1963 году в работе Литтла, Мурти, Суини и Кэрел, посвященной решению задачи коммивояжера. Основными понятиями метода ветвей и границ являются: нижняя оценка; ветвление; правило пересчета оценок; признак оптимальности. Общая схема реализации алгоритма включает следующие этапы:

1. Определяется начальное множество G₀, которое представляет собой множество всех решений. Это множество может состоять из множества перестановок, сочетаний, размещений и т.д. Элементы этого множества решений явно не записываются, а указываются правила их формирования. Графически множество G₀ представляется в виде корневой вершины дерева. Для множества G₀ находится нижняя оценка. Правило нахождения зависит от постановки решаемой задачи. В общем случае нижняя оценка должна удовлетворять следующим требованиям:

должна иметь качественную интерпретацию;

должна быть косвенно связана с критерием;

сравнительно просто вычисляться;

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

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

первый вариант предлагает вычисление точного решения задачи о назначениях венгерским методом;

второй вариант основан на получении приближенного решения двойственной задачи о назначениях. В качестве приближенного решения используется так называемая сумма приводящих констант. Для вычисления этой суммы применяется процедура приведения исходной матрицы C к матрице C₀, в которой на месте минимальных элементов находятся нулевые элементы, причем в каждой строке и в каждом столбце имеется, по крайней мере, один такой элемент. Если из этих элементов можно сформировать замкнутый маршрут, то он будет оптимальным решением, и длина этого маршрута совпадает с суммой приводящих констант, т.е. сумма приводящих констант матрицы С является нижней оценкой для задачи коммивояжера.

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

Исходное множество G₀ делится на ряд непересекающихся между собой подмножеств G₁,…,G_,…,G_(1), количество подмножеств равно (1). Принцип разбиения исходного множества на подмножества, а также количество подмножеств зависят от типа решаемой задачи. В задаче коммивояжера исходное множество G₀ всегда делится только на два подмножества: и . Подмножество содержит все те перестановки, в которых имеется непосредственный переход из r города в m, а подмножество включает перестановки, в которых такой переход отсутствует (рис. 2.2).

В задаче трех станков исходное множество делится на n непересекающих подмножеств, где n – количество деталей, которые должны быть обработаны. Полученные подмножества имеют следующие свойства: подмножество содержит все те перестановки, которые начинаются с детали № 1, а подмножество – с детали № 2 и т.д.