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

1. Введение.

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

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

Впервые метод ветвей и границ был предложен  Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.

2. Описание метода

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

В основе метода ветвей и границ лежат следующие модули (процедуры):

1) ветвления  множества возможных решений; 

2) вычисления  нижних и верхних оценок целевой  функции.

3) определение  правила обхода дерева;

4) отбрасывание неперспективных множеств;

5) проверка на окончание;

2.1 Правила ветвления

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

1. ветвление множества допустимых решений исходной задачи D;
2. ветвление множества D' получаемого из D путем снятия условия целочисленности на переменные.

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

Второй  способ ветвления – более универсальный, чем первый. Ветвление осуществляется, если в оптимальном решении значение хотя бы одной целочисленной по исходной постановке задача переменной не является целочисленным. Среди этих переменных выбирается одна, например j – я. И задача разбивается на две подзадачи, первая – при ограничении новой j-ой переменной целой частью старой j-ой переменной, вторая - при ограничении новой j-ой переменной целой частью старой j-ой переменной +1.

2.2 Формирование оценок целевой функции

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

2.3 Правило обхода дерева

Существует  множество различных стратегий  обхода. Наиболее распространены три  из них или их модификации:

1. «По минимуму\ максимуму оценки». Для следующего разбиения выбирается множество, имеющее к данному шагу минимальную\ максимальную оценку.
2. Односторонний обход дерева. Для последующего разбиение выбирается множество, например левое. Если ветвь оказывается пройденной, то происходит возвращение к ближайшему из предыдущих шагов.
3. Смешанная стратегия. Совмещает в себе 1 и 2.

2.4 Отбрасывание неперспективных  множеств

Множество неперспективно, если относительно него принимается  решение о выбрасывании его из рассмотрения. Исключение происходит с использованием оценок. Т.О. если оценка некоторого множества больше имеющегося рекорда (для задачи на минимум), то среди точек данного множества нет оптимальных точек.

2.5 Работа метода останавливается в соответствии с критерием оптимальность: оценки всех подмножеств не меньше (для задачи на минимум) имеющегося решения. В качестве критериев остановки могут применяться и другие критерии, например условие на незначение отклонения вновь полученного рекорда.