Студопедия — Теоремы двойственности
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






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

Теорема 1. Если в оптимальном решении прямой задачи условие выполняется как строгое неравенство , то соответствующая двойственная переменная равна нулю, то есть Обоснование: Неравенство означает, что i- й ресурс используется не полностью, следовательно, малое изменение этого ресурса не повлияет на результат деятельности (критерий) и поэтому значение двойственной переменной равно нулю.

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

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

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

На рис. приведена геометрическая интерпретация рассмотренных теорем для случая единственного оптимального решения (вершина А). Множество D образовано четырьмя условиями- неравенствами с ресурсами b 1, b 2, b 3 и b4. В оптимальном решении по 1-му и 2-му ресурсам выполняется равенство и изменение любого из них (показано пунктиром для b 1)приводит к перемещению оптимальной вершины и, следовательно, критерия. Поэтому значимость этих ресурсов или их двойственные переменные отличны от нуля. В то же время по 3-му и 4-му ресурсам имеем строгие неравенства и их изменения не влияют на оптимальное значение критерия, что соответствует нулевым дополнительным переменным.

Случай с неединственным оптимальным решением: Линия оптимального значения критерия L* совпадает с границей по 2-му ресурсу. В оптимальном решении, соответствующем вершине А, первые два ресурса используются полностью. Однако изменение b 1 не приводит к изменению критерия, тогда как любое изменение b 2 отражается на оптимальном значении критерия. Поэтому оценки этих ресурсов разные: U 1 = 0, U 2¹0.

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

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

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

Пример

ПЗ L =7 x 1+5 x 2→max, 2 x 1+3 x 2£19, 2 x 1+ x 2£13, 3 x 2£12, 3 x 1£17, x 1³0, x 2³0 Кан. форма ПЗ L =7 x 1+5 x 2→max, 2 x 1+3 x 2+ x 3=19, 2 x 1+ x 2+ x 4=13, 3 x 2+ x 5=12, 3 x 1+ x 6=17, " xj ³0.   Оптимальное решение ДЗ =19 U 1+13 U 2+12 U 3+17 U 4®min 2 U 1+2 U 2+3 U 4³7 3 U 1+ U 2+3 U 3³5 " Ui ³0

Получим решение ДЗ на основе решения ПЗ и теорем двойственности.

Тк дополнительные переменные х5 и х6, входящие в 3 и 4 условия ПЗ, в оптимальном решении не равны нулю, то согласно следствию теоремы 1 .

Из первой группы условий следует, что если исходная переменная ПЗ не равна нулю, то ограничение ДЗ будет выполняться как равенство. Поэтому:

Получили систему 2-х уравнений с двумя неизвестными. Ее решение:

 

.

Т.о, мы нашли решение ДЗ без применения симплекс-метода. Пример демонстрирует связь решений двойственной пары задач, а значения двойственных переменных легко получить из оптимальной симплекс-таблицы ПЗ. Они расположены в вспомогательной строке Z в столбцах начального базиса.

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

из которой следует справедливость теоремы.

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

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

Аналогично доказывается оптимальность U * для двойственной задачи.

Теорема 5. Для любых оптимальных X * и U * линейные формы прямой и двойственной задач равны: L (X *)= (U *). Доказательство. В оптимальных решениях выполняются равенства т 3. Суммируя первую группу по j, а вторую по i:

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

Теорема 6. Если линейная форма одной из задач двойственной пары не ограничена, то условия другой противоречивы. (Обратное не всегда верно, возможна противоречивость в обеих задачах). Доказательство противного. Допустим, что при неограниченности L (x) сверху в прямой задаче условия двойственной задачи непротиворечивы. Тогда существует допустимое решение ДЗ, на котором. значение ее критерия конечно. Но согласно теореме 3 для допустимых решений должно выполняться неравенство L (x (U), что при принятом допущении невозможно (L бесконечно, а конечно). Следовательно, ДЗ не может иметь допустимых решений, то есть ее условия противоречивы. Аналогично доказывается 2-я часть теоремы для случая неограниченности снизу .

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








Дата добавления: 2015-04-19; просмотров: 821. Нарушение авторских прав; Мы поможем в написании вашей работы!



Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Конституционно-правовые нормы, их особенности и виды Характеристика отрасли права немыслима без уяснения особенностей составляющих ее норм...

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

Стресс-лимитирующие факторы Поскольку в каждом реализующем факторе общего адаптацион­ного синдрома при бесконтрольном его развитии заложена потенци­альная опасность появления патогенных преобразований...

ТЕОРИЯ ЗАЩИТНЫХ МЕХАНИЗМОВ ЛИЧНОСТИ В современной психологической литературе встречаются различные термины, касающиеся феноменов защиты...

Этические проблемы проведения экспериментов на человеке и животных В настоящее время четко определены новые подходы и требования к биомедицинским исследованиям...

Studopedia.info - Студопедия - 2014-2024 год . (0.014 сек.) русская версия | украинская версия