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

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

Метод ветвей и границ (англ. 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-полных задач, в том числе задачи коммивояжёра и задачи о ранце.

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

Пример №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) Задача не имеет допустимых решений. ОДР представляет собой пустое множество

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

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

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

Читайте также:  Nano антивирус pro лицензия

Согласно общей идее метода, сначала решается ЗЛП без учета усложненности. Пусть – целочисленная переменная, значение которой в оптимальном решении задачи без учета целочисленности является дробным. Интервал не содержит допустимые целочисленные точки, поэтому его можно исключить из области поиска решения целочисленной задачи. Это делается путем разбиения области допустимых решений нецелочисленной задачи на две области посредством введения дополнительного ограничения на целочисленную переменную для одной задачи и для другой –

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

Пример 5.2. Максимизировать

– целые.

На рисунке 5.3 показаны начальные этапы процесса разбиения исходной задачи на подзадачи в виде дерева.

Исходной является вершина 1, в которой сформулированная задача решается как задача ЛП. Оптимальное решение достигается в точке с координатами и Процесс ветвления далее можно вести по переменной или В ыберем по переменной Тогда выбор переменной порождает две подзадачи, связанные с поиском решения в двух подмножествах, полученных отсекающими ограничениями и На следующем шаге осуществляется выбор одной из подзадач 2 или 3. К сожалению, вопрос о «наилучшем» способе выбора переменной ветвления или последовательности решения подзадач пока еще не решен, и в каждом конкретном случае решается эмпирически.

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

Читайте также:  Как почистить ipad чтобы не тормозил

Рисунок 5.3 — Фрагмент процесса ветвления поиска решения

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

Пусть известна матрица расстояний между пунктами i и j . В качестве неизвестной величины введем переменную

в противном случае.

если коммивояжер из пункта i переезжает в пункт j ;

Модель задачи о коммивояжере будет иметь вид:

, (5.9)

; (5.10)

; (5.11)

. (5.12)

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

Ограничение (5.10) говорит о том, что коммивояжер должен в каждый пункт заехать только один раз, а ограничение (5.11) – из каждого пункта выехать только один раз. Ограничения (5.10) – (5.12) и дополнительное ограничение на маршруте коммивояжера создают так называемый гамильтоновый контур (по имени ирландского математика У. Гамильтона).

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

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

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

Алгоритм исключения подциклов .

Если задачу о коммивояжере ограничить только условиями (5.10) – (5.12), то она станет эквивалентной задаче о назначениях. Поэтому есть методы решения задачи, в которых используют алгоритмы решения задачи о назначениях с исключением возможностей образования подциклов [1, 8, 32].

Ссылка на основную публикацию
Метка на игральной карте
метки на картах • (побрызг) мелкие пятна на шерсти собаки • мелкие пятна, брызги на чем-нибудь • шулерская разметка рубашек...
Майл точка ру вход в почту
Чтобы войти в почтовый ящик: Наберите в строке браузера mail.ru — вы автоматически попадете на страницу мобильной версии. Нажмите надпись...
Макет таблицы в ворде
В этом курсе: Чтобы вставить базовую таблицу, на вкладке Вставка нажмите кнопку Таблица, а затем выделите нужное количество столбцов и...
Метод ветвей и границ требует
Метод ветвей и границ (англ. branch and bound ) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации,...
Adblock detector