В. 28. Алгоритм графического метода решения задачи ЛП с двумя переменными

Шаг 1. По ограничениям задачи построить область допустимых значений (ОДЗ). Каждому неравенству на плоскости соответствует полуплоскость, каждому уравнению соответствует прямая, ОДЗ будет пересечением построенных полуплоскостей и пря­мых. Возможны несколько вариантов ОДЗ (замкнутая область, неограниченная область, луч, отрезок, точка, пустое множество). Если ОДЗ - пустое множество, то задача не имеет решения. Если ОДЗ не пусто, то перейти на шаг 2.

Шаг 2. Построить вектор градиента, координаты начала вектора - (x₁=0, x₂=0,), координаты конца вектора - (x₁=с₁, x₂=с₂), где с₁ и с₂ - коэффициенты целевой функции. Перейти на шаг 3.

Шаг 3. Построить линию уровня целевой функции. Линия уровня целевой функции перпендикулярна вектору градиента и должна проходить по ОДЗ задачи. Перейти на шаг 4.

Шаг 4. Определить точки-кандидаты из ОДЗ для оптимального решения. Если целевая функция на максимум, то линию уровня целевой функции перемещать параллель­но самой себе в направлении градиента до последней точки ОДЗ. Если целевая функция на минимум, то линию уровня перемещаем в направлении антиградиен­та (противоположное градиенту направление). Перейти на шаг 5.

Шаг 5. (Точное определение координат оптимального решения). Если очевидно, что точка-кандидат является оптимальным решением, то подставляем ее значение в целевую функцию и записываем решение задачи ЛП в виде: оптимальное значение целевой функции, и соответствующие значения х₁ и х₂. Если точек-кандидатов несколько, то для каждой такой точки составляется система двух уравнений с двумя неиз­вестными, линии которых в пересечении дают данные точки. Для каждой точ­ки решается система уравнений. Полученные решения подставляются в целевую функцию. В качестве оптимальной выбирается та точка, для которой значение целевой функции лучше. Завершить алгоритм.

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

Замечание - часто ОДЗ имеет достаточно простой вид и сразу известны коорди­наты угловых точек. В этом случае, если угловых точек не слишком много, можно найти ответ, перебирая все эти точки, не рисуя линию уровня.

Пример в распечатке!