Двойственность и интерпретация

У каждой линейной задачи есть зеркальная двойственная, а её решение раскрывает теневые цены ресурсов.

Двойственность — соответствие, при котором каждой прямой задаче LP отвечает двойственная; их оптимальные значения совпадают (сильная двойственность).

Две стороны одной задачи

Вернёмся к цеху: прямая задача — «сколько произвести, чтобы прибыль была максимальна при ограниченных дереве и труде». Двойственная задача задаёт другой вопрос: «по какой минимальной цене стоило бы продать сами ресурсы (дерево, труд), чтобы это было не хуже, чем производить?». Удивительно, но обе задачи имеют один и тот же оптимум.

Прямая и двойственная

Если прямая — $\max c^\top x$ при $Ax\le b,\ x\ge0$, то двойственная — это

$$\min_y\ b^\top y\quad\text{при}\quad A^\top y\ge c,\ y\ge 0.$$

Переменные $y$ — по одной на каждое ресурсное ограничение. Размерности зеркальны: ограничений прямой = переменных двойственной, и наоборот.

Теневые цены

Оптимальные двойственные переменные $y_i^*$ имеют красивый экономический смысл — это теневые цены ресурсов: на сколько вырастет максимальная прибыль, если добавить единицу $i$-го ресурса. Связывающий (активный) ресурс имеет положительную теневую цену, ресурс с запасом — нулевую (его добавление ничего не даёт). Это бесценно для менеджера: подсказывает, какой ресурс расширять в первую очередь.

Проверим равенство значений

Для нашего цеха посчитаем теневые цены, решив двойственную напрямую, и убедимся, что $b^\top y^*$ равно прибыли $355$ из прямой задачи. В оптимуме связывающие оба ограничения, поэтому $y$ находим из системы $A^\top y=c$.

# Прямая: max 30 x1 + 20 x2, дерево 4x1+2x2<=40, труд 2x1+3x2<=42
# Двойственная переменная на ресурс: y1 (дерево), y2 (труд)
# В оптимуме оба ограничения активны -> A^T y = c:
#   4 y1 + 2 y2 = 30
#   2 y1 + 3 y2 = 20
def solve2(a, b, c, d, p, q):
    det = a * d - b * c
    return (d * p - b * q) / det, (-c * p + a * q) / det

y1, y2 = solve2(4, 2, 2, 3, 30, 20)
print("Теневая цена дерева y1 =", round(y1, 3))
print("Теневая цена труда  y2 =", round(y2, 3))
dual_value = 40 * y1 + 42 * y2
print("Значение двойственной b^T y =", round(dual_value, 2))
print("Значение прямой (прибыль)   = 355.0")

Вывод:

Теневая цена дерева y1 = 6.25
Теневая цена труда  y2 = 2.5
Значение двойственной b^T y = 355.0
Значение прямой (прибыль)   = 355.0

Оба значения равны $355$ — сильная двойственность в действии. А теневые цены говорят: лишний кубометр дерева добавит $6.25$ прибыли, лишний час труда — $2.5$. Значит расширять выгоднее запас дерева.

Слабая и сильная двойственность

• Слабая двойственность: любое допустимое значение прямой $\le$ любое допустимое двойственной — двойственная всегда даёт верхнюю границу прямой (для максимизации).
• Сильная двойственность: в оптимуме границы совпадают $c^\top x^*=b^\top y^*$ (для LP всегда, если задача разрешима).

Как работает под капотом

Двойственность — частный случай теории Лагранжа: двойственные переменные $y$ суть множители Лагранжа при ограничениях. Связь оптимумов выражает дополняющую нежёсткость: если ресурс не исчерпан ($s_i>0$), его теневая цена ноль ($y_i=0$); если переменная положительна, соответствующее двойственное ограничение активно. Эти условия — частный случай ККТ, которые мы разберём для нелинейных задач. Двойственность также даёт критерий оптимальности: нашли пару $(x,y)$ с равными значениями — оба решения оптимальны.

Частые ошибки

• Путать направление неравенств в двойственной. Для $\max$ с $\le$ двойственная — это $\min$ с $\ge$.
• Приписывать теневую цену неактивному ресурсу. У ресурса с запасом теневая цена ноль.
• Ждать совпадения значений у неоптимальных решений. Равенство $c^\top x=b^\top y$ — признак оптимальности обоих.

Итоги

• Каждой прямой LP отвечает двойственная: $\max c^\top x \leftrightarrow \min b^\top y$.
• Двойственные переменные — теневые цены ресурсов: прирост прибыли на единицу ресурса.
• Сильная двойственность: в оптимуме значения совпадают; дополняющая нежёсткость связывает запас и цену.