1.5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

1.5.1. Вычислительная схема, основанная на преобразовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является этап пересчета значений А и b при переходе от одного базисного плана к другому (п.

Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц 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.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, т.

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.

Повторяя те же самые действия (их легко проследить по приводимым здесь таблицам Т2(2) и Т2(3), на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т2(3). Легко заметить, что в процессе решения мы «прошли» по той же самой последовательности допустимых базисных планов, которая встречалась в п. 1.4.3.