Лекция 4. Теория двойственности Содержание лекции: 1. Двойственная задача линейного программирования Двойственная задача линейного программирования Двойственная. - презентация

1 Лекция 4. Теория двойственности Содержание лекции: 1. Двойственная задача линейного программирования Двойственная задача линейного программирования Двойственная задача линейного программирования 2. Теоремы двойственности Теоремы двойственности Теоремы двойственности 3. Двойственные оценки в планировании и экономическом анализе Двойственные оценки в планировании и экономическом анализе Двойственные оценки в планировании и экономическом анализе

2 Литература Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. 2-е изд. М.: ЮНИТИ-ДАНА, раздел 3.1. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. 2-е изд. М.: ЮНИТИ-ДАНА, раздел 3.1. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: Изд-во АН СССР, Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: Изд-во АН СССР, / 17 Теория двойственности © Н.М. Светлов, 2007

3 4.1. Двойственная задача линейного программирования Пусть дана задача Если не требовать b i 0, то эту задачу всегда можно переписать в форме 3/ 17 Теория двойственности © Н.М. Светлов, 2007

4 4.1. Исходная (прямая) задача Двойственная задача Интересное свойство (пока только одно) : если ЦФ прямой задачи достигает оптимального значения z, то ЦФ двойственной задачи достигает того же самого оптимального значения z. 4/ 17 Теория двойственности © Н.М. Светлов, 2007

5 4.1. Исходная (прямая) задача Двойственная задача Отличие 1: другие переменные Отличие 1: другие переменные (называемые двойственными переменными) 5/ 17 Теория двойственности © Н.М. Светлов, 2007

6 4.1. Исходная (прямая) задача Двойственная задача Отличие 2: задача решается на минимум ЦФ Отличие 2: задача решается на минимум ЦФ 6/ 17 Теория двойственности © Н.М. Светлов, 2007

7 4.1. Исходная (прямая) задача Двойственная задача Отличие 3: c i и b j меняются местами Отличие 3: c i и b j меняются местами 7/ 17 Теория двойственности © Н.М. Светлов, 2007

8 4.1. Исходная (прямая) задача Двойственная задача Отличие 4: тип ограничений - Отличие 4: тип ограничений - (впоследствии можно изменить, чтобы свободные члены стали неотрицательными) 8/ 17 Теория двойственности © Н.М. Светлов, 2007

9 4.1. Исходная (прямая) задача Двойственная задача Отличие 5: на место параметра a ij подставляется параметр a ji. Отличие 5: на место параметра a ij подставляется параметр a ji. 9/ 17 Теория двойственности © Н.М. Светлов, 2007

10 4.1. Исходная (прямая) задача Двойственная задача 10/ 17 Теория двойственности © Н.М. Светлов, 2007

11 4.1. Исходная (прямая) задача Двойственная задача Пусть ограничения обозначают ресурсы, а переменные – интенсивность технологических процессов Тогда ограничения двойственной задачи представляют собой условия невозможности увеличения прибыли за счёт использования технологического процесса, целевая функция отражает требование минимизации затрат на ресурсы, используемые для выполнения плана прямой задачи, а переменные соответствуют ценам, при которых выполняются вышеназванные требования. 11/ 17 Теория двойственности © Н.М. Светлов, 2007

12 4.1. Второе интересное свойство двойственной задачи Решая прямую задачу, мы заодно необходимо получаем решение двойственной задачи Решая прямую задачу, мы заодно необходимо получаем решение двойственной задачи (в верхней строке заключительной симплексной таблицы и столбцах, соответствующих дополнительным переменным) Отыскание оптимума невозможно без отыскания цен ресурсов, при которых выполняются условия двойственной задачи. Отыскание оптимума невозможно без отыскания цен ресурсов, при которых выполняются условия двойственной задачи. Эти цены называются ценами оптимального плана или двойственными оценками ограничений прямой задачи. Любая попытка тем или иным способом найти оптимальное (по какому-нибудь критерию) распределение ресурсов требует установления или расчёта их цен. Любая попытка тем или иным способом найти оптимальное (по какому-нибудь критерию) распределение ресурсов требует установления или расчёта их цен. 12/ 17 Теория двойственности © Н.М. Светлов, 2007

