Общие принципы решения задач оптимизации методом ветвей и границ

Лекция 5

Вернемся к общей формулировке задачи комбинаторной оптимизации, описанной в разделе 1.2.

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

Будем далее для определенности отыскивать вектор при котором функция принимает минимальное значение.

Предположим также, что известны две процедуры BR и EV:процедура BR позволяет разбить область определения на две непересекающиеся подобласти и меньшего размера, а процедура EV дает возможность получить оценку минимального (нижней границы) значения функции на заданной подобласти Другими словами, нижняя граница – это число, не превышающее значения – минимального значения функции на подобласти

Метод ветвей и границ сводится к построению корневого дерева T, которое пошагово строится по следующему алгоритму:

1. Построить корневой узел дерева и пометить парой , где – нижняя граница, полученная с помощью процедуры EV.

2. Применить процедуру BR к области и сформировать две подобласти и К каждой из подобластей применить процедуру EV и получить оценки и

3. Построить два узла дочерних для коневого узла и пометить их соответственно и

4. Выбрать в текущем дереве T такой лист, в метке которого значение нижней границы не превышает значения границы в остальных листах дерева T, и применить к подобласти, соответствующей выбранному листу, процедуру BR. К каждой из сформированных новых подобластей применим процедуру EV и получить их нижние границы. Построить два новых узла дерева по тому же принципу, что и в пункте 3.

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

6. Найденное значение является оптимальным решением.

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

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

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

Впервые метод ветвей и границ был предложен А. Лендом и А. Дойгом в 1960 г. для решения общей задачи целочисленного линейного программирования [17].

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