Переход от одной к-матрицы ЗЛП к другой к-матрице

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

.

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

= ,

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

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

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

. (3.46)

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

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

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