В. 32 Теорема о крайней точке

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

Требуется доказать: х – БДР ó х – крайняя точка.

(1) Доказать: Если х – БДР => х – крайняя точка

Пусть х - БДР, тогда без ограничения общности считаем, что первые m координат являются базисными x=(x₁, x₂,…, x_m, 0,0,…0), т.е. единичная матрица стоит в начале. Сделаем предположение, что х - не крайняя точка. Тогда по определению крайней точки можно отыскать 2 вектора x’, x” (x’= x”), что х представляется в виде их линейной выпуклой комбинации, т.е. х=α₁х’+α₂х” (т.е. точка – середина отрезка), где α₁+α₂=1, α₁, α₂ ≥0.

Т.к. все неотрицательны (условие задач ЛП)

Т.к. сумма «+» чисел = 0, они все равны 0.

Т.к. не может быть = нулю, следовательно, . Далее, из этого => x’ и x” - БДР.

Аx’=b

Ax”=b; произведение матрицы на вектор можем переписать (x’-x” - соответствующие координаты)

Первые m столбцов матрицы А - линейно-независимы (по условию), т.е. А₁….A_m – ЛНз, x’=x” i=1,..,m. Получили противоречие, т.к. изначально x’ и x” – разные.

(2) Доказать: Если х – крайняя точка => х – БДР.

Предположим, что х - кр. точка. Если х = 0, то любой набор ЛНз столбцов будет базисным, и такой набор всегда можно найти. Если х=0 => х – БДР.

Пусть x≠0, без ограничения общности получим, то именно первые r координат ≠ 0, т.е. x=(x₁, x₂,…, x_r, 0,0,…0).

Т.к. х находится в допустимом множестве, он удовлетворяет ограничениям задачи. Перепишем как . Если окажется, что вектора - столбцы А₁….A_r – ЛНз, то тогда х – БДР и теорема доказана.

Предположим, что А₁….A_r – ЛЗ, то существует набор констант α₁…α_r не все = 0 одновременно, так что: . Перепишем сумму в матричной форме: .

Построим 2 новых точки: , где t>0.

Рассмотрим: т.о., вектора u, v удовлетворяют системе ограничений осталось убедиться, что u,v≠0 (при этом t – очень маленькое число, неравное 0).

t выбираем настолько маленьким, чтобы комбинации U и V остались положительными (при умножении на t). Это и означает, что U и V являются допустимым решением задач.

, это означает, что х лежит на середине, т.е. он не является крайней точкой. Получили противоречие, т.к. предположили, что вектора А₁….A_r – ЛЗ. След-но, они ЛНз и х – БДР.

Смысл:

1. Симплексный метод перебирает БДР (БДР меняется)

2. По теореме о крайней точке БДР являются угловыми точками

3. В вопросе 30 было доказано, что оптимальное решение обязательно находится в угловой точке.

Теорема о крайней точке показывает, что симплексный метод ищет решение как раз среди угловых точек, т.е. действительно ищет оптимальное решение.