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

Министерство  образования и науки РФ

Филиал  Красноярского Педагогического  Университета

имени В.П.Астафьева  в городе Канске

факультет информатики 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

реферат 
 
 
 
 
 
 
 

                                          Выполнила:

                                           Дерезина Мария  Александровна

                                           студентка 3 курса

                                          Проверил:

                                           Баранов Юрий Сергеевич 

                                          Оценка:____________________ 
 
 
 
 
 
 
 
 

Канск, 2010

 

Содержание: 

 

 

Введение

 

     Дискретная оптимизация  как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

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

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

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

       Применение этого метода возможно в решении самых сложных задач, когда неприменимы классические математические методы, а также линейное, нелинейное и динамическое программирование.

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

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

 

1. Понятие о методе ветвей и границ

 

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

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

       Вычисление  нижней границы является важнейшим элементом данной схемы.  

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

 

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

 

       Пусть стоит задача:

           (1)

       где D — конечное множество.

       Алгоритм  является итеративным, и на каждой итерации происходит работа с некоторым подмножеством множества D. Назовем это подмножество текущим и будем обозначать его как D^(q) , где q — индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D⁽¹⁾ =D), и для него некоторым способом вычисляется значение верхней оценки для целевой функции . Стандартная итерация алгоритма состоит из следующих этапов:

       1.Если   можно   указать   план   ,   для   которого , то — решение задачи (1).

       2. Если такой план не найден, то область определения D^(q) некоторым образом разбивается на подмножества , удовлетворяющие условиям:

           (2)

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

       2.1. Если существует такой план  , что

          то этот план оптимальный.

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

       

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

         
 
 
 

       Рис. 1 

       Схема дробления множества D представлена на рис. 1 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.

       Конкретные  реализации метода ветвей и границ связаны с правилами разбиения  на подмножества (правилами ветвления) и построения оценок значений целевых  функций на данных подмножествах (границ). 

 

3. Применение  метода ветвей и границ в решении прикладных задач

 

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

3.1. Задача о ранце

       Имеется ранец (машина, самолет), с известной  его грузоподъемностью. Известен набор  предметов, которые желательно взять с собой. Известны вес и полезность каждого предмета. Нужно выбрать набор предметов, загружаемых в ранец, так чтобы полезность набора оказалась наибольшей. Задача имеет множество применений кроме собственно туристического. Например, нужно загрузить боевой самолет ракетами и бомбами так, чтобы нанести наибольший урон противнику. Или загрузить самолет или машину МЧС так, чтобы доставить пострадавшим груз наибольшей полезности.

       Обозначим:

        – номера предметов;

         – вес  -го предмета;

         – полезность (цена) -го предмета;

       Q – грузоподъемность ранца;

         – количество  -х предметов, загруженных в ранец.

       3.1.1.  Математическая модель задачи.

       Найти ; при ограничениях: – булевы (двоичные) переменные.

       Сформулирована  задача линейного программирования. Казалось бы, зачем нужен еще какой-то особый метод, когда задача решается методом линейного программирования? Дело в том, что задачи линейного программирования с булевыми и вообще целочисленными переменными решаются как раз с применением метода ветвей и границ.

       3.1.2. Пример решения задачи о ранце

       В машину грузоподъемностью 35 т. загрузить  предметы с наибольшей суммарной  ценой (полезностью). Характеристика предметов  дана в таблице:

Номер предмета	1	2	3	4	5	6
Вес                                (т.)	4	7	11	12	16	20
Цена                         (тыс. руб.)	7	10	15	20	27	34

         т.

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

       Получили  вариант загрузки 6–3–1,       т. .

         – значение целевой функции.

        Начинаем строить  дерево и оценивать ветви. Первый шаг показан на рис.1. 
 
 

       Рис.1

       Дерево  строится перевернутым – корни вверху, ветви внизу: так удобнее их строить. Каждый кружок изображает некоторое состояние. Внутри кружка записываются номер груза, добавляемого на очередном шаге, и его количество. Над кружками через вертикальную черту показываются: слева – достигнутая загрузка ранца (машины), справа – суммарная цена (полезность) загруженных предметов. Корень дерева фиксирует начало построения. Загружено 0 предметов (внутри кружка), общая загрузка 0 т (слева над кружком), общая цена 0 (справа над кружком).

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

       Дальнейшее  построение дерева показано на рис.2.