
Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц
T1 и
Т2(q). Таблица
T1 (
рис. 1.7) является общей для всех итераций и служит для получениястроки оценок текущего базисного плана
a0(β
(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)), полученных на этапе поиска допустимого базисного плана, переносится в таблицу
T2(1).
4. Полагаем номер текущей итерацииq равным 1 и переходим к I-этапу.
1-этап. Стандартная итерация алгоритма — выполняется для очередного базисного плана x(β(q)).
1°. Проверка оптимальности текущего базисного плана. Содержимое нулевой строки таблицы T2(q) — δ0(β(q)) переписывается в соответствующую графу таблицы T1. По формуле (1.42) рассчитываем и заполняем строку a0(β(q)). Осуществляем просмотр строки оценок a0(β(q)). Возможны два варианта:
1΄. a0(β(q))≥0 —план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х* =x(β(q)) и оптимальное значение целевой функцииf(х*)=f(x(β(q))).
1". В строке оценок a0(β(q))существует по меньшей мере один элемент a0,j(β(q))<0, т. е. имеющий отрицательную оценку. Следовательно, план x(β(q)) —неоптимален. Выбирается номер l, соответствующий элементу, имеющему минимальную (максимальную по абсолютной величине) отрицательную оценку:
l-й столбец матрицы
A становится
ведущим и должен быть введен в очередной базис. Переходим к пункту 2° алгоритма.

2°.
Определение столбца, выводимого из базиса. Переписываем ведущий столбец
аl из таблицы
T1 в текущую таблицу
Т2(q). По формуле
аl(β
(q)) = Δ
-1(β
(q))
аl заполняем соответствующий столбец в таблице
Т2(q). Возможны два варианта:
2'. Для всехiÎ 1: mаi,l(β(q))≤0. Делается вывод о неограниченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере один индекс
iÎ 1:
m, для которого
аi,l(β
(q))>0. Согласно правилу (1.27) определяются место
r и номер
Nr(β
(q)) для столбца, выводимого из базиса. Переходим к пункту 3° алгоритма.
3°. Пересчет относительно нового базиса элементов столбца bи матрицыΔ-1. Переход к новому базисуβ(q+1), который получается введением в базис β(q) столбца аl и выводом из него столбца аr, осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:

Полагаем номер текущей итерацииq: =q+l и переходим к первому пункту алгоритма.
В завершение подчеркнем, что в силу приведенных выше преимуществ именно модифицированный симплекс-метод реально применяется в программном обеспечении, предназначенном для решения канонических задач линейного программирования.
1.5.2. Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3оно начинается с выбора очевидного исходного базиса, образуемого столбцами {5,2,3}. Для него уже были вычислены Δ-1(β(q)) и b(β(q)), поэтому заполнение начальных таблиц T1 и Т2(1) не представляет труда.

На первой итерации мы переписываем нулевую строку
из Т2(1) вT1 и, умножив ее на матрицу A, получаем строку оценок

Так какa0(β(1)) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β(1), и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l =4.
Переписываем столбец

из таблицы
T1 в
Т2(1) и пересчитываем его координаты относительно текущего базиса, т. е. умножаем матрицу Δ
-1(β
(q)), расположенную в таблице
Т2(1) слева, на
а4.

После заполнения таблицы
Т2(1) данными по вводимому в новый базис столбцу можно перейти к определению номера выводимого столбца. Эта процедура осуществляется в полной аналогии с обычным симплекс-методом. Рассмотрев отношения элементов
bi(β
(1)) и
ai,l(β
(1)) для {
iÎ1:
m| ai,l(β
(1))>0} и определив минимальное из них, находим, что
r =2. Следовательно, столбец с номером
N2(β
(q)) =2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи с
N(β
(2)) ={5, 4, 3}. Элемент
a2,3(β
(1)) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к симплекс-таблице, соответствующей второй итерации
Т2(2), и полагаем индекс текущей итерации
q = 2.