3. Определение вершины. Крайняя точка. Базисное решение. Теоремы о вершине ( теорема 1 о соответствии вершины допустимого множества решений базисному; теорема 2 о ранге матрицы носителя).

Точка(вектор) называется крайней точкой(вершиной) множества М, если из соотношения следует, что либо , либо , либо и .

Базисное решение. Пусть для определения первые m столбцов матрицы А образуют ее базис. Переменные , соответствующие столбцам - базисные переменные, а , соответствующие столбцам - свободные. Допустимое решение является допустимым базисным решением, если значения свободных переменных вектора равны нулю

Теоремы о вершине

Теорема 1 о соответствии вершины допустимого множества решений базисному.

1. базисное решение является вершиной (базисное решение не может быть представлено в виде ЛК каких либо доп. решений)

Если базисное решение, но не является вершиной, то у него есть ЛН столбцы , соотв. базисным переменным. А последние m-n столбцы -своб. и =0.

Если запишем решение

Возьмем произвольные точки и подставим без ост. m-n координат

Т.к. вектора соотв. базисным переменным, они нез-мы, и это равенство выполняется лишь, если все коэф.=0

. Точки совпадают и не может быть ЛК никаких двух точек, значит - вершина, если она базисное опорное решение.

2. Любая угловая точка из области допустимых решений –базисное решение.

Рассмотрим Пусть вершина, у которой часть переменных>0. Чтобы показать, что это решение опорное, надо показать, что вектора-столбцы, соотв. ненулевым координатам ЛН. Пусть это не так, и векторы ЛЗ, но тогда существует набор чисел не все=0 и (1)

Т.к. допустимое решение (2)

Теперь сложим (1) и (2). .

Затем вычтем из (2) (1)

Выберем такой чтобы , это можно сделать так как . Такой найдется, но тогда точки и -точки из области допустимых решений. При этом , т.е. –вып. ЛК с коэф. ½ из множества допустимых решений, а это противоречит тому, что она – вершина( по предположению ЛЗ). Значит предположение неверно, ЛН и наша точка – базисное решение.

Теорема 2 о ранге матрицы носителя.

Точка из допустимого множества – крайняя тогда и только тогда, когда rank =n, где n – число переменных.

Носитель крайней точки – множество всех ограничений, к-е обращает в равенство.

- множество номеров тех векторов, которые определяют носитель

- множество номеров остальных векторов из множества

- матрица, строки которой - вектора ; - соотв. вектор-ограничение

Тогда ограничения принимают вид

а) Если крайняя точка, тогда rank =n

б) Если rank =n, то крайняя точка

а) пусть это не так, т.е. <n , а крайняя точка и имеет решение

Т.к. можно подобрать такое , что и

При этом . Аналогично для

предст. в виде нек вып. комбинации в частности с коэф. ½, т. принадл. множеству, что противоречит определению крайней точки( не мб представлена ЛК) пусть

б) rank =n, а не крайняя точка.

Тогда найдутся такие и , принадлежащие x; , что - середина отрезка между ними. Тогда . В этом случае

Но это противоречит тому, что

Значит предположение неверно.