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

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

На рис.1 пространство допустимых решений задачи целочисленного линейного программирования представлено точками. Соответствующая начальная задача линейного программирования (обозначим ее ЛП0) получается путем отбрасывания условия целочисленности. Ее оптимальным решением будет =3.75, =1.25, z=23.75.

Рис.1.

Так как оптимальное решение задачи ЛП0 не удовлетворяет условия целочисленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что в конечном счете получается оптимальное решение задачи целочисленного линейного программирования. Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи ЛП0 не является целочисленным. Например, выбирая (=3.75), замечаем, что область 3 ? ?4 пространства допустимых решений задачи ЛП0 не содержит целочисленных значений переменной и, следовательно, может быть исключена из рассмотрения, как бесперспективная. Это эквивалентно замене исходной задачи ЛП0 двумя новыми задачами линейного программирования ЛП1 и ЛП2, которые определяются следующим образом:

Пространство допустимых решений ЛП1 = пространство допустимых решений ЛП0 + (), пространство допустимых решений ЛП2 = пространство допустимых решений ЛП0 + ().

На рис.2 изображены пространства допустимы решений задач ЛП1 И ЛП2 . Оба пространства содержат все допустимые решения исходной задачи ЦЛП. Это обозначает, что задачи ЛП1 и ЛП2 «не потеряют» решения начальной задачи ЛП0.

Рис.2.

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

Новые ограничения и взаимоисключаемы, так что задачи ЛП1 и ЛП2 необходимо рассматривать как независимые задачи линейного программирования, что и показано на Рис.3. Дихотомизация задач ЛП - основа концепции ветвления в методе ветвей и границ. В этом случае называется переменной ветвления.

Рис.3.

Оптимальное решение задачи ЦЛП находятся в пространстве допустимых решений либо в ЛП1, либо в ЛП2. Следовательно, обе подзадачи должны быть решены. Выбираем сначала задачу ЛП1 (выбор произволен), имеющую дополнительное ограничение?3.

Максимизировать при ограничениях

Оптимальным решением задачи ЛП1 является, и. Оптимальное решение задачи ЛП1 удовлетворяет требованию целочисленности переменных и. В этом случае говорят что задача прозондирована. Это означает, что задача ЛП1 не должна больше зондироваться, так как она не может содержать лучшего решения задачи ЦЛП.

Мы не можем в этой ситуации оценить качество целочисленного решения, полученного из рассмотрения задачи ЛП1, ибо решение задачи ЛП2 может привести к лучшему целочисленному решению (с большим решением в целевой функции z). Пока мы можем лишь сказать, что значение является нижней границей оптимального (максимального) значения целевой функции исходной задачи ЦЛП. Это значит, что любая нерассмотренная подзадача, которая не может привести к целочисленному решению с большим значением целевой функции, должна быть исключена, как бесперспективная. Если же нерассмотренная подзадача может привести к лучшему целочисленному решению, то нижняя граница должна быть надлежащим образом изменена.

При значении нижней границы исследуем ЛП2. Так как в задачи ЛП0 оптимальное значение целевой функции равно 23.75 и вес ее коэффициенты являются целыми числами, то невозможно получить целочисленное решение задачи ЛП2, которое будет лучше имеющегося. В результате мы отбрасываем подзадачу ЛП2 и считаем ее прозондированной.

Реализация метода ветвей и границ завершена, так как обе подзадачи ЛП1 и ЛП2 прозондированы. Следовательно, мы заключаем, что оптимальным решением задачи ЦЛП является решение, соответствующей нижней границе, а именно, и.

Если бы мы выбрали в качестве ветвлении переменную то ветвления и скорость нахождения оптимального решения были бы другими Рис.4.

Рис.4. Дерево ветвлений решений

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

Дальнейшие поиски в Интернете не принесли ожидаемого результата: либо сложное для не-математиков теоретическое описание, либо понятное, но с ошибками.

Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.

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

Кратко о методе - это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.

Исправленный алгоритм, для нахождения действительно минимального маршрута

Алгоритм состоит из двух этапов:

Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

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

Второй (основной) этап

1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.

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

2. Теперь наше множество S разбиваем на множества - содержащие ребро с максимальным штрафом(S w) и не содержащие это ребро(S w/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества S w/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h,k), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества S w примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для S w равна сумме оценки затрат для S и r(h,k), где r(h,k) - сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.

Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.

Небольшая оптимизация - подключаем эвристику

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух детей - Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

Теперь, собственно, об ошибках в той публикации

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

Доказательство

Вернемся к картинке в начале поста:

А вот решение с исправленным алгоритмом:

Ответ: путь:3=>4=>2=>1=>5=>3 длина: 41
Как видите, включая ребро 5:2 в решение будет ошибкой. Что и требовалось доказать

График сравнения метода ветвей и границ и потраченного времени для случайной таблицы от 5х5 до 10х10:

График максимального и минимального потраченного времени для матриц от 5х5 до 66х66.

Попробовать с подробным решением можно

Метод ветвей и границ − один из комбинаторных методов. В отличие от метода Гомори применим как к полностью, так и частично целочисленнным задачам.

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

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

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

или
, или

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

Очевидно, что возможен один из следующих четырех случаев.

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

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

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

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

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

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

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

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

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

Пример . Найти методом ветвей и границ решение задачи целочисленного программирования

Решение . Находим оптимальный план сформулированной задачи симплексным методом без учета целочисленности переменных, а именно решаем задачу 1.

Оптимальный план задачи 1 линейного программирования

при
.

Для исходной задачи, с учетом целочисленности переменных, полученное решение не является оптимальным.

Для поиска целочисленного оптимального решения разделим интервал изменения переменной x 1 на две области, а именно x 1  и x 1 = 10 , и разобьем заданную задачу на две новые задачи.

