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

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

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

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

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

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

$(1)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 \\ a_{n1}{x}_1+a_{n2}{x}_2⩽b_n\end{array}$

и

$(3)\{\begin{array}{c}{x}_1⩾0\\ x_2⩾0\end{array}$

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга