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

Графический метод решения задач линейного программирования в его непосредственной форме применяется только в случае двух переменных.

Пусть требуется найти максимальное значение функции

(1)

при ограничениях

(2)

,

где ; ; – заданные числа.

Введем на плоскости прямоугольную систему координат . Каждое неравенство задает полуплоскость с границей .

Чтобы определить, какую именно полуплоскость определяет данное неравенство, достаточно взять произвольную точку плоскости (например, начало координат) и подставить в неравенство числа . Если получим верное числовое неравенство, то полуплоскость, в которой лежит данная точка — искомая. В противном случае нужная полуплоскость лежит по другую сторону прямой .

Область допустимых решений системы ограничений (2) – это область пересечения полуплоскостей, определяемых каждым из неравенств.

Допустим, что область допустимых решений системы ограничений (2) — четырехугольник АВСD (рис. 3).

Рассмотрим линейную функцию . При фиксированном значении получаем уравнение прямой линии на плоскости .

На рисунке показана прямая, соответствующую уравнению . Эта прямая пройдет через начало координат. Другим значениям будут соответствовать прямые, параллельные друг другу.

Прямая, уравнение которой получено из целевой функции задачи при равенстве ее постоянной величине, т.е. прямая , называется линией уровня целевой функции.

Известно, что коэффициенты при переменных в уравнении прямой на плоскости являются координатами вектора нормали к этой прямой: . Следовательно, нормальный вектор всех линий уровня .

Если перемещать линию уровня параллельно ее начальному положению в направлении вектора (см. рис. 3), то для данного случая последней точкой, в которой линия уровня коснется области допустимых решений, окажется точка В.

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

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

Таким образом, алгоритм решения задачи линейного программирования с двумя переменными графическим методом такой:

1. Строится область допустимых решений.

2. Строится вектор с точкой приложения в начале координат.

3. Перпендикулярно вектору проводится одна из линий уровня, соответствующая уравнению .

4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находится максимум или минимум функции.

В зависимости от вида области допустимых решений и целевой функции возможны следующие случаи:

На рис.4,а линия уровня дважды становиться опорной по отношению к многоугольнику решений. Минимальное значение целевая функция достигает в точке В, максимальное — в точке D. Задача имеет единственное решение.

На рис. 4, б максимальное значение целевая функция принимает на опорной прямой, совпадающей со стороной АЕ многоугольника, задача имеет бесконечное множество решений.

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

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

или

, . , .