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

максимум целевой функции, то в двойственной ей – минимум.
Коэффициенты при

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

ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга.
5.Число

неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.
6.Условие неотрицательности переменных сохраняется в обеих задачах.

то другая также имеет конечный оптимум, причем экстремальные значения целевых

функций совпадают:


Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

Y*=(y1*,…,ym*) являлись оптимальными решениями, соответственно, прямой и двойственной задач, необходимо и

достаточно, чтобы выполнялись следующие соотношения:

при подстановке в соответствующее ограничение двойственной задачи оптимального решения Y*  это

ограничение обращается в верное равенство, и наоборот.

двойственной задачи представляют собой оценки влияния свободных членов bi в

системе ограничений прямой задачи на величину целевой функции L(X*):


Компоненты оптимального решения двойственной задачи yi* принято называть двойственными оценками. В экономике употребляется также термин «объективно обусловленные оценки».
На свойствах двойственных оценок базируется экономико-математический анализ распределения ресурсов.

задаче (I). Если запасы ресурсов bi , i=1,...,m изменить, то может

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

оценки отражают сравнительную дефицитность факторов производства.
Чем выше величина оценки

yj*, тем выше дефицитность j-го ресурса.
Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

значение целевой функции.
Величина двойственной оценки какого-либо ресурса показывает, насколько

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

хозяйственных решений.
С помощью двойственных оценок можно определить выгодность выпуска

новых изделий, эффективность новых технологических способов производства. При этом эффективным может считаться тот вариант производства, для которого сумма прибыли, недополученной из-за отвлечения дефицитных ресурсов, будет меньше прибыли получаемой. Разница между этими величинами (Δj) вычисляется как:


В том случае, если Δj ≤ 0, вариант производства является выгодным, если Δj > 0 – вариант невыгоден.

с точки зрения конечного эффекта.
Например, отношение

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

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

Свойства двойственных оценок