 |
 |
 |
 |
|
 |
 |
41
Из (1.74)-(1.75) очевиден допустимый план двойственной задачи
и исходный сопряженный базис, образуемый векторами а
n+1
,
а
n+2
,
…., а
n+m
. При этом начальный
псевдоплан равен
Таким образом, при решении задачи вида (1.66)-(1.68) двойственный симплекс-метод имеет
несомненные преимущества по сравнению с прямым.
Другое важное направление использования двойственного симплекс-метода связано с поиском
оптимальных планов в тех задачах, условия которых претерпели некоторые изменения после того, как
они уже были решены с помощью стандартной симплекс-процедуры. Типичными примерами таких
изменений являются:
изменение компонент вектора ограничений b, что, допустим, может быть интерпретировано
как
корректировка объемов доступных ресурсов в процессе управления экономическим
объектом;
добавление новых ограничений к системе условий задачи, что достаточно часто случается при
совершенствовании используемой экономико-математической модели.
В первом случае, т. е. при изменении вектора b, достоинства двойственного симплекс-метода
очевидны, так как ранее найденный оптимальный базис можно использовать в качестве исходного
сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл.
4 при рассмотрении методов решения целочисленных задач.
В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного
алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что существует и
вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием
обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники
организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным
описанием данной версии алгоритма можно ознакомиться в [1]. Отметим лишь, что она обладает теми
же принципиальными преимуществами, что и модифицированный симплекс-метод.
1.7.4. Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном,
примере процесс решения КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к
задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе
ограничений b в результате которых
Содержание исходной симплекс-таблицы T
(1)
(за исключением столбца b(?
(1)
)) будет идентично
содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для
вычисления значений b(?
(1)
) в данном случае можно воспользоваться обратной матрицей, полученной
на последней итерации в п. 1.5.2: