3.3. Условие оптимальности для злп.

Лемма:

Пусть точка - оптимальная точка ЗЛП. Пусть существуют точки,..., X , такие что =, где>0 и=1, тогда

(c, ) = (c,) = ... = (c,).

Доказательство : ( идея )

Предположим, что (c, ) (c, ) ...  (c, ). (*)

Тогда (c, ) = (c,) = (по св-ву скал. произв.) = (c, ) (c, ) = (c,) ; учитывая (*), получаем (c,) = (c,) .

Далее по индукции.

Теорема ( об угловой точке ) :

Если для ЗЛП существует оптимальная точка , то найдется угловая точкаX такая , что (c,) = (c,).

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

1.Пусть допустимое множество X ограничено. По теореме о представлении:

=; 0 , =1,- угловые (крайние ) точки множества X.

В случае необходимости перенумеруем так, чтобы0,...,0,= 0,...,= 0 ; тогда=,>0 ,=1. На основании предыдущей леммы можно утверждать, что (c,) = (c,) = ... = (c,).

Теперь в качестве можно взять любую угловую точку,..., X .

2.Пусть X не ограничено, а - оптимальная точка.

Выберем некоторое число > 0 и построим два множества:

L = {x : },= {x :=}.

Иллюстрация для :

Число выбираем так , чтобы L , но .

Тогда  XL , которое является ограниченным (см. рисунок). Поэтому :

=,>0 ,=1,- угловые (крайние ) точки множества XL (по теореме о представлении).

Если хотя бы одна точка l, то теорема доказана , т.к.- угловая точка множества X (см. рисунок).

Если все  , i =,то из представления=,>0 ,=1,

i =следует что , что противоречит выбору числа.

Т.к. выпукло:

=+-=+-=,

если , (проверка определения выпуклого множества).

3.4. Базис и базисное решение.

Пусть X = { x :, i =, 0 }

(c, x) = - ?

Введем векторы :

, которые называются векторами условий .

Тогда ЗЛП имеет вид :

,  0 , j =

(c, x) - ?

Определение: Допустимое решение называется базисным, если система векторов условий , отвечающих его положительным компонентам (>0) линейно независима. При этом упомянутая система векторов называется базисом.

* речь идет о векторах

Теорема (о допустимом решении ЗЛП) :

Допустимое решение является крайней точкой (планом) тогда и только тогда, когда оно базисное.

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

Достаточность () Пусть x - базисное решение. Без ограничения общности можно предположить , что первые k компонент x (решения) отличны от нуля, остальные - нули . Т.е. x = . По определению базисного решения :и система векторов, ...,линейно независима. Покажем, что x является крайней точкой. Допустим противное, то есть что точкаx может быть представлена в виде:

x = + (1 -), 0 <<1,, X - различные точки

В силу того, что >0, 1->0идолжны иметь вид :

=

=

Т.к. и- допустимые точки, то

, следовательно 0

Из линейной независимости векторов , ...,следует , что=, а это противоречит тому, что, поэтому x – крайняя точка.

Необходимость(). Пусть x = является крайней точкой X.

Покажем, что x является базисным решением. Для этого достаточно показать, что система векторов , ...,линейно независима . Предположим противное.

Тогда (не все нулевые) такие, что 0

Т.к. x - допустимое решение, то

Рассмотрим при произвольном >0 следующее выражения :

,

Ясно, что можно подобрать так , чтобы точки

=

=

имели положительные компоненты, т.е. были бы допустимыми решениями. Тогда получаем: x = , т.е. x не является крайней точкой. Тогда предположение неверно, система, ...,линейно независима . Теорема доказана.

Следствие 1: Т.к. векторы, ...,имеют размерность m , то крайняя точка, принадлежащая X, имеет не более чем m положительных компонент.

Следствие 2: Каждой угловой точке соответствует не более m ( k  m ) линейно независимых векторов системы , ...,.

Следствие 3: Число крайних точек множества X конечно.

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

Замечание :

Можно показать, что каждой крайней точке соответствует не более n активных ограничений.

Количество ограничений в ЗЛП n+m.

Количество крайних точек не больше , то есть – конечно.