Решение задачи линейного программирования графически

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

Определение. Любое решение системы ограничений называется допустимым решением ЗЛП.

Определение. Допустимое решение, в котором целевая функция достигает максимального или минимального значения, называется оптимальным решением.

В силу этих определений задача ЛП может быть сформулирована следующим образом.

Среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию

Заметим, что переменные в ЗЛП принимают, как правило, неотрицательные значения (), поэтому область расположена в I четверти координатной плоскости.

Рассмотрим линейную функцию и зафиксируем какое-нибудь её значение , пусть, к примеру : . Графиком этого уравнения будет прямая, проходящая через начало координат , смотри рис.2.5. При изменении этого фиксированного значения прямая будет смещаться параллельно и «зачертит» всю плоскость. Линии являются линиями уровня функции F.

Рис. 2.5

Пусть многоугольник допустимая область. При изменении прямая при некотором значении достигает многоугольника назовём эту точку «точкой входа», и затем, пройдя многоугольник, при некотором значении будем иметь с ним последнюю общую точку , назовём эту точку «точкой выхода».

Вектор является градиентом функции F и показывает направление роста функции. Функция F перпендикулярна этому вектору. Очевидно, что своего наименьшего значения целевая функция достигнет в точке «входа» и наибольшего значения в точке «выхода» .

Учитывая, что оптимальное значение на множестве допустимых, целевая функция принимает в точке «входа» или «выхода», т. е. в вершинах области решений, можно предложить следующий план решения ЗЛП:

1) построить область решений системы ограничений;

2) построить прямую для целевой функции, перпендикулярную вектору , и параллельным переносом этой прямой найти точку «входа» или «выхода» (в зависимости от требования минимизировать или максимизировать целевую функцию);

3) определить координаты этой точки, вычислить в них значение целевой функции.

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