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

Впервые метод ветвей и границ был предложен в 1960 г. в работе Лэнд и Дойг применительно к задаче целочисленного линейного программирования. Однако эта работа не оказала заметного непосредственного влияния на развитие дискретного программирования. Фактически «второе рождение» метода ветвей и границ связано с работой Литтла, Мурти, Суини и Кэрел , посвященной задаче коммивояжера; в этой же работе было впервые предложено и общепринятое теперь название метода «метод ветвей и границ». Начиная с этого момента появляется весьма большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех (да еще применительно к «классически трудной» задаче о коммивояжере) объясняется тем, что Литтл, Мурти, Суини и Кэрел первыми обратили внимание на широту возможностей метода ветвей и границ, отметили важность использования специфики задачи и сами весьма удачно этой спецификой воспользовались.

В § 1 настоящей главы излагается общая идея метода ветвей и границ; в § 2 - алгоритм Лэнд и Дойг для задачи целочисленного линейного программирования, в § 3 - метод Литтла и др. авторов для задачи коммивояжера.

§ 1. Идея метода ветвей и границ

1.1. Рассмотрим задачу дискретного программирования в следующей общей форме.

Минимизировать

при условии

Здесь G - некоторое конечное множество.

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

I. Вычисление нижней границы (оценки).

