ЛЕКЦИЯ №6
1.14.1 Двойственная злп и двойственный симплекс-метод
Для каждой ЗЛП (прямой (исходной) задачи) может быть сформирована соответствующая ей двойственная по следующим правилам:
Каждому i-ому ограничению прямой задачи в двойственной задаче ставится в соответствие двойственная оптимизационная переменная u[i]. При этом каждому ограничению типа “ “ соответствует , а ограничению типа “ = ” – свободная u[i].
Каждой j-ой оптимизационной переменной в исходной задаче ставится в соответствие j-ое ограничение в двойственной задаче. При этом, если в прямой задаче , то в двойственной формируется ограничение типа неравенства:
.
Если же - свободная, то в двойственной задаче формируется ограничение типа равенства:
.
При направлении оптимизации в исходной задачи на max , в двойственной задаче критерий оптимизации формируется следующим образом:
Двойственная задача является задачей линейного программирования. Можно сказать, что двойственная задача является как бы “транспонированной” по отношению к прямой задаче (см. рис. 1.24).
Нетрудно убедиться, что двойственная ЗЛП по отношению к двойственной ЗЛП является прямой (исходной) задачей.
Рассмотрим прямую задачу в канонической форме:
, . (1.95)
Соответствующая ей двойственная задача, сформированная по указанным выше правилам, будет иметь следующий вид:
, , (1.96)
где - m-мерная вектор-строка двойственных переменных.
Приведем рассуждения, показывающие, что базисное допустимое решение двойственной задачи (1.96) можно формировать так же, как и базисное решение исходной задачи (1.95) путем выбора системы m линейно независимых столбцов матрицы условий А исходной задачи.
Очевидно, что число ограничений типа неравенств в задаче (1.96) будет не меньше, а скорее больше числа переменных (n≥m, см. 1.7), причем все они являются неравенствами. На основе определения крайних точек допустимого базисного множества (см. 1.5.1) и соответствующего ему допустимого базисного решения можно сформировать следующее правило нахождения допустимого базисного решения двойственной задачи (1.96):
Из ограничений задачи (1.96) выбрать некоторые m, представить их в виде равенств (необходимо, чтобы равенства были линейно независимые) и решить систему m линейных уравнений относительно m неизвестных.
Подставить найденное решение во все остальные ограничения. Если они будут выполняться, то найденное в п.1 решение является допустимым базисным решением двойственной задачи.
При выполнении п.1 (при формировании системы уравнений относительно двойственных переменных) фактически выбирается базис прямой задачи (1.7), формируются соответствующая базисная матрица B и вектор c(B):
. (1.97)
Из (1.97) следует, что
. (1.98)
Необходимо обратить внимание, что в последней строке симплекс-таблицы T2(Bk) (см. 1.38) находятся базисные значения двойственных переменных, взятые с противоположным знаком: ( ), т.е. .
Здесь мы подошли к очень важному понятию двойственности в линейном программировании - понятию сопряженного базиса прямой задачи.
Сопряженным базисом исходной задачи B* называют такой ее базис, который определяет допустимое базисное решение двойственной задачи ( ).
Формальным условием сопряженности базиса исходной задачи (1.95) является неположительность ее строки симплекс-разностей.
Действительно
.
Таким образом, видим, что строка симплекс-разностей исходной задачи, вычисленная для выбранного базиса, определяется как разность правой и левой частей ограничения двойственной задачи для ее базисного решения:
, -
и из условия допустимости базисного решения для двойственной задачи следует условие неположительности строки симплекс разностей ( ) и наоборот: если базис выбран так, что ему соответствует неположительная строка симплекс-разностей, то базис является сопряженным .
И еще одно новое понятие. Базисное решение исходной задачи, соответствующее сопряженному базису, называют псевдопланом.
Использование термина «псевдоплан» станет понятным из рассмотрения следующего раздела.