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

Рассмотрим задачу линейного программирования с двумя переменными

.

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

Рис. 4.1.

Рассмотрим линию уровня линейной функции Q(x), то есть линию вдоль которой эта функция принимает одно и то же фиксированное значение a. График этой линии задается уравнением

Для различных значений величины a линии уровня линейной функции параллельны. Одно из свойств линий уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону значение функции только возрастает, а при смещении в другую сторону – только убывает. Направление, в котором следует осуществлять сдвиг, чтобы достичь меньших значений целевой функции, можно найти построением другой линии уровня. Путем параллельного переноса прямой Q(x)=a в направлении меньших значений целевой функции достигают того, что эта прямая будет пересекать допустимую область решений (многоугольник) по части ее границы – множеству точек Р. (В общем случае параллельная прямая может пересекать допустимую область в одной точке, по отрезку, лучу или прямой.) Все другие допустимые точки лежат на линиях уровня, принадлежащих большим значениям целевой функции. Все точки, лежащие на линиях уровня с меньшими значениями, являются не допустимыми. Таким образом, множество точек Р является множеством оптимальных решений.

Пример. Решить геометрическим методом следующую задачу линейного программирования: