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

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

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

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

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

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



Эта статья также доступна на следующих языках: Тайский

  • Next

    Огромное Вам СПАСИБО за очень полезную информацию в статье. Очень понятно все изложено. Чувствуется, что проделана большая работа по анализу работы магазина eBay

    • Спасибо вам и другим постоянным читателям моего блога. Без вас у меня не было бы достаточной мотивации, чтобы посвящать много времени ведению этого сайта. У меня мозги так устроены: люблю копнуть вглубь, систематизировать разрозненные данные, пробовать то, что раньше до меня никто не делал, либо не смотрел под таким углом зрения. Жаль, что только нашим соотечественникам из-за кризиса в России отнюдь не до шоппинга на eBay. Покупают на Алиэкспрессе из Китая, так как там в разы дешевле товары (часто в ущерб качеству). Но онлайн-аукционы eBay, Amazon, ETSY легко дадут китайцам фору по ассортименту брендовых вещей, винтажных вещей, ручной работы и разных этнических товаров.

      • Next

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

  • Еще приятно, что попытки eBay по руссификации интерфейса для пользователей из России и стран СНГ, начали приносить плоды. Ведь подавляющая часть граждан стран бывшего СССР не сильна познаниями иностранных языков. Английский язык знают не более 5% населения. Среди молодежи — побольше. Поэтому хотя бы интерфейс на русском языке — это большая помощь для онлайн-шоппинга на этой торговой площадке. Ебей не пошел по пути китайского собрата Алиэкспресс, где совершается машинный (очень корявый и непонятный, местами вызывающий смех) перевод описания товаров. Надеюсь, что на более продвинутом этапе развития искусственного интеллекта станет реальностью качественный машинный перевод с любого языка на любой за считанные доли секунды. Пока имеем вот что (профиль одного из продавцов на ебей с русским интерфейсом, но англоязычным описанием):
    https://uploads.disquscdn.com/images/7a52c9a89108b922159a4fad35de0ab0bee0c8804b9731f56d8a1dc659655d60.png