Метод ветвей и границ с. Задача коммивояжера - метод ветвей и границ. Что это такое

23.02.2019

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

На рис.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. Дерево ветвлений решений

4.3.1. Общая схема метода «ветвей и границ». Другим широко применяемым для решения задач дискретного программирования методом является метод ветвей и границ . Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его «второе рождение» произошло в 1963 г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере .

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

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

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

Алгоритм является итеративным, и на каждой итерации происходит работа с некоторым подмножеством множества D . Назовем это подмножество текущим и будем обозначать его как D ( q ) , где q - индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D (1) =D ), и для него некоторым способом вычисляется значение верхней оценки для целевой функции max f(x) ≤ ξ( D (1)). Стандартная итерация алгоритма состоит из следующих этапов:

1°. Если можно указать план x (q ) ∊D (q ) , для которого f(x (q ) ) ≤ξ( D (q )), то x (q ) =х* - решение задачи (4.29).

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

Для каждого подмножества находятся оценки сверху (верхние границы) для целевой функции ξD 1 ( q ) , ξD 2 ( q ) , ..., ξD l 1 ( q ) , уточняющие ранее полученную оценку ξD ( q ) , то есть ξD i ( q ) ≤ ξD ( q ) , i ∊1:l q . Возможно одно из двух:

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

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

2.2. Если такой план не найден, то выбирается одно из множеств D i ( q ) , i ∊1:l q (как правило, имеющее наибольшую оценку

Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как D 1 ( q +1) , D 2 ( q +1) ,..., D l ( q +1) ( q +1) , после чего процесс повторяется.

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

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

4.3.2. Решение ЦЗЛП методом ветвей и границ. Рассмотрим применение алгоритма метода ветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, через D ( q ) обозначается подмножество множества допустимых планов задачи. Перед началом первой итерации (q = 1) в качестве текущего множества берется все множество D (D (1) = D ), после чего решается стандартная задача линейного программирования (D (1) , f ). Нетрудно заметить, что она является непрерывным аналогом

исходной задачи (4.2)-(4.3). Если найденный оптимальный план (1) содержит только целочисленные компоненты, то он является и оптимальным планом для (4.2)-(4.3): (1) = x* . В противном случае значение f ( (1)) становится оценкой (верхней границей) значения целевой функции на множестве D (1) , и мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.

1) Выбирается некоторая нецелочисленная компонента плана k ( q ) . Поскольку в оптимальном плане она должна быть целой, то можно наложить ограничения x k ≤ [ k ( q ) ] и x k ≥ [ k ( q ) ]+1. Таким образом, D ( q ) разбивается на подмножества

Графическая интерпретация такого разбиения множества D ( q ) приведена на рис. 4.4.

2) Решаются задачи линейного программирования

Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих множествах:

Если оптимальный план для одной из решенных задач удовлетворяет условию

и содержит только целые компоненты, то, значит, найдено решение основной задачи (4.2)-(4.3). В противном случае среди всех концевых подмножеств , полученных как на предыдущих (D i ( q )), так и на текущем (D 1 ( q ) , D 2 ( q )) этапе, выбирается область с наибольшей оценкой ξ(D i ( q )). Она становится текущим рассматриваемым подмножеством (D ( q +1)). Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.

При решении задач (D 1 ( q ) , f ) и (D 2 ( q ) , f ) можно воспользоваться результатами решения предыдущей задачи (D ( q ) , f ). Рассмотрим вариант организации вычислительного процесса на примере задачи ( 1 ( q ) , f ) (для ( 2 ( q ) , f ) он выглядит аналогично с точностью до знаков неравенств).

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

Тогда система ограничений задачи (D ( q ) , f ) может быть представлена как

а получаемая на ее основе система ограничений задачи ( 1 ( q ) , f ) как

где х n +1 ≥ 0 - фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для преобразования неравенства в строгое равенство.

Очевидно, что 1≤k≤m , т. к. небазисные компоненты оптимального плана (m +1≤j≤n ) равны нулю, т. е. являются заведомо целочисленными. Тогда с учетом сделанных предположений о виде базиса можно записать:

Как видно из (4.39), в k -м столбце имеется всего два отличных от нуля элемента: в k -й и (m +1)-й строках. Если вычесть из (m +1)-го уравнения k -e, то, учитывая, что [ά k ] – ά k =-{ά k }, получим эквивалентную систему:

Проведенные преобразования системы ограничений D 1 ( q ) позволили явно выделить сопряженный базис, образуемый столбцами с номерами 1,..., m , n +1, и соответствующий ему псевдоплан (ά 1 , ..., ά m , 0,...., 0, -{ά k }), т.е. для решения задачи (D 1 ( q ) , f ) может быть применен алгоритм двойственного симплекс-метода. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5.

Для случая задачи (D 2 ( q ) , f ) преобразование симплекс-таблицы, получаемое на базе аналогичных рассуждений, приведено на рис. 4.6.

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

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

КЛЮЧЕВЫЕ ПОНЯТИЯ

Ø Ø Задачи с неделимостями.

Ø Ø Экстремальные комбинаторные задачи.

Ø Ø Задачи с разрывными целевыми функциями.

Ø Ø Правильное отсечение.

Ø Ø Метод Гомори.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

4.1. Какие основные проблемы возникают при решении дискретных задач?

4.2. Сформулируйте задачу о ранце.

4.3. Какие экономико-математические модели могут быть сведены к задаче о коммивояжере?

4.4. Приведите пример моделей с разрывными целевыми функциями.

4.5. Какой принцип используется для построения правильного отсечения в методе Гомори?

4.6. Перечислите основные этапы, входящие в «большую» итерацию метода Гомори.

4.7. Какую роль играет алгоритм двойственного симплекс-метода при решении целочисленной

линейной задачи методом Гомори?

4.8. Перечислите принципиальные идеи, лежащие в основе методов ветвей и границ.

4.9. Как производится построение отсечения при решении целочисленной линейной задачи методом

ветвей и границ?

4.10. Опишите схему решения целочисленной задачи линейного программирования методом ветвей и

4.11. За счет каких преобразований удается построить сопряженный базис при добавлении

отсекающего ограничения?

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

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

Алгоритм решения:

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

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

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

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

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

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

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

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х 0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

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

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

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

целочисленный программирование задача коммивояжер ранец

Общее описание

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

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

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

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

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

Применение

Метод используется для решения некоторых NP-полных задач, таких как:

См. также

Примечания

Wikimedia Foundation . 2010 .

Смотреть что такое "Метод ветвей и границ" в других словарях:

метод ветвей и границ - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва] Тематики электротехника, основные понятия EN branch and bound method … Справочник технического переводчика

метод - метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди … Словарь-справочник терминов нормативно-технической документации

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр … Википедия

У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force) метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… … Википедия

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

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

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

Книги

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