Для любых допустимых решений Х=(хь x2,..., хn) и Y =(y1, y2,…,ym) исходной и двойственной задач справедливо неравенство:
Теорема. (Достаточный признак оптимальности)
Если X*=(x*1,x*2,...,x*n) и У*=(y*1,y*2,-..,y*m) — допустимые решения взаимодвойственных задач, для которых выполняется равенство: F(X*)=Z(Y*),
то X* — оптимальное решение исходной задачи, а Y* — оптимальное решение двойственной.
Возникает вопрос: всегда ли для каждой пары взаимодвойственных задач одновременно существуют оптимальные решения, возможна ли, например, ситуация, когда одна из двойственных задач имеет решение, а другая нет? Ответ на этот вопрос дает следующая теорема.
Первая (основная) теорема двойственности
Если одна из взаимодвойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: Fmax(X) = Zmin(X) F(X*)=Z(Y*).
Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.
Замечание. Утверждение, обратное по отношению ко второй части основной теоремы двойственности, в общем случае неверно, т.е. из того, что условия исходной задачи противоречивы, не следует, что линейная функция не ограничена.
Достарыңызбен бөлісу: |
