Переход от одной к-матрицы злп к другой к-матрице

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

(3.45)

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

=,

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

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

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

(3.46)

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

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

, (3.47)

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

Теорема 1.8 Пусть в к-м столбце К-матрицы - есть хотя бы один строго положительный элемент (,). Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую К-матрицу - , выбрав направляющий элемент из условия:

(3.48)

Определение. Величину

, (3.49)

где - вектор, компонентами которого являются коэффициенты линейной функции при базисных () переменных опорного плана, определяемого матрицей , назовем j-й симплекс-разностью матрицы .

Если столбец является единичным в матрице , то =0.

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

_(3.50)

, (3.51)

где К - номер столбца , вводимого в базис при получении матрицы из. определяется по формуле (3.48).

Теорема 1.9. Пусть в матрице есть и в столбце ( , ) есть хотя бы один строго положительный элемент. Тогда от матрицы можно перейти к матрице , причем

f () f(). (3.52)

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

Так как в столбце матрицы есть строго положительный элемент, то согласно теореме 1.1 от матрицы можно перейти к новой матрице ЗЛП, выбрав направляющий элемент из условия (3,48).

Неравенство (3.52) вытекает из выражения (3.51), так как , а _0.

_{Теорема доказана.}

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

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

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

или

(3.52)

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

(3.53)

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

или

,

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

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

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

Пусть К-я симплекс-разность матрицы

, (3.54)

и все

(3.55)

Матрица определяет опорный план

Рассмотрим вектор

,

у которого

где - любое положительное число.

Остальные компонент вектора положим равными нулю.

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

Имеем:

или окончательно

(3.56)

Так как , то из (3.56) следует, что для любого числа всегда можно найти план ЗЛП, для которого

т.е. линейная форма не ограничена сверху на множестве планов.

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