Понятие о методе ветвей и границ.

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

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

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

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

Начальная задача распадется на две (2) и (3). В задачу (2) добавится ограничение , а в задачу (3) добавится ограничение.

Решаем эти задачи. В результате список задач может либо расшириться, либо уменьшиться. Если в результате решения задач (2) или (3) нецелочисленный оптимальный план, при котором , то эта задача исключается. Если, то из данной задачи формируются две новые.

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

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

Пример 13.

Решить задачу в целых числах.

За принимаем значение целевой функции в точке (0;0).

Решим задачу симплекс-методом. Получим Z=13. ПолучимZ=13. Так как первая компонента х₁^*дробная, то из области допустимых решений исключим полосу. Получим две задачи:

Задача 1. х1, х2- целые

Задача 2. х1, х2- целые

Решим задачу (3) симплекс-методом. Условия задачи (3) противоречивы.

Решим задачу (2). Z=14/3. Хотяпо прежнему сохраняем, так как план Х^*₃не целочисленный. х₂^*дробная, следовательно, исключаем полосу.

Задача 4. х1, х2- целые

Задача 5. х1, х2- целые

Решим задачу (4) Z=12. Задачу исключаем из списка, но меняем

Решим задачу (5) Z=12,25.не меняем, так как план не целочисленный. Исключаем полосу. Получим

Задача 6. х1, х2- целые

Задача 7. х1, х2- целые

Решим задачу (7) симплекс-методом. Условия задачи (7) противоречивы.

Решим задачу (6). Z=10,5., следовательно, задача исключается из списка.

Список задач полностью исчерпан. Получен оптимум

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

Задания

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

1.

2.