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

Формальная схема метода ветвей и границ.

0 шаг. Вычисляют оценку . Если удается найти допустимую точку , для которой , то – решение задачи (5.8). Если решение не найдено, то и переход к 1 шагу.

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

.

Далее разбивается на непересекающиеся подмножества.

Еще не подвергавшиеся разбиению подмножества переобозначают и переходят к k+1 шагу.

(5.9)

На каждом шаге решаются непрерывные задачи линейного программирования:

На 0 шаге: задача

На k-шаге: задачи и .

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

Для задачи определятся (верхняя граница), где – решение задачи . Если решение нецелочисленно, то граница недопустима. Если задача решения не имеет, то .

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

Интервал, между двумя целыми числами отличается друг от друга на единицу и поэтому решения (5.9) быть не может. Необходимое условие целочисленности :

1)

2)

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

Следовательно, мы должны добавить эти ограничения в . В силу этого задачаразбивается на 2 подмножества (происходит ветвление) и формируются задачи:

В процессе решения строится дерево задач для обеспечения наглядности.

Пусть К-множество вершин, не подвергавшихся ветвлению.

, где

I – множество вершин, из которых возможно ветвление (висячие вершины)

J – множество вершин, из которых невозможно ветвление (концевые вершины)

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

Вводится - после решения задачи .

Начальное значение

Если на некотором шаге задача решения не имеет, то не имеет смысла вводить дополнительные ограничения, следовательно дальше ветвить не стоит.

Пусть мы выполнили k-шагов. При этом решены задачи 0,1,…,2k. Значение нижней границы . Рассмотрев , находим и, если выполняется условие , то дальше ветвление из этой вершины прекращается (верхняя граница уже ниже того, что получили).

Если условие , то из вершины множества I превращаются в множества J. Поэтому решение завершается, когда

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