Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

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

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

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

при ограничениях

где

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

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

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

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

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

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

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

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

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

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