[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4]

Теоремы двойственности.

Теорема.
Если X* = (х*1,х*2,...,х*n) и Y* =(у*1, у*2,...,у*m) - допустимые решения взаимно двойственных задач, для которых выполняется равенство F(X*) = Z(Y*),        (6.10) то X* - оптимальное решение исходной задачи I, а У* - двойственной задачи II.

Первая (основная) теорема двойственности.
Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: Fmax = Zmin или F(X*) = Z(Y*) Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.

Теорема.
Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2, ..., m u j = 1, 2, ..., n: если x*j > 0, то y*m+j = 0 для исходных переменных прямой задачи если x*n+i > 0, то у*i = 0 - для дополнительных, и аналогично, если у*i > 0, то х*n+i = 0; если y*m+j > 0, то х*j = 0.

Из теоремы следует важный вывод о том, что введенное ранее соответствие между переменными взаимно двойственных задач при достижении оптимума (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения.
Рассмотренная теорема является следствием следующей теоремы.

Вторая теорема двойственности.
Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные ее оптимального решения.

Соответствие переменных

Переменные исходной задачи
Первоначальные	Выравнивающие
Выравнивающие	Первоначальные
Переменные двойственной задачи

Замечание.
Если в одной из взаимно двойственных задач нарушается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное.

Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплексным методом. Этот метод бывает выгодно применять, когда первое базисное решение исходной задачи недопустимое или, например, когда число ее ограничений m больше числа переменных n.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [В начало страницы]