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

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

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

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

, , (3.37)

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

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

.

Тогда

, ,

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

,

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

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

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

. (3.38)

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

(3.39)

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

(3.40)

при условиях

(3.40 – 3.42)

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

причём

, (3.43)

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

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

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

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

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

Теорема доказана.

7. Обоснование симплекс-метода решения КЗЛП: К-матрицы, условия перехода от одной К-матрицы к другой, изменение целевой функции при переходе от одной К-матрицы к другой, критерий оптимальности опорного плана, критерий неразрешимости ЗЛП (критерий неразрешимости без доказательства)

Пусть известна К-матрица

(3.45)

Обозначим через вектор номеров базисных (единичных) столбцов матрицы , -вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей , и могут быть отличны от нуля. Остальные (n-m) компонент опорного плана, определяемого матрицей , равны нулю. Очевидно, что векторы и полностью задают опорный план, определяемый матрицей . Например, пусть

= ,

тогда =(3,1,6); = =(1,2,4) и, следовательно, опорный план, определяемый , имеет вид

=(2,0,1,0,0,4).

Итак, пусть К-матрица (3.45) определяет невырожденный опорный план

(3.46)

Выберем в матрице столбец , не принадлежащий единичной подматрице, т.е. , и такой, что в этом столбце есть хотя бы один элемент больше нуля.

Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана-Гаусса. В результате получим новую матрицу

, (3.47)

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

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

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

По условию теоремы

или

(3.52)

Пусть - произвольный план задачи линейного программирования. Умножим левую и правую части (3.52) на , тогда в силу неотрицательности получим

(3.53)

Согласно (3.53) имеем

или

,

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

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

8. Обоснование симплекс-метода решения КЗЛП: К-матрицы, условия перехода от одной К-матрицы к другой, изменение целевой функции при переходе от одной К-матрицы к другой, критерий оптимальности опорного плана (критерий оптимальности без доказательства), критерий неразрешимости ЗЛП.

Пусть известна К-матрица

(3.45)

Обозначим через вектор номеров базисных (единичных) столбцов матрицы , -вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей , и могут быть отличны от нуля. Остальные (n-m) компонент опорного плана, определяемого матрицей , равны нулю. Очевидно, что векторы и полностью задают опорный план, определяемый матрицей . Например, пусть

= ,

тогда =(3,1,6); = =(1,2,4) и, следовательно, опорный план, определяемый , имеет вид

=(2,0,1,0,0,4).

Итак, пусть К-матрица (3.45) определяет невырожденный опорный план

(3.46)

Выберем в матрице столбец , не принадлежащий единичной подматрице, т.е. , и такой, что в этом столбце есть хотя бы один элемент больше нуля.

Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана-Гаусса. В результате получим новую матрицу

, (3.47)

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

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

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