Прямая и двойственная задачи. Теоремы двойственности. Экономическая интерпретация двойственных задач

Пусть имеем задачу в стандартном виде на максимум

, или, в векторной форме: . (4.4)

Используя ее коэффициенты, построим задачу на минимум следующего вида:

, или, в векторной форме: , (4.5)

где - вспомогательные переменные (множители Лагранжа – см. далее).

Такие задачи называются взаимно двойственными. Одну из них (первую или вторую) можно назвать прямой задачей, а другую – двойственной к ней. Механизм построения двойственной задачи очень прост. Выписываем прямую задачу, например (4.4), и к каждому функциональному ограничению приписываем слева переменные

.

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

Если прямой считать задачу вида (4.5), то слева от функциональных ограничений выписываются переменные

,

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

Применяя положения и выводы теории нелинейного программирования к задачам вида (4.4) или (4.5) (как упоминалось выше, это правомерно), заметим следующее:

1⁰ Если допустимое множество содержит внутреннюю точку[1], то, очевидно выполняются условия Слейтера, а значит, условия Куна-Таккера являются необходимыми для наличия в точке локального максимума – для задачи (4.4) (минимума – для задачи (4.5)).

2⁰ Поскольку все функции, образующие ограничения, линейны (а значит, и выпуклы) и целевая функция тоже линейна (а, значит, и вогнута), то условия Куна-Таккера являются также и достаточными для наличия в точке глобального максимума – для задачи (4.4) (минимума – для задачи (4.5)).

Выпишем функции Лагранжа для прямой и двойственной задачи. При этом вместо привычного обозначения множителей Лагранжа () для задачи вида (4.4) будем использовать обозначение , а для задачи вида (4.2) – обозначение . Итак, для задачи вида (4.5) имеем:

, (4.6)

а для задачи вида (2):

. (4.7)

Нетрудно видеть, что для любых значений переменных и значения функций Лагранжа (4.6) и (4.7) совпадают. Действительно,

. (4.8)

Таким образом, множители Лагранжа для задачи (4.4) являются инструментальными переменными задачи (4.5), а инструментальные переменные задачи (4.4) являются множителями Лагранжа задачи (4.5), и наоборот.

Нетрудно видеть, что условия Куна-Таккера для задач (4.4) и (4.5) совпадают и имеют вид: .

Нетрудно видеть, что для любых допустимых точек значение целевой функции задачи (4.4) всегда не больше, чем значение целевой функции задачи (4.5). Действительно, так как для допустимых точек имеют место неравенства и , то и , а так как правые части этих неравенств совпадают – см. (4.8), то

, (4.9)

причем значения в левой и правой частях неравенства (4.9) совпадают лишь в тех допустимых точках, в которых выполняются условия дополняющей нежесткости:

. (4.10)

Из того факта, что условия Куна-Таккера прямой и двойственной задач совпадают, а сами условия являются необходимыми и достаточными для наличия глобального оптимума, вытекают так называемые теоремы двойственности.

Поиск по сайту: