2015-05-10
381
Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные.
Найти минимальное значение функции
при ограничениях вида
и
Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми: 
.
Линейная функция (1) при фиксированных значениях 
является уравнением прямой линии: 
.
Пример графического решения задачи линейного программирования с 6 условиями.
Построим многоугольник решений системы ограничений (2) и график линейной функции (1) пр 
. Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию:
Найти точку многоугольника решений, в которой прямая опорная и функция при этом достигает минимума.
Значения 
уменьшаются в направлении вектора 
, поэтому прямую передвигаем параллельно самой себе в направлении вектора 
.
Если многоугольник решений ограничен (см. рисунок), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках 
и 
), причём минимальное значение принимает в точке . Координаты точки 
находим, решая систему уравнений прямых 
и 
.
Если же многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.
Случай 1. Прямая , передвигаясь в направлении вектора или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.
Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.
