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

Тот же цех, тот же начальник — другой вопрос. Раньше мы спрашивали: «сколько выпускать столов и тумб?» А теперь спросим иначе: «сколько на самом деле стоит нам час станка?» Продать час нельзя, станок уже куплен, но цена у него есть — теневая. Она спрятана в двойственной задаче, и у каждой задачи линейного программирования такой двойник ровно один.

Как построить двойственную задачу: пять правил#

Прямая задача — наш план производства: $F=2x_1+3x_2\to \max$ при $x_1+2x_2\le 8$, $x_1+x_2\le 6$, $x_1,x_2\ge 0$. Правила построения двойственной задачи:

1. максимум меняется на минимум (и наоборот: у задачи на минимум двойственная — на максимум);
2. правые части ограничений $b_i$ становятся коэффициентами целевой функции, а коэффициенты $c_j$ — правыми частями;
3. матрица условий транспонируется: каждая строка ограничений прямой задачи превращается в столбец переменных двойственной;
4. знаки ограничений переворачиваются: «≤» становится «≥»;
5. неотрицательность сохраняется: если у прямой задачи $x_j\ge 0$, то у двойственной $y_i\ge 0$.

Переменные $y_1,y_2$ называют двойственными оценками ресурсов. Такая пара — максимум с ограничениями «≤» против минимума с ограничениями «≥» — называется симметричной: задачи меняются местами простой перестановкой.

Пример: фабрика глазами логиста#

Решить двойственную можно симплексом, а можно рассуждением. Оптимум прямой задачи — $x_1=4$, $x_2=2$: обе продукции в плане, значит, оба ограничения двойственной активны — если бы одно выполнялось строго, план можно было бы улучшить. Оба станка загружены полностью, значит, обе цены могут быть положительны. Остаётся система:

Прочтите ограничения двойственной задачи экономически, до всяких теорем. Первое: час станка А плюс час станка Б должны стоить не меньше двух тысяч — иначе было бы выгодно перевести все мощности на столы и наращивать их бесконечно. Второе: два часа А и час Б — не меньше трёх тысяч — иначе все мощности ушли бы на тумбы. Двойственная задача — это план цен, при котором выпускать что-либо сверх оптимального становится невыгодно: всякий «внеконкурсный» продукт окупается ровно по оценке или дороже.

Целевая функция двойственной задачи: $Z=8\cdot 1+6\cdot 1=14$ — ровно столько же, сколько прибыль $F=14$. Совпадение здесь не случайность, а содержание основной теоремы.

Что говорят теоремы двойственности#

• Теорема о взаимной двойственности: если прямая задача имеет оптимум, то двойственная тоже разрешима — у обеих существуют оптимальные планы.
• Слабая двойственность: для любых допустимых планов $F(x)\le Z(y)$ — прибыль не может превысить оценку ресурсов. Зазор между ними называют двойственным.
• Основная (сильная) теорема двойственности: на оптимальных планах значения совпадают, $F^{\ast }=Z^{\ast }$.
• Условие дополняющей нежёсткости: $y_i>0$ только при активном $i$-м ограничении; $x_j>0$ только при активном $j$-м ограничении двойственной.

Эти четыре строчки — весь каркас. Слабая двойственность даёт мгновенную проверку: получили $F^{\ast }>Z^{\ast }$? Ошибка в вычислениях, дальше можно не искать. Сильная — даёт контроль наоборот: оба значения совпали при допустимых планах — оба решения верны, обосновывать ничего больше не нужно.

Слабую двойственность нетрудно и доказать — двух строчек на пальцах. Из ограничений двойственной $c_j\le {\sum }_i{a}_{ij}{y}_i$, умножаем на $x_j\ge 0$ и суммируем по $j$: получается $F(x)\le {\sum }_i{y}_i\left({\sum }_j{a}_{ij}{x}_j\right)$. В скобках стоят левые части ограничений прямой задачи, они не больше $b_i$; домножаем на $y_i\ge 0$, суммируем — и выходит $F(x)\le {\sum }_i{b}_i{y}_i=Z(y)$. Любая прибыль не превышает любую оценку ресурсов. На оптимумах зазор стягивается в нуль — это уже сильная теорема, и её доказательство проглядывает из финальной симплекс-таблицы: строка оценок и есть мост между задачами.

