Автор работы: Пользователь скрыл имя, 06 Декабря 2014 в 14:16, реферат
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.
Оглавление
Двойственность в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.
Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной. Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару. Различают симметричные, несимметричные и смешанные двойственные задачи.
Пусть задача (2) на максимум прибыли – прямая, а (1) –двойственная к ней. Т.е. вектор х – вектор условных цен ресурсов. А искомый план y –оптимальный ассортимент.
Если задача (1)разрешима, то разрешима и задача (2) и наоборот. И при этом .
Максимальная прибыль задачи сопровождается наилучшей оценкой использования ресурсов или максимальной эффективности использования технологий отвечает наилучшая оценка используемых ресурсов. Двойственные оценки помогают ответить на вопрос, какова наименьшая стоимость набора ресурсов, дающая возможность обращения ресурсов в продукты и продажи этих продуктов с целью максимизации прибыли. При оптимальном поведении экономической системе или фирме безразлично, использовать ли ресурсы для производства и продать продукты, чтобы получить прибыль или продать ресурсы по эффективным ценам, уже не производя продукты.
Для того чтобы пара планов x*, y* была оптимальной в прямой и двойственной задачах соответственно, необходимо и достаточно, чтобы выполнялись следующие условия:
Экономический смысл второй теоремы двойственности:
1. Если yj>0, j технология рентабельна (соответственно, j ограничение двойственной задачи, которое характеризует условные удельные оценки затрат ресурсов при выпуске одной единицы
продукции j вида, выполняется как строгое равенство), то. условная удельная оценка всех используемых ресурсов при производстве одной единицы продукции j вида равна прибыли cj. И
наоборот, если условная оценка удельных затрат используемых ресурсов равна прибыли cj, то данная технология рентабельна.
2. Если xj=0, т.е. j технология нерентабельна, то
условная удельная оценка затрат больше удельной
прибыли. И наоборот, если условная удельная
оценка затрат ресурсов
технология нерентабельна.
3. Если yi>0 (условная цена i ресурса отлична от 0), то весь i ресурс расходуется полностью. Наоборот, если (i ресурс используется полностью), то у него есть ненулевая «цена», как мера его дефицитности. Эти «цены» в сравнении с собой устанавливают некоторую упорядоченность среди дефицитных ресурсов (чем больше «цена», тем более дефицитен ресурс).
4. Если цена равна 0, т.е. i-ый ресурс недефицитен, тогда соответствующее ограничение по расходу i ресурса выполняется как строгое неравенство.
Если двойственная оценка xi*>0, то вдоль оптимального плана y* эта оценка xi* есть частная производная функции L по i-му аргументу, т.е.
Третью теорему двойственности можно использовать для приближенного определения изменения прибыли в исходной задаче при изменении дефицитных ресурсов без решения новой задачи с измененными ресурсами.
Введем функцию Лагранжа для (1)
Из второй теоремы двойственности следует, что на оптимальном решении задач (1),(2) существует такое
Образуем функцию Лагранжа в задаче (2)
Опять же на оптимальном решении задач (1),(2) существует такое
Если положить .
Используя функции Лагранжа и можно показать(!!!!!), что задача (1) может быть записана в виде
А задача (2)
Учитывая имеем следующее представление для задачи (2)
Из второй теоремы двойственности следует, что на оптимальном решении x*, y*,
Оказывается, что для введенной здесь функции Лагранжа
имеется очень интересное свойство.
Теорема. Неотрицательный вектор х* является оптимальным решением задачи (1), т.к. существует неотрицательный вектор у*,что пара (х*,у*) является седловой точкой функции Лагранжа
Или
С помощью функций Лагранжа в задаче нелинейного программирования
По аналогии с задачами ЛП Вулфом была доказана следующая теорема.
Теорема. Пусть функция и все функции
выпуклые и дифференцируемые, а также выполняются условие Слейтера. Тогда задача (3) может быть записана как
где
Если задача (3) имеет решение х*, то в двойственной задаче
существует такое y*, что (х*,у*) является решением двойственной задачи, и при этом экстремумы двух задач равны между собой.
Такой результат позволяет и для задач нелинейной оптимизации вводить аналог качественных характеристик – например, двойственные оценки есть мера чувствительности ограничений к изменению параметров(весов, объемов и др.), или условные цены или некие предельные характеристики решения.
Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием — математическое программирование.
Двойственность, в математическом программировании, как и вообще в математике, играет фундаментальную роль. Она выступает в качестве краеугольного камня соответствующих теорий, порождает арсенал конструктивных средств анализа математических моделей, построения эффективных алгоритмов решения задач и формальной оценки этой эффективности. Двойственность, в зависимости от ее конкретного содержания, определяемого конкретной математической дисциплиной (алгебра, функциональный анализ, теория оптимального управления и т.д.), несет в себе следы специфики соответствующей дисциплины. Но именно это обстоятельство и превращает двойственность, в математике, в здание, в гармонически организованную и насыщенную архитектуру.
Информация о работе Теорема двойственности и ее экономический смысл