Лекция: Теоремы двойственности.
Рассмотрим стандартную задачу ЛП и двойственную к ней:
Таблица 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)