Графическое решение. Пусть ЗЛП имеет две неизвестные

Рассмотрим сначала графический метод решения ЗЛП на примерах, а затем

сформулируем общие его положения.

Пример 1. Решить графически ЗЛП

Решение. Прежде всего построим область, задаваемую системой неравенств. На плоскости проведем прямую Затем в неравенство поставим, например, точку (0, 0). Очевидно, что , поэтому неравенству будет удовлетворять та полуплоскость, в которую эта точка входит. Аналогично поступая с оставшимися неравенствами, получим пятиугольник (рис. 1).

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

В результате получим

Пример 2. Решить графически ЗЛП

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

0

Рис. 3

Пример 3. Решить графически ЗЛП

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

з

с

0

Рис. 4

Пример 4. Решить графически ЗЛП

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

0

Рис. 5

1. Графически могут решаться:

а) задачи, заданные в стандартной форме, содержащие не более двух пере-

менных;

б) задачи, заданные в канонической форме с числом свободных переменных ;

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

2. Основной формой для графического решения является 1-й тип задач. Поэтому, если встречаются 2-й или 3-й тип задач, то предварительно их модель должна быть приведена к 1-му типу.

3. Решение задачи первого типа осуществляется в два этапа:

- построение области допустимых решений;

- нахождение в этой области оптимального решения.

4. При построении области допустимых решений могут встретиться:

а) пустая область;

б) многоугольник;

в) неограниченная многоугольная область.

В пустой области задача не имеет решения из-за несовместности системы ограничений в области допустимых решений. Для многоугольника задача всегда имеет решение. В случае в) в зависимости от направления вектора (от коэффициентов функции z) задача может иметь или не иметь решения. Последнее связано с неограниченностью функции z в области допустимых решений.

5. Задача может иметь единственное оптимальное решение, совпадающее с одной из вершин области, и бесчисленное множество решений (ребро многоугольника допустимой области).