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

Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.

Описание метода

Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные.

Найти минимальное значение функции

$(1)\quad Z = c_1x_1 + c_2x_2\,$

при ограничениях вида

$(2)\quad \left\{ \begin{matrix} a_{11}x_1 + a_{22}x_2 \leqslant b_1 \\ a_{21}x_1 + a_{22}x_2 \leqslant b_2 \\ \ldots \\ a_{n1}x_1 + a_{n2}x_2 \leqslant b_n \end{matrix} \right .$

и

$(3)\quad \left\{ \begin{matrix} x_1 \geqslant 0\\ x_2 \geqslant 0\\ \end{matrix} \right .$

Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми: $a_{i1}x_1 + a_{i2}x_2 = b_i, (i = 1, 2,\ldots, n); x_1=0; x_2=0$.

Линейная функция (1) при фиксированных значениях $Z\,$ является уравнением прямой линии: $c_1x_1 + c_2x_2 = const\,$.

Пример графического решения задачи линейного программирования с 6 условиями.

Построим многоугольник решений системы ограничений (2) и график линейной функции (1) при $Z = 0\,$. Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию:

Найти точку многоугольника решений, в которой прямая $c_1x_1 + c_2x_2 = const\,$ опорная и функция $Z\,$ при этом достигает минимума.

Значения $Z = c_1x_1 + c_2x_2\,$ уменьшаются в направлении вектора $N =(-c_1, -c_2)\,$, поэтому прямую $Z = 0\,$ передвигаем параллельно самой себе в направлении вектора $N\,$.

Если многоугольник решений ограничен (см. рисунок), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках $B\,$ и $E\,$), причём минимальное значение принимает в точке $E\,$. Координаты точки $E (x_1, x_2)\,$ находим, решая систему уравнений прямых $DE\,$ и $EF\,$.

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

Случай 1. Прямая $c_1x_1 + c_2x_2 = const\,$, передвигаясь в направлении вектора $N\,$ или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.

Литература

• Кремер Н.Ш. Исследование операций в экономике. — Москва: Юнити, 2000. — С. 55-57. — 408 с.
• Ашманов С.А. Линейное программирование. — Москва: «Наука», 1981. — 304 с.

Для улучшения этой статьи по математике желательно?: Викифицировать статью. Переработать оформление в соответствии с правилами написания статей. Проставив сноски, внести более точные указания на источники. Проставить интервики в рамках проекта Интервики.