Графический метод решения задачи ЛП. Теоретические сведения

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

Каждое из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости некоторую полуплоскость (рис. 1), а система неравенств в целом — пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т. е. обладающую следующим свойством: если две точки, А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.

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

ЦФ при фиксированном значении определяет на плоскости прямую линию. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня .

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

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений — единственная точка; задача не имеет решений.

Рисунок 1 Геометрическая интерпретация ограничений и ЦФ задачи.