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

 

Этот метод точного решения ЗЦЛП чаще всего используется на практике. Он состоит в следующем.

Сначала решается ослабленная задача. Если полученное оптимальное решение целочисленное, то ЗЦЛП решена. Если же оптимальное решение ЗЛП не является целочисленным, то производим "ветвление" следующим образом. Пусть переменная х_s приняла в оптимальном решении значение q_s, которое не является целым. Тогда рассматриваем две ЗЦЛП. Первая получается добавлением ограничения х_s <=[q_s], вторая – добавлением ограничения х_s >=[q_s] + 1, где [q_s] - целая часть числа q_s .

Каждая из этих двух задач аналогичным образом может разбиться еще на две задачи т.д.

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

Недостаток метода ветвей и границ состоит в том, что часто оптимальное решение ЗЦЛП достигается после очень большого числа ветвлений.

Вернемся к ЗЦЛП примера 1.

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