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

       Рис.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. Затраты на перемещение между городами заданы следующей матрицей: