Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Рассмотрим стандартную задачу ЛП и двойственную к ней:
Таблица 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)
Дата публикования: 2015-01-26; Прочитано: 321 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!