Нижняя граница линейной функции не изменилась: Z 0 = 0. Решаем одну из задач, например задачу 3, симплексным методом. Получаем, что условия задачи противоречивы.

Решаем задачу 2 симплексным методом. Получаем оптимальный целочисленный план поставленной задачи 2, который является также оптимальным планом задачи 1:

при
.

Таким образом, в результате одного ветвления задачи было найдено ее оптимальное решение.

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

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

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

Ветвление производится последовательным введением дополнительных ограничений. Пусть x k – целочисленная переменная, значение которой в оптимальном решении получилось дробным. Интервал [β k ] ≤ x k ≤ [β k ]+1 не содержит целочисленных компонентов решения. Поэтому допустимое целое значение x k должно удовлетворять одному из неравенств x k ≥[β k ]+1 или x k ≤[β k ]. Это и есть дополнительные ограничения. Введение их в методе ветвей и границ на каждом шаге порождает две не связанные между собой подзадачи. Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.

Применение метода ветвей и границ рассмотрим на конкретном примере.

Пример 1. Методом ветвей и границ F(x) = 2x 1 + 3x 2 при ограничениях

3x 1 +4x 2 ≤24

2x 1 +5x 2 ≤22

x 1,2 ≥0 - целые

1-й шаг метода ветвей и границ. с отброшенными условиями целочисленности с помощью симплекс-метода (табл. 1 – 3).

По данным табл. 3 запишем оптимальное нецелое решение

		; x * 2 =2	4	; F max =16	6
			7		7

Таблица 1 - симплекс-таблица для задачи ЛП

Таблица 2 - симплекс-таблица для задачи ЛП

Таблица 3 - симплекс-таблица для задачи ЛП

Графическая интерпретация задачи приведена на рис. 1. Здесь ОДЗП представлена четырехугольником ABCD, а координаты вершины С совпадают с x * 1 и x * 2 . Обе переменные в оптимальном решении являются нецелыми, поэтому любая из них может быть выбрана в качестве переменной, инициирующей процесс ветвления.

Пусть это будет x 2 . Выбор x 2 порождает две подзадачи (2 и 3), одна из них получается путем добавления ограничения x 2 ≥3 к исходной задаче, а другая – путем добавления ограничения x 2 ≤2. При этом ОДЗП разбивается на две заштрихованные области (рис. 1), а полоса значений 2 < x 2 < 3 исключается из рассмотрения. Однако множество допустимых целочисленных решений сохраняется, порожденные подзадачи содержат все целочисленные решения исходной задачи.

Рисунок 1 - графическая интерпритация решения примера методом ветвей и границ

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

Пусть вначале решается подзадача 3 с дополнительным ограничением x 2 ≤2 или x 2 + x 5 = 2 . Из табл. 3 для переменной x 2 справедливо следующее выражение -2/7x 3 +3/7x 4 +x 2 =18/7 или x 2 =18/7+2/7x 3 -3/7x 4 , тогда 2/7x 3 -3/7x 4 +x 5 =-4/7 . Включаем ограничение в табл. 3, при этом получим новую таблицу (табл. 4).

Осуществляя оптимизацию решения, переходим к табл. 5, которой соответствует решение

		; x * 2 =2	; F max =16	2
				3

Переменная x 1 нецелая, поэтому ветвление необходимо продолжить; при этом возникают подзадачи 4 и 5 с ограничениями x 1 ≤5 и x 1 ≥6 соответственно. Полоса значений 5 < x 1 < 6 исключается из рассмотрения.

Таблица 5 - симплекс-таблица для задачи ЛП

3-й шаг метода ветвей и границ. Решаются подзадачи 4 и 5. Из рис. 1 видно, что оптимальное целочисленное решение подзадачи 4 достигается в вершине К с координатами x * 1 =5, x * 2 =2, однако это не означает, что найден оптимум исходной задачи. Причиной такого вывода являются еще не решенные подзадачи 3 и 5, которые также могут дать целочисленные решения. Найденное целочисленное решение F = 16 определяет нижнюю границу значений целевой функции, т.е. меньше этого значения оно быть не должно.

Подзадача 5 предполагает введение дополнительного ограничения x 1 ≥6 в подзадачу 3 . Графическое решение на рис. 1 определяет вершину L с координатами x * 1 =6, x * 2 =3/2 , в которой достигается оптимальное решение подзадачи 5: F max = 16.5 . Дальнейшее ветвление в этом направлении осуществлять нецелесообразно, так как большего, чем 16, целого значения функции цели получить невозможно. Ветвление подзадачи 5 в лучшем случае приведёт к другому целочисленному решению, в котором F = 16.

4-й шаг метода ветвей и границ. Исследуется подзадача 2 с ограничением x 2 ≥3, находится её оптимальное решение, которое соответствует вершине М (рис. 1) с координатами x * 1 =3.5, x * 2 =3. Значение функции цели при этом F max =16, которое не превышает найденного ранее решения. Таким образом, поиск вдоль ветви x 2 ≥3 следует прекратить.

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

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

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

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

Общий план решения задачи коммивояжера

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

Построение матрицы с исходными данными.
Нахождение минимума по строкам.
Редукция строк.
Нахождение минимума по столбцам.
Редукция столбцов.
Вычисление оценок нулевых клеток.
Редукция матрицы.
Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

Подробная методика решения задачи коммивояжера

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

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di ) и выписываем его в отдельный столбец.

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка .

4. Нахождение минимума по столбцам

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка .

6. Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку ». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М ». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

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

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

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

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9 .

9. Вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4 .

Общая длина пути: L = 30 .

Практическое применение задачи коммивояжера

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

Решение задачи коммивояжера онлайн

Галяутдинов Р.Р.