2.2. Алгоритм и табличная реализация двойственно­го симплекс-метода.

Обобщая сказанное в предыдущем пун­кте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП.

0-этап. Нахождение исходного сопряженного (двой­ственно допустимого базиса). Результатом 0-этапа являют­ся сопряженный базис β⁽¹⁾ и соответствующие ему псевдоплан x(β⁽¹⁾), матрица A(β⁽¹⁾) и вектор b(β⁽¹⁾), которые будут исполь­зованы на первой итерации. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.

I-этап. Стандартная итерация алгоритма — выполня­ется для очередного сопряженного базиса β^(q).

1°. Проверка оптимальности текущего псевдоплана: осу­ществляется просмотр значений b_i(β^(q)), i1:m. Возможны два варианта:

1΄. Для всех i1:m, b_i(β^(q)) ≥ 0. Тогда текущий псевдоплан x(β^(q)) одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный про­цесс закончен. Элементы оптимального плана х* определяют­ся по формуле

а достигаемое на нем значение целевой функции равно

1". Существует по меньшей мере один номер строки r1:m, для которого b_r(β^(q))<0 . Следовательно, псевдоплан x(β^(q)) — неоптимален. Выбирается строка с номером r, такая, что

Она становится ведущей и определяет номер столбца N_r(β^(q)), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.

2°. Определение столбца, вводимого в базис. Рассматрива­ется ведущая строка а_r(β^(q)). Возможны два варианта:

2'. Для всех j1: n а_r,j(β^(q)) ≥ 0. Делается вывод об отсут­ствии допустимых планов у решаемой задачи (D = Ø) и за­вершается вычислительный процесс*.

2". В строке а_r(β^(q)) существует по крайней мере один эле­мент а_r,j(β^(q))<0. Согласно правилу (1.62) определяются l — номер столбца, вводимого в очередной базис. Переходим к пун­кту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относи­тельно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи A и век­тора ограничений b относительно нового базиса β^(q+1), который получается в результате вывода из базиса β^(q) столбца а^r и вво­да в него столбца а^l. Полагаем номер текущей итерации q: = q+1 и переходим к первому пункту алгоритма.

По аналогии со стандартным симплекс-методом вычислитель­ную процедуру двойственного симплекс-метода удобно офор­млять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с формальной стороны их структура остается неизменной. Иног­да считается целесообразным добавить к двойственной симп­лекс-таблице строку, содержащую строку со значениями λ_j, которые вычисляются на этапе определения столбца, вводимо­го в базис.

2.3. Особенности применения двойственного симп­лекс-метода.

Алгоритм двойственного симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исход­ного сопряженного базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей, сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев исходный псевдоплан может быть опре­делен достаточно легко.

Рассмотрим задачу минимизации:

при обмеженнях

где

Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные х_n+1, х_n+2, ... , х_n+m:

Задача, двойственная к (1.70)—(1.72), будет иметь вид:

Из (1.74)-(1.75) очевиден допустимый план двойственной задачи

и исходный сопряженный базис, образуемый векторами аⁿ⁺¹, аⁿ⁺², …., а^n+m. При этом начальный псевдоплан равен

Таким образом, при решении задачи вида (1.66)-(1.68) двой­ственный симплекс-метод имеет несомненные преимущества по сравнению с прямым.

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

• изменение компонент вектора ограничений b, что, допу­стим, может быть интерпретировано как корректиров­ка объемов доступных ресурсов в процессе управления экономическим объектом;

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

В первом случае, т. е. при изменении вектора b, достоинства двойственного симплекс-метода очевидны, так как ранее найден­ный оптимальный базис можно использовать в качестве исход­ного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотре­нии методов решения целочисленных задач.

В заключение отметим, что в настоящем параграфе был рас­смотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что су­ществует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных мат­риц), но, поскольку этот вопрос представляет интерес в основ­ном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознако­миться в [1]. Отметим лишь, что она обладает теми же прин­ципиальными преимуществами, что и модифицированный симп­лекс-метод.