Метод ветвей и границ для линейных задач целочисленного программирования

Рассмотрим целочисленную задачу линейного программирования (ЦЗЛП):

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

Конкретизируем основные этапы метода ветвей и границ применительно к данной задаче.

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

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

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

 

Схема работы метода ветвей и границ для ЦЗЛП

Шаг 1. Определение начального рекорда. (При отсутствии дополнительной информации R= ). Задать k =0.

Шаг 2. Решение оценочной задачи на множестве . Если полученная точка  целочисленная, то решение найдено. Останов.

Шаг 3. Выбор индекса , такого что координата  - не целая.

Шаг 4. Ветвление .

Шаг 5. Решение оценочных задач линейного программирования и вычисление оценок  и . Если какая-то из полученных оптимальных точек целочисленная, то переход к шагу 7.

Шаг 6. Выбор перспективного множества  в соответствии со стратегией. Положить  Переход к шагу 2.

Шаг 7. Возможная смена рекорда и сокращение перебора за счет отбрасывания неперспективных множеств.

Шаг 8. Проверка критерия оптимальности. Если он выполнен, останов. Иначе переход к шагу 6.

Пример.

 

        

 

Полагаем R= .

Решаем исходную задачу без требования целочисленности. Графическая иллюстрация решения приведена на рисунке. Оптимальной точкой является , .

Так как точка не целочисленная, осуществляем ветвление (например, по первой координате): , .

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

Так как целочисленного решения опять не получено, осуществляем ветвления множества : , .

Решаем оценочные задачи на множествах  и . Получаем , , , .

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

Решаем оценочные задачи на множествах  и . Получаем , ,  Ø.

Получено целочисленное решение. Происходит смена рекорда R=-5. Множества ,  и  выбрасываем из рассмотрения как неперспективные (их оценки превышают или равны рекордному значению).

Так как перспективных множеств для ветвления не осталось, то останов, получено оптимальное решение: , .

Дерево вариантов в данной задаче имеет вид:

 

                                                              

 

                                                                        

                              

                        

                                                             

                              

 

 

                   

 

УПРАЖНЕНИЯ

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

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

3. Решить ЦЗЛП:

                  

Ответ: =(2,4)              Ответ: =(7,4)                 Ответ: =(2,5)

  

      

 

ЗАДАЧА

О НАЗНАЧЕНИЯХ.

ВЕНГЕРСКИЙ

МЕТОД РЕШЕНИЯ