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

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

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

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

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

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

реферат 
 
 
 
 
 
 
 

                                          Выполнила:

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

                                           студентка 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 т. загрузить  предметы с наибольшей суммарной  ценой (полезностью). Характеристика предметов  дана в таблице:

         т.

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

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

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

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

       Рис.1

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

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

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

       Рис.2.

       Над состоянием (6-1) производим дихотомию, пытаясь загрузить пятый груз. Налево  (5-1), направо (5-0). Но ветвь (5-1) недопустима, т.к. при этом будет загружено 36 т, что превышает грузоподъемность (35 т). Ветвь (5-1) отсекается, на рисунке зачеркивается. Дальнейшее развитие системы показано на рис.3.

       Рис.3.

       Рассматриваем ветвь (6-1)–(5-0). Так как пятый предмет не берется, загрузка машины и общая цена груза не изменяются, над состоянием (5-0) записаны те же числа (20/34), что и над предыдущим состоянием (6-1).

       Строим  ветви из состояния (5-0), дихотомия (4-1) и (4-0). Вариант (4-1) возможен, но неэффективен. У состояния (4-1) нет дальнейшего развития, т. к. загрузка равна 32 т, оставшаяся грузоподъемность равна т. и ни одного предмета догрузить нельзя. Допустимая цена груза равна , где 56 – полученная нами предварительная оценка целевой функции. Поэтому вариант (4-1) отбрасывается.

       Развиваем состояние (4-0). Две ветви (3-1) и (3-0). Анализируем (3-1): загрузка 31, цена 49.  Развиваем (3-1) на две ветви (2-1) и (2-0). Состояние (2-1) имеет загрузку 38 т., превышающую грузоподъемность.  Ветвь (2-1) недопустима и поэтому отбрасывается.

       Из (2-1) возвращаемся назад в (3-1) и идем по правой ветви в (2-0), у которой грузоподъемность и оценка равны соответственно 31/49. Из состояния (2-0) есть два пути: (1-1) и (1-0). Оценка  (1-1) равна 35/56, допустима загрузка, а цена не меньше установленной оценки 56. Оставляем ветвь (1-1) для дальнейшего анализа. Т. к. (1-1) не имеет продолжений, возвращаемся обратно в (2-0) и анализируем вариант (1-0). Он допустим, но по цене 49 меньше оценки 56, поэтому вариант (1-0) отбрасывается.

       Проанализируем, как мы двигались по дереву. Начиная  от корня (0), пошли вниз и налево. И так всегда – при анализе  нового состояния производили дихотомию и двигались по левой ветви, оставляя правую для дальнейшего анализа. Как только упирались в тупик, из которого дальнейшее движение вниз невозможно, как, напр., из состояний (5-1),  (4-1), (2-1) и (1-1), то возвращались на шаг назад и начинали анализировать свободную (неразвитую) правую ветвь. Такой принцип (справа налево, а потом направо) не единственный, но нужен какой-то принцип, чтобы не запутаться и не оставить ни одной ветви без анализа.

       Из  достигнутого состояния (1-0) возвращаемся обратно в (2-0), но нет неанализированных (свободных) ветвей. Последовательно возвращаемся обратно, но свободную ветвь находим только в самом корне (0). Следовательно, все варианты от (0) в направлении (6-1) рассмотрены и лучшим оказался вариант (6-3-1), который был нами выявлен в предварительном анализе. Переходим к анализу состояния (6-0). На рисунок 4 перенесем дерево с рисунка 3, оставив только продуктивные ветви, т.е. такие, которые допустимы и увеличивают загрузку и цену.

       Рис.4.

       Состояние (6-0) анализируется так же, как раньше анализировалось (6-1). Обрывается ветвь от (4-1) на (3-1), т.к. загрузка превышает грузоподъемность ( ). Состояние (2-1) оказывается конечным, т.к. достигнута загрузка 35 т и больше ничего загрузить нельзя. Но в состоянии (2-1) цена равна 57, что больше, чем в найденном ранее варианте (6-3-1). Поэтому ветвь (6-1)-(3-1)-(1-1) отбрасываем (зачеркиваем). Лучшим становится вариант (5-4-2) с загрузкой 35 т и ценой 57. Изменяем теперь оценку границы с 56 на 57. Это значит, что ветви, по которым невозможно превысить цену 57, должны быть отброшены.

       Из (2-0) возвратимся в состояние (4-0) и оценим его перспективность. Загрузка (4-0) равна 16, а цена 27. Оставшаяся свободная грузоподъемность равна т. Наибольший прирост цены можно получить, догрузив предметы 3 и 2; при этом цена возрастет на 25 и станет равна , что меньше уже достигнутой цены 57. Следовательно, ветвь на (4–0) бесперспективна и ее нужно оборвать.

       Возвращаемся  в состояние (5-0) с загрузкой 0 и ценой 0. Оставшиеся предметы  (4, 3, 2, 1) имеют общий вес 34, и их можно погрузить. При этом цена груза составит , что меньше 57. Значит эта ветвь не перспективна, обрываем ее. Отсечение особенно успешно было проведено в состояниях (5-0) и (4-0), что существенно сократило перебор.

       Оптимальным по цене оказался вариант загрузки предметов 5, 4 и 2, общий вес при котором равен 35 т, а цена 57. Применение метода ветвей и границ дает уверенность, что оптимальный вариант не потерян.

3.2. Задача Коммивояжера

      В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил  детскую головоломку, в которой  предлагалось совершить «круговое  путешествие» по 20 городам, расположенных  в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b, … t. Обязательным условием являлось требование: каждый город за исключением первого можно посетить один раз.

    Гамильтонова  задача о путешественнике нередко  преобразуется в задачу о коммивояжере. Коммивояжер – не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно.

    Решение задачи коммивояжера методом ветвей и границ можно реализовать  с  помощью языков программирования.

3.2.1 Определения

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

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

3.2.2. Постановка задачи

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

     В терминах теории графов задачу можно  сформулировать следующим образом. Задано n вершин и матрица {c_ij}, где c_ij ≥0 – длинна (или цена) дуги (i, j), . Под маршрутом коммивояжера z будем понимать цикл i₁, i₂,…, i_n, i₁ точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера, длина маршрута l(z) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i₁ – фиксирована. Требуется найти маршрут z₀ Î Z, такой, что l(z₀)= min l(z), z Î Z.

3.2.3. Решение задачи

     Основная  идея метода ветвей и границ состоит  в том, что вначале строят нижнюю границу φ длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы множества всех маршрутов, т.е. φ(Z)≤ φ ( ), φ(Z) ≤ φ ( ).

     Сравнивая нижние границы φ ( ) и φ ( ), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

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

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

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

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

3.2.4. Разбиение множества маршрутов на подмножества

     Для выделения претендентов на включение  во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ_ij нулевых элементов этой матрицы. Степень нулевого элемента Θ_ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c_ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

     Множество маршрутов, не включающих дугу (i, j) получаем путем замены элемента c_ij на бесконечность.

3.2.5. Пример решения задачи коммивояжера методом ветвей и границ

     Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей: