Графический метод: алгоритм метода

Алгоритм графического метода решения задач линейного программирования с двумя переменными:

Алгоритм графического метода решения задач линейного программирования с двумя переменными:

1) Построить область допустимых решений.

2) Если область допустимых решений является пустым множеством, то задача не имеет решения вследствие несовместности системы ограничений.

3) Если область допустимых решений является непустым множеством, построить вектор-градиент целевой функции.

4) Произвольную линию уровня, имеющую общие точки с ОДР, перемещаем параллельно самой себе до опорной прямой в направлении вектора-градиента (при решении задачи на максимум) или в противоположном направлении (при решении задачи на минимум).

5) Если при перемещении линии уровня по ОДР в направлении, соответствующем приближению к экстремуму целевой функции, линия уровня уходит в бесконечность, то задача не имеет решения вследствие неограниченности целевой функции.

6) Если ЗЛП имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих ОДР и имеющих общие точки с соответствующей опорной прямой. Если целевая функция задачи достигает экстремума в двух вершинах ОДР, то она достигает экстремума также в любой точке, лежащей на отрезке, соединяющем эти две вершины. Задача имеет бесконечное множество оптимальных решений.

7) Вычислить значение целевой функции на оптимальном решении.