Теоремы двойственности

Теорема 1 двойственности

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

Доказательство

Из определения функции и неравенств (11),(12) вытекает, что

Из (12) следует . Следовательно - точка наименьшего значения.

Для выпуклости вверх надо показать

т.к. -линейна.

Надо доказать что - выпуклая

Доказательство

Т.к. , то . Получаем, что если взять промежуточную точку , то

Переходя к определению

Т.е выпукла вверх.

выпукла вниз.

Теорема 2 двойственности

Функция имеет седловую точку тогда и только тогда, когда для

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