Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Двойственные задачи линейного программированияСодержание книги Поиск на нашем сайте
Рассмотрим задачу о производстве продукции из ограниченного количества сырья: производитель производит n видов продукции из m видов сырья в количестве b 1, b 2, …, bm. Известны расходы каждого вида сырья на каждый вид продукции аij, i = 1,…, n; j = 1,…, m, а также прибыль от реализации продукции каждого вида сj, j =1,…, m. Составить план выпуска продукции x 1, …, xn, при котором суммарная прибыль от реализации была бы наибольшей. Математическая модель данной задачи имеет вид: xj ³ 0, j = 1,2… n. Данной задаче поставим в соответствие следующую задачу: второй производитель хочет перекупить сырье, имеющееся у первого производителя. По какой минимальной цене первый производитель может его продать, чтобы выручка от продажи не уступала бы прибыли от производства. Составим математическую модель задачи: Целевая функция: выручка от продажи сырья (или затраты на покупку сырья) стремиться к минимуму. Параметры управления: у 1,…, уm продажная цена товара. Тогда а 11 у 1 – стоимость сырья первого вида, которое расходуется на одно изделие первого тип, а 21 у 2 – стоимость сырья второго вида, которое расходуется на одно изделие первого типа и т.д. тогда – стоимость сырья всех видов, расходуемых на единицу первого вида продукции. Естественно, что первый производитель продаст сырье в том случае, если суммарная стоимость сырья превосходит цену единицы продукции . Рассуждая аналогично для остальных видов продукции, получим систему ограничений Целевая функция имеет функциональное выражение вида: . Математические модели двух изложенных выше задач называются двойственными. Такая пара моделей является симметричной парой двойственных задач. Составим двойственную задачу для задачи из предыдущего параграфа: . Система ограничений двойственной задачи имеет транспонированную матрицу по сравнению с прямой задачей. В качестве столбца свободных членов используются коэффициенты целевой функции, а в качестве коэффициентов целевой функции – столбец свободных членов. Знаки неравенств меняются, целевая функция стремится к минимуму. Обратим внимание, что для построения симметричной задачи все неравенства должны быть однотипные, если же в системе ограничений есть противоположное неравенство, то необходимо его умножить на –1. F=500 у 1+380 у 2 à min. Система ограничений и целевая функция содержат две переменные, следовательно, задача может быть решена графически. Построим прямые и отметим полуплоскости, являющиеся решениями каждого неравенства.
Построим опорную прямую: 500 y 1 + 380 y 2 = 0 и укажем направление градиента целевой функции grad F =(500;380).
На рис. 2.7 отмечена область допустимых неотрицательных решений системы ограничений обратной задачи. Точкой «входа» прямой L в ОДР является точка А – точка пересечения первой и второй прямых. Найдем ее координаты.
Решим систему методом Крамера:
у 1= 6 д.е.; у 2 = 6 д.е. F = 500×6+380×6 = 5280 д.е.
Итак, наименьшая цена, за которую первый продавец может продать сырье первого типа – 6 д.е.; сырье второго типа – 6 д.е. При этом он получит 5280 д.е. Обратим внимание, что при решении прямой задачи в § 2.3 значение целевой функции было такое же. Это является иллюстрацией первой теоремы двойственности: Если одна из пары задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение, причем значения целевых функций задач на них совпадают. Если же одна из них не имеет оптимального решения, то у другой система ограничений будет несовместна. По решению двойственной задачи можно восстановить решение исходной задачи. Для этого используют вторую теорему двойственности: Если при подстановке оптимального решения в систему ограничений i- ое ограничение выполняется как строгое неравенство, то i -ая координата оптимального решения двойственной задачи равна нулю, и, наоборот, если i -ая координата оптимального решения двойственной задачи отлична от нуля то, i-ое ограничение исходной задачи выполняется как равенство. Подставим решение (6; 6) в систему ограничений, так как обе координаты отличны от нуля, то в исходной задаче оба ограничения выполняются как равенства Первые два ограничения выполняются как равенства, вторые два – как строгие неравенства (этот результат виден также из рисунка). По теореме третья и четвертая координаты исходной задачи равны нулю. Подставим получившийся результат в систему ограничений исходной задачи: Þ
Решим систему методом Крамера:
Получили то же оптимальное решение, что и в предыдущем параграфе симплексным методом.
|
||||
Последнее изменение этой страницы: 2016-08-01; просмотров: 271; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.97.9.171 (0.005 с.) |