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

Рассмотрим задачу ЛП в стандартной форме записи:

(1).

при ограничениях.

(2).

Рассмотрим эту задачу на плоскости, т. е. при п = 2. Пусть система неравенств (2) совместна (имеет хотя бы одно решение):

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область.

Если в системе ограничений (2) n = 3, то неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i1х₁ + а_i2х₂ + а_i3х₁ = b_i, а условия не отрицательности — полупространства с граничными плоскостями соответственно x_i = 0 (i = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений.

Пусть в системе (2) п>3, тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью а_i1х₁ + а_i2х₂ + … + а_inх_n = b_i i = 1,2,…, m, а условия неотрицательности — полупространства с граничными гиперплоскостями x_j = 0, j = 1,2,…, n.

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

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

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник .

Выберем произвольное значение целевой функции. Получим. Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение. Считая в равенстве (1) параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). Найдём частные производные целевой функции по и.

(4).

(5).

Частная производная (4) ((5)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и — скорости возрастания соответственно вдоль осей и. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор — указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор перпендикулярен к прямым семейства.

Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.

С учетом системы ограничений строим область допустимых решений.

Строим вектор наискорейшего возрастания целевой функции — вектор градиентного направления.

Проводим произвольную линию уровня.

При решении задачи на максимум перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке). В случае решения задачи на минимум линию уровня перемещают в антиградиентном направлении Определяем оптимальный план и экстремальное значение целевой функции .