Метод ветвей и границ. Решение задачи коммивояжера

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

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

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

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

4.1. Формальное описание 

Пусть рассматривается задача вида

                                                            f , гдеf(x) – вещественная функция, а D –конечное множество допустимых решений. Пусть d ⊆ D. Функцию b(d), ставящую в соответствие множеству d разбиение его на подмножества d₁, ..., d_N,  N > 1, будем называть ветвлением.

Вещественная функция Н(d) называется нижней границей для d, если

1)          );

2)  на одноэлементном множестве {x} верно равенство H({x}) = f(x). 

Алгоритм, реализующий метод ветвей и границ, состоит из последовательности однотипных шагов. На каждом шаге известен рекорд x⁰ и подмножества t₁, t₂, ... , t_L непросмотренных решений. В начале работы алгоритма L = 1, t₁ = D, x⁰ – произвольный элемент множества D или пустое множество (на пустом множестве положим значение функционала равным бесконечности).

На каждом шаге алгоритм начинает работу с проверки элементов разбиения. Пусть проверяется множество t_j. Множество t_j отсекается в одном из двух, последовательно проверяемых случаев: а) если H(t_j)≥  f(x⁰); б) если H(t_j) <  f(x⁰) и найден такой элемент y_j∈ t_j, что f(y_j) = min f(x)= 

x t∈ _j

= H(t_j).

В случае б происходит смена рекорда x⁰ = y_j.

Пусть t₁, t₂, ... , t_M  (M ≤ L) – неотсеченные множества (будем считать, что отсечены множества с номерами  M + 1, ..., L).

В случае M = 0  алгоритм заканчивает работу, и в качестве решения задачи принимается рекорд x⁰. При  М ≥ 1  среди множеств t₁, ..., t_M  выбирается множество для нового ветвления. Пусть таковым является множество t₁. Тогда осуществляется ветвление b(t₁) = (d₁, ..., d_N), в результате которого получаем список множеств d₁, ..., d_N, t₂, ... , t_M. Эти множества нумеруются числами от 1 до L, и начинается новый шаг алгоритма.

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

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

При определении «перспективного» элемента разбиения в основном