WikiSort.ru - Не сортированное

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

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

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

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

${\displaystyle (1)\quad Z=c_{1}x_{1}+c_{2}x_{2}}$

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

${\displaystyle (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.}$

и

${\displaystyle (3)\quad \left\{{\begin{matrix}x_{1}\geqslant 0\\x_{2}\geqslant 0\\\end{matrix}}\right.}$

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

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

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

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

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

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

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

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

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

Литература

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

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