![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Теория двойственности
Любой задаче линейного программирования можно сопоставить сопряженную или двойственную ей задачу. Причем, совместное исследование этих задач дает, как правило, значительно больше информации, чем исследование каждой из них в отдельности. Любую задачу линейного программирования можно записать в виде Первоначальная задача называется исходной или прямой. Модель двойственной задачи имеет вид: Переменные двойственной задачи Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой. Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой. Двойственная задача по отношению к исходной составляется согласно следующим правилам: 1. целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид 2. матрица 3. Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче; 4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи; 5. Каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства Математические модели пары двойственных задач могут быть симметричными и несимметричными. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем переменные в двойственной задаче могут быть и отрицательными. В симметричных двойственных задачах система ограничений как исходной, так и двойственной задачи задается в виде неравенств, причем на двойственные переменные налагается условие неотрицательности.
где
Рассмотрим пример, показывающий, как в реальной экономической ситуации появляются взаимно двойственные задачи линейного программирования. На некотором предприятии после выполнения годового плана возник вопрос: как поступить с остатками сырья? Из оставшегося сырья можно наладить производство продукции и реализовать его или продать сырье. Предположим, что имеется два вида сырья
При исследовании первой возможности (наладить выпуск товаров Прибыль, которую получит предприятие от реализации товара, составит В интересах предприятия эту прибыль максимизировать. Это прямая задача. Объективно обусловленными оценками двойственной задачи Справедливое требование со стороны продающего предприятия состоит в следующем: если взять сырье, идущее на производство единицы товара Это требование можно представить в виде системы неравенств: В левой части каждого неравенства предполагаемая выручка от продажи сырья, необходимого для производства единицы товара Что касается покупателя, то он заинтересован в минимизации расходов на покупку сырья, т.е. величины
Дата добавления: 2014-01-13; Просмотров: 266; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |