Лекция: ПЕРЕХОД ОТ ОДНОЙ К-МАТРИЦЫ ЗЛП К ДРУГОЙ К-МАТРИЦЕ

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

.

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

= ,

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

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

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

. (3.46)

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

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

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