Двойственная задача

Найти у_i – оценки единицы каждого вида ресурсов, минимизирующих суммарную оценку ресурсов, при условии, что оценка ресурсов, необходимых для производства единицы каждого вида продукции, была бы не меньше цены единицы соответствующей продукции. у_i – оценка i-ro ресурса с точки зрения его лимитированности в оптимальном плане (теневая цена i-ro ресурса).

Свойство 1. Оценка как мера влияния ограничения на оптимальное значение целевой функции. Это свойство показывает ещё одну связь между переменными прямой и двойственной задач. Поясним это подробнее.

Пусть х* = (х₁*, х₂*,..., х_j^*,..., х_n*) – оптимальное решение прямой задачи, а у* = (у₁*, у₂*,..., у_i*,..., у_m*) – оптимальное решение двойственной задачи:

Z_max = С₁x₁* +... + С_jx_j* +... + С_nХ_n*;

W_min = b₁y₁* +... + b_iy_i* +... + b_my_m*.

На основании первой теоремы двойственности (Z_max = W_min) можно записать

С₁х₁* +... + С_jx_j^* +... + С_nх_n* = b₁у₁* +... + b_iу_i* +... + b_my_m^*.

Отсюда следует, что

Z_max = b₁у₁* +... + b_iу_i* +... + b_my_m^*.

Поставим вопрос: как изменится величина Z_max, если в исходной задаче увеличить свободный член b в i-м ограничении-неравенстве на величину .

Величина Z_max, рассматриваемая теперь как функция переменных b₁, b₂,..., b_i,..., b_m, получит приращение ∆Z_max.

Частные производные этой функции по любому из этих аргументов (при условии неизменности остальных) имеют вид

Учитывая, что функция Z_max линейная, получим

∆Z_max = y_i ∙ ∆b_i,

т.е. при увеличении объёма i-гo ресурса на единицу (∆b_i = 1) оптимальное значение целевой функции увеличится на оценку единицы этого ресурса. Если же объём i-гo ресурса изменить на k единиц, то целевая функция изменится на величину k ∙ у_i* при условии, что это изменение не выйдет за границы устойчивости двойственных оценок.

Свойство 2. Оценка как мера дефицитности ресурса. Это свойство следует из теоремы 2. Если у_i* = 0, то из (4.9) следует, что т.е. i-й ресурс не полностью используется в оптимальном плане и его оценка равна нулю. В соответствии с 1-м свойством, увеличение объёма этого ресурса не приведёт к увеличению объёма выпускаемой продукции. Такой ресурс будем называть недефицитным (нелимитирующим). Для недефицитного ресурса значение соответствующей балансовой переменной показывает его остаток после выполнения оптимального плана. Если у_i* > 0, то из (4.8) имеем т.е. если i-й ресурс полностью расходуется в оптимальном плане, то его оценка положительна. Такой ресурс будем называть дефицитным (лимитирующим). Чем больше оценка ресурса, тем он дефицитнее с точки зрения его вклада в результат производства. Величина, на которую увеличивается значение целевой функции при увеличении количества лимитирующего ресурса на единицу, называется оценкой ресурса или его теневой ценой. Теневая цена ресурса – это оценка единицы данного ресурса в оптимальном решении.

Свойство 3. Оценка как мера эффективности выпускаемой продукции. Это свойство также следует из теоремы 2. Пусть х_j* > 0. Это означает, что продукция вида j производится в оптимальном плане. Из (4.11) имеем т.е. оценка ресурсов на производство единицы j-й продукции равна стоимости единицы этой продукции. Такую продукцию будем считать рентабельной. Если х_i* = 0, то из (4.10) следует, что т.е. продукция j-го вида в оптимальном плане не производится, потому что аналогичная оценка ресурсов превышает цену единицы этой продукции. Такую продукцию будем считать нерентабельной.

Свойство 4. Оценка как средство балансировки затрат и результатов в оптимальном плане. Это свойство следует из условия (4.7) теоремы 1:

Левая часть этого равенства означает стоимость произведённой продукции, т.е. результат производства, а правая – оценку используемых ресурсов, т.е. затраты экономической системы. Следовательно, в оптимальном плане результаты производства балансируются затратами системы на это производство. В случае неоптимальности плана по известной теореме линейного программирования

т.е. для произвольного плана задачи результат не больше затрат на производство.