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

Рассмотрим такой пример:

при условиях

Рис. 4.1. 

Каждое из этих неравенств определяет полуплоскости, пересечение которых дает многоугольник, заштрихованый на рис. 4.1. Этот многоугольник (выпуклый многогранник) и представляет собой допустимое множество решений R(x₁, x₂) задачи ЛП. Теперь рассмотрим целевую функцию

f(x₁,x₂)=4x₁+3x₂,

пусть ее значения

f(x₁,x₂)=12000=Z₁.

График уравнения 4х₁+3х₂=12000 - прямая с отрезками на осях x₁=3000; x₂=4000.

При f(x₁,x₂)=24000 получим прямую z₂.

Прямая z₂ параллельная прямой z₁, но расположена выше от нее. Передвигая прямую z вверх параллельно самой себе, приходим к такому ее положению, когда прямая и множество R будут иметь только одну общую точку А.

Очевидно, что точка А (x₁=2000; x₂=6000) - оптимальное решение, так как она лежит на прямой с максимально возможным значением . Заметим, что эта точка оказалась крайней точкой множества R.

При векторной форме ограничения задачи ЛП записываются так:

(3.1)

где

Рассмотрим допустимое множество A₁, A₂,.,A_n в пространстве данных векторов. Поскольку в формуле (3.1) , то все положительные комбинации векторов A₁,A₂,.,A_n образуют конус. Поэтому вопрос о существовании допустимых решений равнозначен вопросу о принадлежности вектора b этому конусу. Поскольку A₁,A₂,.,A_n m -мерные векторы (n > m), то среди них всегда обнаружится m линейно-независимых векторов, образующих базис m -мерного пространства и содержащих конус, образованный векторами A₁,A₂,.,A_n...

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

Расширенная форма задачи ЛП. Для решения задач ЛП необходимо переходить от ограничений - неравенств к ограничениям в форме уравнений. Для этого в каждое неравенство вводят по одной свободной переменной , чтобы превратить его в равенство. В таком виде задачу ЛП называют расширенной и записывают так:

(3.2)

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

a₁₁x₁+a₁₂x₂+.+a_1nx_n+1x_n+1+0x_n+2+...+0x_n+m=b₁;

a₂₁x₁+a₂₂x₂+.+a_2nx_n+0x_n+1+1x_n+2+...+0x_n+m=b₂;

........................................

a_m1x₁+a_m2x₂+.+a_mnx_n+0x_n+1+0x_n+2+...+1x_n+m=b_m ...

В матричной форме эта задача имеет следующий вид:

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

где

(3.3)

Наконец, векторная форма записи расширенной задачи ЛП:

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

(3.4)

Рис. 4.2. 

Рис. 4.3. 

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

Установим отношение между элементами R и R₁:

На рис. 4.2 и 4.3 изображены допустимые множества решений обеих задач. Очевидно, что треугольник ОСА (рис. 4.2) - допустимое множество R - есть проекция допустимого множества R₁ (рис.4.3) на подпространство .

В общем случае допустимое множество решений исходной задачи R есть проекция допустимого множества решений расширенной задачи R₁ на подпространство исходных переменных .