Теневые цены: сколько стоит лишний час станка#

Теневая цена $y_1=1$ читается так: добавьте станку А один час фонда — прибыль вырастет на тысячу. Проверим честно. Ограничение $x_1+2x_2\le 9$ при прежнем $x_1+x_2\le 6$ даёт вершину $(3,3)$: прибыль $2\cdot 3+3\cdot 3=15$ — было 14, стало 15. Прибавка в точности $y_1\cdot \Delta b_1=1\cdot 1$.

Тот же фокус со станком Б: правая часть $x_1+x_2\le 7$ даёт вершину $(6,1)$ с прибылью $12+3=15$. И снова плюс тысяча: $y_2\cdot \Delta b_2=1\cdot 1$. Пока структура оптимума не меняется, прибыль линейно отвечает на ресурсы: $\Delta F=y_1\Delta b_1+y_2\Delta b_2$ — в этом и есть экономический смысл двойственных оценок.

Отсюда рабочее правило планирования: расширять первым тот ресурс, у которого теневая цена выше. В нашей паре цены равны — по тысяче за час у каждого станка, и приращения безразличны. Стоило бы тумбе подорожать — цены разошлись бы, и план модернизации напрашивался бы сам: деньги идут туда, где цена ресурса больше.

А если ресурс в избытке? Приставим к цеху станок В с ограничением $x_1+x_2\le 15$: он не прижат, план тратит на изделия 6 часов из 15. Его двойственная оценка $y_3=0$ — сколько ни наращивай фонд В, прибыль не сдвинется. Дефицитный ресурс имеет положительную цену, избыточный — нулевую.

В финальной симплекс-таблице это видно без расчётов: оценки при балансовых переменных и есть двойственные цены. Наша таблица кончалась строкой $(0,0,1,1)$ — вот они, $y_1=1$, $y_2=1$, вынесенные симплексом бесплатно. Как таблица строилась — симплекс-метод.

Несимметричная двойственность: что меняется#

Правила со знаком зависят от формы прямой задачи. Если ограничения записаны равенствами, знак соответствующих $y_i$ свободен. Если какая-то переменная $x_j$ не ограничена по знаку, $j$-е ограничение двойственной превращается в равенство. Максимуму с ограничениями «≥» отвечают неположительные оценки. Логика одна — «каждому знаку свой сдвиг» — но перед построением пару приводят к одной из стандартных форм. Для ручных задач хватает симметричного случая; несимметричная механика нужна, например, в матричных играх, где смешанные стратегии живут в уравнениях, — подробности в уроке про смешанные стратегии.

Несимметричный случай стоит увидеть на нашей же задаче. Перепишем ограничение станка А как равенство $x_1+2x_2=8$ — тогда $y_1$ свободна по знаку: ресурс задан жёстко, его «цена» может быть и отрицательной, если лишний фонд мешает. Если же переменная $x_j$ не ограничена по знаку, её столбец отвечает равенством в двойственной задаче — равенство в прямой порождает свободу в двойственной и наоборот. Правил немного, но они жёсткие: перед построением пару приводят к одной из стандартных форм, иначе знаки перепутаются.

Как проверить сильную двойственность на числах#

1. 1
   Допустимость прямой: план $(4,2)$: $4+2\cdot 2=8\le 8$, $4+2=6\le 6$ — верно; $F=2\cdot 4+3\cdot 2=14$.
2. 2
   Допустимость двойственной: план $(1,1)$: $1+1=2\ge 2$, $2\cdot 1+1=3\ge 3$ — верно; $Z=8\cdot 1+6\cdot 1=14$.
3. 3
   Сравниваем: $14=14$ — сильная двойственность выполнена, оба плана оптимальны.
4. 4
   Контроль дополняющей нежёсткости: оба ограничения активны — обе цены положительны; обе продукции выгодны — оба неравенства двойственной активны. Противоречий нет.

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

Следующий шаг: возьмите задачу о рационе из первого урока и постройте к ней двойственную — «задачу оценки питательности». Решите обе и сравните значения. Если $F^{\ast }$ и $Z^{\ast }$ сошлись — правила усвоены; если разошлись — ищите перевёрнутый знак, обычно он один.