Построение двойственной задачи
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (для бакалавров 1-го курса очной формы обучения) Часть II
Ростов-на-Дону
УДК 517(07) Линейное программирование (для бакалавров 1-го курса очной формы обучения). Часть II. – Ростов н/Д: Рост. гос. строит. ун-т, 2011. – 24 с.
Изложены двойственная задача ЛП и ее решение, транспортная задача ЛП и ее решение, особенности решения транспортных задач с неправильным балансом. Приведён образец индивидуального задания, снабжённый подробным решением входящих в него задач. Предназначены для бакалавров 1-го курса очной формы обучения специальностей ОБД, АС дорожно-транспортного института, а также для бакалавров экономических специальностей. Электронная версия методических указаний находится в библиотеке, ауд. 224.
УДК 517(07)
Составители: канд. физ.-мат. наук, доц. М. М. Цвиль канд. физ.-мат. наук, доц. В. В. Шамраева ассист. И. В. Цветкова ассист. В. В. Новиков
Рецензент: канд. физ.-мат.наук, доц. Г.А. Можаев
Редактор Т.М. Климчук Доп. план 2011 г., поз. 183 Подписано в печать 12.07.11. Формат 60´84/16. Бумага писчая. Ризограф. Уч.-изд.л. 1,8. Тираж 20 экз. Заказ 385 Редакционно-издательский центр Ростовского государственного строительного университета 344022, Ростов-на-Дону, ул. Социалистическая, 162 Ó Ростовский государственный Теория двойственности
Построение двойственной задачи
Любой задаче ЛП (исходной) можно поставить в соответствие другую, которая называется двойственнойили сопряжённой.Они образуют пару двойственных ( или сопряжённых ) задач ЛП . Составим двойственную к задаче использования сырья (1.2.1). Имеется видов сырья в количестве , которые используются для изготовления видов продукции. Известно: – расход -го вида сырья на единицу -й продукции; прибыль от реализации единицы -го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Математическая модель данной задачи имеет вид (в матричной форме): ; ; . (6.1.1) Здесь , объём производства -го вида продукции. Предположим, что второй потребитель хочет перекупить сырьё. Составим двойственную задачу, решение которой позволит определить условия продажи сырья. Введём вектор оценок (цен) видов сырья . Тогда затраты на приобретение сырья в количестве равны . Второму производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья, поэтому целевая функция имеет вид . Первому производителю невыгодно продавать сырьё, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие -й продукции меньше прибыли , получаемой при реализации этого изделия, т.е. , . В матричной форме задача имеет следующий вид: ; ; . (6.1.2) Таким образом, связь между исходной и двойственной задачами состоит в том, что коэффициенты целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены системы ограничений исходной задачи служат коэффициентами целевой функции двойственной задачи, а матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. В теории двойственности используются 4 пары двойственных задач:
где С = (c1, c2, …, cn); Y = (y1, y2, …, ym); ; ; .
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (378)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |