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

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

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

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

.

а также нижняя граница линейной функции, т. е. при любом плане X .

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

.

где — целая часть числа. В результате из задачи 1 формируют две задачи: 2 и 3, отличающиеся друг от друга тем, что в задаче 2 кроме ограничений задачи 1 добавлено ограничение:

.

А в задаче 3 кроме тех же ограничений добавлено ограничение:

.

Получим список из двух задач: 2 и 3.

Решаем одну из них (в любом порядке). В зависимости от полученного решения список задач расширяется, либо уменьшается.

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

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

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