Теорема двойственности линейного программирования

Любую задачу линейного программирования можно записать в двух взаимосвязанных формах: прямой и двойственной. Теорема двойственности линейного программирования утверждает, что эти две задачи неразрывно связаны - их оптимальные значения совпадают, а решение одной несёт полную информацию о решении другой. Это не формальный трюк, а мощный инструмент: двойственная задача даёт оценку качества решения, объясняет экономический смысл ограничений (теневые цены) и нередко решается проще исходной. Разберём, как строится двойственная задача, что именно гарантируют слабая и сильная теоремы двойственности и как применять условия дополняющей нежёсткости на практике.

Прямая и двойственная задачи: как они связаны

Возьмём прямую задачу линейного программирования в стандартной форме на максимум:

$\max\; z = c^\top x \quad \text{при} \quad Ax \le b,\; x \ge 0.$

Здесь $x \in \mathbb{R}^n$ - вектор переменных, $A$ - матрица ограничений размера $m \times n$, $b$ - вектор правых частей, $c$ - вектор коэффициентов цели. Каждому ограничению прямой задачи ставится в соответствие двойственная переменная $y_i$, и двойственная задача формулируется так:

$\min\; w = b^\top y \quad \text{при} \quad A^\top y \ge c,\; y \ge 0.$

Получается красивая симметрия: число переменных двойственной задачи равно числу ограничений прямой, и наоборот. Прямая максимизирует - двойственная минимизирует; матрица ограничений транспонируется; векторы $b$ и $c$ меняются ролями. Прежде чем строить двойственную задачу вручную, удобно проверить себя через инструмент ниже - он соберёт корректную постановку по вашим данным.

Правила построения двойственной задачи

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

• ограничению-неравенству $\le$ в прямой задаче соответствует переменная $y_i \ge 0$ в двойственной;
• ограничению $\ge$ соответствует $y_i \le 0$;
• ограничению-равенству $=$ соответствует свободная переменная $y_i$ (любого знака);
• неотрицательной переменной $x_j \ge 0$ соответствует двойственное ограничение $\ge$;
• свободной переменной $x_j$ соответствует двойственное ограничение-равенство $=$.

Для прямой задачи на минимум знаки симметрично меняются. Эти правила удобно запоминать через мнемонику: «знаковое» ограничение порождает знаковую переменную, а равенство - свободную. Если запутались, всегда можно привести задачу к канонической форме (все ограничения одного типа) и применить базовое правило, а затем учесть, что двойная двойственность возвращает исходную задачу: двойственная к двойственной - это прямая.

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

Слабая теорема двойственности - фундамент всей теории. Она утверждает: для любого допустимого решения $x$ прямой задачи (на максимум) и любого допустимого решения $y$ двойственной задачи (на минимум) выполняется неравенство

$c^\top x \le b^\top y.$

Иными словами, значение целевой функции прямой задачи никогда не превышает значения двойственной. Доказательство одностраничное: из $Ax \le b$, $y \ge 0$ следует $y^\top A x \le y^\top b$, а из $A^\top y \ge c$, $x \ge 0$ следует $c^\top x \le y^\top A x$. Объединяя цепочку, получаем $c^\top x \le b^\top y$.

Практические следствия слабой теоремы:

• любое допустимое $y$ даёт верхнюю оценку оптимума прямой задачи, а любое допустимое $x$ - нижнюю;
• если для некоторых $x^*$ и $y^*$ оказалось $c^\top x^* = b^\top y^*$, то оба они оптимальны (зазора больше быть не может);
• если прямая задача не ограничена сверху ($z \to +\infty$), то двойственная не имеет допустимых решений.

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

Слабая теорема гарантирует лишь неравенство; сильная теорема двойственности замыкает разрыв. Её формулировка: если прямая задача имеет конечное оптимальное решение $x^*$, то и двойственная имеет конечное оптимальное решение $y^*$, причём их оптимальные значения точно совпадают:

$c^\top x^* = b^\top y^*.$

Разность $b^\top y - c^\top x \ge 0$ называют зазором двойственности (duality gap), и для линейного программирования в оптимуме он строго равен нулю. Это ключевое отличие от выпуклого нелинейного программирования, где зазор может быть положительным. Сильная теорема означает, что задачу можно решать с любой из двух сторон - результат идентичен. Симплекс-метод фактически решает обе задачи одновременно: финальная симплекс-таблица содержит оптимальное $x^*$ в столбце решения и оптимальное $y^*$ в строке оценок (коэффициентах при базисных переменных). Связь с условной оптимизацией глубже, чем кажется: тот же аппарат двойственных оценок возникает и в методе штрафных функций, где множители Лагранжа восстанавливаются предельным переходом.

Теорема о дополняющей нежёсткости

Третий столп теории - теорема о дополняющей нежёсткости (complementary slackness). Она даёт точную алгебраическую связь между оптимальными решениями прямой и двойственной задач. Пусть $x^*$ и $y^*$ - оптимальные решения. Тогда для каждой пары «ограничение - переменная» выполнено:

$y_i^* \,\big(b_i - (Ax^*)_i\big) = 0 \quad \text{и} \quad x_j^* \,\big((A^\top y^*)_j - c_j\big) = 0.$

Смысл такой: если двойственная переменная $y_i^* > 0$ (ресурс «ценен»), то соответствующее ограничение прямой задачи выполнено как равенство - ресурс исчерпан до конца. И наоборот: если ограничение выполнено строго ($(Ax^*)_i < b_i$, ресурс в избытке), то его двойственная цена $y_i^* = 0$. Аналогично для переменных: если $x_j^* > 0$ (продукт производится), то соответствующее двойственное ограничение активно. Эти условия позволяют по решению одной задачи восстановить решение другой без полного перерешивания: достаточно записать, какие ограничения активны, и решить получившуюся систему линейных уравнений.

Экономический смысл: теневые цены

Двойственные переменные $y_i^*$ имеют прозрачную экономическую интерпретацию - это теневые цены (shadow prices), или предельная ценность ресурсов. Величина $y_i^*$ показывает, на сколько вырастет оптимум прямой задачи при увеличении $i$-го ресурса $b_i$ на единицу (в пределах, пока структура решения не меняется):

$y_i^* = \frac{\partial z^*}{\partial b_i}.$

Если завод максимизирует прибыль при ограничениях на сырьё, рабочее время и оборудование, то двойственные оценки скажут, какой именно ресурс «узкое место»: у дефицитного ресурса теневая цена положительна, у избыточного - равна нулю (что прямо следует из дополняющей нежёсткости). Это превращает теорему двойственности из абстрактной математики в инструмент принятия решений: куда вкладывать средства, какой ресурс докупать, сколько максимум стоит дополнительная единица сырья. Именно поэтому двойственные оценки активно используют в экономическом анализе, логистике и планировании производства.

Когда двойственность нарушается

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

• прямая задача не ограничена ($z \to +\infty$) $\Rightarrow$ двойственная несовместна (нет допустимых $y$);
• прямая задача несовместна (нет допустимых $x$) $\Rightarrow$ двойственная либо несовместна, либо не ограничена;
• обе задачи могут оказаться несовместными одновременно - редкий, но возможный случай.

Эти соотношения тоже следствие слабой теоремы и удобны для диагностики: если при решении симплекс-методом обнаружилась неограниченность, можно сразу заключить, что двойственная задача не имеет допустимых точек, и наоборот.

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

• Путают направление оптимизации. Двойственная к задаче на максимум - это задача на минимум, и наоборот. Если оставить тот же тип цели, все знаки и оценки получатся бессмысленными.
• Неверно сопоставляют знаки переменных и ограничений. Ограничению $\ge$ в задаче на максимум соответствует $y_i \le 0$, а не $y_i \ge 0$. Лучше один раз привести к канонической форме, чем угадывать.
• Забывают про дополняющую нежёсткость при восстановлении решения. Нельзя просто приравнять все ограничения к равенствам - активны лишь те, у которых двойственная цена положительна.
• Считают зазор двойственности ненулевым. Для линейного программирования в оптимуме $b^\top y^* - c^\top x^* = 0$ всегда. Положительный зазор - признак ошибки в расчётах.
• Трактуют теневую цену глобально. Оценка $y_i^*$ показывает прирост оптимума лишь локально - пока изменение $b_i$ не меняет набор активных ограничений (базис).

FAQ

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

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

Как по решению прямой задачи найти решение двойственной? Используя условия дополняющей нежёсткости. По оптимальному $x^*$ определяют, какие ограничения прямой задачи активны и какие переменные положительны, выписывают соответствующие равенства для $y^*$ и решают полученную систему. Альтернатива - взять двойственные оценки прямо из финальной симплекс-таблицы.

Коротко

Теорема двойственности линейного программирования связывает прямую задачу с двойственной, где переменные и ограничения меняются ролями, а матрица транспонируется. Слабая теорема даёт оценку $c^\top x \le b^\top y$ для любых допустимых решений; сильная теорема гарантирует точное равенство оптимумов $c^\top x^* = b^\top y^*$ при конечном решении. Теорема о дополняющей нежёсткости связывает активность ограничений с положительностью двойственных переменных, а сами эти переменные имеют смысл теневых цен - предельной ценности ресурсов. Вместе эти результаты делают двойственность не формальным приёмом, а рабочим инструментом оценки решений и экономического анализа.