Графический метод решения задачи линейного программирования
основан на
геометрической
интерпретации
задачи
линейного программирования
и применяется в основном при решении задач двумерного
пространства
и только некоторых
задач
трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.
Описание метода
Пусть
задача
линейного программирования задана в двумерном пространстве, то есть ограничения содержат две
переменные
.
Найти минимальное значение функции
при ограничениях вида
и
Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет
полуплоскость
с
граничными
прямыми:
.
Построим многоугольник решений
системы
ограничений (2) и график
линейной функции
(1) при
. Тогда поставленной задаче линейного программирования можно дать следующую
интерпретацию
:
Значения
уменьшаются в направлении
вектора
, поэтому прямую
передвигаем параллельно самой себе в направлении вектора
.
Если
многоугольник
решений ограничен (см. рисунок), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках
и
), причём минимальное значение принимает в точке
. Координаты точки
находим, решая
систему уравнений
прямых
и
.
Если же многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.
Случай 1.
Прямая
, передвигаясь в направлении вектора
или противоположно ему, постоянно пересекает
многоугольник
решений и ни в какой
точке
не является опорной к нему. В этом случае
линейная функция
не ограничена на многоугольнике решений как сверху, так и снизу.
Случай 2.
Прямая
, передвигаясь, всё же становится опорной относительно
многоугольника
решений. Тогда в зависимости от вида области
линейная функция
может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.
Литература
Кремер Н.Ш.
Исследование операций в экономике. — Москва: Юнити, 2000. — С. 55-57. — 408 с.