7 алгоритм метода ветвей и границ Задачи, приводящиеся к целочисленным. Задачи о неделимостях, коммивояжера и о распределении инвестиций. кратко

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

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

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

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

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

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

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

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

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

Рис 1 задачи математического программирования

Сформулируем алгоритм метода ветвей и границ. Предположим, что решается задача максимизации. Зададим нижнюю границу оптимального значения целевой функции z задачи ЦП равной - .Положим i=0.

Шаг 1.(Зондирование и определение границы.)Выбираем i-ю подзадачу линейного программировании ЛПi для исследования. Решаем ЛПi и зондируем ее, при этом возможна одна из трех ситуаций:

а) Оптимальное значение целевой функции задачи ЛПi не может улучшить текущей нижней границы.

b) ЛПi приводит к лучшему допустимому целочисленному решению, чем текущая нижняя граница

c) ЛПi не имеет допустимых решений.

Возможны два варианта:

a) Если задача ЛПi прозондирована, нижняя граница изменится только при условии, что найдено лучшее значение задачи ЦП. Если все подзадачи прозондированы, необходимо закончить вычисления: оптимальным решением задачи ЦП является то, которое соответствует текущей нижней границе, если таковая существует. Иначе положить i=i+1 и повторить Шаг 1.

b) Если задача ЛПi не прозондирована, переходим к Шагу 2 для выполнения ветвления.

Шаг 2.(Ветвление) Выбираем одну из целочисленных переменных x_j, оптимальное значение x_j* в оптимальном решении задачи ЛПi не является целым числом. Об этом говорит сайт https://intellect.icu . Исключаем из пространства допустимых решений [x_j*]< x_j*<[x_j*]+1 путем формирования двух подзадач ЛП, которые соответствуют ограничениям x_j[x_j*] и x_j [x_j*]+1..

Полагаем i=i+1 и переходим к Шагу 1.

Для решения задачи минимизации в алгоритме необходимо заменить нижнюю границу верхней (начальное значение которой равно ).

Задачи, приводящиеся к целочисленным.

задачи о неделимостях .

1. Задачи о покрытии множества.

Примером задачи о покрытии множества может быть задача о размещении складов, при котором расстояние от склада до каждого потребителя не превышает 100 км. Другим примером может служить определение числа и месторасположения студенческих общежитий, при котором студент тратит на дорогу до университета не более 1 часа, задача размещения пожарных команд, при котором расстояние до любой точки города покрывается за 5 мин.

Задача о покрытии множества может быть сформулирована так:

при ограничениях:

Величины a_ij называются коэффициентами покрытия. Они принимают значения, равные единице, если потребитель находится в пределах j-й области(покрывается j-й областью), и равна нулю в противном случае. Аналогично x_j принимает значение, равное единице, если в j-й области расположен некоторый объект и равное нулю в противном случае. Ограничения задачи требуют, чтобы каждый из m потребителей был «покрыт» по крайней мере одним из n объектов. Цель в данном случае – «покрыть» потребителей с минимальными затратами, причем c_j – стоимость помещения объекта в j-ю область. Поскольку задача является целочисленной, к ней применим любой метод решения проблем ЦП.

Пример. Университет устанавливает телефоны доверия на территории городка. Желательно установить минимальное количество телефонов таким образом, чтобы на каждой из улиц городка был расположен по крайней мере один телефон.

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

Пусть переменная x_j равна 1, если телефон расположен на перекрестке j (j=1..8) и 0 в противном случае. Задача требует размещения по меньшей мере одного телефона на каждой из 11 улиц (от A до K). Поэтому задача формируется так: z=x₁+x₂+x₃+x₄+x₅+x₆+x₇+x₈min,

x₁+x₂ 1(A)

x₂+x₃ 1(B)

x₄+x₅ 1(C)

x₇+x₈ 1(D)

x₆+x₇ 1(E)

x₂+x₆ 1(F)

х₁+х₆ 1(G)

x₄+x₇ 1(H)

x₂+x₄ 1(I)

x₅+x₈ 1(J)

x₃+x₅ 1(K)

