Экономико-математические методы и модели. Теоремы двойственности

1. Экономико-математические методы и модели

к.э.н., доц. Косухина М.А.

2. Учебные вопросы

• Двойственная ЗЛП:
•Теория;
•Составление.
•Примеры.
05.03.2020
Лекция 5 ЭМММ

3. Прямая и двойственная задачи

Каждой ЗЛП можно определенным образом сопоставить некоторую
другую ЗЛП, называемой двойственной по отношению к исходной.
Пусть имеется задача по максимизации ЦФ:
05.03.2020
Лекция 5 ЭМММ

4. Правила составления

1. Целевая функция исходной задачи задается на максимум, а
целевая функция двойственной на минимум;
2. Матрица, составленная из коэффициентов системы ограничений
исходной
задачи
транспонируются
для
получения
коэффициентов системы ограничений двойственной задачи;
3. Число переменных в двойственной задаче равно числу
соотношений в исходной задаче;
4. Число соотношений системы ограничений в двойственной
задаче равно числу переменных в исходной задаче;
05.03.2020
Лекция 5 ЭМММ

5. Правила составления

5. Коэффициентами при неизвестных в целевой функции
двойственной задаче являются свободные члены в системе
ограничений исходной задачи;
6. Правыми частями соотношений системы ограничений в
двойственной задаче являются коэффициенты при неизвестных
в целевой функции исходной задачи;
05.03.2020
Лекция 5 ЭМММ

6. Правила составления

5. Коэффициентами при неизвестных в целевой функции
двойственной задаче являются свободные члены в системе
ограничений исходной задачи;
6. Правыми частями соотношений системы ограничений в
двойственной задаче являются коэффициенты при неизвестных
в целевой функции исходной задачи;
05.03.2020
Лекция 5 ЭМММ

7. Правила составления

7.
05.03.2020
Лекция 5 ЭМММ

8. Пример

05.03.2020
Лекция 5 ЭМММ

9. Пример

05.03.2020
Лекция 5 ЭМММ

10. Пример 2

05.03.2020
Лекция 5 ЭМММ

11. Свойства двойственной ЗЛП

Решая прямую задачу, мы заодно необходимо получаем решение
двойственной задачи (в верхней строке заключительной симплексной
таблицы и столбцах, соответствующих дополнительным переменным).
Отыскание оптимума невозможно без отыскания цен ресурсов, при которых
выполняются условия двойственной задачи.
Эти цены называются ценами оптимального плана или
двойственными оценками ограничений прямой задачи.
Любая попытка тем или иным способом найти оптимальное (по какомунибудь критерию) распределение ресурсов требует установления или
расчёта их цен.
05.03.2020
Лекция 5 ЭМММ

12. Свойства двойственной ЗЛП

Если мы построим двойственную задачу к двойственной задаче,
то получим исходную (прямую) задачу.
Как следствие, двойственные оценки ограничений двойственной
задачи равны соответствующим переменным прямой задачи.
Интересно, что свойства двойственности мы уже наблюдали у
модели межотраслевого баланса
05.03.2020
(её можно рассмотреть как ЗЛП, в которой параметры максимизируемой целевой
функции равны значениям добавленной стоимости).
Лекция 5 ЭМММ

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

Те о р е м а 1 .
а. Если в паре взаимно-двойственных задач одна имеет оптимальное
решение, то и другая имеет оптимальное решение с тем же значением ЦФ.
б. Если ЦФ одной из взаимно-двойственных задач не ограничена, то
допустимая область другой пуста.
Следствие.
Если допустимая область одной из взаимно-двойственных задач пуста, то у
другой она либо тоже пуста, либо её ЦФ не ограничена.
05.03.2020
Лекция 5 ЭМММ

14. Теорема 2 (условие дополняющей нежёсткости)

а. Разница между левой и правой частями любого ограничения прямой
задачи может отличаться от нуля лишь тогда, когда соответствующая
переменная двойственной задачи равна нулю.
б. Переменная прямой задачи может отличаться от нуля лишь тогда, когда
разница между левой и правой частями соответствующего ограничения
двойственной задачи равна нулю.
Избыток любого ресурса в оптимальном плане не стоит ни копейки.
Это вполне естественно, так как этот избыток невозможно использовать для увеличения
целевой функции.
05.03.2020
Лекция 5 ЭМММ

15. Теорема 3 (теорема об оценках)

• Каждая
двойственная
переменная
равна
частной
производной
оптимального значения ЦФ прямой задачи по свободному члену её
ограничения, соответствующего данной двойственной переменной.
• Двойственная переменная (двойственная оценка) показывает:
• на сколько увеличится ЦФ, если количество соответствующего ресурса
увеличится на единицу
• в границах, в которых значение двойственной оценки остаётся
неизменным (то есть в пределах устойчивости оптимального плана)
• если ЦФ стоимостная и нет транзакционных издержек:
• по какой максимальной цене ещё выгодно покупать ресурс
• по какой минимальной цене ещё выгодно продавать ресурс
05.03.2020
Лекция 5 ЭМММ

16. Двойственные оценки в планировании и экономическом анализе

• Проверка адекватности модели
• Почему в реальности избыточны одни ресурсы, а в оптимальном плане –
другие?
• Объяснима ли разница между реальными ценами ресурсов и ценами
оптимального плана?
• Определение конкурентного преимущества при выпуске продукции по новой
технологии
• Сравнение двойственной оценки продукции с её рыночной ценой
• Определение целесообразности внедрения новой технологии (анализ
проекта)
05.03.2020
Лекция 5 ЭМММ

17. ДЗ

• Экономическая интерпретация двойственной задачи.
05.03.2020
Лекция 5 ЭМММ