В чем заключается метод ветвей и границ в дискретном программировании?
Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. 1
Суть метода заключается в упорядоченном переборе вариантов, рассмотрении лишь тех из них, которые оказываются по определённым признакам перспективными, и отбрасывании бесперспективных вариантов. 2
В основе метода лежит идея последовательного разбиения множества допустимых решений на подмножества. 24 На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. 24
Для метода ветвей и границ необходимы две процедуры: 1
- Ветвление. 1 Множество допустимых значений переменной разбивается на подобласти (подмножества) меньших размеров. 1 Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. 1
- Нахождение оценок (границ). 1 Заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной. 1
В основе метода лежит следующая идея: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти, то первая может быть исключена из дальнейшего рассмотрения. 1
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. 1
Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. 1
