Алгоритм решения задачи графическим методом

Решение задач ЛП графическим методом осуществляется по следующему алгоритму.

1. Находим область допустимых решений (ОДР) по каждому ограничению и общую ОДР.

2. Находим координаты угловых точек и значение F(x) в каждой точке. Max F(x) определяет точку оптимального решения.

3. Строим вектор-градиент grad F(x)= F(x) по координатам (0,0; c₁,c₂), который показывает направление наискорейшего возрастания целевой функции.

4. Проводим линию уровня (линию прибыли), которая перпендикулярна вектору-градиенту.

5. Линию уровня перемещаем по направлению вектора F для задач на максимум и в направлении, противоположном F, для задач на минимум.

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

Если окажется, что линия уровня параллельна одной из сторон ОДР, то задача ЛП будет иметь бесчисленное множество решений.

Если ОДР представляет неограниченную область, то целевая функция может быть неограниченна.

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

1. Находим координаты точки экстремума и значение целевой функции в ней.