Пример графического решения задачи ЛП

Решить графически задачу ЛП, заданную в канонической форме:

      (6)

               (7)

                                            (8)

Число уравнений задачи m=3, число неизвестных n=5. Тогда n-m=2 и задача может быть сведена к задаче на плоскости относительно свободных переменных. Возьмем в качестве базисных переменные  и выразим их через свободные (небазисные переменные):

                                                                                           (9)

По условию (8) переменные могут принимать только неотрицательные значения, т. е. допустимой областью задачи ЛП (6) - (8) будет область, определяемая условиями (8), (9), или

                                (10)

Чтобы получить задачу ЛП относительно переменных , подставим значения базисных переменных (9) в целевую функцию (6). В результате получим

                            (11)

Задача (10), (11) эквивалентна задаче (6) - (8), поэтому, решая графически задачу (10), (11), получим решение задачи (6) - (8).

Этап 1. Построение допустимой области.

Каждое из неравенств (10) определяет некоторую полуплоскость :

Так, неравенство  определяет правую полуплоскость. Неравенство  определяет полуплоскость, лежащую по ту сторону от прямой , где . Подставляя значения  в это неравенство, получим 0>-2, значит, координаты (0,0) удовлетворяют первому неравенству (10) и область решений этого неравенства включает начало координат. Аналогично определяют полуплоскости остальных неравенств (10).

На рисунке прямые, соответствующие условию , отмечены цифрой в скобках.

Получили допустимую область M – выпуклый пятиугольник OABCD.

Этап 2. В допустимой области M находим оптимальное решение.

Строим прямую  и определяем направление возрастания функции , это направление вектора . Перемещая прямую L параллельно самой себе в направлении вектора  до тех пор, пока она будет сохранять общие точки с областью допустимых решений, найдем, что в крайнем возможном положении прямая L пройдет через точку . Этому положению прямой L соответствует значение . Для нахождения координат точки  необходимо совместно решить систему уравнений граничных прямых, на которых лежит точка :

В результате получаем искомое оптимальное решение . Подставляя значения  и  в целевую функцию и в равенства (9), получим оптимальное значение целевой функции  и оптимальное решение