Доказательство. Заметим, прежде всего, что если правые части bi (i = 1,2, ,m) системы линейных уравнений равны нулю

Заметим, прежде всего, что если правые части b_i (i = 1, 2, …, m) системы линейных уравнений равны нулю, то, так как ранг матрицы А равен m, вектор является вырожденным опорным планом задачи линейного программирования. Поэтому в дальнейшем будем предполагать, что среди b_i есть отличные от нуля.

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

(2.34)

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

(2.35)

Введём обозначение

(2.36)

Изменением знака в (2.35) можно всегда добиться, чтобы μ было положительным.

Умножим левую и правую части (2.35) на и полученное равенство сложим с (2.34), будем иметь

или, так как

(2.37)

В силу (2.36)

(2.38)

и обязательно существует такое j, для которого в соотношении (2.38) имеет место равенство.

Положим для определённости, что .

Таким образом, мы построили план задачи линейного программирования, j-я компонента которого есть , а остальные n-k+1 компонент равны нулю.

Если при этом векторы оказались линейно зависимыми, то рассуждая аналогично, получим план задачи линейного программирования, у которого k-2 строго положительных компонент и так далее до тех пор, пока не построим такой план задачи линейного программирования с l (l≤ k) строго положительными компонентами, что соответствующие этим компонентам векторы будут линейно независимыми. Так по предложению среди b_i есть отличные от нуля, то l ≠ 0.

Согласно определению опорного плана ЗЛП построенный план является при l = m невырожденным, а при l < m вырожденным опорным планом задачи линейного программирования.

Теорема 2.14. Пусть векторы - планы задачи линейного программирования. Тогда вектор

(2.39)

где

(2.40)

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

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

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

Тогда , то есть вектор , определяемый соотношениями (2.39) и (2.40) также является решением задачи линейного программирования.

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

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

(2.41)

Тогда учитывая (2.40), будем иметь

.

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

Можно доказать следующую теорему о существовании оптимального опорного плана или опорного решения задачи линейного программирования.

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

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

Заметим, что так как по условию теоремы множество планов P не пусто, то согласно теореме 2.13 оно имеет хотя бы одну крайнюю точку.

Рассмотрим 2 случая:

1. Пусть Р – выпуклый многогранник, а - решение задачи линейного программирования. Тогда согласно теореме 2.9, точка может быть представлена в виде выпуклой линейной комбинации конечного числа крайних точек этого множества,

, , (2.42)

где - крайние точки множества Р.

Исключим из системы крайних точек те, которые входят в разложение (2.42) с коэффициентом α _i=0. Пусть это будут точки

.

Тогда

, ,

т.е. выполняются условия теоремы 2.14 и, следовательно,

,

что и доказывает теорему.

2. Пусть Р – неограниченное множество, а - конечное решение задачи линейного программирования.

Тогда можно указать такое положительное число М, что

. (2.43)

Введём дополнительное функциональное ограничение

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

(2.44)

при условиях

Множество планов данной задачи обозначим . Множество – ограниченное, а так как компоненты вектора удовлетворяют условиям (2.45) – (2.47) и , то является решением задачи. Следовательно, согласно доказанному в случае 1 во множестве существуют крайние точки такие, что

причём

, (2.48)

Если бы хотя бы одна крайняя точка (i=1, 2, …, N) не принадлежит гиперплоскости

, (2.49)

то она является крайней точкой множества Р и теорема доказана.

Пусть все крайние точки (i=1, 2, …, N) принадлежат гиперплоскости (2.49), то есть имеют место равенства

Тогда из (2.48) имеем

что противоречит условию (2.43) выбора М> 0.

Теорема 2.16 (следствие теоремы 2.15). Если решение задачи линейного программирования достигается в нескольких крайних точках области Р, то оно достигается и в любой выпуклой линейной комбинации этих точек.