Геометрическая интерпретация и графическое решение ЗЛП

Задача с двумя переменными.

Пусть требуется найти решение, доставляющее:

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

Начнем с геометрической интерпретации области допустимых решений.

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

Рис. 1.

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

Если построить на одном рисунке область допустимых решений, вектор и одну из линий уровня, например, Z=0, то задача сводится к определению в области допустимых решений точки в направлении вектора, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции Z. Это и есть графический способ решения ЗЛП. Если задача разрешима, могут представиться следующие случаи: задача имеет единственное решение (рис. 2, а); задача имеет бесконечное множество — альтернативный оптимум (рис. 2, б); целевая функция не ограничена; область допустимых решений — единственная точка, задача не имеет решения.