Линеаризация: параллельные дуги и длина входа

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

Крючок: дешёвая третья партия

Как думаешь, нужно ли запрещать использовать дорогой тариф раньше дешёвого отдельным ограничением? На участке перевозки первые две партии стоят по одному, следующие три - по четыре, последняя - по семь. Сделаем три параллельные дуги с ёмкостями 2,3,1 и ценами 1,4,7. Балансы не различают эти дуги: у них одинаковые концы. Если решение использует дорогую дугу, пока дешёвая свободна, можно перенести между ними часть потока и снизить цену, сохранив все балансы.

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

Представь купоны на перевозку с разными тарифами. Каждый купон разрешает перевозить фиксированное число партий. Для заданной суммы партий ты выбираешь доступные дешёвые купоны. Порядок выдачи купонов не важен; важны их пределы и цены. Выпуклость исходного тарифа как раз означает, что следующая группа купонов не дешевле предыдущей. В модели со скидкой за объём такой свободный выбор уже искажает смысл тарифа.

Механизм: разложение одной дуги

Пусть точки излома равны 0=q₀<q₁<…<qₖ=u, а наклоны участков s₁≤…≤sₖ. Константу C(0) временно вычтем. Заменяем исходную дугу k параллельными. У дуги r ёмкость qᵣ-qᵣ₋₁, цена sᵣ. Полный поток x через исходную дугу равен сумме потоков заменяющих дуг. Поскольку концы общие, узловые равенства сохраняются.

Решение назовём последовательным, если оно заполняет ранние участки до перехода к поздним; при равных ценах можно переупорядочить поток без изменения цели. Пусть поздняя дуга несёт положительный поток, а ранняя имеет остаток ёмкости. Перенесём минимум этих двух величин на раннюю. Баланс не изменится, цена не возрастёт, одна из двух дуг достигнет границы. Повторяя обмен, получим последовательное решение. Поэтому существует оптимальное последовательное решение, даже если решатель вернул другую раскладку на равных наклонах.

В последовательном решении первые участки заполнены, один может быть заполнен частично, остальные пусты. Его линейная цена равна C(x)-C(0), потому что сумма «длина пройденного участка × наклон» восстанавливает полную цену. Сведение работает в обе стороны: каждый исходный поток раскладывается последовательно, каждый оптимум линейной сети можно привести к такому виду и собрать обратно.

Правило: точность определяется точками

Для целых x используй qᵣ=r и sᵣ=C(r)-C(r-1). Тогда линейная сеть точно совпадает с ценой функции на всех допустимых целых значениях. Между целыми точками она задаёт линейную интерполяцию, которая может отличаться от исходной кривой. Не выдавай минимум интерполяции за точный непрерывный минимум исходной функции.

Разбор: тариф из трёх участков

Вернёмся к ёмкостям 2,3,1 и ценам 1,4,7. При потребности четыре заполняем первую дугу двумя партиями и вторую двумя. Цена 2·1+2·4=10. Использование первой и третьей по одной, второй двумя тоже даёт четыре, но стоит 1+8+7=16. Перенос единицы с третьей на первую уменьшает цену на шесть и восстанавливает последовательность.

При потребности шесть все участки заполнены, цена 2+12+7=21. Восстановленная функция равна x при x≤2, затем 2+4(x-2) до пяти, затем 14+7(x-5). Обрати внимание на число 14: это накопленная цена первых пяти партий. Если поставить третий участок как 7x, скачок в точке пять даст неверный тариф.

# tariff_segments.py
capacities = [2, 3, 1]
slopes = [1, 4, 7]
for need in [0, 1, 2, 4, 5, 6]:
    left = need
    total = 0
    allocation = []
    for capacity, slope in zip(capacities, slopes):
        take = min(left, capacity)
        allocation.append(take)
        total = total + take * slope
        left = left - take
    assert left == 0
    print(need, allocation, total)
# 0 [0, 0, 0] 0
# 1 [1, 0, 0] 1
# 2 [2, 0, 0] 2
# 4 [2, 2, 0] 10
# 5 [2, 3, 0] 14
# 6 [2, 3, 1] 21

Разбор: квадрат и цена явного раскрытия

Пусть C(x)=x², ёмкость четыре. Получаем четыре дуги ёмкости один с ценами 1,3,5,7. При x=3 линейная сумма 1+3+5=9 равна квадрату трёх. При дробном x=1.5 интерполяция платит 1+0.5·3=2.5, исходный квадрат равен 2.25. Сведение целой задачи верно; требовать совпадения между узлами сетки нельзя.

Теперь ёмкость равна 2²⁰. Формула квадрата осталась той же; запись ёмкости требует двадцать один двоичный разряд. Единичное раскрытие создаст 1 048 576 дуг вместо одной. При ёмкости 2⁴⁰ их число снова вырастет в миллион раз. Поэтому алгоритм с O(mU) дугами называют псевдополиномиальным относительно компактного входа: он полиномиален по численному U, а не по числу его разрядов.

Если же пользователь передал миллион различных участков явным списком, миллион дуг соответствует длине исходного входа. В этом случае применение полиномиального алгоритма линейного минимального потока остаётся полиномиальным по размеру данных. Нужно знать формат ввода, прежде чем читать оценку времени.

Что ломается при скидке за объём

Возьми C(0)=0,C(1)=5,C(2)=6. Приращения 5 и 1 убывают. Две свободные параллельные дуги предложат для одной партии цену один, хотя исходный тариф требует пять. Обмен дешёвого и дорогого участков больше не восстанавливает разрешённый порядок. Для вогнутой цены нужны другие методы, часто с дискретными решениями о включении мощности. Это не погрешность чисел: изменилась структура задачи.

Нижние границы тоже требуют аккуратного переноса. Если исходная дуга должна нести минимум l, сначала вычти обязательный поток и пересчитай балансы. Новая цена остатка равна C(l+y)-C(l), а не C(y). Именно сдвиг аргумента сохраняет нужные наклоны после обязательной поставки.

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

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

Теперь сам

Есть цена C(x)=(x-1)², x целый от нуля до трёх. Вычти C(0) и построй единичные дуги. Ответ: приращения -1,1,3, ёмкости все один. Для x=2 сумма приращений ноль, но исходная цена один: нужно вернуть вычтенную константу C(0)=1. Она не меняет оптимальный план, зато влияет на численную стоимость в отчёте.