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

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

Описание методаПравить

 

Пример графического решения задачи линейного программирования с 6 условиями. Cтроим на плоскости область допустимых решений. У нас 6 неравенств. Неравенства превращаем в равенства, получаем прямые (оси координат задаются неполными уравнениями прямой Ax = 0 определяет ось Oy и By = 0 определяет ось Ox). Проводим прямые. Каждя прямая делить плоскость на две полуплоскости. Каждый раз выбираем одну. Берем точку, если неравенство истинно значит выбираем эту полуплоскость. Если ложно, выбираем противоположную.

 

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

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

$(1)Z=c_1{x}_1+c_2{x}_2$$(1)\quad Z=c_{1}x_{1}+c_{2}x_{2}$ 

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

$(2)\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2⩽<!--\; ⩽\; -->b_1\\ a_{21}{x}_1+a_{22}{x}_2⩽<!--\; ⩽\; -->b_2\\ \dots <!--\; \dots \; -->\\ a_{n1}{x}_1+a_{n2}{x}_2⩽<!--\; ⩽\; -->b_n\end{array}$$(2)\quad \left\{{\begin{matrix}a_{11}x_{1}+a_{12}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)\{\begin{array}{c}{x}_1⩾<!--\; ⩾\; -->0\\ x_2⩾<!--\; ⩾\; -->0\end{array}$$(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,\dots <!--\; \dots \; -->,n);x_1=0;x_2=0$$a_{i1}x_{1}+a_{i2}x_{2}=b_{i},(i=1,2,\ldots ,n);x_{1}=0;x_{2}=0$ .

Линейная функция (1) при фиксированных значениях $Z$$Z$  является уравнением прямой линии: $c_1{x}_1+c_2{x}_2=const$$c_{1}x_{1}+c_{2}x_{2}=const$ .

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

Найти точку многоугольника решений, в которой прямая $c_1{x}_1+c_2{x}_2=const$$c_{1}x_{1}+c_{2}x_{2}=const$  опорная и функция $Z$$Z$  при этом достигает минимума.

Значения $Z=c_1{x}_1+c_2{x}_2$$Z=c_{1}x_{1}+c_{2}x_{2}$  уменьшаются в направлении вектора $N=(-<!--\; -\; -->c_1,-<!--\; -\; -->c_2)$$N=(-c_{1},-c_{2})$ , поэтому прямую $Z=0$$Z=0$  передвигаем параллельно самой себе в направлении вектора $N$$N$ .

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

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

Случай 1. Прямая $c_1{x}_1+c_2{x}_2=const$$c_{1}x_{1}+c_{2}x_{2}=const$ , передвигаясь в направлении вектора $N$$N$  или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

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

ЛитератураПравить

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