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

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

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

(14)

(15)

(16)

– целые, . (17)

В дальнейшем будем также предполагать, что допустимое множество задачи (14)-(16) ограничено.

Идея метода ветвей и границ основана на следующем элементарном факте. Рассмотрим любую переменную и некоторое целое число γ > 0. Тогда оптимальное решение задачи (14)-(17) будет удовлетворять либо линейному ограничению

, (18)

либо линейному ограничению

. (19)

Для иллюстрации возможности использования этой дихотомии предположим, что найдено оптимальное решение задачи (14)-(16), в котором, к примеру, . Поставим и решим еще две задачи линейного программирования, каждая из которых содержит условия (15) и (16). Однако, в одной из этих задач к ним добавлено условие , а в другой – . Предположим далее, что каждая из этих задач имеет оптимальное решение, удовлетворяющее условию (17). Тогда решение, доставляющее меньшее значение целевой функции, на самом деле является оптимальным решением исходной задачи (14)-(17). Обычно одна (или обе) из таких задач не имеет оптимального решения, удовлетворяющего (17), вследствие чего могут потребоваться дополнительные вычисления. Излагаемый далее алгоритм определяет систематическую схему применения (18) и (19), обеспечивающую в конечном счете получение оптимального решения.

Описание алгоритма. На каждой итерации (с номером r) имеется оценка (верхняя граница) оптимального значения целевой функции, обозначим эту оценку . На первой итерации можно взять либо заведомо больше оптимального значения, либо равным значению целевой функции, соответствующему фиксированному допустимому решению. При отсутствии какой‑либо информации об особенностях рассматриваемой задачи в самом неблагоприятном случае можно принять . Помимо верхней границы имеется основной список задач линейного программирования, подлежащих решению. Эти задачи отличаются друг от друга условиями вида (18)-(19). На первой итерации (r = 1) основной список содержит всего одну задачу (14)‑(16).

На произвольной итерации r выполняются следующие шаги.

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

2. Решить выбранную задачу. Если она не имеет допустимого решения или если оптимум задачи больше или равен , то принять и вернуться к шагу 1. В противном случае перейти к шагу 3.

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

4. Выбрать любую переменную , не имеющую целого значения в полученном на шаге 2 оптимальном решении задачи. Пусть – значение этой переменной, а – наибольшее целое число, не превосходящее . Добавить две задачи линейного программирования в основной список. В систему ограничений каждой из этих задач включить все ограничения задачи, выбранной на шаге 1; кроме того, в одной из них к этим ограничениям добавить неравенство , а в другой – . Принять и вернуться к шагу 1.

Остановка алгоритма означает, что основной список исчерпан. Если к этому моменту имеется зафиксированное решение, доставляющее целевой функции значение , где r – номер последней итерации, то это решение оптимально. В противном случае допустимого решения не существует. Как показывают примеры, можно получить целочисленное решение, не дойдя до последней итерации, однако при этом неизвестно, действительно ли оно является оптимальным.

Подробности изложенного алгоритма поясним на примере задачи (20)

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

(21) (22)

– целые, . (23)

На первой итерации (r = 1) примем верхнюю границу значений целевой функции = 0, поскольку (0,0,0,8,8) ^Т – допустимое решение задачи (20)‑(23). Основной список содержит лишь одну задачу линейного программирования (20)-(22), которую назовем задачей А. Решим эту задачу (вычеркнув ее из основного списка). Оптимальное решение задачи , оптимум . Поскольку решение не является целочисленным, выберем, например, х₁ и внесем в основной список задачи Б и В, которые отличаются от задачи А одним дополнительным ограничением: задача Б имеет дополнительное ограничение , а задача В – .

Дальнейший ход итераций удобно представить блок-схемой в виде графа (дерева).

ЗадачаА, r = 1, z⁽¹⁾ = 0

ЗадачаБ, r = 3, z⁽³⁾ = 0 ЗадачаВ, r = 2, z⁽²⁾ = 0

Допустимых решений нет

Задача Г. r = 11, z⁽¹¹⁾ =-13 Задача Д. r = 4, z⁽⁴⁾ = 0

Задача Е. r = 6, z⁽⁶⁾ = 0 Задача Ж. r = 5, z⁽⁵⁾ = 0

Допустимых решений нет

Задача З. r = 8, z⁽⁸⁾ = 0 Задача И. r = 7, z⁽⁷⁾ = 0 Допустимых решений нет

Задача К. r = 10, z⁽¹⁰⁾ = 0 Задача Л. r = 9, z⁽⁵⁾ = 0 Допустимых решений нет

После одиннадцатой итерации полагаем и возвращаемся к основному списку, после чего вычисления прекращаются, так как основной список пуст. Оптимальным решением задачи (20)-(23) является х ^*=(0, 0, 1, 1, 1) ^Т, зафиксированное на итерации r = 10.

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

Ход итераций, как уже говорилось, можно представить блок-схемой в виде дерева. При этом каждая вершина дерева отображает задачу в основном списке, а каждая ветвь инцидентна одной из задач, добавляемых в основной список на шаге 4. Связь с графическим представлением объясняет использование понятия «ветвь» в названии метода, а понятие «граница» (оценка) появилось в этом названии, благодаря испытанию, выполняемому на шаге 2. Заметим, что ветвь, ведущая к задаче Г, обрывается несмотря на то, что оптимальное решение этой задачи не является целочисленным. Это объясняется тем, что к моменту достижения задачи Г при r = 11 уже получено допустимое решение, при котором целевая функция принимает значение –13. Поэтому дальнейшее ветвление при наложении более сильных ограничений уже не может улучшить полученное ранее допустимое решение. При обрыве некоторых ветвей (в рассматриваемом примере это ветви, заканчивающиеся задачами В, Г, Ж, И, К, Л) нужно вернуться обратно, просматривая соответствующие ветви с целью отыскания любой нерешенной задачи, содержащейся в блок-схеме.

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

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

Дата добавления: 2015-08-29