1.6. Двойственный симплекс-метод
В экономических приложениях часто встречаются задачи, отличающиеся свободными членами и (или) коэффициентами целевой функции. В таких случаях бывает удобно использовать базис, соответствующий оптимальному плану одной из задач, в качестве начального базиса для другой задачи. В частности, двойственные оценки для второй задачи могут оставаться неотрицательными, в то время как соответствующий базисный план может быть уже недопустимым.
В качестве примера рассмотрим следующую ЗЛП:
Приведем ее к каноническому виду, введя дополнительные переменные х3, х4, х5 0.
Для того чтобы получить единичный базис, умножим второе и третье структурное ограничение на (-1). Тогда ЗЛП преобразуется к виду:
Векторы А3, А4, А5 образуют единичный базис этой ЗЛП. Ее частным решением будет вектор х0 = (0; 0; 21; -3; -2). Этот вектор не является БДП, поскольку две координаты отрицательные, однако при этом все двойственные оценки неотрицательны, т.е. с другой стороны выполнен признак оптимальности плана. Для решения таких задач применяется алгоритм двойственного симплекс-метода.
Таким образом, двойственный симплекс-метод используется в ситуациях, когда в ЗЛП существует базисное решение (план), которому соответствуют неотрицательные двойственные оценки.
Определение 16. Решение системы линейных уравнений (1.63) , соответствующее базису А , называется псевдопланом или почти допустимым базисным решением (ПДБР), если все двойственные оценки неотрицательны (j , ), а среди координат плана существует, по крайней мере, одна отрицательная координата (xk0 < 0, k).
Здесь . Итак, двойственный симплекс-метод применяется тогда, когда в ЗЛП имеется псевдоплан.
В рассмотренной выше ЗЛП вектор х0 = (0; 0; 21; -3; -2) представляет собой псевдоплан. Чаще всего псевдоплан появляется в задачах, в которых
Ограничения имеют вид Ах b.
Коэффициенты целевой функции сj 0, и при этом C(х) min.
В ЗЛП вводится существенное или активное ограничение, т.е. такое ограничение, которое изменяет оптимальный план в первоначально заданном множестве допустимых планов.
Теорема 1.9. Признак оптимальности псевдоплана.
Пусть х* = (х*1 ,…, х*n) – псевдоплан, в котором , тогда х* – оптимальный план.
Доказательство. Так как х* псевдоплан, то ему соответствует некоторый базис. Поскольку по условию теоремы , то х* – БДП. Из определения псевдоплана следует, что . При этом попадаем в условия теоремы «Признак оптимальности БДП» (п. 1.4.2). Таким образом, х* – оптимальный план.
1.6.1. Алгоритм двойственного симплекс-метода
Рассмотрим ЗЛП:
(1.67)
Пусть в данной задаче (1.67) имеется псевдоплан х0. Наличие псевдоплана предполагает, что на текущей итерации мы имеем систему ограничений вида
(1.68)
В (1.68) все координаты xk0 не определены по знаку, т.е. могут быть как положительными, так и отрицательными. При этом в ЗЛП (1.67) все оценки .
Переход к новому псевдоплану осуществляется по двум правилам.
Правило 1. Определение номера вектора, выводимого из базиса.
Из базиса выводится вектор Аr, у которого номер r определяется из соотношения:
.
Вообще говоря, если отрицательных компонент несколько, то можно выбрать любую и выводить соответствующий вектор, но это может увеличить число итераций.
Правило 2. Определение номера вектора, вводимого в базис.
Номер вектора s, вводимого в базис, выбирается из отношений двойственных оценок к отрицательным элементам r-ой строки симплекс-таблицы, а именно из условия:
.
В этом случае ведущим элементом будет , а все элементы симплексной таблицы пересчитываются по формулам, идентичным формулам в симплекс-методе. Воспользовавшись фрагментом симплекс-таблицы (табл. 1.8), запишем формулы пересчета ее элементов.
Таблица 1.8.