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

 

Рассмотрим процедуру на примере.

 

Пример 5.1.

Дано:

, целые.

 

Получено решение исходной задачи , оно нецелое. Значение функции на этом решении . Обозначим его .

 

В нашем случае нецелой является координата , выделим ее целую часть , и разобьем исходную задачу на две:

 

 

 

 

 

 

 

 

 

 

 

 

Т.о. ЗЛП-2 будет содержать все ограничения исходной задачи и новое ограничение , а ЗЛП-3 также все ограничения исходной задачи и . Такое разбиение привело к тому, что старое нецелочисленное решение стало недопустимым в обеих задачах, однако при этом из начального МДР не было потеряно ни одной целой точки.

 

Решаем теперь ЗЛП-2.

 

 

Решение ЗЛП-2: , оно целое. Значение функции .

 

Решаем теперь ЗЛП-3.

 

 

Решение ЗЛП-3: , нецелое. Значение функции на этом решении .

 

Т.к. решение в ЗЛП-2 целое, но оптимальное значение функции в ЗЛП-2 меньше, чем в ЗЛП-3, то его можно считать нижней границей возможного целого решения в задаче. Обозначим его .

 

В ЗЛП-3 на нецелом решении значение функции больше, чем , значит, продолжаем ветвить задачу. Нецелой координатой в ЗЛП-3 является, выделим ее целую часть , и разобьем задачу на две:

 

 

 

 

 

 

 

 

 

 

 

 

Т.о. ЗЛП-4 будет содержать все ограничения задачи ЗЛП-3 и новое ограничение , а ЗЛП-5 также все ограничения задачи ЗЛП-3 и .

 

Решаем теперь ЗЛП-4.

 

 

Решение ЗЛП-4: , оно целое. Значение функции на этом решении .

 

Решаем теперь ЗЛП-5.

 

 

Решение ЗЛП-5 – не имеет решения, т.к. МДР пусто.

 

Т.к. оптимальное значение функции в ЗЛП-4 меньше, чем, вычисления закончены. Решением задачи является  (решение ЗЛП-2).

 

Алгоритм решения задачи методом ветвей и границ

 

1. Решить ЗЛП-1 без требований на целочисленность переменных. Если ее решение целое, то процесс закончен. Если нет, то обозначить значение функции на этом решении .   2. Начать ветвление ЗЛП-1, для этого выбрать нецелую переменную для построения дополнительных ограничений. Если нецелых переменных более одной, выбор осуществить по одному из следующих принципов: это переменная с наибольшим или наименьшим номером; это переменная с наименьшей или наибольшей дробной частью; это переменная, которой соответствует наибольший коэффициент в целевой функции; это переменная с наибольшим приоритетом.

 

3. Выделить у выбранной координаты  целую часть и разветвить ЗЛП-1 на две: ЗЛП-2 = ЗЛП-1 + ; ЗЛП-3 = ЗЛП-1 + .   Решить ЗЛП-2 и ЗЛП-3. Если их решение нецелое, то продолжить ветвление до тех пор, пока не будет найдено 1-е целое решение. Значение функции на нем обозначить .   4. Вопрос о дальнейшем ветвлении оставшихся нецелых задач решается путем сравнения значения функции на нецелых  решениях с . Если , то ветвление не производится, если , то задача ветвится дальше. Т.о. ветвление какой-либо задачи заканчивается, если выполняется одно из условий: решение целочисленно; значение целевой функции; МДР пусто.   5. Если ветвление всех задач закончено, то выбирается решение (решения), которому соответствует наибольшее значение целевой функции. Если не найдено ни одно целое решение, то исходная задача не имеет решения.

 

Сходимость метода ветвей и границ. Алгоритм является конечным, если МДР является ограниченным.