Экономическая интерпретация двойственной задачи и теории двойственности

Экономико-математический анализ решений. Сформулируем экономические выводы на примере пары двойственных задач, приведенных выше:

1. для любого допустимого плана производства X и любого допустимого вектора оценки ресурсов Y общая созданная стоимость не превосходит суммарной оценки ресурсов;
2. если задача определения оптимального плана, максимизирующего выпуск продукции разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученная при реализации оптимального плана совпадает с суммарной оценкой ресурсов.
   Оценки выступают как инструмент балансирования затрат и результатов. Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, т.е. равенство общей оценки продукции и ресурсов, и обуславливают убыточность всякого другого плана, отличного от оптимального;
3. если по некоторому оптимальному плану X* производства расход i-го ресурса строго меньше его запаса Ьъ то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок Y* его j-ая компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Значит, двойственные оценки могут служить мерой дефицитности ресурса;
4. двойственные оценки ресурсов показывают, на сколько денежных единиц изменится максимальная прибыль от реализации продукции при изменении запаса соответствующего ресурса на одну единицу.

• как мера дефицитности ресурсов и продукции;
• как мера влияния ограничений на целевую функцию;
• как инструмент определения эффективности отдельных вариантов;
• как инструмент балансирования затрат и результатов.

Переменные у₁, у₂, у₃ будут обозначать условную предполагаемую цену за ресурс 1, 2, 3 вида соответственно. Тогда доход от продажи видов сырья, расходуемых на производство одной единицы продукции I, равен: 5у₁ + 1· у₃. Т.к. цена продукции I типа равна 3 ед., то 5у₁ + у₃ ≥ 3, в силу того, что интересы предприятия требуют, чтобы доход от продажи сырья был не меньше, чем от реализации продукции. Именно в силу такого экономического толкования система ограничений двойственной задачи принимает вид:

А целевая функция G = 400y₁ + 300y₂ + 100y₃ подсчитывает условную суммарную стоимость всего имеющегося сырья. Понятно, что в силу I теоремы двойственности F(x*) = G(y*) равенство означает, что максимальная прибыль от продажи всей готовой продукции совпадает с минимальной условной ценой ресурсов. Условные оптимальные цены у_i показывают наименьшую стоимость ресурсов, при которой выгодно обращать эти ресурсы в продукцию, производить.

Еще раз обратим внимание на то, что у_i - это лишь условные, предполагаемые, а не реальные цены на сырье. Тот факт, что у₁* = 0 вовсе не означает, что реальная цена первого ресурса нулевая. Равенство нулю условной цены означает лишь, что этот ресурс не израсходован полностью, имеется в излишке, недефицитен. Действительно, посмотрим на первое неравенство в системе ограничений задачи I, в котором подсчитывается расход первого ресурса: 5х₁* + 0,4х₂* + 2х₃* + 0,5х₄* = 66 < 400. его избыток составляет х₅ = 334 ед. при данном оптимальном плане производства. Этот ресурс имеется в избытке, и поэтому для производителя он недефицитен, его условная цена равна 0, его не надо закупать. Наоборот, ресурс 2 и 3 используются полностью, причем у₃ = 4 а у₂ = 1, т.е. сырье третьего вида более дефицитно, чем второго, его условная цена больше. Если производитель продукции имел бы возможность приобретать дополнительно сырье к уже имеющемуся, с целью получения максимального дохода от производства, то увеличив сырье второго вида на единицу, он бы получил дополнительно доход в у₂ денежных единиц, с увеличением на единицу сырья третьего вида, значение целевой функции увеличилось бы еще на у₃ единицы.

