Двойственность в линейном программировании
Двойственность — это фундаментальная концепция оптимизации, которая утверждает, что каждой прямой задаче линейного программирования можно поставить в соответствие другую задачу, называемую двойственной, причём эти две задачи связаны глубокими математическими и экономическими соотношениями; двойственность не является просто формальным приёмом, а отражает двойственную природу любого оптимизационного выбора: любое решение о производстве или распределении ресурсов одновременно является решением об оценке этих ресурсов, и именно эта симметрия позволяет получить не только само оптимальное решение, но и его содержательную интерпретацию в терминах теневых цен, а также даёт мощные инструменты для анализа чувствительности и проверки оптимальности.
Двойственная задача — это специальным образом построенная оптимизационная задача, которая получается из исходной прямой задачи путём транспонирования матрицы коэффициентов, замены ролей переменных и ограничений, а также обращения целевой функции с максимизации на минимизацию или наоборот; в двойственной задаче переменные соответствуют ограничениям прямой задачи и интерпретируются как оценки единиц ресурсов, а ограничения двойственной задачи соответствуют переменным прямой задачи и требуют, чтобы стоимость ресурсов, затрачиваемых на производство единицы каждого продукта, была не ниже прибыли от этого продукта, что делает двойственную задачу не просто математическим конструктом, а содержательной моделью ценообразования в экономике.
Двойственность в работе отвечает на управленческие вопросы — какие ресурсы дефицитны, где выгоднее расширять мощности и как оценивать чувствительность плана без полного пересчёта с нуля.
Эта глава переводит фокус с механики "получить оптимум" на аналитику "объяснить оптимум". Здесь появляется язык теневых цен и экономической интерпретации ограничений для отчётов, планирования и защиты решений перед бизнесом.
Если после чтения вы выписываете двойственную задачу и поясняете смысл y* в терминах ресурсов, цель главы выполнена.
У каждой задачи линейного программирования есть парная двойственная задача. Связь между ними объясняет "цены" ресурсов в оптимуме, условия оптимальности без перебора вершин и то, почему в последней симплекс-таблице (статья 4) появляются оценки ограничений.
Двойственная задача - экономический смысл для новичка
| Вопрос | Ответ через двойственность |
|---|---|
| Сколько "стоит" ещё один час станка? | y₁* — маржинальная ценность 1-го ресурса в оптимуме |
| Можно ли улучшить план без пересчёта всей таблицы? | если приведённая стоимость продукта > 0 — ввод продукта ещё выгоден |
Почему Z* из прямой = W* из двойственной? | сильная двойственность — два взгляда на одну и ту же оптимальную точку |
Прямая отвечает — "сколько произвести". Двойственная — "как оценить дефицит ресурсов", чтобы ни один продукт не был "занижен" относительно его коэффициента в цели.
Маржинальная ценность — это показатель, который в контексте двойственности характеризует, на сколько изменится оптимальное значение целевой функции прямой задачи при небольшом изменении правой части соответствующего ограничения, то есть при изменении доступного количества конкретного ресурса на одну единицу; эта ценность равна оптимальному значению соответствующей двойственной переменной и имеет фундаментальный экономический смысл предельной полезности ресурса: она показывает, сколько максимально можно заплатить за дополнительную единицу данного ресурса, чтобы увеличение затрат не превысило прироста результата, и именно благодаря этому понятию двойственные переменные часто называют теневыми ценами или объективно обусловленными оценками.
1-й ресурс — это условное обозначение для первого ограничения в системе прямой задачи, которое обычно соответствует некоторому дефицитному фактору производства, такому как рабочее время, сырьё, оборудование или бюджет, причём в двойственной задаче ему соответствует первая двойственная переменная, показывающая маржинальную ценность именно этого ресурса; анализ первого ресурса, как и всех остальных, позволяет определить, является ли ограничение активным в оптимальной точке, то есть используется ли ресурс полностью, или имеется его избыток, и если ресурс не активен, то его теневая цена равна нулю, что означает, что дополнительные количества этого ресурса не могут улучшить целевой результат, тогда как дефицитный ресурс получает положительную теневую цену.
Парная постановка — это способ представления задачи линейного программирования вместе с её двойственной в виде единой симметричной пары, где оба объекта записаны в сопоставимой форме, с выделением матрицы коэффициентов, векторов целевых коэффициентов и правых частей, причём такая парная запись подчёркивает их структурное родство и позволяет легко переходить от одной задачи к другой по формальным правилам; парная постановка особенно полезна при изучении теорем двойственности, поскольку она наглядно демонстрирует, как ограничения одной задачи соответствуют переменным другой, а целевой вектор одной становится вектором правых частей другой, и наоборот, что делает отношения между ними прозрачными и удобными для анализа.
Прямая и двойственная задачи (схема)
Прямая — это исходная, первичная задача линейного программирования, которая формулируется непосредственно из реальной экономической или инженерной ситуации и содержит переменные решения, целевую функцию и ограничения в их естественной постановке, например, максимизация прибыли при ограничениях на ресурсы; прямая задача является той, с которой начинается весь анализ, и для неё строится двойственная, причём все теоремы двойственности формулируются именно относительно пары «прямая — двойственная», и в учебной практике обычно прямая задача решается симплекс-методом, а двойственная используется для интерпретации, хотя возможен и обратный порядок, когда проще решить двойственную задачу, если она имеет меньше ограничений или более удобную структуру.
Зачем получать двойственность из прямой — это вопрос о прагматической и теоретической ценности построения двойственной задачи, и ответ включает несколько аспектов: во-первых, двойственная задача часто имеет меньшую размерность, что упрощает вычисления; во-вторых, её решение даёт теневые цены ресурсов, что позволяет экономически интерпретировать результат и принимать решения об инвестициях в дополнительные ресурсы; в-третьих, двойственность предоставляет мощный критерий оптимальности через условия дополняющей нежёсткости, которые позволяют проверить любое кандидатное решение на оптимальность без полного перебора; в-четвёртых, двойственные оценки используются в анализе чувствительности, чтобы понять, как изменения параметров задачи повлияют на оптимальное решение; и наконец, в-пятых, многие современные алгоритмы, включая методы декомпозиции и внутренней точки, активно используют двойственную структуру для повышения эффективности и устойчивости вычислений.
Для прямой в форме максимизации —
max Z = cᵀx
при Ax ≤ b
x ≥ 0
Двойственная (стандартная парная постановка) —
min W = bᵀy
при Aᵀy ≥ c
y ≥ 0
y — вектор двойственных переменных, по одной на каждое ограничение прямой задачи.
| Прямая | Двойственная |
|---|---|
переменные xⱼ (объёмы) | ограничения с cⱼ |
ограничения Ax ≤ b (ресурсы) | переменные yᵢ (оценки ресурсов) |
max | min |
RHS bᵢ — запасы | коэффициенты цели bᵢ |
Правило памяти — "столбец прямой → строка двойственной", знаки неравенств меняются при переходе max↔min.
Правило памяти — это мнемоническое правило, которое помогает быстро и без ошибок построить двойственную задачу для произвольной прямой задачи линейного программирования, и оно гласит: если прямая задача имеет m ограничений и n переменных, то двойственная будет иметь n ограничений и m переменных, при этом матрица коэффициентов транспонируется, вектор целевых коэффициентов меняется местами с вектором правых частей, а направление оптимизации меняется на противоположное, причём для каждого ограничения прямой задачи типа «≤» соответствующая переменная двойственной задачи будет неотрицательной, для типа «≥» — неположительной, а для равенства — свободной; это правило сводит потенциально сложную процедуру построения двойственной задачи к последовательности простых механических операций, что делает её доступной даже для начинающих.
max↔min — это ключевое правило трансформации при переходе от прямой задачи к двойственной, которое утверждает, что если прямая задача решается на максимум, то двойственная будет решаться на минимум, и наоборот, причём это обращение оптимизационного направления является не произвольным соглашением, а следствием фундаментальной теоремы двойственности, которая гарантирует равенство оптимальных значений обеих задач; эта замена направления не просто меняет знак, а перестраивает всю логику: задача оценки ресурсов (минимизация затрат на их приобретение) становится естественным двойником задачи их использования (максимизация выпуска или прибыли), и именно это взаимное обращение придаёт двойственности её глубокий экономический смысл.
Как получить двойственную из прямой
Для max Z = cᵀx, Ax ≤ b, x ≥ 0 —
- Введите по одной переменной
yᵢ ≥ 0на каждое ограничениеi(тип≤при max). - Цель двойственной —
min W = b₁y₁ + b₂y₂ + …— коэффициентыbᵢиз правых частей прямой. - Для каждого
xⱼ(столбецA) запишите неравенство —a₁ⱼy₁ + a₂ⱼy₂ + … ≥ cⱼ(знак≥при max в прямой). - Направление оптимизации — min у
W, если прямая была max.
Разбор первого двойственного ограничения для продукта x₁ (коэффициент в цели c₁=3) —
2y₁ + y₂ ≥ 3
Читается — "взвешенная цена ресурсов (2 единицы ресурса 1 + 1 единица ресурса 2) должна быть не ниже выгоды от единицы продукта A". В оптимуме часто выполняется равенство — продукт "на грани выгодности".
Пример на задаче станков
Прямая (введение) —
max Z = 3x₁ + 2x₂
2x₁ + x₂ ≤ 8
x₁ + 2x₂ ≤ 8
x ≥ 0
Двойственная —
min W = 8y₁ + 8y₂
2y₁ + y₂ ≥ 3
y₁ + 2y₂ ≥ 2
y₁, y₂ ≥ 0
Смысл yᵢ — "сколько стоит" единица i-го ресурса в оптимальном плане (тень цены, shadow price). Если ресурс 1 полностью использован (2x₁+x₂=8), в оптимуме обычно y₁ > 0; если есть запас — часто y₁ = 0.
Численное решение двойственной (из симплекса)
Оптимум прямой (симплекс) — Z* = 40/3, x₁* = x₂* = 8/3, s₁* = s₂* = 0 (оба ресурса на пределе).
Двойственные оценки (из строки −Z оптимальной таблицы при slack в небазисе) —
y₁* = 4/3, y₂* = 1/3
Проверка сильной двойственности — W* = 8y₁* + 8y₂* = 64/3 + 8/3 = 40/3 = Z*.
Проверка двойственных неравенств (должны выполняться с равенством в оптимуме) —
2y₁* + y₂* = 8/3 + 1/3 = 3 = c₁ ✓
y₁* + 2y₂* = 4/3 + 2/3 = 2 = c₂ ✓
Дополняющая нежёсткость на этом примере
| Переменная / ограничение | Значение в оптимуме | Следствие |
|---|---|---|
s₁ = 0, s₂ = 0 | оба ресурса исчерпаны | оба ограничения активны → y₁* > 0, y₂* > 0 |
x₁, x₂ > 0 | оба продукта в плане | оба двойственных ограничения по продуктам — равенства (2y₁+y₂=3, y₁+2y₂=2) |
Если бы s₁ > 0 | остаток по 1-му ресурсу | по дополняющей нежёсткости ожидали бы y₁* = 0 |
Практический вывод для IT — если увеличить лимит второго ресурса на 1 единицу, в линейной модели прибыль вырастет примерно на y₂* ≈ 0,33; лимит первого — на ≈ 1,33 (пока базис не сменился).
Принципы двойственности
1. Слабая двойственность
Если x допустима для прямой, y — для двойственной, то
cᵀx ≤ bᵀy (для пары max/min)
Прямое значение не превосходит двойственное (для стандартной пары).
2. Сильная двойственность
Если одна из задач имеет конечный оптимум, то и вторая тоже, и
Z* = W*
Оптимальные значения совпадают — главный практический факт.
3. Дополняющая нежёсткость
В оптимуме —
- если
xⱼ > 0, соответствующее двойственное ограничение — равенство; - если ограничение прямой неравно как равенство (запас ресурса), соответствующая
yᵢ = 0.
Это аналог "либо нагрузка, либо цена нуля" в экономике и "либо переменная, либо оценка" в алгоритме.
4. Несовместность и неограниченность
| Прямая | Двойственная |
|---|---|
| неограничена (max → ∞) | несовместна |
| несовместна | неограничена или несовместна (в зависимости от формы) |
Экономическая интерпретация
Прямая — "сколько произвести продуктов, чтобы максимизировать выручку при лимитах ресурсов".
Двойственная — "какие внутренние цены ресурсов минимизируют оценку плана, не занижая "ценность" каждого продукта".
В IT-аналогии — yᵢ — маржинальная ценность ещё одной единицы CPU-часа или ГБ RAM в узком месте кластера.
Двойственность и симплекс-таблица
В оптимальной симплекс-таблице прямой задачи (max, форма ≤, строка −Z + cᵀx = 0) —
| Где смотреть | Что получаем |
|---|---|
Коэффициент в строке −Z при slack sᵢ (не в базисе) | yᵢ* = −(коэффициент) при нашей конвенции (в примере: −(−4/3) = 4/3) |
Коэффициент при небазисном xⱼ | приведённая стоимость — если > 0, ввод xⱼ ещё улучшит Z |
RHS строки −Z | −Z* (оптимальное значение с обратным знаком) |
Поэтому после ручного симплекса можно прочитать двойственное решение из последней таблицы — без отдельного решения двойственной задачи.
Двойственный симплекс-метод
Прямой симплекс на каждом шаге держит допустимый план (RHS ≥ 0) и улучшает цель. Двойственный симплекс стартует с таблицы, где строка цели уже "оптимальна" (для max — нет улучшения по небазисным в вашей конвенции), но правая часть одной или нескольких строк отрицательна — план недопустим.
Типичные ситуации —
- после изменения запасов
bᵢв уже решённой задаче; - завершение двухфазного метода, когда фаза 1 вывела искусственные переменные, а RHS ещё нужно поправить;
- чувствительный анализ — "что если лимит ресурса ужесточили на Δ единиц".
Двойственная допустимость (правильные знаки в строке Z) сохраняется на каждом шаге; восстанавливается прямая допустимость (неотрицательный RHS). Отсюда название метода.
Когда применять и когда нет
| Ситуация | Двойственный симплекс | Прямой симплекс / фаза 1 |
|---|---|---|
Оптимальная Z-строка, есть RHS < 0 | да | прямой не стартует |
RHS ≥ 0, в Z есть улучшение | нет | да |
Нет ни допустимого, ни "оптимального" Z | сначала довести Z (этап 1 в учебниках) или фаза 1 | |
| Задача несовместна | алгоритм сигнализирует (нет положительного pivot) | то же на фазе 1 |
Два этапа
Алгоритм разбит на два этапа — сначала приводят строку Z к виду "как в оптимуме", затем выправляют столбец свободных членов.
Этап 1 — двойственная допустимость (строка Z)
Для задачи минимизации (как в классических симплекс-таблицах) —
- Если все коэффициенты в
Z-строке неотрицательны → переход к этапу 2. - Иначе выбирают столбец с отрицательным коэффициентом в
Z. - В этом столбце ищут отрицательный элемент ограничения → разрешающая строка. Если отрицательных нет → решений нет.
- Считают двойственные отношения — отношения элементов
Z-строки к элементам разрешающей строки (только там, где знаменатель подходит по принятой конвенции); минимум задаёт входящий столбец. - Один шаг Жордана → повтор с п. 1.
Для максимизации в нашей конвенции (−Z + cᵀx = 0) этап 1 часто уже выполнен в оптимальной таблице прямой задачи — тогда сразу работают этапом 2.
Этап 2 — прямая допустимость (столбец RHS)
- Если все
RHS ≥ 0→ оптимум (при уже "хорошей"Z-строке). - Иначе выбирают строку с наименьшим (самым отрицательным)
RHS— разрешающая строка. - В этой строке ищут разрешающий столбец по наименьшему двойственному отношению (отношения элементов
Z-строки к положительным элементам разрешающей строки). Если положительных нет → задача неограничена / несовместна в постановкеmin. - Жордановский шаг → снова п. 1 этапа 2.
Чтобы искать максимум двойственным симплексом в стандартной таблице, переходят к min (−Z) и берут ответ с обратным знаком из свободного члена F-строки — так же, как при сведении min к max в постановке.
Мини-пример (логика этапа 2)
Задача уже решена симплексом: Z* = 40/3, оба ресурса на пределе. Руководство уменьшает второй лимит с 8 до 5 — в таблице появляется строка с RHS = −1 (план формально недопустим), а коэффициенты в Z-строке остаются как в оптимуме.
Действия —
- Выходящая строка — с отрицательным
RHS. - Входящий столбец — по минимальному двойственному отношению среди положительных коэффициентов в этой строке (часто "возвращается" slack или продукт, который ослабит нарушение).
- После одного–двух жордановых шагов
RHSснова неотрицателен → новыйZ*без полного пересчёта с нуля.
Численные таблицы для тренировки — в типовых задачах на двойственный симплекс; здесь важна схема: сохраняем "оптимальность" строки цели, чиним запасы.
Сравнение с прямым симплексом
| Прямой | Двойственный | |
|---|---|---|
| Что сохраняем | допустимость x | "оптимальность" Z-строки |
| Что чиним | значение цели | отрицательные RHS |
| Типичный старт | slack-базис | оптимальная таблица после Δb |
Постановка двойственной "по строкам"
Для каждого ограничения прямой —
| Прямое (max) | Двойственное (min) |
|---|---|
≤ bᵢ | переменная yᵢ ≥ 0 |
= bᵢ | yᵢ свободная (любой знак) |
≥ bᵢ | yᵢ ≤ 0 |
Для каждой переменной прямой —
| Прямая | Двойственное |
|---|---|
xⱼ ≥ 0 | j-е ограничение: ≥ cⱼ |
xⱼ свободная | j-е ограничение: = cⱼ |
xⱼ ≤ 0 | j-е ограничение: ≤ cⱼ |
При ручном разборе двойственную выписывают механически, затем проверяют размерность — число y = число ограничений прямой.
Двойственность в ЛП - связь прямой и двойственной задачи
| Применение | Пояснение |
|---|---|
| Чувствительность | как меняется Z*, если ослабить одно ограничение (Δb) |
| Верификация | нижняя/верхняя оценка оптимума из допустимых x и y |
| Алгоритмы | двойственный симплекс (старт с "почти оптимальной" таблицы) |
| Транспортная | метод потенциалов — двойственные uᵢ, vⱼ |
Чувствительность — как читать изменения ресурсов
Если базис не меняется, двойственная оценка yᵢ* даёт линейное приближение —
ΔZ ≈ yᵢ* · Δbᵢ
Это очень полезно в планировании —
- оценить, стоит ли "покупать" дополнительный ресурс;
- понять, какой лимит является настоящим bottleneck;
- быстро приоритизировать инвестиции без полного пересчёта десятков сценариев.
При больших изменениях b базис может смениться, и линейная оценка перестанет быть точной. Тогда модель нужно решать заново.
Быстрый алгоритм проверки пары (x, y)
- Проверить допустимость
xв прямой. - Проверить допустимость
yв двойственной. - Сравнить
cᵀxиbᵀy(слабая двойственность). - Если значения равны, а обе точки допустимы - это оптимум.
Связь с транспортной задачей
Транспортная ЗЛП — разреженная структура A. Двойственные переменные разбивают на потенциалы поставщиков uᵢ и потребителей vⱼ; условие оптимальности uᵢ + vⱼ ≤ cᵢⱼ — прямое следствие двойственности.
Дальше — транспортная задача.