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

Рассмотрим стандартную задачу ЛП и двойственную к ней:

Таблица 37.1

Прямая задача (I)	Двойственная ей задача (II)
……………………… ………	……… ……………………………..

Пара двойственных задач (I) и (II) называется парой симметрических двойственных задач.

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

Рассмотрим пару симметрических двойственных задач в матричной форме записи.

Таблица 37.2.

Прямая задача (I)	Двойственная ей задача (II)

Здесь , , , ,

- матрица из строк и столбцов, - транспонированная матрица. Введем обозначения для допустимых областей задачи (I) и (II).

,

Основное неравенство двойственности: для любых допустимых решений прямой задачи и для любых допустимых решений двойственной задачи выполняется неравенство .

Следствие (достаточное условие оптимальности): если для некоторых допустимых решений и выполняется равенство значений целевых функций , то , - оптимальные решения задачи (I) и (II) соответственно.

Первая теорема двойственности: е сли одна из пары двойственных задач (I) и (II) разрешима, то разрешима и другая задача, причем оптимальные значения целевых функций прямой и двойственной задач совпадают.

, (37.1)

где , оптимальные планы задач (I) и (II) соответственно.

Вторая теорема двойственности: чтобы допустимые решения , пары двойственных задач (I) и (II) были оптимальными необходимо и достаточно, чтобы выполнялись условия:

1) , (37.2)

2) . (37.3)