- •Введение 2
- •Глава 1. Линейные математические модели 4
- •Глава 2. Специальные задачи линейного программирования 32
- •Заключение 64 Список литературы 65
- •Глава 1. Линейные математические модели
- •1.1.Постановка задачи линейного программирования
- •1.2. Графический метод решения задачи линейного программирования
- •1.3. Основная задача линейного программирования
- •1.4. Симплекс-метод
- •1.5. Двойственная задача линейного программирования. Экономическая интерпретация
- •1.6. Целочисленное линейное программирование. Метод Гомори
- •Глава 2. Специальные задачи линейного программирования
- •2.1 Построение транспортной модели
- •2.2 Сбалансированные и несбалансированные транспортные модели
- •2.3 Определение начального плана транспортировок. Методы "северо-западного" угла, минимального элемента, Фогеля
- •2.4 Оптимальный план транспортной задачи. Метод потенциалов
- •2.5 Задача о назначениях
- •2.6 Венгерский метод решения задачи о назначениях
- •2.7 Применение задачи о назначениях к решению экономических проблем
- •Хазанова л.Э. Математическое моделирование в экономике. 141 с., изд-во «БеК», 1998 г.
1.5. Двойственная задача линейного программирования. Экономическая интерпретация
Рассмотрим задачу линейного программирования следующего вида:
В задаче требуется максимизировать целевую функцию. Все ограничения являются неравенствами со знаком , все переменные неотрицательны. Задача содержит управляющих переменных и ограничений. Коэффициенты при переменных в целевой функции: ; свободные члены: .
Двойственная задача линейного программирования имеет вид:
В двойственной задаче требуется найти минимум целевой функции, ограничения — неравенства со знаком , управляющие переменные неотрицательны. Задача содержит управляющих переменных и ограничений. Коэффициенты целевой функции задачи являются свободными членами исходной ЗЛП, а свободные члены двойственной задачи — коэффициентами целевой функции исходной ЗЛП. Матрица коэффициентов двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы — строками.
Задачи (1.5.1), (1.5.2) и (1.5.3), (1.5.4) называются парой взаимно двойственных задач линейного программирования. Для двойственных задач верна следующая теорема.
Теорема двойственности: если одна из взаимно двойственных задач имеет оптимальное решение , то другая также имеет оптимальное решение . При этом соответствующие им оптимальные значения целевых функций и равны. Поясним экономический смысл двойственной модели.
Пусть в качестве управляющих переменных исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметрами — количество ресурсов -ого типа, используемых для изготовления изделий. Через обозначено количество ресурсов -ого типа, идущее на изготовление одного изделия -ого вида. Тогда исходная модель (1.5.1), (1.5.2) соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.
Пусть предприятие решило прекратить производство изделий и продать ресурсы, идущие на их изготовление. Обозначим через цены на единицу ресурсов -ого вида. Цены на ресурсы должны удовлетворять следующим двум условиям:
они не должны быть слишком высокими, иначе ресурсы невозможно будет продать;
цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции.
Первое условие выражается формулой (1.5.3), второе условие — ограничениями (1.5.4). В левой части каждого из неравенств (1.5.4) стоит прибыль от продажи ресурсов всех типов, идущих на изготовление -ого изделия, в правой части — прибыль от продажи -ого изделия. Таким образом, двойственная задача (1.5.3) — (1.5.4) соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов. Значения переменных часто называют теневыми ценами.
Построение двойственной задачи позволяет глубже разобраться в поставленной экономической проблеме.