Получение целочисленного решения методом ветвей и границ

Система имела вид:

 

Для метода ветвей требуется иметь только 2 переменные. Выразив , получаем:

Изобразим задачу графически:

Рисунок 1. Метод ветвей и границ. Выручка

Двигая перпендикуляр к градиенту по направлению наибольшей скорости возрастания функции упрёмся в точку С(6,4;11), соответствующую оптимальному нецелочисленному решению и максимальному значению функции = 314,6 тысяч рублей.

Ветвление начинается с множества ABCD. Следуя методу, получаем следующее решение:

Таблица 4. Метод ветвей и границ. Выручка

С=(6,4;11) f(C)=314,6

 

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

3. Графическое решение задачи с функцией «прибыль»

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

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

Рисунок 2. Графическое решение. Прибыль

При решении мы снова упираемся в точку В (6,4;11). В ней мы получаем максимальное значение прибыли, равное 84 тысяч рублей.