Двойственность: у каждой задачи есть задача-свидетель

Если ты умеешь построить двойственную задачу, доказать слабую двойственность в одну строку и объяснить, почему max-flow/min-cut - частный случай, листай до «Теперь сам».

Как думаешь, откуда берётся верхняя граница

Цех из прошлых уроков: максимизировать 5x + 4y при 2x + 3y <= 12 и 4x + y <= 10. Не решая задачу, докажи, что прибыль не больше 25.

Вот способ: умножь первое ограничение на 1, второе на 1 и сложи: 6x + 4y <= 22. Цель 5x + 4y не больше левой части (коэффициенты не меньше при x, y >= 0), значит прибыль не больше 22. Уже лучше 25. А можно ли подобрать множители так, чтобы граница стала точной? Вот это и есть двойственная задача.

На что это похоже

Спор двух сторон. Одна говорит: «я умею получить вот столько» - и предъявляет план. Другая: «больше столько-то получить нельзя» - и предъявляет расчёт, который это доказывает. Пока их числа не совпали, спор продолжается: либо план не лучший, либо расчёт не самый жёсткий. Совпали - спор окончен, и обе стороны правы. Ровно это мы уже видели с потоком и разрезом.

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

ПРЯМАЯ                              ДВОЙСТВЕННАЯ
максимизировать cᵀx                 минимизировать bᵀy
при Ax <= b                         при Aᵀy >= c
   x >= 0                              y >= 0

переменных n, ограничений m         переменных m, ограничений n

Каждому ОГРАНИЧЕНИЮ прямой задачи соответствует ПЕРЕМЕННАЯ двойственной - множитель, с которым это ограничение входит в оценку. Каждой переменной прямой - ограничение двойственной.

Про обозначения: Aᵀ - это транспонированная матрица, то есть та же таблица, у которой строки и столбцы поменялись местами (Aᵀ[j][i] = A[i][j]); запись cᵀx означает обычную сумму c₁x₁ + ... + cₙxₙ. Именно транспонирование и превращает «строка ограничения» в «столбец коэффициентов при переменной».

слабая двойственность (доказательство в одну строку):
    cᵀx <= (Aᵀy)ᵀx = yᵀ(Ax) <= yᵀb = bᵀy
    первое «<=» - из Aᵀy >= c и x >= 0
    второе «<=» - из Ax <= b и y >= 0

сильная двойственность:
    если у прямой задачи есть конечный оптимум, то он есть и у двойственной,
    и значения РАВНЫ

дополняющая нежёсткость (две половины, работают обе):
    ограничение прямой задачи НЕ активно  ⇒  двойственная переменная при нём = 0
    переменная прямой задачи ПОЛОЖИТЕЛЬНА ⇒  двойственное ограничение при ней - равенство
    (и то же самое в обратную сторону, если поменять задачи местами)

Дополняющая нежёсткость читается по-человечески: у ресурса, который не израсходован полностью, теневая цена равна нулю. Логично - лишний час станка, который и так простаивает, ничего не стоит.

Правило

У каждой линейной задачи есть двойственная: ограничения становятся переменными, переменные - ограничениями, максимум - минимумом. СЛАБАЯ ДВОЙСТВЕННОСТЬ: cᵀx <= bᵀy для любых допустимых x и y, поэтому любое допустимое решение двойственной задачи доказывает верхнюю границу для прямой. СИЛЬНАЯ ДВОЙСТВЕННОСТЬ: в оптимуме значения совпадают. Двойственные переменные - теневые цены ресурсов, и по дополняющей нежёсткости у неисчерпанного ресурса цена нулевая. Теорема о максимальном потоке и минимальном разрезе и теорема Кёнига - частные случаи сильной двойственности.

Разбор: двойственная задача для цеха

Прямая: максимизировать 5x + 4y при 2x + 3y <= 12 (станок), 4x + y <= 10 (сборка).

Двойственные переменные: u - цена часа станка, v - цена часа сборки.

минимизировать 12u + 10v
    2u + 4v >= 5        изделие 1: его ресурсы должны стоить не меньше прибыли
    3u +  v >= 4        изделие 2: то же самое
    u >= 0,  v >= 0

