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

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

Теорема 1. Если в оптимальном решении прямой задачи условие выполняется как строгое неравенство , (32)

то соответствующая двойственная переменная равна нулю, то есть

Обоснование следует из смысла двойственных переменных. Малое изменение ресурса не повлияет на критерий.

Следствие. Если дополнительная переменная в i-м условии прямой задачи больше нуля, то соответствующая двойственная переменная равна нулю. В этом случае i-е условие без дополнительной переменной будет заведомо строгим неравенством, что и оговорено в теореме.

Теорема 2. Если в единственном оптимальном решении прямой задачи условие выполняется как равенство, то есть (33) то соответствующая двойственная переменная будет заведомо не равна нулю.

Равенство (33) означает, что i-й ресурс полностью исчерпан, следовательно, малые изменения этого ресурса обязательно приведут к изменению критерия и поэтому его значимость не равна нулю.

Следствие. Если дополнительная переменная в i-м условии равна нулю, то двойственная переменная этого условия не равна нулю.

Теорема 1'. Если в оптимальном решении двойственной задачи условие выполняется как строгое неравенство (34) то соответствующая переменная прямой задачи равна нулю: Интерпретация: если затраты превышают производимую стоимость, то производить такую продукцию невыгодно.

Теорема 2' Если в единственном оптимальном решении двойственной задачи условие выполняется как равенство, то соответствующая переменная прямой задачи строго больше нуля: .(35) Так как производимая стоимость равна затратам, то производство такой продукции окупается.

Обобщением рассмотренных теорем является вторая основная теорема двойственности: Для того чтобы векторы X* и U* являлись оптимальными решениями прямой и двойственной задач соответственно, необходимо и достаточно выполнение следующих условий:

(36)

Теорема 3. Если X и U – допустимые решения прямой и двойственной задач соответственно, то L(X) £ (U).(37)

Доказательство. Так как допустимость решений означает выполнение неравенств в ПЗ и в ДЗ, то

Теорема 4. Если X* и U* - допустимые решения прямой и двойственной задач и L(X*)= (U*), то они являются оптимальными решениями двойственной пары задач.

Доказательство. Согласно теореме 3 L(X)£ (U*). И так как L(X*)= (U*) по условию теоремы, то L(X)£ L(X*). Следовательно, X*- оптимальное решение прямой задачи по определению. Аналогично доказывается оптимальность U* для двойственной задачи.

Теорема 5. Для любых оптимальных X* и U* линейные формы прямой и двойственной задач равны: L(X*)= (U*). (38)

Доказательство. В оптимальных решениях выполняются равенства (36). Суммируя первую группу по j, а вторую по i

Из равенства левых частей следует равенство правых и, значит, справедливость теоремы.

Теорема 6. Если критерий одной из задач двойственной пары не ограничен, то условия другой противоречивы. (Обратное не всегда верно).

Доказательство проведем от противного. Допустим, что при неограниченности L(x) сверху в прямой задаче условия двойственной задачи непротиворечивы. Тогда существует допустимое решение ДЗ, на котором. значение ее критерия конечно. Но согласно теореме L(x)£ (U), что при принятом допущении невозможно (L бесконечно, а конечно).

Первая основная теорема двойственности:

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