Если перед производителем стоит вопрос, "выгодно ли производить какую-либо продукцию при условии, что затраты на единицу продукции составят 3, 1, 4 единиц 1, 2, 3-го видов сырья соответственно, а прибыль от реализации равна 23 единицам", то в силу экономического истолкования задачи ответить на этот вопрос несложно, поскольку затраты и условные цены ресурсов известны. Затраты равны 3, 1, 4, а цены у₁* = 0, у₂* = 1, у₃* = 4. Значит, можно посчитать суммарную условную стоимость ресурсов, необходимых для производства этой новой продукции: 3 · 0 + 1 · 1 + 4 · 4 = 17 < 23. значит продукцию производить выгодно, т.к. прибыль от реализации превышает затраты на ресурсы, в противном случае ответ бы на этот вопрос был отрицательным.

Ответим на вопрос, как изменится целевая функция в оптимальном плане, если цену первого вида продукции увеличить до 20?
Оценка y₁=0, ресурс не дефицитен, и оптимальный план X не изменится: ΔF_max=Δc₁*x₁=(20-3)*0=0
В данном случае, значение целевой функции не изменилось, поскольку в оптимальном плане x₁=0.

Видеоинструкция

Анализ решения задачи линейного программирования с помощью теории двойственности

Двойственность в задачах линейного программирования

Двойственность

Пример   

т.е. вторая переменная не ограничена по знаку, она может быть как больше 0, так и меньше 0.
Построим двойственную задачу. Так как число ограничений равно трем, то имеем три переменных: u₁, u₂, u₃. ЦФ задачи (Д) имеет вид:
max W = U*B = u₁b₁ + u₂b₂ + u₃b₃  = u₁ + 4u₂ + 3u₃
В прямой задаче имеем матрицу А: .
В задаче (Д) имеем транспонированную матрицу:  .
Таким образом, двойственная задача выглядит так:
max W = u₁ + 4u₂ + 3u₃

Теорема двойственности. Если X и U - соответственно допустимые решения произвольных прямой и двойственной задач, то Z = C*X ≥ W = U*B.
Следствие из теоремы. Если X^*, U^* - соответственно решения прямой и двойственной задач, удовлетворяющих равенству C*X^* = U^*B, то планы X^* и  U^*– оптимальные решения прямой и двойственной задач соответственно.
Теорема. Пусть заданы прямая и двойственная задачи:
а) если прямая и двойственная задачи имеют решения, то каждая из этих задач имеет оптимальное решение и
Z^* = min(П) = max(Д) = W^*
б) если одна из них имеет неограниченный оптимум, то другая не имеет решения.
Теорема. Два решения (X и U) соответственно прямой и двойственной задач оптимальны тогда и только тогда, если выполняется условие: 
(U* A_j - c_j)*x_j = 0; j = 1, n,  где A_j  –  j–й столбец матрицы A.
Поясним некоторые вопросы. На этапе постановки задачи производится анализ с целью ответить на вопросы: «Что будет, если…?» и (или) «Что надо, …, чтобы …?». Анализ с целью ответа на первый вопрос называется вариантным анализом, на второй – решениями по заказу. Вариантный анализ бывает следующих видов: Параметрическим будем называть такой анализ, который заключается в решении задачи при различных значениях некоторого параметра; Под структурным анализом будем понимать решение задачи оптимизации при различной структуре ограничений; Многокритериальный анализ – это решение задачи по разным целевым функциям; Если исходные данные, используемые при решении задачи, зависят от соблюдения дополнительных условий, то такой анализ называется анализом при условных исходных данных.
Во вторую группу – решения по заказу – входят задачи, целью которых является решение задачи оптимизации при заданных значениях: переменных, левых частей ограничений, целевой функции. Кроме анализа, выполняемого на этапе постановки задачи, мощным средством, помогающим принять решение, является анализ полученного оптимального плана.

Вопросы для самоконтроля

1. Для каждой ли задачи ЛП существует двойственная?
2. Как связаны прямая исходная и двойственная задачи?
3. Что такое сопряженные ограничения?
4. Сформулируйте теоремы двойственности.
5. Каков экономический смысл дополнительных переменных в исходной задаче?
6. Каков экономический смысл основных переменных в двойственной задаче?
7. Как изменится значение целевой функции, если запас i-го ресурса увеличить на единицу?