Потенциалы обобщённой сети и сертификат оптимальности

Если умеешь получить потенциалы из одного параметра, переходи к «Теперь сам».

Крючок: где забыли множитель

Как думаешь, можно ли сохранить обычную цену c-π(i)+π(j), заменив только балансы? Пусть дуга превращает одну единицу в две. У конечного узла каждая полученная единица имеет оценку π(j), значит, приход изменяет оценку на 2π(j). Без двойки приведённая цена сравнивает разные физические количества. Проверка по такому сертификату способна объявить выгодное изменение невыгодным.

В этой главе используем знак потенциалов из формулы c-π(i)+μπ(j). В предыдущих уроках обычных потоков могло встречаться соглашение c+π(i)-π(j). Они переходят друг в друга заменой π на -π. Внутри одного вычисления знак не меняем.

На что это похоже: внутренние оценки ресурсов

Представь бухгалтерские оценки единицы ресурса на каждом складе. Отправка тратит одну местную единицу, получение приносит μ конечных единиц. К прямой цене перевозки добавляем разницу этих оценок. Сами оценки не меняют реальный план и цену сравнения допустимых планов: их вклад зависит только от фиксированных балансов. Зато правильно выбранные оценки делают видимым направление возможного улучшения.

Механизм: почему сертификат работает

Обозначим приведённую цену r(i,j)=c(i,j)-π(i)+μ(i,j)π(j). Сумма r·x равна сумме c·x минус сумма π(i)b(i). Это следует группировкой: при каждом π(i) исходящие потоки дают минус, входящие с множителем дают плюс. Так как для всех допустимых x вектор b одинаков, разность между двумя целями постоянна. Поэтому минимизация исходной и приведённой цены даёт одинаковые планы.

Для кандидата x потребуем: если x=0, то r≥0; если x=u, то r≤0; если 0<x<u, то r=0. Для любой другой допустимой точки x разность приведённых целей есть сумма r(x-x). На нижней границе x-x≥0, поэтому произведение неотрицательно. На верхней x-x≤0 и r≤0, произведение снова неотрицательно. Во внутренней точке произведение нулевое. Вся сумма ≥0, значит, x не дороже x. Это достаточное доказательство оптимальности.

При u=0 дуга фиксирована и её вклад в любую разность равен нулю; не нужно одновременно требовать от её цены оба знака. В алгоритме такие дуги можно убрать. Для структуры F,L,U задаём r=0 на всех F, даже если часть базисных дуг случайно попала на границу. Такая более сильная система служит основой симплексного шага.

Правило: распространяй аффинные выражения

Положи π(root)=θ. По дереву для дуги i→j из r=0 получаем π(j)=(π(i)-c)/μ. Для дуги j→i получаем π(j)=c+μπ(i). Каждое значение имеет вид f+gθ, то есть константа плюс коэффициент при одном неизвестном. Дополнительная дуга a→b даёт уравнение c-π(a)+μπ(b)=0. На хорошем дереве его коэффициент при θ ненулевой, и θ определяется однозначно.

Разбор: две вершины, один параметр

В F входят A→B с μ=2,c=3 и B→A с μ=3/4,c=1. Выберем корень A, дополнительной вторую дугу. По первой π(B)=(θ-3)/2. Из второй 1-(θ-3)/2+(3/4)θ=0. Получаем 2.5+0.25θ=0, откуда θ=-10. Значит, π(A)=-10,π(B)=-6.5.

Проверяем первую цену: 3-(-10)+2·(-6.5)=0. Вторую: 1-(-6.5)+(3/4)·(-10)=0. В прошлой главе эти дуги несли x=4,y=8 для b(A)=-2,b(B)=0; исходная цена 3·4+1·8=20. Приведённая цель ноль, а постоянная сумма πb=(-10)·(-2)=20. Числа совпали с доказанной связью.

# generalized_potentials.py
from fractions import Fraction as F
pi_a = F(-10)
pi_b = (pi_a - 3) / 2
r_ab = 3 - pi_a + 2 * pi_b
r_ba = 1 - pi_b + F(3, 4) * pi_a
print(pi_a, pi_b, r_ab, r_ba)
# -10 -13/2 0 0
x_ab = F(4)
x_ba = F(8)
b_a = x_ab - F(3, 4) * x_ba
b_b = x_ba - 2 * x_ab
actual = 3 * x_ab + x_ba
shifted = r_ab * x_ab + r_ba * x_ba
constant = pi_a * b_a + pi_b * b_b
assert actual == shifted + constant
print(actual, constant)
# 20 20

Разбор: проверяем небазисную дугу

Добавим параллельную дугу A→B с множителем один. Если её цена четыре, приведённая цена равна 4+10-6.5=7.5. На нижней границе ноль это нужный знак: увеличение только этой переменной при восстановлении остальных не улучшит цель. Если она уже на верхней границе, знак неверен: уменьшение потока может улучшить план, такая дуга имеет право войти в базис.

Если цена новой дуги равна -5, получаем -5+10-6.5=-1.5. На нуле это нарушение: алгоритм попробует увеличить поток на ней. Положительная исходная цена не гарантирует положительную приведённую, как и отрицательная исходная не гарантирует отрицательную: оценки в вершинах учитывают все способы перестроить базисный поток. Чтобы объявить оптимум, проверяем все небазисные дуги и сами балансы, а не только одну удобную цену.

Механизм: ненулевой знаменатель

Если обойти единственный цикл, последовательная подстановка потенциалов возвращает выражение θ=K+Lθ, где L равен обратному множителю цикла либо самому множителю, в зависимости от выбранного обхода. Единственность требует 1-L≠0, что равносильно μ(W)≠1. Поэтому хорошесть леса нужна и для потоков, и для потенциалов. При сохраняющем цикле система r=0 либо противоречива, либо допускает свободный сдвиг: однозначного θ не будет.

Обход дерева посещает каждую вершину и дугу один раз. Представление f+gθ хранит два числа на вершину. Поэтому вычисление потенциалов занимает O(n) арифметических операций на весь лес, если корни и порядок обхода известны. Если коэффициенты рациональные, длина их записи может расти; арифметическая оценка не равна числу битовых операций.

Что ломается при проверке одной двойственной стороны

Нулевые цены F могут существовать даже для потока с отрицательной базисной переменной. Такой поток недопустим и оптимальность не доказана. С другой стороны, допустимость без правильных знаков небазисных дуг тоже не сертификат. Удобный отчёт проверяющего хранит отдельно максимальное нарушение баланса, нарушение границ и нарушение приведённых знаков. Тогда ошибка указывает, какую часть доказательства нужно восстановить.

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

Потенциалы позволяют проверить ответ решателя, не повторяя весь путь его поиска. Для небольшой сети ты можешь сохранить x и π как сертификат, а проверяющий за линейный проход подтвердит балансы, границы и знаки. Это особенно полезно, когда сравнение с перебором уже невозможно, а доверять только сообщению «решено» недостаточно.

Теперь сам

При π(A)=-10,π(B)=-6.5 найди цену c новой дуги A→B с μ=2, при которой её приведённая цена нулевая. Ответ: c+10-13=0, поэтому c=3. При c=2 дуга на нижней границе нарушает условие оптимальности, при c=4 знак соответствует нижней границе. Сначала умножь конечный потенциал на μ, затем сравни знак.