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

Программирования

Рассмотрим задачу линейного программирования: найти значения переменных х_j (j=1, n), обеспечивающих минимальное значение линейной функции вида (3.1) при ограничениях, заданных неравенствами вида (3.7) и (3.8).

Согласно теореме 3.1 и определению 3.1 совокупность чисел х₁, х₂,..., х_n, удовлетворяющих ограничениям (3.7) и (3.8), является допустимым решением задачи линейного программирования. Если система неравенств (3.7) при условии (3.8) имеет хотя бы одно решение, она называется совместной, а в противном случае несовместной.

Рассмотрим случай, когда r = n - m = 2 (то есть, число свободных переменных равно 2, а число базисных переменных - m). Предположим, что свободными переменными являются х ₁ и х ₂, а базисными - х ₃,..., х _n, которые выразим через свободные х ₁ и х ₂.

С учетом условия неотрицательности переменных получим систему ограничений вида:

a₁₁·x₁ + a₁₂·x₂ ≤ b_1,

a₂₁·x₁ + a₂₂·x₂ ≤ b₂ (3.11)

......

a_m1·x₁+ a_m2·x₂ ≤ b_m,

x₁ ≥ 0, x₂ ≥ 0.

Каждое неравенство этой системы на плоскости х₁Ох₂ (рис. 3.1) геометрически определяет полуплоскость с граничной прямой a_i1·x₁ + a_i2·x₂ = b_i, (i = 1,m), (условия неотрицательности переменных определяют полуплоскости, соответственно, с граничными прямыми x₁= 0, x₂= 0). Если система уравнений совместна, полуплоскости, пересекаясь, образуют общую часть называемую областью допустимых решений (ОДР), которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (3.11). Совокупность этих точек (решений) называется многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

Если в системе ограничений (3.7) - (3.8) r = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства с граничной плоскостью a_i1·x₁ + a_i2·x₂ + a_i3·x₃ = b_i , (i = 1, m), а условия неотрицательности - полупространства с граничными плоскостями x_i = 0, (i = 1, 2, 3).

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

Если в системе ограничений (3.7) - (3.8) r > 3; то каждое неравенство определяет полупространство n - мерного пространства с граничной гиперплоскостью a_i1·x₁ + a_i2·x₂ +... + a_in·x_n= b_i, (i = 1, m). Если система ограничений совместна, то по аналогии с трехмерным пространством она образует общую часть n-мерного пространства, называемую многогранником решений, так как координаты каждой его точки являются решением системы.

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

Существуют теоремы.

Теорема 3.2. Множество всех планов задачи линейного программирования выпукло. То есть, во всех случаях отрезок, соединяющий две точки этого множества, целиком относится этому множеству.