Доказательство. Пусть вектор - опорный план ЗЛП, у которого компоненты строго положительные, а остальные (n-k) компонент равны нулю.

Пусть вектор - опорный план ЗЛП, у которого компоненты строго положительные, а остальные (n-k) компонент равны нулю.

Тогда согласно определению опорного плана ЗЛП векторы линейно независимы.

Предположим, что вектор не является крайней точкой множества P, то есть существуют векторы , и такие, что

(2.26)

Векторы и - планы ЗЛП. Это означает, во-первых, что компоненты векторов и неотрицательные и вследствие (2.26) ровно k компонент вектора и ровно k компонент вектора могут быть строго положительными. Остальные (n-k) компонент каждого из векторов и равны нулю.

Во-вторых, компоненты векторов и удовлетворяют функциональным ограничениям (2.24) ЗЛП. Следовательно, имеют место слудующие равенства:

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

(2.27)

Так как векторы линейно независимы, то из (2.27) следует, что или . Последнее означает, что = .

Получили противоречие, следовательно, - крайняя точка множества P.

Обратно, пусть теперь вектор - крайняя точка множества P, строго положительными компонентами которой являются . Так как вектор - план ЗЛП, то его компоненты удовлетворяют функциональным ограничениям (2.24) задачи, то есть имеет место равенство

(2.28)

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

(2.29)

Зададим некоторое ε > 0. Умножим левую и правую части равенства (2.29) сначала на ε, затем на (-ε). Каждое из полученных равенств сложим с (2.28), в результате получим

(2.30)

(2.31)

Выберем ε настолько малым, чтобы выполнялись неравенства

(2.32)

(2.33)

Рассмотрим векторы и , у каждого из которых отличными от нуля могут быть лишь k компонент

и

соответственно, а остальные n-k компонент равны нулю.

Согласно (2.30)- (2.33) векторы и являются планами ЗЛП.

Имеем , то есть лежит внутри отрезка, соединяющего две различные точки и множества P.

Последнее означает, что - не крайняя точка множества P. Получили противоречие, следовательно, - опорный план ЗЛП.

Следствие 1. Крайняя точка множества P может иметь не более m строго положительных компонент.

Следствие 2. Число крайних точек множества P конечно не превышает .

Следствие 3. Если множество P ограниченное, то оно является выпуклым многогранником.

Теорема 2.12. (о существовании оптимального плана или решения ЗЛП) Если линейная форма ограничена сверху на непустом множестве P, то ЗЛП разрешима, то есть существует такая точка , что . (теорема Вейерштрасса)

Теорема 2.13. Если множество P не пусто, то оно имеет опорный план (или крайнюю точку).