![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теоремы двойственности
Между решениями прямой и двойственной задач существует тесная взаимосвязь, которая устанавливается теоремами двойственности. Эта связь позволяет по решению одной задачи двойственной пары получать решение другой. Теорема 1. Если в оптимальном решении прямой задачи условие выполняется как строгое неравенство то соответствующая двойственная переменная равна нулю, то есть Обоснование следует из смысла двойственных переменных. Малое изменение ресурса не повлияет на критерий. Следствие. Если дополнительная переменная в i-м условии прямой задачи больше нуля, то соответствующая двойственная переменная равна нулю. В этом случае i-е условие без дополнительной переменной будет заведомо строгим неравенством, что и оговорено в теореме. Теорема 2. Если в единственном оптимальном решении прямой задачи условие выполняется как равенство, то есть Равенство (33) означает, что i-й ресурс полностью исчерпан, следовательно, малые изменения этого ресурса обязательно приведут к изменению критерия и поэтому его значимость не равна нулю. Следствие. Если дополнительная переменная в i-м условии равна нулю, то двойственная переменная этого условия не равна нулю.
Теорема 1'. Если в оптимальном решении двойственной задачи условие выполняется как строгое неравенство Теорема 2' Если в единственном оптимальном решении двойственной задачи условие выполняется как равенство, то соответствующая переменная прямой задачи строго больше нуля: Обобщением рассмотренных теорем является вторая основная теорема двойственности: Для того чтобы векторы X* и U* являлись оптимальными решениями прямой и двойственной задач соответственно, необходимо и достаточно выполнение следующих условий:
Теорема 3. Если X и U – допустимые решения прямой и двойственной задач соответственно, то L(X) £ Доказательство. Так как допустимость решений означает выполнение неравенств Теорема 4. Если X* и U* - допустимые решения прямой и двойственной задач и L(X*)= Доказательство. Согласно теореме 3 L(X)£ Теорема 5. Для любых оптимальных X* и U* линейные формы прямой и двойственной задач равны: L(X*)= Доказательство. В оптимальных решениях выполняются равенства (36). Суммируя первую группу по j, а вторую по i
Теорема 6. Если критерий одной из задач двойственной пары не ограничен, то условия другой противоречивы. (Обратное не всегда верно). Доказательство проведем от противного. Допустим, что при неограниченности L(x) сверху в прямой задаче условия двойственной задачи непротиворечивы. Тогда существует допустимое решение ДЗ, на котором. значение ее критерия конечно. Но согласно теореме L(x)£ Первая основная теорема двойственности: Если одна из задач двойственной пары разрешима, то и другая задача разрешима, при этом оптимальные значения критериев равны; при неразрешимости одной из задач другая тоже неразрешима.
|