 |
 |
 |
 |
|
 |
 |
27
очередной итерации q преобразование Жордана—Гаусса не над матрицей А(?
(q)
), а над матрицей
?
-1
(?
(q)
). При этом учитывается и то, что при необходимости, применяя формулу (1.26), всегда можно
получить А(?
(q)
)
по ?
-1
(?
(q)
). Более того, для выполнения описанных выше действий симплекс-
процедуры нам в действительности не требовалась матрица А(?
(q)
)
целиком. Реально в ней
использовались только строка оценок a
0
(?
(q)
)
и ведущий столбец
a
l
(?
(q)
). Данные соображения
положены в основу вычислительной схемы симплекс-метода, основанной на преобразовании обратных
матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм
был предложен в 1951 г. в работах Л. В. Канторовича.
Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц T1 и
Т2
(q)
. Таблица T1 (рис. 1.7) является общей для всех итераций и служит для получения
строки оценок
текущего базисного плана a
0
(?
(q)
). Если обозначить через
?
i
(?
(q)
)
(i
0 : m) строки матрицы ?
-1
(?
(q)
), то
из (1.26), в частности, следует, что
Как видно из рис. 1.7, T1 состоит из трех блоков:
в центре содержится матрица А;
в левом блоке таблицы на каждой итерации дописываются нулевые строки матрицы ?
-1
(?
(q)
)
для
текущего базиса;
нижний блок, расположенный под матрицей
А, на каждой итерации дополняется строкой
оценок текущего плана, вычисленной по формуле (1.42).
Симплекс-таблица Т2
(q)
, изображенная на рис. 1.8, соответствует допустимому базису КЗЛП
?
(q)
,
получаемому на
q-й итерации. Столбец N(?
(q)
) содержит номера базисных столбцов (в
последовательности вхождения в базис); столбец b(?
(q)
) — компоненты вектора ограничений
относительно текущего базиса
?
(q)
; ?
-1
(?
(q)
)
— матрица, обратная по отношению к матрице расширенных
столбцов текущего базиса ?
(q)
; графа а
l
содержит расширенный вектор условий, вводимый в базис на
текущей итерации, а следующая графа — координаты а
l
(?
(q)
) ?
этого же столбца в текущем базисе
(q)
.
По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.
0-этап. Нахождение допустимого базисного плана.
1. Для поиска допустимого базиса может быть применен метод минимизации невязок,
рассмотренный в п. 1.4.5. При этом для решения вспомогательной задачи используется процедура
модифицированного симплекс-метода. В результате 0-этапа мы получаем допустимый базисный план
x(?
(1)
) и соответствующие ему матрицу ?
-1
(?
(1)
)
и вектор b(?
(1)
).
2. Заполняем центральную часть таблицы T1, содержащую матрицу А.
3. Содержимое матрицы ?
-1
(?
(1)
)
и вектора b(?
(1)
), полученных на этапе поиска допустимого