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

Для более полного представления о задаче линейного программирования сделаем её геометрическую интерпретацию. Совокупность любого числа линейных ограничений выделяет в пространстве x₁, x₁,..., x_n некоторый выпуклый многогранник, ограничивающий область допустимых значений переменных (ОДЗП). Геометрическую интерпретацию и решение задачи линейного программирования нетрудно получить лишь в простейших случаях при n = 2 или n = 3. Рассмотрим задачу: max{F(x)= c₁x₁+ c₂x₂|( a_j1x₁+ a_j2x₂)≥(≤)b_j,j=1,m; x₁≥0, x₂≥0}.

Каждое из ограничивающих неравенств определяет полуплоскость, лежащую по одну сторону прямой a a_j1x₁+ a_j2x₂)=b_j , j = 1,m. ОДЗП получится в результате пересечения m полуплоскостей. Условия неотрицательности позволяют ограничиться рассмотрением положительного квадранта.

На рис. 1 показан один из возможных вариантов ОДЗП в виде замкнутого многоугольника для случая m = 3.

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

Координаты x₁ и x₂ любой точки, принадлежащей области, удовлетворяют системе ограничений задачи линейного программирования. Чтобы найти оптимальное решение, зададим функции цели некоторое постоянное значение F₁ = c₁x₁ + c₂x₂ = const и построим прямую F₁, которая будет отсекать на оси ординат (x₁ = 0) отрезок , x₂=F₁/c₂ а на оси абсцисс (x₂=0) – отрезок x₁=F₁/c₁. Если задать другие значения функции цели F₂ , F₃ ,... и изобразить соответствующие линии, то получим семейство параллельных прямых, которые называются линиями уровня функции цели. Направление стрелки показывает направление увеличения целевой функции F₁ < F₂ < F₃ < .... Величину функции цели можно характеризовать расстоянием d от начала координат до линии уровня в соответствии с выражением d=(F₁/F₂)cosα.

В теории линейного программирования доказано, что если оптимальное решение задачи линейного программирования существует и единственно, то оно достигается в некоторой вершине многоугольника решений. Очевидно, что целевая функция достигает максимального значения тогда, когда её линия будет проходить через точку M. Координаты этой точки будут оптимальным решением задачи. Минимальное значение рассматриваемой функции будет достигаться в начале координат. Таким образом, если требуется определить такие x₁ и x₂, которые обеспечивают максимум функции цели, то геометрически это означает, что необходимо провести прямую F = const , проходящую хотя бы через одну вершину области и имеющую максимальное расстояние d от начала координат.

В случае минимизации это расстояние должно быть минимальным. В зависимости от вида ОДЗП и расположения линий уровня могут встретиться случаи, изображенные на рис. 2.

Рис. 2 - Различные варианты решения задач линейного программирования

На рис.2, а функция F достигает минимума в начале координат. При максимизации функции ее линия совпадает со стороной ВС, ограничивающей ОДЗП. Координаты любой точки отрезка ВС будут доставлять максимум функции F, что соответствует бесчисленному множеству оптимальных решений задачи линейного программирования.

На рис. 2, б ОДЗП не замкнута, целевая функция сверху не ограничена, т.е. максимального значения не имеет. Минимальное значение функция принимает в точке A.

На рис. 2, в приведен случай несовместных ограничений, в этом случае функция цели не имеет ни максимума, ни минимума, так как ОДЗП представляет собой пустое множество.