Двойственная задача
min 
(
) = y 0+ b 1 y 1+ b 2 y 2,
a 11 y 1+ a 12 y 2 
c 1,
a 12 y 1+ a 22 y 2 c 2,
a 13 y 1+ a 23 y 2 c 3,
y 1 0, y 2 0.
В качестве исходной задачи в приведенной паре взаимно двойственных задач можно принимать и задачу на min: исходная задача – min f (
) и « », двойственная задача – max () и « 
».
Связь между оптимальными планами 2-х двойственных задач устанавливают теоремы двойственности.
Теорема 1. (основная теорема двойственности). Если одна из двойственных задач разрешима, то разрешима и другая, причем экстремальные значении целевых функций задач равны: max f () = min (). Если одна из двойственных задач неразрешима, то неразрешима и другая.
Теорема 2. (о дополняющей нежесткости). Если при подстановке координат (компонент) оптимального плана в систему ограничений исходной задачи i -е ограничение обращается в неравенство, то i -я координата оптимального плана двойственной задачи равна нулю. Если i -я координата оптимального плана исходной задачи положительна, то i -е ограничение двойственной задачи удовлетворяется ее оптимальным решением как строгое равенство.
Т.о. для оптимальных планов двойственных задач имеют место соотношения:
y * i (
aijx * j – bi) = 0: если 
aijx * j <bi, то y * i = 0,
x * j (
aijy*i – cj) = 0: если x*j >0, то 
aijy*i – cj = 0,
где x * j и y * i – соответствующие оптимальные значения исходной и двойственной к ней задаче.
Справедливы утверждения и в другом порядке: из двойственной задачи получают решение исходной задачи.
|
|
|
Покажем решение двойственных задач и анализ процесса на примере.
Дата добавления: 2015-12-17; просмотров: 16; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!