Презентация Двойственность в линейном программировании онлайн

Содержание слайда: Двойственность в линейном программировании ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННОСТИ

Содержание слайда: Двойственные ЗЛП: постановка

Содержание слайда: Правила получения двойственной задачи из задачи исходной Если в исходной задаче ищется максимум целевой функции, то в двойственной ей – минимум. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, – неравенства вида “≥”.

Содержание слайда: Правила получения двойственной задачи из задачи исходной 4.Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга. 5.Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой. 6.Условие неотрицательности переменных сохраняется в обеих задачах.

Содержание слайда: Теоремы двойственности Теорема 1  Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают: Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

Содержание слайда: Теоремы двойственности Теорема 2 (о дополняющей нежесткости).  Для того чтобы X*=(x1*,…xn*) и Y*=(y1*,…,ym*) являлись оптимальными решениями, соответственно, прямой и двойственной задач, необходимо и достаточно, чтобы выполнялись следующие соотношения:

Содержание слайда: Теоремы двойственности Вывод из теоремы 2 Если компонент оптимального решения xj* больше нуля, то при подстановке в соответствующее ограничение двойственной задачи оптимального решения Y*  это ограничение обращается в верное равенство, и наоборот.

Содержание слайда: Теоремы двойственности Теорема об оценках. Значения переменных yi* в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi в системе ограничений прямой задачи на величину целевой функции L(X*): Компоненты оптимального решения двойственной задачи yi* принято называть двойственными оценками. В экономике употребляется также термин «объективно обусловленные оценки». На свойствах двойственных оценок базируется экономико-математический анализ распределения ресурсов.

Содержание слайда: Пояснение теоремы об оценках Пусть L* - максимальное значение дохода в задаче (I). Если запасы ресурсов bi , i=1,...,m изменить, то может измениться и максимальный доход L*. Это означает, что L* является функцией от ресурсов  bi  , i=1,...,m. Оптимальное значение двойственной переменной yi=yi* числено равно дополнительному доходу L* при увеличении i-го ресурса на единицу, если величина  bi = 1 является достаточно малой по сравнению с величиной bi. Отсюда очень важное практическое применение. Пусть L* - максимальное значение дохода в задаче (I). Тогда, изменяя i-й ресурс  на единицу, получим новое значение максимального дохода по формуле:              или более общий вид                  

Содержание слайда: Свойства двойственных оценок Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки yj*, тем выше дефицитность j-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

Содержание слайда: Свойства двойственных оценок Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. Значение объективно обусловленной оценки называют теневой ценой ресурса. Теневая цена - это стоимость единицы ресурса в оптимальном решении. Однако нужно учитывать, что двойственные оценки позволяют измерить эффективность лишь незначительного изменения объема ресурсов. При значительных изменениях может быть получен новый оптимальный план и новые двойственные оценки.

Содержание слайда: Свойства двойственных оценок Свойство 3. Оценки как инструмент определения эффективности отдельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых технологических способов производства. При этом эффективным может считаться тот вариант производства, для которого сумма прибыли, недополученной из-за отвлечения дефицитных ресурсов, будет меньше прибыли получаемой. Разница между этими величинами (Δj) вычисляется как: В том случае, если Δj ≤ 0, вариант производства является выгодным, если Δj > 0 – вариант невыгоден.

Содержание слайда: Свойства двойственных оценок Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта. Например, отношение показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне; или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести при уменьшении на единицу объема i-го ресурса, если мы хотим, чтобы значение целевой функции не изменилось.

Содержание слайда: Применение теорем двойственности позволяет, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи. Применение теорем двойственности позволяет, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.

Содержание слайда: Тема окончена Удачи!