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

Теорема 1. Множество всех допустимых решений системы ограничений ЗЛП выпукло.

Доказательство.

Дана ЗЛП в матричном виде: Z=CX®max(min) при ограничениях A×X = B, X ³ 0 .

Пусть Х1=(х11, х21,…, хn1) и Х2=(х12, х22,…, хn2) – два допустимых решения ЗЛП, соответственно выполняются соотношения A×X1 = B, X1 ³ 0; A×X2 = B, X2 ³ 0.

Необходимо доказать, что выпуклая комбинация решений Х1 и Х2

Х=l1Х1+l2Х2, l1³ 0, l2³0, l1+l2=1 также допустимое решение задачи.

Действительно, АХ=А(l1Х1+l2Х2)= l1АХ1+l2АХ2=l1В+l2В=(l1+l2)В=В,

т.е. получаем, что Х удовлетворяет системе AX = B, следовательно является решением.

Но т.к. X1 ³ 0; X2 ³ 0, l1 ³ 0,l2 ³ 0, то и Х ³ 0, т.е. удовлетворяет и условию X ³ 0, значит является допустимым решением ЗЛП.

¨

Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение ЗЛП, дается в следующей фундаментальной теореме.

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

Доказательство.

Предположим, что многогранник решений ограниченный, имеет конечное число угловых точек. Обозначим его через К. В двумерном пространстве К имеет вид многоугольника, изображенного на рисунке.

Свойства решений задачи линейного программирования - student2.ru Свойства решений задачи линейного программирования - student2.ru Обозначим угловые точки через х2 Х2 Х3,

Х1, Х2,…,Хр, Х1

Свойства решений задачи линейного программирования - student2.ru а оптимальный план – через Х*. Xi Хi

Тогда Z(X*)£ Z(X) 0 Хр х1

для всех точек Х многогранника решений К. Если Х* - угловая точка, то первая часть теоремы доказана.

Предположим, что Х* не является угловой точкой. Тогда Х* на основании теоремы 2 (о представлении выпуклого многогранника) можно представить как выпуклую линейную комбинацию угловых точек К, т.е.

Х*=l1Х1+l2Х2+…+lрХр, li ³ 0 ( i=1,2,…,p ), Свойства решений задачи линейного программирования - student2.ru =1.

Так как Z (X) – линейная функция, получаем

Z (X*)= Z (l1Х1+l2Х2+…+lрХр)= l1 Z (X1)+ l2 Z (X2)+…+ lp Z (Xp). (*)

В этом разложении среди значений Z(Xi) ( i=1,2,..,p ) выберем наименьшее (пусть оно соответствует угловой точке Хк ( 1£к£р ) ) и обозначим его через m, т.е. Z (Xк)=m. Заменим в (*) каждое значение Z (Xi) этим наименьшим значением. Тогда, так как li ³ 0 , Свойства решений задачи линейного программирования - student2.ru =1, то

Z(X*)³l1m+l2m+…+lрm= m Свойства решений задачи линейного программирования - student2.ru =m.

По предположению, Х* - оптимальный план, поэтому, с одной стороны, Z(X*)£m, но, с другой стороны, доказано, что Z(X*)³m, значит, Z(X*)=m= Z(Xк), где Хк – угловая точка.

Итак, существует угловая точка Хк, в которой линейная функция принимает минимальное значение.

Для доказательства второй части теоремы допустим, что Z (X) принимает минимальное значение более чем в одной угловой точке, например в точках Х1, Х2,…,Хq,1<q£p; тогда

Z(X1)= Z(X2)=…= Z(Xq)=m.

Пусть Х – выпуклая линейная комбинация этих угловых точек:

Х=l1Х1+l2Х2+…+lqХq, li ³ 0 ( i=1,2,…,q ), Свойства решений задачи линейного программирования - student2.ru =1.

Тогда, учитывая, что Z (X) – линейная функция, получаем

Z(X)=Z(l1Х1+l2Х2+…+lqХq)= l1Z(X1)+ l2Z(X2)+…+ lqZ(Xq)=l1m+l2m+…+lqm= =m Свойства решений задачи линейного программирования - student2.ru =m,

т.е. линейная функция Z принимает минимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек Х12,…,Хq. ¨

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

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

Следующая теорема посвящена аналитическому методу нахождения угловых точек.

Теорема 3. Каждому допустимому базисному решению (опорному плану) ЗЛП соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.

Доказательство.

Пусть Х= (x1, x2, ... , xm,0,…,0) - допустимое базисное решение системы ограничений A1x1+A2x2+…+Anxn= B, в которой первые m компонент – базисные переменные, а остальные n-m компонент – свободные, равные нулю в базисном решении (если это не так, то соответствующие переменные можно переменуровать).

Покажем, что Х – угловая точка многогранника решений.

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

Х1= (x1(1), x2(1), ... , xn(1)), Х2= (x1(2), x2(2), ... , xn(2)),

другими словами, - выпуклой линейной комбинацией точек Х1 и Х2 многогранника решений, т.е. (*) Х=l1Х1+l2Х2, l1> 0, l2>0, l1+l2=1.

