Метод ветвей и границ алгоритм

Метод ветвей и границ алгоритм

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

Пример №1 . В задаче методом Гомори (или методом ветвей и границ) найти оптимальные решения задач целочисленного линейного программирования. Дать геометрическую интерпретацию процесса решений задач.
Z=3x1 + 2x2 → max
при ограничениях:
x1 + x2 ≤ 13
x1 — x2 ≤ 6
-3x1 + x2 ≤ 9
x1≥0, x2 ≥0
x1, x2 – целые числа.

Пример №2 .
5x1 + 2x2 ≤ 14
2x1 + 5x2 ≤ 16
x1 , x2 – целые числа
Z = 3x1 + 5x2 → max
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
5x1+2x2≤14
x1≥2

Решив систему уравнений, получим: x1 = 2, x2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16

Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
2x1+5x2≤16
x1≤1

Решив систему уравнений, получим: x1 = 1, x2 = 2.8
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2.8 = 17

Решим графически задачу 111 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x2≥3 (3)
x1≥1 (4)
x1≥0 (5)
x2≥0 (6) Задача не имеет допустимых решений. ОДР представляет собой пустое множество

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

Метод ветвей и границ впервые предложен в 1960 году Аилсой Ленд и Элисон Дойг [1] для решения задач целочисленного программирования.

Читайте также:  Почему в почте не отображаются картинки

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

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

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

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

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

Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце.

Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.

Читайте также:  Тариф смарт действует по всей россии

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

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

Алгоритм Литтла является частным случаем МВиГ, т.е. в худшем случае его сложность равна сложности полного перебора. Теоретическое описание выглядит следующим образом:

Имеется множетво S всех гамильтоновых циклов рафа. На каждом шаге в S ищется ребро (i, j), исключение которого из маршрута максимально увеличит оценку снизу. Далее происходит разбиение множества на два непересекающихся S1 и S2. S1 — все циклы, содержащие ребро (i, j) и не содержащие (j, i). S2 — все циклы, не содержащие (i, j). Далее вычисляется оценка снизу для длины пути каждого множества и, если она превышает длину уже найденного решения, множество отбрасывается. Если нет — множества S1 и S2 обрабатываются так же, как и S.

Алгоритмическое описание

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

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

  1. Из каждого элемента каждой строки вычитается минимальный элемент данной строки. При этом минимальный элемент строки прибавляется к нижней границе
  2. Из каждого столбца аналогично вычитается минимальный элемент и прибавляется к нижней границе.
  3. Для каждого нулевого элемента M(i, j) вычисляется коэффициент, равный сумме минимальных элементов строки i и столбца j, исключая сам элемент (i, j). Этот коэффициент показывает, насколько гарантированно увеличится нижняя граница решения, если исключить из него ребро (i, j)
  4. Ищется элемент с максимальным коэффициентом. Если их несколько, можно выбрать любой (все равно оставшиеся будут рассмотрены на следующих шагах рекурсии)
  5. Рассматриваются 2 матрицы — M1 и M2. M1 равна M с удаленными строкой i и столбцом j. В ней находится столбец k и строка l, в которых не содержится inf1 и элемент M(k, l) приравнивается inf1. Как было сказано ранее, это необходимо во избежание преждевременных циклов (т.е. на первых этапах (k, l) == (j, i)). Матрица M1 соответствует множеству, сожержащему ребро (i, j). Вместе с удалением столбца и строки ребро (i, j) включается в путь.
  6. M2 равна матрице M, у которой элемент (i, j) равен inf2. Матрица соответствует множетсву путей, не сожержащих ребро (i, j) (важно понимать, что ребро (j, i) при этом не исключается).
  7. Переход к п.1 для матриц M1 и M2.
Читайте также:  Разрешение экрана монитора как поменять

Эвристика состоит в том, что у матрицы M1 нижняя граница не больше, чем у матрицы M2 и в первую очередь рассматривается ветвь, содержащая ребро (i, j).

Пример

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

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

1 2 3 4
inf 20 18 12 8
1 5 inf 14 7 11
2 12 18 inf 6 11
3 11 17 11 inf 12
4 5 5 5 5 inf

Реализация

Шаг 1

Получение нулей в каждой строке и каждом столбце.

Ссылка на основную публикацию
Adblock detector