Переход от одной К-матрицы ЗЛП к другой К-матрице
Пусть известна К -матрица
(2.55)
Обозначим через вектор номеров базисных (единичных) столбцов матрицы , -вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей , и могут быть отличны от нуля. Остальные (n-m) компонент опорного плана, определяемого матрицей , равны нулю. Очевидно, что векторы и полностью задают опорный план, определяемый матрицей . Например, пусть
= ,
тогда =(3, 1, 6); = =(1, 2, 4) и, следовательно, опорный план, определяемый , имеет вид
=(2, 0, 1, 0, 0, 4).
Итак, пусть К -матрица (2.55) определяет невырожденный опорный план
(2.56)
Выберем в матрице столбец , не принадлежащий единичной подматрице, т.е. , и такой, что в этом столбце есть хотя бы один элемент больше нуля.
Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана-Гаусса. В результате получим новую матрицу
, (2.57)
элементы которой выражаются через элементы матрицы следующим образом: (2.58)
(2.59)
, (2.60)
в которой столбец стал единичным, но которая может и не быть К -матрицей, так как среди величин могут быть отрицательные. Условия выбора направляющего элемента , позволяющие получить новую К -матрицу - , т.е. обосновывающие способ перехода от опорного плана к опорному плану , составляет содержание следующей теоремы:
Теорема 2.18. Пусть в k -м столбце К -матрицы - есть хотя бы один строго положительный элемент ( , ). Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую К -матрицу - , выбрав направляющий элемент из условия:
(2.61)
Доказательство.
Получим условия, которым должен удовлетворять направляющий элемент , чтобы

Из соотношения следует, что
> 0
тогда и только тогда, когда
> 0.
Это первое условие, которое мы должны наложить на выбор направляющего элемента.
Из соотношения следует, что

тогда и только тогда, когда
(1)
Это условие выполняется для всех 
Перепишем неравенство (1) для строго положительных в виде (2)
Очевидно, что неравенство (2) будет выполняться для всех > 0, если выбрать таким, что
> 0.
Симплекс-разность К-матрицы ЗЛП
Определение 2.19. Величину
,
где - вектор, компонентами которого являются коэффициенты линейной функции при базисных ( ) переменных опорного плана, определяемого матрицей , назовем j-й симплекс-разностью матрицы .
Если столбец является единичным в матрице , то =0
Посмотрим, как изменяется j-я симплекс - разность при переходе от K -матрицы к новой K - матрице ЗЛП. Согласно определению симплекс – разности имеем
.
Используя в этом соотношении формулы
(1)
(2)
, (3)
найдем


Сложим последнее равенство с тождеством

в результате получим

или окончательно
. (2.62)
Изменение функции цели ЗЛП при переходе от одной К-матрицы к другой
Пусть и - опорные планы, определяемые матрицами и соответственно.
Тогда очевидно, что
(2.63)
Посмотрим, как изменяется функция цели при переходе от K -матрицы к новой K - матрице задачи линейного программирования. Имеем

Используя в этом соотношении формулы (1)-(3), найдем
Сложим это равенство с тождеством

в результате получим


или в векторной форме
, (2.64)
где k - номер столбца , вводимого в базис при получении матрицы из . определяется по формуле (2.61).
Теорема 2.19 Пусть в матрице есть и в столбце ( , ) есть хотя бы один строго положительный элемент. Тогда от матрицы можно перейти к матрице , причем
f ( ) f ( ). (2.65)
Доказательство.
Так как в столбце матрицы есть строго положительный элемент, то согласно теореме 2.18 от матрицы можно перейти к новой матрице ЗЛП, выбрав направляющий элемент из условия (2.61).
Неравенство (2.65) вытекает из выражения (2.64), так как , а 0.
Теорема 2.20. (критерий оптимальности опорного плана) Пусть все симплекс-разности матрицы неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным.
Доказательство.
По условию теоремы

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

или
,
что и доказывает теорему.
Теорема 2.21. Пусть в матрице есть , и в столбце ( , ) нет ни одного строго положительного элемента. Тогда ЗЛП (2.52)-(2.54) не имеет конечного решения.
Доказательство.
Пусть k -я симплекс-разность матрицы 
, (2.68)
и все
(2.69)
Матрица определяет опорный план


Рассмотрим вектор
,
у которого


где - любое положительное число.
Остальные компонент вектора положим равными нулю.
В силу условия (2.69) компоненты вектора неотрицательные. Легко убедиться в том, что компоненты вектора удовлетворяют и функциональным ограничениям (2.53) ЗЛП, т.е. вектор - план ЗЛП при любом положительном .
Имеем:


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

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