(Полагаем, что l1¹0, l2¹0, ибо в противном случае точка Х совпадет с точкой Х1 или Х2).

Запишем векторное равенство (*) в координатной форме:

Свойства решений задачи линейного программирования - student2.ru

Поскольку xj(1)³0, xj(2)³0 (j=1,2,…,n), l1>0 и l2>0 , то из последних n-m равенств следует, что xm+1(1)=0, xm+1(2)=0,…, xn(1)=0, xn(2)=0, т.е. в решениях Х1, Х2 и Х системы уравнений A1x1+A2x2+…+Anxn= B значения n-m компонент равны в данном случае нулю:

Х1= (x1(1), x2(1), ... , xm(1),0,…,0), Х2= (x1(2), x2(2), ... , xm(2),0,…,0).

Эти компоненты можно считать значениями свободных переменных.

Поскольку Х1 и Х2 – планы, то

A1x1(1)+A2x2(1)+…+Amxm(1)= B, A1x1(2)+A2x2(2)+…+Amxm(2)= B.

Вычитая из первого соотношения второе, получаем

(x1(1)- x1(2))A1+(x2(1)- x2(2))A2+…+(xm(1)- xm(2))Am= 0.

По предположению, векторы А1, А2, ... ,Аm линейно независимы, поэтому последнее соотношение выполняется, если

x1(1)- x1(2)=0; x2(1)- x2(2)=0;…;xm(1)- xm(2)= 0.

Отсюда x1(1)=x1(2); x2(1)=x2(2);…;xm(1)=xm(2).

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

Докажем обратное утверждение. Пусть Х = (x1, x2, ... , xm,0,…,0) – угловая точка многогранника решений и первые ее m координат положительны. Покажем, что Х – допустимое базисное решение (опорный план).

Предположим противное, т.е. векторы А1, А2, ... ,Аm линейно зависимы. Тогда существуют такие числа l1, l2, ... ,lk, не все равные нулю, при которых выполняется соотношение

l1А1+ l2А2+ ... + lmАm=0. (*)

Зададим некоторое число e>0, умножим на него равенство (*):

el1А1+ el2А2+ ... +elmАm=0. (**)

По условию А1x1+ А2x2+ ... +Аmxm=B. (***)

Равенство (**) почленно сложим с равенством (***):

(x1 + el1 1+ (x2 + el2 2+ ... +(xm + elmm=B,

Теперь равенство (**) почленно вычтем из (***), получаем:

(x1 - el1 1+ (x2 - el2 2+ ... +(xm- elmm=B.

Сравнивая полученные последних два равенства с равенством (***), заключаем, что при любом e исходная система ограничений А1x1+ А2x2+ ... +Аnxn=B имеет два решения:

X1=( x1 + el1; x2 + el2; …; xm + elm; 0;…;0),

X2=( x1 - el1; x2 - el2; …; xm - elm; 0;…;0).

Все хi³0 (j=1,2,…,n), поэтому число e можно подобрать настолько малым, что все компоненты решений Х1 и Х2 примут неотрицательные значения, тогда Х1 и Х2 будут различными допустимыми решениями ЗЛП.

При этом, как легко видеть, решение ½ (Х1 + Х2) =X (показать самостоятельно), т.е. точка Х лежит на отрезке (в данном случае на его середине), расположенном в многограннике решений, а значит является выпуклой линейной комбинацией точек Х1, Х2. А значит не является угловой точкой, что противоречит условию теоремы о том, что Х – угловая точка.

Итак, наше допущение, что система векторов А1, А2, ... ,Аm линейно зависима, привело к противоречию. Следовательно, сделанное допущение неверно и система векторов линейно независима.

¨

Следствие 1. Так как векторы А1, А2, ... , Аn имеют размерность m, то угловая точка многогранника решений имеет не более чем m положительных компонент
xi > 0 (i=1,2, ..., m).

Следствие 2. Каждой угловой точке многогранника решений соответствует k£m линейно независимых векторов системы А1, А2, ... , Аn.

Можно предположить, что система векторов А1, А2, ... , Аn задачи линейного программирования всегда содержит m линейно независимых векторов. Если при решении частной задачи это не очевидно, то первоначальную систему векторов дополняют m линейно независимыми векторами, затем находят решение расширенной задачи.

Следствие 3. Если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.

Итак, если линейная функция ЗЛП ограничена на многограннике решений, то:

- существует такая угловая точка многогранника решений, в которой линейная функция ЗЛП достигает своего оптимального значения;

- каждый опорный план (допустимое базисное решение, каждое из которых определяется системой m линейно-независимых векторов, выбираемой из системы n векторов А1, А2, ... ,Аn) соответствует угловой точке многогранника решений.

Контрольные вопросы

1. Различные формы задач линейного программирования (общая, стандартная, каноническая) и их эквивалентность.

2. Понятие плана, вырожденный и невырожденный опорный план, оптимальный план.

Наши рекомендации