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

Метод ВИГ (или метод направленного перебора) относится к группе комбинаторных методов решения как линейных, так и нелинейных ЗДП. Этот метод дает общий подход к решению ЗДП, содержащих конечное число допустимых планов, и за конечное число шагов позволяет найти точное решение задач конечной размерности. Разные реализации метода объединяются общей идеей перехода от полного перебора планов к целенаправленному, сокращенному перебору. Сокращение перебора осуществляется за счет массового отсечения неперспективных планов.

Пусть имеет место задача ДП в общем виде:

(1)

Здесь f(X)- скалярная функция своих аргументов, G- конечное множество.

Несмотря на большое разнообразие алгоритмов, разрабатываемых для решения прикладных задач вида (1), им всем свойственны общие основные этапы:

1. Вычисление нижней границы целевой функции f(X) на множестве G и его подмножествах (в случае решения задачи на максимум – вычисление верхней границы),

2. Разбиение множества G на дерево подмножеств,

3. Пересчет нижней границы f(X) на подмножествах,

4. Вычисление допустимых планов,

5. Проверка планов на оптимальность,

6. В случае получения приближенного решения – оценка его точности.

Рассмотрим все эти этапы.

1. Вычисление нижней границы (оценки) целевой функции f(X) на множестве планов G или его подмножествах G_iÎ G сводится к определению числа , для которого справедливо неравенство , или .

2. Разбиение (ветвление) множества G на дерево подмножеств.

Определение. Множества и называются разбиением множества G на подмножества G_i.

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

Ветвление происходит по следующей схеме:

0-й шаг. Имеется исходное множество G=G⁰. Некоторым способом его разбивают на конечное число подмножеств .

к-тый (k>0) шаг. Имеются множества , еще не подвергшиеся ветвлению. По определенному правилу, указанному ниже, среди них выбирают подмножества и разбивают их на конечное число подмножеств . Затем еще не подвергавшиеся на этом шаге разбиению множества и новые подмножества , обозначают (перенумеровывают) как . (Рис.1.)

Рис.1

3. Пересчет нижних границ целевой функции f(X) на подмножествах.

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

4. Вычисление допустимых планов.

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

5. Проверка планов на оптимальность.

Пусть имеется разбиение и найден некоторый план . Если при этом , то - оптимальный план исходной задачи (1).

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

6. Оценка точности приближенного решения.

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

Формальная схема метода ветвей и границ.

0 шаг. Обозначается . Вычисляется нижняя граница целевой функции . Если при этом удается найти такой план , что , то - оптимальный план задачи (1).

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

1 шаг. Вычисляют нижние границы на полученных подмножествах: . Если удается найти такой план , что и , то - оптимальный план задачи (1).

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

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

В противном случае снова выбирают для разбиения наиболее перспективное множество по правилу: . Далее не подвергшиеся разбиению и , на данном шаге переобозначают как .

Этот процесс ветвления продолжается до тех пор, пока не будет найдено решение задачи (1).

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