2.4 Элементарное преобразование базиса и симплекс-таблицы

Перебор базисов, который происходит при решении задачи симплекс-методом, производится посредством минимального из­менения рассматриваемого в данный момент базиса. Таким ми­нимальным изменением, очевидно, является замена одного из ба­зисных столбцов на другой столбец матрицы А из числа неба­зисных. Подобное преобразование базиса мы и будем называть элементарным. Естественно, выбор того и другого столбца при этом преобразовании не является произвольным, а производится в соответствии с определенными правилами, что и делает перебор целенаправленным.

Наша ближайшая цель — проследить за изменением симплекс-таблицы при таком преобразовании базиса и установить правило, которое может быть использовано для получения симплекс-таб­лицы, соответствующей преобразованному базису.

Пусть в базисе В = [А^),..., Аст(т)], которому соответствует симплекс-таблица (2.5), столбец Аа^ решено заменить на стол­бец А3, в 6 Б1. Результатом такой замены будет новый базис В' = [А(7(1),..., А(7(г_1), А3, А(7(г+1),..., А(7(т)], если только элемент ггз симплекс-таблицы не равен 0. Это легко понять, если учесть, что согласно (2.4) (г1з,..., гтз)т = В~1 А31 т.е. А3 = В(г1з,..., гтз)т или

т

А3 = ^2 ггв^-а(%) • г = 1

Поскольку разложение любого вектора по векторам базиса един­ственно, то при ггз ф 0 вектор А3 не может быть представлен в ви­де линейной комбинации векторов Аа^,..., А(7(г_1), Аа^г+1^,..., ^ст(т)) ЧТО означает линейную независимость столбцов в В'. В случае ггз = 0 вышеприведенное представление вектора А3 сви­детельствует о линейной зависимости столбцов матрицы В'.

Чтобы сформулировать правило, согласно которому может быть получена симплекс-таблица, соответствующая преобразо­ванному базису В', напомним, что элементами таблицы являют­ся коэффициенты линейной системы (2.1"), (2.2"), полученной из системы (2.1), (2.2) путем приведения ее к диагональной форме относительно базисных переменных и переменной —ги. Так как новый набор базисных переменных отличается от старого только одной переменной х3 (заменившей переменную ж^,.)), то для полу­чения элементов новой симплекс-таблицы достаточно выполнить один шаг метода исключения Гаусса-Жордана, чтобы исключить х3 из всех, кроме одного, уравнений системы (2.1"), (2.2"), соот­ветствующей старому базису В (используя для этого единствен­ное уравнение данной системы, содержащее из числа базисных только исключаемую из базиса переменную жст(г), т.е. г-е уравне­ние).

Таким образом, мы приходим к следующему правилу: разде­лить г-ю строку симплекс-таблицы на ггз и прибавить ее, умноженную на надлежащим образом подобранные числа, к другим строкам так, чтобы 1 в позиции (г, в) осталась единственным не­нулевым элементом й-го столбца. Если воспользоваться обозна­чением о.і для г-ж вектор-строки симплекс-таблицы, то правило преобразования можно изобразить схематично следующим обра­зом:

При этом г-я строка, з-ж столбец и элемент гГ8 называются ведущими.