Как видно, все переменные модели являются двоичными. В данном случае aij=1 для всех j. В общем случае они могут быть различны. Задача относится к классу комбинаторных.

задача коммивояжера .

В 1831г в Германии вышла книга под названием «Кто такой коммивояжер и что он должен делать для своего процветания?». Одна из рекомендаций книги гласила: «Важно посетить как можно больше мест возможного сбыта, не посещая ни одно из них дважды». По-видимому, это была первая формулировка задачи коммивояжера.

Имеется n городов. Расстояния между любой парой городов известны и составляют a_ij (i,j=,i j). Если прямого маршрута между городами i и j не существует, тоa_ij=. Расстояния между городами удобно записывать в виде матрицы A=(a_ij)_nn, где a_ij=.

j i	1	2	…	n
1		a12	…	a1n
2	a21		…	a2n
…	…	…	…	…
n	an1	an2	…

В общем случае матрица несимметрична.

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

Если задачу определить в терминах теории графов, городам соответствуют вершины графа, а дорогам – дуги. Задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Под длиной контура понимают сумму длин дуг.

Определим булевы переменные так:

1, если коммивояжер переезжает из города i в город j (i,j=)

x_ij=

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

Тогда задача заключается в описании переменных x_ij:

(1)

с ограничениями:

(въезд в город j) (2)

(выезд из города i) (3)

(4)

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

Условия a_ij= исключаются в оптимальном решении значения x_ij=1, как не имеющие смысла. Ограничения (2) требуют, чтобы маршрут включал только один въезд в каждый город, а (3) – только один выезд из каждого города. Целевая функция (1) – это длина гамильтонова контура.

Решение задачи, описанной только условиями (1)-(3) не обязательно является контуром, проходящим через все города. В частности, в результате решения (1)-(3) могут быть получены два и более несвязных контуров. Для устранения возможности образования не гамильтоновых контуров служат ограничения (4). Покажем, что они действительно исключают все частичные контуры и не исключают ни одного гамильтонова контура.

Рассмотрим частичный контур, проходящий через k-й город (kij=1 для k переменных. Складывая все неравенства вида (4), содержащие k переменных x_ij=1, получим неравенство , которое недопустимо (разности u_i-u_j взаимно уничтожатся). Следовательно (4) исключает возможность образования любого частичного контура.

Теперь установим, что существуют значения переменных u_i, удовлетворяющие ограничениям (4) для любого гамильтонова контура. Положим, что u_i=p(p=1,2,…n), если город i в гамильтоновом контуре посещается по порядку P-м, причем u₁=1 и u_j=u_i+1, j=; j- номер города в гамильтоновом контуре. Так, например, в контуре 1-3-6-8-… значения u_i будут следующими u₁=1,u₃=2,u₆=3,u₈=4,…Из этого предположения следует, что при x_ij=0 соответствующее неравенство (4) принимает вид u_i-u_jn-1 и всегда выполняется, поскольку u_ij>1 при j1. При x_ij=1 эти ограничения выполняются как равенства: u_i+u_j+nx_ij=p-(p+1)+n=n-1.

Таким образом доказано, что для любого гамильтонова контура существуют значения переменных u_i, удовлетворяющие ограничениям (4).

При решении задачи коммивояжера прямым перебором требуется (n-1)! вариантов. Уже при количестве городов 16-20 время решения задачи возрастает до астрономических цифр. Поэтому задачу коммивояжера решают методами ЦЛП.

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

задача о распределении инвестиций .

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

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

1, если проект j утвержден

x_j=

0, если проект j не утвержден

Задача ЦЛП выглядит так:

z=20x₁+40x₂+20x₃+15x₄+30x₅ max

5x₁+4x₂+3x₃+7x₄+8x₅25

x₁+7x₂+9x₃+4x₄+6x₅25

8x₁+10x₂+2x₃+x₄+10x₅25

x₁,x₂,x₃,x₄ {0,1}.

Вау!! 😲 Ты еще не читал? Это зря!

• метод северо-западного угла
• МЕТОД ГОМОРИ
• ОГРАНИЧЕНИЯ ТИПА «ИЛИ-ИЛИ»
• метод отсекающих плоскостей
• целочисленное программирование

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