Метод ветвей и границ -- один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
Алгоритм решения:
Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план 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) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.
Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод.
целочисленный программирование задача коммивояжер ранец
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. За счет каких преобразований удается построить сопряженный базис при добавлении
отсекающего ограничения?
Метод ветвей и границ относится к комбинаторным методам решения целочисленных задач и применим как к полностью, так и к частично целочисленным задачам.
Суть метода ветвей и границ – в направленном частичном переборе допустимых решений. Будем рассматривать . Вначале она решается без ограничений на целочисленность. При этом находится верхняя граница 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 следует прекратить.
Отметим, что алгоритм метода ветвей и границ является наиболее надёжным средством решения целочисленных задач, он положен в основу большинства прикладных программ для ПЭВМ, используемых для этих целей.
Для решения задач линейного программирования имеется широкий набор разнообразных машинных программ, которые избавляют от трудоёмкого процесса вычислений вручную. Однако интерпретация информации, выведенной на печать, невозможна без чёткого представления о том, почему и как работает .
Метод ветвей и границ − один из комбинаторных методов. В отличие от метода Гомори применим как к полностью, так и частично целочисленнным задачам.
Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам полезными для нахождения оптимального решения.
Идея метода ветвей и границ состоит в следующем: пусть решена ослабленная задача без ограничения целочисленности, и - целочисленная переменная, значение которой в оптимальном плане является дробным. Тогда интервал
не
содержит допустимых решений с целочисленной
координатой
.
Следовательно, допустимое целое значение
должно удовлетворять
или
,
или
Введение этих условий в задачу порождает две несвязанные между собой задачи с одной и той же целевой функцией, но непересекающимися областями допустимых значений переменных. В этом случае говорят, что задача разветвляется.
Очевидно, что возможен один из следующих четырех случаев.
Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи на новых ограничениях по этой переменной, полученных разделением ее ближайших к решению целочисленных значений.
Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Для определенности здесь и далее полагаем, что решается задача о максимуме целевой функции. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и вместе со значением целевой функции на нем дает искомое решение.
Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, произвести ветвление по дробной переменной и построить две новые задачи.
Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и производим ветвление на две новые задачи, разбивая область изменения этой переменной на две, ограниченные целыми числами справа и слева соответственно.
Таким образом, процесс построения все новых и новых задач может быть представлен на рисунке в виде ветвистого дерева, с вершиной, обозначенной «задача 1», и отходящими от этой вершины ветвями. Такая последовательность действий при нахождении оптимального решения задачи целочисленного программирования нашла свое отражение в названии этого метода.
Исходная вершина отвечает оптимальному плану исходной задачи 1, а каждая соединенная с ней ветвью вершина отвечает оптимальным планам новых задач, построенных для новых ограничений по одной из переменных, имеющих в оптимальном плане задачи 1 значение в виде дробного числа.
Каждая из вершин имеет свои ответвления, при этом на каждом шаге выбирается та вершина, для которой значение целевой функции будет наибольшим.
Если на некотором шаге будет получен план, имеющий целочисленные значения, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.
Пример . Найти методом ветвей и границ решение задачи целочисленного программирования
Решение . Находим оптимальный план сформулированной задачи симплексным методом без учета целочисленности переменных, а именно решаем задачу 1.
Оптимальный план задачи 1 линейного программирования
при
.
Для исходной задачи, с учетом целочисленности переменных, полученное решение не является оптимальным.
Для поиска целочисленного оптимального решения разделим интервал изменения переменной x 1 на две области, а именно x 1 и x 1 = 10 , и разобьем заданную задачу на две новые задачи.
|
|
|
Нижняя граница линейной функции не изменилась: Z 0 = 0. Решаем одну из задач, например задачу 3, симплексным методом. Получаем, что условия задачи противоречивы.
Решаем задачу 2 симплексным методом. Получаем оптимальный целочисленный план поставленной задачи 2, который является также оптимальным планом задачи 1:
при
.
Таким образом, в результате одного ветвления задачи было найдено ее оптимальное решение.
Впервые метод ветвей и границ был предложен в 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 - оптимальный план.
Если же оптимальный план не найден, то выбираем «наиболее перспективное» для дальнейшего разбиения множество по следующему правилу:
Разбиваем множество на несколько (обычно не пересекающихся) подмножеств.