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

Рассмотрим случай основной задачи линейного программирования, когда число переменных x_j превышает количество уравнений ограничений на 2, то есть n-m = 2. В этом случае задача линейного программирования приобретает наглядную геометрическую интерпретацию и для ее решения можно воспользоваться графическим методом.

Выделим из всей совокупности x_j две переменных, которые назовем свободными переменными. Используя уравнения-ограничения (3.6), выразим остальные переменные, называемые базисными, через свободные.

Пусть в качестве свободных переменных выбраны переменные x ₁ и x ₂. Тогда базисные переменные будут связаны со свободными следующими соотношениями

x 3 = b 3 + a 31 x 1 + a 32 x 2 x 4 = b 4 + a 41 x 1 + a 42 x 2 ....................... xn = bn + an 1 x 1 + an 2 x 2

(3.8)

Построим координатные оси O x ₁ и O x ₂. Каждая точка координатной оси соответствует определенному значению одной из свободных переменных. Отметим штриховкой те полуоси, на которых переменные x ₁ и x ₂ принимают неотрицательные значения. Так переменная x ₁ принимает неотрицательные значения вправо от оси O x ₂, а переменная x ₂ - вверх от оси O x ₁. Очевидно, в первом квадрате переменные x ₁ и x ₂ будут неотрицательными.

По условию задачи все остальные переменные также должны быть неотрицательными, то есть x ₃³0, x ₄³0,..., x_n ³0 или

b 3 + a 31 x 1 + a 32 x 2 ³ 0 ...................... bn + an 1 x 1 + an 2 x 2 ³ 0

(3.9)

 

Рис.3.1

Если положить x ₃= 0, то есть взять предельно допустимое значение x ₃, то уравнение

b ₃ + a ₃₁ x ₁ + a ₃₂ x ₂ = 0

в координатах x 1O x 2 представляет собой уравнение прямой. Каждая точка прямой соответствует x ₃=0. Область, лежащая по одну сторону этой прямой, будет соответствовать положительным значениям x 3, а по другую сторону - отрицательным. Отметим штриховкой ту область, где переменная x ₃ принимает положительное значение.

Аналогичным образом построим прямые x ₄= 0,..., x_n = 0 и опре­делим области, где переменные x ₄>0, x ₅>0,..., x_n >0. Тогда область (многоугольник), каждая точка которых соответствует неотрицательным значениям переменных x ₁, x ₂,..., x_n и будет областью допустимых значений.

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

L (x) = с1x1 + c2x2 + c3(b3 + a31x1 + a32x2) +... + cn(bn + an1x1 + a2x2) = g0 + g1x1 + g2x2

(3.10)

где

g₀ = c₃b₃ +... + c_nb_n

g₁ = c₁ + c₃a₃₁ +... + c_na_n1

g₂ = c₂ + c₃a₃₂ +... + c_na_n2

 

Положим значение L (x) = G ₁.

Тогда уравнение

G 1 = g0 + g1 x 1 + g2 x 2 или g0 - G 1 + g1 x 1 + g2 x 2 = 0

(3.11)

представляет собой уравнение прямой в координатах x ₁O x ₂. Она пересекает координатные оси в точках

Определив эти точки, построим прямую (3.11).

Изменим значение целевой функции до G ₂. Очевидно, уравнение

g0 - G2 + g1x1 + g2x2 = 0

(3.12)

также является уравнением прямой. Изменение целевой функции от G ₁ до G ₂ соответствует перемещению прямой параллельно самой себе.

При решении задачи ЛП графическим способом для построения исходной прямой удобно положить L (x) = g₀.

Тогда из (3.10) следует, что

.

(3.13)

Назовем прямую L ₀(x) основной прямой. Так как она проходит через начало координат, то для ее построения необходимо найти еще одну точку. Очевидно, уравнению (3.13) удовлетворяет также и точка (g₂, -g₁). Перемещение основной прямой параллельно самой себе в направлении определяемом вектором, направленным из начала координат в точку (-g₁, -g₂) будет соответствовать уменьшению значения целевой функции L (x). Точка x*, принадлежащая области допустимых решений и наиболее удаленная от начала координат в направлении перемещения прямой целевой функции и будет оптимальным решением задачи линейного программирования.