Смысл ограничений: если бы ресурсы, уходящие на изделие, стоили ДЕШЕВЛЕ прибыли от него, их выгодно было бы пустить в дело, а не продавать. Оптимальные цены - те, при которых этого соблазна нет ни для одного изделия, и при этом суммарная стоимость запасов минимальна.

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

2u + 4v = 5
3u +  v = 4      →  v = 4 − 3u  →  2u + 16 − 12u = 5  →  u = 1.1,  v = 0.7

значение двойственной: 12·1.1 + 10·0.7 = 13.2 + 7 = 20.2
значение прямой:        5·1.8 + 4·2.8  = 9 + 11.2  = 20.2      совпало

Числа 1.1 и 0.7 - не абстракция, это готовый ответ на вопрос «что докупать». Лишний час станка добавит к прибыли 1.1, лишний час сборки - 0.7. Если час станка на рынке стоит дешевле 1.1, его надо брать; дороже - не надо. Ни одного дополнительного вычисления для этого не потребовалось: теневые цены выпали из той же задачи.

Разбор: поток и разрез - это двойственная пара

Запишем максимальный поток как линейную задачу: переменные - потоки по рёбрам f(u,v), цель - максимум величины, ограничения - ёмкости и сохранение.

Двойственная к ней задача выглядит так: каждой вершине приписывается число, каждому ребру - неотрицательная переменная, а минимизируется сумма c(u,v) по рёбрам с единицей. В оптимуме эти числа оказываются нулями и единицами: единица означает «вершина слева от разреза». То есть двойственное решение - это и есть разрез, а сильная двойственность превращается в теорему о максимальном потоке и минимальном разрезе.

прямая задача:      максимальный поток          |f|
двойственная:       минимальный разрез          c(S, T)
слабая двойственность:  |f| <= c(S, T)          урок первой главы
сильная:                max |f| = min c(S, T)   теорема Форда-Фалкерсона

Почему решение двойственной оказалось целым, хотя линейная задача про целость ничего не обещает: у матрицы ограничений потока есть свойство полной унимодулярности - любой её квадратный минор (определитель квадратного куска, вырезанного из матрицы) равен 0, 1 или −1. У таких матриц ВСЕ вершины многогранника целые, поэтому и поток, и разрез выходят целыми сами собой. То же свойство у матрицы двудольного паросочетания - отсюда и теорема Кёнига, и честные ответы «да/нет» в задачах о назначениях.

А вот когда матрица не унимодулярна, дробные вершины возвращаются, и задача с требованием целых значений становится NP-трудной. Именно поэтому «линейное программирование - легко, целочисленное - трудно» и не противоречит тому, что поток всегда целый.

Что ломается без этого

Первое: строить двойственную задачу, забыв поменять направление неравенств или знак цели, - тогда слабая двойственность перестаёт выполняться, и проверить себя нечем. Второе: считать теневую цену у ресурса, который израсходован не полностью: она нулевая по дополняющей нежёсткости, и «цена» из решателя в этом случае говорит лишь о вырожденности. Третье: применять теневые цены к большим изменениям: они верны ЛОКАЛЬНО, пока набор активных ограничений не поменялся; докупив сто часов станка, пересчитывать надо заново. Четвёртое: ожидать целых решений от произвольной линейной задачи - целость даёт структура матрицы, а не сам метод. Пятое: путать сильную двойственность с «всегда есть оптимум»: если прямая задача несовместна, двойственная бывает неограниченной, и это законная пара исходов.

Зачем это в работе

Двойственность - это способ ДОКАЗАТЬ ответ, а не только получить его. В переговорах, отчётах и код-ревью «вот решение и вот сертификат его оптимальности» звучит иначе, чем «программа так посчитала». Теневые цены из двойственной задачи прямо отвечают на вопросы планирования: какой ресурс расширять первым, сколько мы готовы заплатить за дополнительную мощность, какие ограничения вообще ни на что не влияют. Решатели возвращают двойственные переменные вместе с решением - это поле в ответе, которое многие не читают, а зря. И, наконец, двойственность - основной инструмент доказательств в самом курсе: три теоремы этого раздела (поток и разрез, Кёниг, Холл) - три проявления одного факта.

Теперь сам

Построй двойственную задачу к такой: максимизировать 3x + 5y при x + y <= 8, 2x + y <= 10, x, y >= 0. Проверь слабую двойственность на паре x = 2, y = 6 и u = 5, v = 0. Что эта пара доказывает, а что нет?