ЛЕКЦИЯ №6

1.14.1 Двойственная злп и двойственный симплекс-метод

Для каждой ЗЛП (прямой (исходной) задачи) может быть сформирована соответствующая ей двойственная по следующим правилам:

1. Каждому i-ому ограничению прямой задачи в двойственной задаче ставится в соответствие двойственная оптимизационная переменная u[i]. При этом каждому ограничению типа “ “ соответствует , а ограничению типа “ = ” – свободная u[i].

2. Каждой j-ой оптимизационной переменной в исходной задаче ставится в соответствие j-ое ограничение в двойственной задаче. При этом, если в прямой задаче , то в двойственной формируется ограничение типа неравенства:

.

Если же - свободная, то в двойственной задаче формируется ограничение типа равенства:

.

3. При направлении оптимизации в исходной задачи на 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. Из ограничений задачи (1.96) выбрать некоторые m, представить их в виде равенств (необходимо, чтобы равенства были линейно независимые) и решить систему m линейных уравнений относительно m неизвестных.

2. Подставить найденное решение во все остальные ограничения. Если они будут выполняться, то найденное в п.1 решение является допустимым базисным решением двойственной задачи.

При выполнении п.1 (при формировании системы уравнений относительно двойственных переменных) фактически выбирается базис прямой задачи (1.7), формируются соответствующая базисная матрица B и вектор c(B):

. (1.97)

Из (1.97) следует, что

. (1.98)

Необходимо обратить внимание, что в последней строке симплекс-таблицы T₂(B_k) (см. 1.38) находятся базисные значения двойственных переменных, взятые с противоположным знаком: ( ), т.е. .

Здесь мы подошли к очень важному понятию двойственности в линейном программировании - понятию сопряженного базиса прямой задачи.

Сопряженным базисом исходной задачи B^* называют такой ее базис, который определяет допустимое базисное решение двойственной задачи ( ).

Формальным условием сопряженности базиса исходной задачи (1.95) является неположительность ее строки симплекс-разностей.

Действительно

.

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

, -

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

И еще одно новое понятие. Базисное решение исходной задачи, соответствующее сопряженному базису, называют псевдопланом.

Использование термина «псевдоплан» станет понятным из рассмотрения следующего раздела.