Общая схема метода ветвей и границ.

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

Основное содержание метода.

Рассмотри задачу дискретного программирования:

(3.9) (3.10)

где G – некоторое конечное множество. В основе метода лежит выполнение нескольких этапов решения задачи:

1) Вычисление нижней границы (оценки). Часто можно указать, вычислить нижнее значение целевой функции на множестве планов Gили на его подмножестве , то есть найти такое число (или ), что для любого имеет место (или для любого имеет место ).

2) ветвление (разбиение множества планов Gна подмножества). Ветвление, то есть построение дерева подмножеств, происходит по такой многошаговой процедуре:

0-й шаг: имеется множество . Некоторым образом оно разбивается на конечное число (обычно не пересекающихся) подмножеств: .

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

3) пересчет границ (оценок): Очевидно, что если , то

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

4) Вычисление планов. Способ вычисления планов в последовательно разветвляемых подмножествах в сильной степени зависит от операции конкретной задачи.

5) признак оптимальности. Пусть и план Х принадлежит некоторому подмножеству . Если при этом , , то Х является оптимальным планом задачи (3.9), (3.10).

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

Алгоритм метода ветвей и границ:

0-й шаг: вычисляем , если при этом удается найти такой план Х, что , то - оптимальный план. Если оптимальный план не найден, то некоторым способом разбиваем на конечное число подмножеств и переходим к шагу 1.

1-ый шаг: вычисляем . Если при этом удается найти такой план Х что , для некоторого r () и , то - оптимальный план.

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

заново обозначаем через и переходим к шагу 2.

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

32 Метод ветвей и границ, решение линейных целочисленных задач.(Метод Ленд и Дойг)