Метод гомори ветвей и границ. Метод ветвей и границ целочисленного программирования. Основные понятия

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

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

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

Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 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:

при
.

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

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

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

Oooo. ooooooooo .ooooo. ooooooooo .ooooo.
.dP""Y88b d"""""""8" 888" `Y88. d"""""""8" d88" `8.
]8P" .8" 888 888 .8" Y88.. .8"
.d8P" .8" `Vbood888 .8" `88888b.
.dP" .8" 888" .8" .8" ``88b
.oP .o .8" .88P" .8" `8. .88P
8888888888 .8" .oP" .8" `boood8"

Введите число, изображенное выше:

Подобные документы

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

курсовая работа , добавлен 05.03.2012


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

курсовая работа , добавлен 01.10.2009


Сущность и описание симплекс-метода и улучшенного симплекс-метода (метода обратной матрицы), преимущества и недостатки их применения в линейном прогаммировании. Листинг и блок-схема программы на языке Turbo Pascal для решения математической задачи.

курсовая работа , добавлен 30.03.2009


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

курсовая работа , добавлен 20.12.2008


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

курсовая работа , добавлен 25.11.2011


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

курсовая работа , добавлен 08.11.2009


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

курсовая работа , добавлен 28.06.2015

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

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

Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода.

Рассмотрим реализацию метода ветвей и границ для задачи коммивояжёра и задачи о рюкзаке.

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

Пример.

Пусть в задаче коммивояжера задана следующая матрица стоимостей переездов

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

.

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

,

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

Суммируя элементы и , получим константу приведения:

.

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

.

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

Разбиваем множество всех допустимых маршрутов на два подмножества:

– подмножество, содержащее дугу ;

– подмножество, не содержащее дугу

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

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

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

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

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

Очевидно, что если, например,V 22 окажется хуже рекорда илиD 22 =, правая ветвь обрывается (говорят также, что она прозондирована). Если же оценкаV 22 будет лучше Z , производится ветвление: множествоD 22 разбивается на 2 подмножества. Решение завершится, когда все ветви будут прозондированы.

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

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

Каким образом разбивать перспективное множество на подмножества;

Как определять верхнюю оценку критерия на рассматриваемом множестве.

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

Пусть известен диапазон возможных значений j -й переменной

0  х j  d j ,

которая в непрерывном оптимальном решении оказалась нецелочисленной и равной x j * . Тогда целочисленное значение этой переменной может достигаться либо в интервале 0  х j 
,либо в интервале
+1 х j  d j , где
- целая часть (рис. 7.6).

Это соответствует разбиению непрерывного множестваD н на два непересекающихся подмножества D 1 н и D 2 н , объединение которых не равно D н . В то же время такое разбиение целочисленного множества удовлетворяет соотношениям (7.9). При этом целочисленные множества, как исходное, так и порожденные, включены в соответствующие непрерывные множества. Следовательно, поиск целочисленного решения на непрерывном множестве даст тот же результат, что и на целочисленном. Легко увидеть, что приведенное выделение подинтервалов по одной переменной приводит к разбиению исходного множества на два подмножества при любом числе переменных.

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

Выбор начального значения рекорда зависит от ситуации:

если известно какое-либо целочисленное значение, то рекорд принимается равным критерию в этом решении;

при положительности всех коэффициентов критерия можно взять нулевое значение рекорда;

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

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

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

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

Пример 7.3 . Применим алгоритм ветвей и границ к задаче

L= 9x 1 + 5x 2  max;

3x 1 - 6x 2  1;

5x 1 +2x 2  28;

 x j  0 , целые.

Отбрасывая условие цедочисленности, получаем непрерывную задачу, которую помещаем в список задач. Так как коэффициенты критерия положительны, начальное значение рекорда принимаем равным нулю. Берем из списка единственную задачу и решаем ее. Получаем оптимальное решение в вершине А (рис. 7.7):x 1 * =4,72; x 2 * =2,19 . Ветвление производим по переменнойx 1 . Добавляя к решенной задаче ограничение x 1 4, образуем задачу 2, а добавление x 1 5 дает задачу 3. Допустимые множества новых задач покзаны на рис. 7.7. Эти задачи помещаем в список задач. Решение задачи 2 достигается в точке В, а задачи 3 – в С. Весь ход решения исходной задачи представлен в виде дерева решений на рис. 7.10. Порядок решения задач из списка отражает счетчик итераций k . На 3-й итерации (задача 4) получено целочисленное решение со значением критерия 41 (точка D нарис. 7.8). Поэтому изменяется рекорд: Z =41.Задача 6 имеет нецелочисленное решение (вершина Е на рис. 7.9), задача 8 – целочисленное решение в точкеF. В результате после 7-й итерации рекорд становится равным 50.

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

Из приведенного дерева решений видно, что число задач в списке могло быть меньше при другом порядке решения задач. Действительно, если бы сначала были решены задачи правой ветви с рекордом Z= 50, то после решения задачи 2 не произошло бы ветвления, так как верхняя оценка оказалась бы ниже рекорда (V=L * =45,17<50).

Естественно возникает вопрос: а как на числе задач и дереве решений может отразиться выбор другой переменной для ветвления? Так, в нашем примере если после 1-й итерации произвести ветвление по переменнойx 2 , то получим дерево, показанное на рис. 7.11. Оно содержит на 2 задачи больше, чем на рис. 7.10. Конечно, оно может быть также другим при ином порядке решения задач.

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

Из алгоритма и приведенного примера следует, что ветвь обрывается по одной из трех причин:

неразрешимость задачи;

задача имеет целочисленное решение;

верхняя оценка не больше рекорда.

Теперь сделаем ряд замечаний относительно метода ветвей и границ. Как уже отмечалось, в базовом алгоритме не оговариваются правила выбора задачи и переменной. В большинстве программных реализаций метода используются правила, основанные на эвристических оценках перспективности задач и переменных. В некоторых пакетах, например, "ЛП в АСУ" предлагается несколько вариантов управления процессом решения: от автоматического до ручного, в котором пользователь может сам делать выбор как задачи, так и переменной. Кроме того, алгоритмы, основанные на методе ветвей и границ, могут существенно отличаться в связи с учетом особенностей класса задач. Например, для задачи коммивояжера, определение оценки значительно упрощено (не требуется решать непрерывную линейную задачу).

Метода ветвей и границ имеет преимущества в сравнении с методом отсечений:

накопление ошибок менее значительное, так как решение идет по разным ветвям;

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

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

Недостатки метода ветвей и границ:

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

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

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