Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2017-11-16 | 358 |
5.00
из
|
Заказать работу |
|
|
Каждая задача линейного программирования имеет двойственную ей задачу. Двойственную задачу можно наделить вполне определенным смыслом.
Рассмотрим в качестве исходной задачу определения оптимальной производственной программы (симметричную на максимум целевой функции).
Предположим, предприятие, разрабатывающее программу, рассматривает в качестве альтернативы продажу ресурсов. При каких условиях реализация данной альтернативы станет возможной? Определить данные условия можно, решив задачу следующего содержания:
В данной задаче: - условные (маржинальные) цены ресурсов, характеризующие изменение выручки предприятия при изменении запаса ресурса на единицу:
.
Целевая функция задачи характеризует основания выбора решения о приобретении ресурсов покупателем. Покупатель стремится минимизировать расходы на покупку запасов .
Ограничения характеризуют основания выбора решения продавцом, то есть предприятием. Предприятие желает получить от продажи ресурсов доход, не меньший, чем доход от продажи продукции по ценам . В каждом ограничении сопоставляется оценка ресурсов, требуемых для выпуска единицы изделия, с ценой продажи единицы изделия.
Для составления каждого неравенства коэффициенты (нормы расхода ресурсов) отбираются по второму индексу, обозначающему номер продукта. Данная задача является двойственной по отношению к задаче определения оптимальной производственной программы. Двойственная задача, как видно, также имеет симметричную запись. Вполне правомерно говорить о существовании пары взаимно двойственных симметричных задач.
На базе сопоставления форм записи обеих задач можно вывести следующие правила построения симметричных двойственных задач:
|
1) если целевая функция прямой задачи максимизируется, то двойственной – минимизируется, и наоборот;
2) числу ограничений прямой задачи равно число переменных двойственной задачи;
3) числу переменных прямой задачи равно число ограничений двойственной задачи;
4) для получения ограничений двойственной задачи необходимо транспонировать матрицу коэффициентов прямой задачи;
5) в двойственной задаче знак ограничений-неравенств противоположен знаку ограничений-неравенств прямой задачи;
6) переменные двойственной задачи неотрицательны.
Рассмотрим две возможности использования теории двойственности: 1) для рационализации решения задач, симметричных на минимум целевой функции; 2) для проведения анализа оптимальной производственной программы.
Трансформация записи задачи, симметричной на минимум целевой функции, не обеспечивает получения первоначального неотрицательного базисного решения.
В исходном пункте мы располагаем следующей записью:
При трансформации записи в каноническую система линейных уравнений принимает следующий вид:
Следовательно, матрица системы уже не будет содержать в своем составе единичную матрицу как подсистему:
Ранее рассматривались возможности получения начального неотрицательного базисного решения либо с помощью преобразований матрицы, либо с помощью искусственных переменных. Теория двойственности открывает еще одну возможность - составить двойственную задачу и решить ее симплекс-методом. В соответствии с доказанными теоремами двойственности, если одна из пары двойственных задач имеет оптимальное решение, то его имеет и другая задача. Экстремальные значения целевых функций задач совпадают
, а оптимальные значения переменных исходной задачи определяются по правилу соответствия (рис. 3) в индексной строке заключительной симплексной таблицы.
|
Рис. 3. Соответствие между переменными прямой и двойственной задач.
Следует отметить, что данная схема фиксирует именно соответствие между переменными, а не тождество их значений. Справедливым является следующее утверждение:
Двойственные оценки ресурсов находят применение в так называемом постоптимизационном анализе, так как они являются маржинальными ценами ресурсов
. Это позволяет принимать решения о перспективах изменения запаса соответствующего ресурса в следующем плановом периоде. Кроме того, значения позволяют судить о дефицитности ресурсов. Если , то ресурс бездефицитен, то есть его запас избыточен; если положительна, то запас ресурса используется полностью.
Двойственные оценки можно также использовать при принятии решений о целесообразности расширения ассортимента. Предположим, поступило предложение о расширении ассортимента выпускаемых изделий за счет дополнительного продукта. Цена данного продукта , а нормы расхода ресурсов . Определим оценку ресурсов, требуемых для выпуска единицы нового изделия, и сравним ее с ценой продажи изделия. Расширять ассортимент выгодно, если
< .
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!