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

 

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

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

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

Пусть Х₁=(х₁¹, х₂¹,…, х_n¹) и Х₂=(х₁², х₂²,…, х_n²) – два допустимых решения ЗЛП, соответственно выполняются соотношения A×X₁ = B, X₁ ³ 0; A×X₂ = B, X₂ ³ 0.

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

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

Действительно, АХ=А(l₁Х₁+l₂Х₂)= l₁АХ₁+l₂АХ₂=l₁В+l₂В=(l₁+l₂)В=В,

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

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

¨

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

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

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

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

Обозначим угловые точки через х₂ Х₂ Х₃,

Х₁, Х₂,…,Х_р, Х₁

а оптимальный план – через Х^*. X_i Х_i

 

Тогда Z(X^*)£ Z(X) 0 Х_р х₁

 

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

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

Х^*=l₁Х₁+l₂Х₂+…+l_рХ_р, l_i ³ 0 (i=1,2,…,p), =1.

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

Z (X^*)= Z (l₁Х₁+l₂Х₂+…+l_рХ_р)= l₁ Z (X₁)+ l₂ Z (X₂)+…+ l_p Z (X_p). (*)

В этом разложении среди значений Z(X_i) (i=1,2,..,p) выберем наименьшее (пусть оно соответствует угловой точке Х_к (1£к£р)) и обозначим его через m, т.е. Z (X_к)=m. Заменим в (*) каждое значение Z (X_i) этим наименьшим значением. Тогда, так как l_i ³ 0, =1, то

Z(X^*)³l₁m+l₂m+…+l_рm= m =m.

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

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

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

Z(X₁)= Z(X₂)=…= Z(X_q)=m.

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

Х=l₁Х₁+l₂Х₂+…+l_qХ_q, l_i ³ 0 (i=1,2,…,q), =1.

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

Z(X)=Z(l₁Х₁+l₂Х₂+…+l_qХ_q)= l₁Z(X₁)+ l₂Z(X₂)+…+ l_qZ(X_q)=l₁m+l₂m+…+l_qm= =m =m,

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

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

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

 

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

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

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

Пусть Х= (x₁, x₂,..., x_m,0,…,0) - допустимое базисное решение системы ограничений A₁x₁+A₂x₂+…+A_nx_n= B, в которой первые m компонент – базисные переменные, а остальные n-m компонент – свободные, равные нулю в базисном решении (если это не так, то соответствующие переменные можно переменуровать).

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

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

Х₁= (x₁⁽¹⁾, x₂⁽¹⁾,..., x_n⁽¹⁾), Х₂= (x₁⁽²⁾, x₂⁽²⁾,..., x_n⁽²⁾),

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

(Полагаем, что l₁¹0, l₂¹0, ибо в противном случае точка Х совпадет с точкой Х₁ или Х₂).

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

Поскольку x_j⁽¹⁾³0, x_j⁽²⁾³0 (j=1,2,…,n), l₁>0 и l₂>0, то из последних n-m равенств следует, что x_m+1⁽¹⁾=0, x_m+1⁽²⁾=0,…, x_n⁽¹⁾=0, x_n⁽²⁾=0, т.е. в решениях Х₁, Х₂ и Х системы уравнений A₁x₁+A₂x₂+…+A_nx_n= B значения n-m компонент равны в данном случае нулю:

Х₁= (x₁⁽¹⁾, x₂⁽¹⁾,..., x_m⁽¹⁾,0,…,0), Х₂= (x₁⁽²⁾, x₂⁽²⁾,..., x_m⁽²⁾,0,…,0).

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

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

A₁x₁⁽¹⁾+A₂x₂⁽¹⁾+…+A_mx_m⁽¹⁾= B, A₁x₁⁽²⁾+A₂x₂⁽²⁾+…+A_mx_m⁽²⁾= B.

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

(x₁⁽¹⁾- x₁⁽²⁾)A₁+(x₂⁽¹⁾- x₂⁽²⁾)A₂+…+(x_m⁽¹⁾- x_m⁽²⁾)A_m= 0.

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

x₁⁽¹⁾- x₁⁽²⁾=0; x₂⁽¹⁾- x₂⁽²⁾=0;…;x_m⁽¹⁾- x_m⁽²⁾= 0.

Отсюда x₁⁽¹⁾=x₁⁽²⁾; x₂⁽¹⁾=x₂⁽²⁾;…;x_m⁽¹⁾=x_m⁽²⁾.

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

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

Предположим противное, т.е. векторы А₁, А₂,...,А_m линейно зависимы. Тогда существуют такие числа l₁, l₂,...,l_k, не все равные нулю, при которых выполняется соотношение

l₁ А₁+ l₂ А₂+... + l _mА_m=0. (*)

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

e l₁ А₁+ e l₂ А₂+... +e l _mА_m=0. (**)

По условию А₁x₁+ А₂x₂+... +А_mx_m=B. (***)

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

(x₁ + e l₁ ) А₁+ (x₂ + e l₂ ) А₂+... +(x_m + e l_m) А_m=B,

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

(x₁ - e l₁ ) А₁+ (x₂ - e l₂ ) А₂+... +(x_m- e l_m) А_m=B.

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

X₁=(x₁ + e l₁; x₂ + e l₂; …; x_m + e l_m; 0;…;0),

X₂=(x₁ - e l₁; x₂ - e l₂; …; x_m - e l_m; 0;…;0).

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

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

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

¨

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

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

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

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

 

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

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

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

 

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

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

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