Понятие двойственности.
Математическая модель задачи:
(1)
(2)
(3)
Двойственная задача: 
(4)
(5)
По смыслу задачи оценки не должны быть отрицательными:
(6)
Переменные 
называют двойственными оценками или объективно обусловленными оценками.
Задачи (1)-(3) и (4)-(6) называют парой взаимно двойственных ЗПЛ.
Между прямой и двойственной задачами можно установить следующую взаимосвязь:
1. Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.
2. Коэффициенты 
целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.
3. Свободные члены 
ограничений прямой задачи являются коэффициентами целевой функции двойственной.
4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа 
. Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа 
.
6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной — числу переменных прямой.
7. Все переменные в обеих задачах неотрицательны.
Теорема. Для любых допустимых планов 
и 
прямой и двойственной ЗЛП справедливо неравенство 
, т.е.
(7) – основное неравенство теории двойственности.
Теорема. (критерий оптимальности Канторовича)
Если для некоторых допустимых планов 
и 
пары двойственных задач выполняется неравенство 
, то и являются оптимальными планами соответствующих задач.
|
|
|
Теорема. (малая теорема двойственности)
Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.
Дата добавления: 2015-12-17; просмотров: 16; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!