13 4.1. Третье интересное свойство двойственной задачи Если мы построим двойственную задачу к двойственной задаче, то получим исходную (прямую) задачу. Если мы построим двойственную задачу к двойственной задаче, то получим исходную (прямую) задачу. Как следствие, двойственные оценки ограничений двойственной задачи равны соответствующим переменным прямой задачи. Как следствие, двойственные оценки ограничений двойственной задачи равны соответствующим переменным прямой задачи. Интересно, что свойства двойственности мы уже наблюдали у модели межотраслевого баланса (её можно рассмотреть как ЗЛП, в которой параметры максимизируемой целевой функции равны значениям добавленной стоимости). 13/ 17 Теория двойственности © Н.М. Светлов, 2007

14 4.2. Теоремы двойственности Теорема 1. а.Если в паре взаимно-двойственных задач одна имеет оптимальное решение, то и другая имеет оптимальное решение с тем же значением ЦФ. б.Если ЦФ одной из взаимно-двойственных задач не ограничена, то допустимая область другой пуста. Следствие. Если допустимая область одной из взаимно-двойственных задач пуста, то у другой она либо тоже пуста, либо её ЦФ не ограничена. 14/ 17 Теория двойственности © Н.М. Светлов, 2007

15 4.2. Теорема 2 (условие дополняющей нежёсткости) а.Разница между левой и правой частями любого ограничения прямой задачи может отличаться от нуля лишь тогда, когда соответствующая переменная двойственной задачи равна нулю. б.Переменная прямой задачи может отличаться от нуля лишь тогда, когда разница между левой и правой частями соответствующего ограничения двойственной задачи равна нулю. Избыток любого ресурса в оптимальном плане не стоит ни копейки. Это вполне естественно, так как этот избыток невозможно использовать для увеличения целевой функции. 15/ 17 Теория двойственности © Н.М. Светлов, 2007

16 4.2. Теорема 3 (теорема об оценках) Каждая двойственная переменная равна частной производной оптимального значения ЦФ прямой задачи по свободному члену её ограничения, соответствующего данной двойственной переменной. Двойственная переменная (двойственная оценка) показывает: на сколько увеличится ЦФ, если количество соответствующего ресурса увеличится на единицу на сколько увеличится ЦФ, если количество соответствующего ресурса увеличится на единицу в границах, в которых значение двойственной оценки остаётся неизменным (то есть в пределах устойчивости оптимального плана) в границах, в которых значение двойственной оценки остаётся неизменным (то есть в пределах устойчивости оптимального плана) если ЦФ стоимостная и нет транзакционных издержек: если ЦФ стоимостная и нет транзакционных издержек: по какой максимальной цене ещё выгодно покупать ресурс по какой максимальной цене ещё выгодно покупать ресурс по какой минимальной цене ещё выгодно продавать ресурс по какой минимальной цене ещё выгодно продавать ресурс 16/ 17 Теория двойственности © Н.М. Светлов, 2007

17 4.3. Двойственные оценки в планировании и экономическом анализе Проверка адекватности модели Проверка адекватности модели Почему в реальности избыточны одни ресурсы, а в оптимальном плане – другие? Почему в реальности избыточны одни ресурсы, а в оптимальном плане – другие? Объяснима ли разница между реальными ценами ресурсов и ценами оптимального плана? Объяснима ли разница между реальными ценами ресурсов и ценами оптимального плана? Определение конкурентного преимущества при выпуске продукции по новой технологии Определение конкурентного преимущества при выпуске продукции по новой технологии Сравнение двойственной оценки продукции с её рыночной ценой Сравнение двойственной оценки продукции с её рыночной ценой Определение целесообразности внедрения новой технологии (анализ проекта) Определение целесообразности внедрения новой технологии (анализ проекта) 17/ 17 Теория двойственности © Н.М. Светлов, 2007