Загрузка...

Схема метода ветвей и границ


Для решения ЗЛЦП существует 3 группы методов:

1) Методы отсечения или отсекающих плоскостей

2) Комбинаторные методы

3) Эвристические методы

Познакомимся с одним из универсальных и наиболее эффективных методов 2-ой группы – методом ветвей и границ. Комбинаторные методы – это методы целенаправленного упорядоченного перебора. Общая идея методов заключается в замене полного перебора всех возможных вариантов частичными переборами значительно меньших объемов. Комбинаторные методы эффективны при решении ЗЛП, ЗЛЦП, динамического программирования, нелинейного программирования и др. Наиболее эффективным и распространенным методом является метод ветвей и границ.

Идею метода рассмотрим на примере мешка с монетами, в котором есть одна фальшивая, отличающаяся большим весом. Рассмотрим задачу дискретного программирования в общем виде. Для функции clip_image002необходимо найти max при условии clip_image004, где D(1) – некоторое конечное или счетное множество, f – функция любого вида. Часто удается найти верхнею границу или оценку целевой функцию Z на множестве D(1) . Эту оценку будем обозначать j( D(1)) и называть оценкой множества D(1). Она будет удовлетворять условию:

clip_image006 clip_image008

Рассмотрим схему метода ветвей и границ по шагам:

Исходный, или нулевой шаг

Находим оценку j( D(1)). Если при этом удалось найти такой план clip_image010 и для которого clip_image012, то clip_image014 — оптимальный план. Если оптимальный план не найден, то переходим к 1 шагу.

Множество D(1) некоторым образом разбиваем на конечное число непересекающихся подмножеств в Di(1), clip_image016 таких что clip_image018 и clip_image020. Затем вычисляем верхние границы или оценки этих подмножеств.

clip_image022

Если при этом удалось найти такой план clip_image024, где r=[1,r], который удовлетворяет условиям: clip_image026, то план clip_image014[1]является оптимальным.

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

Пусть это будет подмножество Dn(1) и для него j( Dn(1))clip_image028 j( Di(1))

— — — — — — — — — — — — —

К шаг (К=2, 3,…..)

" К=2 Dn(1) некоторым образом разбивают на конечное число непересекающихся подмножеств Dn,i(1), clip_image030 и затем все неподвергающиеся делению подмножества переобозначаем: clip_image032

На К – ом шаге будем иметь конечное число неподвергающихся делению подмножеств clip_image034. Вычислим оценки этих подмножеств j( Di(К)). Если при этом удалось найти такой план clip_image036, что clip_image038, то clip_image014[2] – оптимальный план.

и т. д.

Схематически процесс нахождения оптимального плана можно изобразить в виде графа:

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

Авторами метода ветвей и границ является 4 американских математика: Литл, Мурти, Суини и Кэрол, которые разработали его в 1963 г. при решении задачи Комивояжора.

Загрузка...