Выпуклая стоимость: цена следующей единицы

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

Крючок: все машины на короткую дорогу?

Как думаешь, стоит ли отправлять четвёртый грузовик туда же, куда отправили первые три? Между складом и портом две дороги. На первой полный расход C₁(x)=x², на второй C₂(y)=3y. Нужно перевезти четыре целые партии. Первая дорога кажется дешёвой: при одной партии она стоит один. Но при четырёх расход равен шестнадцати. Для новой партии нужно сравнить новую плату, а уже потраченные деньги отдельно не помогают выбрать направление.

В обозначении x² квадрат означает x·x. Приращение квадрата равно (x+1)²-x²=2x+1: раскрываем скобки и сокращаем два одинаковых x². Именно это число платит планировщик за следующую целую партию. Оно растёт при увеличении x, поэтому первая дорога не останется дешёвой навсегда.

На что это похоже: очередь у станка

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

Механизм: отделяем множество потоков от цели

На дуге i→j переменная x означает число отправленных единиц, u - её ёмкость. В каждой вершине сумма исходящих x минус сумма входящих x равна b(i). Положительное b означает запас, отрицательное - потребность. На всех дугах 0≤x≤u. Цель - минимизировать сумму C по дугам. Здесь C каждой дуги зависит только от её собственного потока: такую цель называют разделимой. Цена, зависящая сразу от двух потоков, требует иной модели.

В непрерывном определении выпуклость означает: значение функции в точке между двумя аргументами не выше соответствующей взвешенной суммы их значений. Для целых аргументов достаточно, чтобы соседние приращения не убывали. Поэтому таблица полных цен 0,1,4,9 выпукла: приращения 1,3,5 растут. Таблица 0,5,7,8 не выпукла: приращения 5,2,1 убывают, она выражает скидку за объём.

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

Правило: сначала зафиксируй область

Для целого выпуклого потока используй неубывающие дискретные приращения. Не заменяй их производной без смены модели. Целочисленность линейных потоков не доказывает целочисленность минимума выпуклой задачи. При целых ёмкостях и балансах непрерывный минимум может лежать между целыми точками.

Разбор: четыре партии и две дороги

Переберём x на первой дороге; на второй будет 4-x. При x=0 полная цена 12, при x=1 цена 1+9=10, при x=2 цена 4+6=10, при x=3 цена 9+3=12, при x=4 цена 16. Значит, два целых оптимума: (1,3) и (2,2), оба стоят десять. Равенство соседних приращений даёт возможность выбора без потери.

Непрерывная задача имеет цель x²+3(4-x). Выделим квадрат: (x-1.5)²+9.75. Квадрат неотрицателен, поэтому минимум достигается при x=1.5 и стоит 9.75. Это допустимый дробный поток, но не план перевозки неделимых партий. Округление каждой дуги по отдельности может сломать балансы; здесь баланс сохраняем, вычисляя вторую переменную как остаток.

# convex_routes.py
costs = []
x = 0
while x <= 4:
    y = 4 - x
    cost = x * x + 3 * y
    costs.append(cost)
    x = x + 1
best = min(costs)
plans = []
x = 0
while x <= 4:
    if costs[x] == best:
        plans.append([x, 4 - x])
    x = x + 1
print(costs)
print(best, plans)
# [12, 10, 10, 12, 16]
# 10 [[1, 3], [2, 2]]

Разбор: водители и общий диспетчер

Теперь поток делим непрерывно, всего четыре единицы. Задержка одного водителя на первой дороге t₁(x)=x, на второй t₂(y)=3. В равновесии при использовании обеих дорог водители видят одинаковую задержку. Получаем x=3, y=1; суммарная задержка 3·3+1·3=12.

Диспетчер минимизирует x·t₁(x)+y·t₂(y)=x²+3y. Из предыдущего разбора он выбирает x=1.5 и y=2.5; общая задержка 9.75. Водителю на второй дороге выгоден переход: он не учитывает задержку, которую создаёт другим. Поэтому системный оптимум отличается от равновесия.

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

Потенциальная функция равна Φ(x)=Σ∫₀ˣ tₐ(z)dz. Интеграл - накопленная площадь под графиком. Если увеличить поток дуги с x до x+ε, добавится узкая полоска площади примерно t(x)ε. Отношение добавленной площади к ε при ε→0 равно t(x); это производная, то есть скорость изменения функции. Поэтому производная интеграла задержки равна самой задержке, а не полной системной цене x·t(x). Неубывание t даёт выпуклость его интеграла: добавляемые полоски не становятся дешевле.

Перенесём малую величину ε с используемого маршрута Q на маршрут P. На общих дугах изменения сократятся, на остальных изменение Φ в первом порядке равно ε(T(P)-T(Q)), где T - сумма задержек дуг маршрута. Если P быстрее Q, эта величина отрицательна и потенциал можно уменьшить. В минимуме такой пары нет: получаем условие Уордропа. Обратно, если все используемые маршруты минимальны, любое перераспределение фиксированного спроса имеет неотрицательное первое изменение Φ. По выпуклости Φ это достаточное условие глобального минимума. Если ограничение ёмкости запрещает перенос, такое доказательство сравнивает только разрешённые изменения: обычное равенство задержек всех используемых путей уже не следует.

В нашем примере Φ=x²/2+3y. При x=2,y=2 задержки равны два и три. Переносим ε со второй дороги на первую: Φ меняется на -ε+ε²/2, что отрицательно при 0<ε<2. При x=3,y=1 первое изменение ноль, остаётся ε²/2≥0. Поэтому минимум потенциала действительно означает отсутствие выгодного малому водителю перехода. Системную цель x²+3y это рассуждение не заменяет: у неё другая производная.

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

Ёмкость U записывается примерно log₂U битами. Формула x² короткая даже при миллиардной ёмкости. Таблица миллиарда приращений длинная. Алгоритм, который создаёт по дуге на каждую единицу ёмкости, полиномиален по размеру таблицы, но может быть экспоненциальным по длине компактной записи U. Позже масштабирование позволит работать с формулой без разворачивания всей таблицы. Стоимость вычисления функции тоже нужно учитывать.

Зачем в работе: сформулировать штраф за перегрузку

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

Теперь сам

Для трёх целых партий оставь C₁(x)=x², C₂(y)=4y. Выпиши цены для x=0,1,2,3 и найди минимум. Затем сравни непрерывный минимум. Ответ: 12,9,8,9; целый план (2,1) стоит восемь. Непрерывная цель равна (x-2)²+8, поэтому здесь разницы нет. Совпадение в одном примере не возвращает общую теорему целочисленности.