2.6.1. Вычислительные формы двойственной задачи

При решении задачи НЛП часто важно знать, имеет ли место двойственное равенство. Допустим, мы пользуемся алгоритмом, который вычисляет как допустимые прямой задачи, так и допустимые точки двойственной задачи. При этом алгоритм составлен так, что вычисления прекращаются, как только достигнуты для которых Согласно теореме 2.18 мы тогда очень близки к оптимальной точке. Условие останова имеет смысл, если существует двойственное равенство. Однако в противном случае возможно, что

и условие останова никогда не будет удовлетворено.

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

В общей форме двойственная задача заключается в нахождении

Или в более детальной формулировке: найти

при

Вогнутая двойственная задача. Допустим, что и все функции вогнуты.

Тогда равенство справедливо в том и только в том случае, если имеет место .

В этом случае мы получаем задачу, двойственную к задаче НЛП с вогнутой целевой функцией и вогнутыми ограничениями. Найти

при

Двойственная задача Л П. Частным случаем вогнутой двойственной задачи является двойственная задача линейного программирования Пусть задача НЛП заключается в том, чтобы найти при Вогнутая двойственная задача имеет вид: найти при

Однако из следует

Тогда вогнутая двойственная задача сводится к обычной двойственной задаче найти при