Часто удается найти нижнюю границу (оценку) целевой функции на множестве планов (или на некотором его подмножестве т. е. такое число что для имеет место

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

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

Еще не подвергавшиеся разбиению множества

заново обозначаются через

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

III. Пересчет оценок. Если множество то, очевидно,

Поэтому, разбивая в процессе решения некоторое множество на подмножества

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

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

V. Признак оптимальности. Пусть

и план X принадлежит некоторому подмножеству Если при этом

то X - оптимальный план задачи (1.1) - (1.2).

Доказательство непосредственно следует из определения оценки.

Обычно этот признак применяется на некотором этапе ветвления (т. е., говоря формально, при ; см. п. II).

VI. Оценка точности приближенного решения. Пусть

Если X - некоторый план исходной задачи (т. е. ), то

Доказательство и здесь сразу следует из определения оценки.

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

1.3. Изложим формальную схему метода ветвей и границ.

0-й шаг. Вычисляем оценку . Если при этом удается найти такой план X, что

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

Если оптимальный план не найден, то по некоторому способу разбиваем множество на конечное число подмножеств

и переходим к шагу.

1-й шаг. Вычисляем оценки Если при этом удается найти такой план X, что для некоторого и

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

Если же оптимальный план не найден, то выбираем «наиболее перспективное» для дальнейшего разбиения множество по следующему правилу:

Разбиваем множество на несколько (обычно не пересекающихся) подмножеств.

Рассмотрим задачу дискретного программирования в общем виде:

Найти -вектор неизвестных, D- конечное

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

Идея метода состоит в разбиении D на непересекающиеся подмножества Di (эта процедура называется ветвлением) и вычислении верхней и нижней границ целевой функции на каждом из подмножеств. Нижнюю границу будем обозначать Н, а верхнюю Е. Соответственно Hi Eo, то это подмножество не содержит точку оптимума и может быть исключено из дальнейшего рассмотрения. Если верхняя граница Ei H заменяем Н на min Hi. Если Е=Н, то задача решена, иначе надо продолжить процедуру ветвления и вычисления верхней и нижней границ. При этом разбиению на очередном шаге могут подвергаться все или только некоторые подмножества до достижения равенства верхней и нижней границ, причём не на отдельном подмножестве, а для допустимой области в целом.

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

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

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

Рис. 5.1.

Теперь подмножествами Di являются множества траекторий, каждая из которых проходит через соответствующую i-ую точку.

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

Эффективность такого подхода зависит от точности получаемых оценок, т.е. от Ei - Hi, и от затрат времени на их вычисление.

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

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

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева - это подмножества частично упорядоченных вариантов решений.
Вершина (i, j) соответствует подмножеству всех маршрутов, содержащих ребро (i,j), а вершина (i*,j*) - подмножеству всех маршрутов, где это ребро отсутствует.
Процесс разбиения на эти подмножества можно рассматривать как ветвление дерева. Поэтому метод называется методом поиска по дереву решений , или методом ветвей и границ .
Метод ветвей и границ представляет собой алгоритм направленного перебора множества вариантов решения задачи. Сущность метода ветвей и границ состоит в том, что от корня дерева ветвятся не все вершины.

Метод ветвей и границ решения целочисленных задач линейного программирования (ЦЗЛП)

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

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

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

Согласно общей идее метода, сначала решается задача с ослабленными ограничениями (задача линейного программирования). Пусть хr - целочисленная переменная, значение xr* которой в оптимальном решении ослабленной задачи является дробным. Интервал < xr < +1 не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение хr должно удовлетворять одному из неравенств xr ≤[ xr* ] или хr ≥[ xr* ] +1.
Введение этих условий в задачу с ослабленными ограничениями порождает две не связанные между собой задачи. В таком случае говорят, что исходная задача разветвляется (или разбивается) на две подзадачи. Осуществляемый в процессе ветвления учет необходимых условий целочисленности позволяет исключить части многогранника допустимых решений, не содержащие точек с целыми координатами.

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

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

Рассмотрим задачу целочисленного линейного программирования (ЗЦЛП) :
Найти вектор , максимизирующий линейную форму (3.1)
и удовлетворяющий условиям:

x 1 , x 2 ,…,x p –целые (p≤n) (3.4)
Пусть, для каждой целочисленной переменной можно указать верхнюю и нижнюю границы, в пределах которых безусловно содержатся ее оптимальные значения, то есть
V j ≤x j ≤ W j , (3.5)
При этом в систему функциональных ограничений необходимо включить р неравенств (3.5).

В начале любой S-й итерации метода ветвей и границ необходимо иметь:
1. Основной список задач линейного программирования, каждая из которых должна быть решена в последующих итерациях (на первой итерации список содержит одну ЗЛП- задачу 1 (3.1- 3.3) и (3.5).
2. Нижнюю границу оптимального значения линейной формы задачи (3.1) - (3.3), (3.5) Z0 (s) . На первой итерации в качестве Z0 (1) можно взять значение функции f(x) в любой целочисленной точке x, лежащей внутри области(3.2) - (3.5). Если такую точку указать трудно, то можно положить Z0 (1) = - ∞, но это приводит к значительному увеличению числа итераций.

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

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

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

Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план 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) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

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

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

Метод можно применять как к полностью, так и частично целочисленным задачам.

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

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

Алгоритм:

1. Задается начальное значение рекорда и в список задач помещается исходная задача без требования целочисленности переменных.

2. Анализируется список задач: если он пуст, то переход на шаг 6. Иначе выбирается одна из задач с удалением ее из списка.

3. Выбранная задача решается одним из методов линейного программирования. Если задача неразрешима или оптимальное значение критерия L* £ Z , ветвь обрывается (задача прозондирована). Переход на шаг 2.

4. Полученное решение анализируется на целочисленность. Если решение целочисленное, оно фиксируется, рекорду присваивается оптимальное значение критерия решенной непрерывной задачи (Z :=L* ), ветвь обрывается и осуществляется переход на шаг 2.

5. Выбирается одна из переменных, имеющих нецелочисленные значения. По ней производится ветвление: порождаются 2 задачи, одна образуется присоединением к решенной (родительской) задаче условия х j £ , другая – добавлением к родительской ограничения х j ³ +1. Эти задачи заносятся в список задач. Переход на шаг2.

6. Вывод результатов (если значение рекорда больше начального, получено оптимальное решение исходной задачи, иначе задача неразрешима).

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

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

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

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

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

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

Нельзя оценить число задач, которые придется решать; Отсутствие признака оптимальности. Оптимальность устанавливается только по исчерпании списка задач; Размерность ограничена примерно 100.