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

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