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

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

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

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

Определяя эти числа, находим симплексным  методом решение двух задач линейного программирования

 

- целые .

и

- целые .

Возможны четыре случая при решении этой пары задач:

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

Таким образом, при решении задачи получаем схему:

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

 

Пример

Найдем решение задачи

- целые .

 

Решение. Находим  решение без учета целочисленности задачи симплекс методом.

 

 

Рассмотрим следующую пару задач:

Задача №1

 

 

и задача №2

 

Первая задача имеет  оптимальный план

 

 

вторая – неразрешима.

Проверяем на целочисленность план первой задачи. Это условие не выполняется, поэтому строим следующие задачи:

Задача №1.1

 

 

и задача №1.2

 

 

Задача №1.2 неразрешима, а задача №1.1 имеет оптимальный план , на котором значение целевой функции .

В результате получили, что  исходная задача целочисленного программирования имеет оптимальный план и .

3. Решение задачи коммивояжера методом ветвей и границ

 

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

 

3.1 Постановка задачи

 

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

Очевидно, в полном орграфе  циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес Ґ, считая, что Ґ – это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом Ґ можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе.

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

пусть – полный ориентированный граф и – весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

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

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

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

Слова привести матрицу  по строкам означают, что все строки матрицы приводятся. Аналогичный  смысл имеют слова привести матрицу  по столбцам.

Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.

Весом элемента матрицы  называют сумму констант приведения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на Ґ. Следовательно, слова самый тяжелый нуль в матрице означают, что в матрице подсчитан вес каждого нуля, а затем фиксирован нуль с максимальным весом.

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

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

множеству G всех обходов  коммивояжера сопоставлено чис-ло j(G) и  матрица M₁.

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

Сопоставим множеству  следующую матрицу M_1,1: в матрице M₁ заменим на Ґ число в клетке . Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M_1,1; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в дальнейшем через j( ), сопоставим множеству .

Теперь множеству  тоже сопоставим некую матрицу M_1,2. Для этого в матрице M₁ заменим на Ґ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M_1,2. Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j( ), сопоставим множеству .

Теперь выберем между  множествами  и то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j( ) и j( )).

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

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

К выбранному множеству  с сопоставленными ему матрицей и числом j повторим все то же самое  и так далее, пока это возможно.

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

После этого осуществляется улучшение рекорда вплоть до получения  окончательного ответа.

 

3.2 Условие задачи

 

Студенту Иванову поручили разнести некоторые важные документы  из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кратчайший путь. Расстояния между объектами даны в таблице

.	12-ый корпус	Белый дом	КРК «Премьер»	Администрация	5-ый корпус
12-ый корпус	0	6	4	5	2
Белый дом	6	0	3	3,5	4,5
КРК «Премьер»	4	3	0	5,5	5
Администрация	5	3,5	5,5	0	2
5-ый корпус	2	4,5	5	2	0

 

3.3 Математическая модель задачи

 

Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус – 1, Белый дом – 2, КРК «Премьер» – 3, Администрация – 4 и 5-ый корпус – 5. Соответственно общее количество пунктов . Далее введем альтернативных переменных , принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (8) и (9).

 

     (8)

     (9)

 

Для обеспечения непрерывности  маршрута вводятся дополнительно n переменных и дополнительных ограничений (10).

 

      (10)

 

Суммарная протяженность  маршрута F, которую необходимо минимизировать, запишется в следующем виде:

 

      (11)

 

В нашем случае эти условия запишутся в следующем виде:

 

 (8 а)