Обобщённый поток: выход дуги отличается от входа

Если умеешь проверять баланс с множителями, переходи к «Теперь сам».

Крючок: четыре отправили, три получили

Как думаешь, допустим ли план с запасом четыре и спросом три без дополнительных источников? Если дуга имеет μ=3/4, отправление четырёх как раз покрывает спрос три. Обычная сеть назвала бы сумму балансов ненулевой и отвергла условие. В обобщённой сети недостающая единица исчезает на дуге. Модель хранит это преобразование явно, поэтому проверка должна умножать поток при входе в вершину назначения.

На что это похоже: обмен валюты

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

Механизм: четыре числа на каждой дуге

У дуги есть отправленный поток x, верхняя граница u, цена c за единицу отправления и положительный рациональный множитель μ. Рациональный значит, что число можно записать как отношение двух целых; это позволяет считать учебные примеры без ошибки округления. Цель - сумма c·x. В вершине i выполняется сумма исходящих x минус сумма μ·x для входящих дуг, равная b(i).

При μ<1 дуга теряет количество, при μ>1 увеличивает его, при μ=1 возвращается обычный поток. Умножитель преобразует именно выход, а цена начисляется на вход. Если дуга пропускает максимум десять литров до очистки и выход равен 0.8, получить можно не больше восьми литров. Ограничение на восемь выходных литров равносильно входной ёмкости десять; смешение этих двух соглашений меняет допустимые планы.

Нижнюю границу l можно убрать подстановкой x=l+y. Тогда в начале дуги новый баланс b(i)-l, в конце b(j)+μl, цель меняется на постоянную c·l. Для петли i→i оба изменения относятся к одной вершине: новый баланс b(i)-(1-μ)l. Такие петли полезны для учёта свободной мощности и для начального искусственного базиса.

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

Правило: ограничения целочисленности отдельно

Множители положительны, но поток в линейной постановке может быть дробным даже при целых балансах. Если предмет задачи требует целых самолётов, смен или неделимых изделий, добавление x∈Z создаёт другую оптимизационную задачу. Не округляй каждую переменную независимо: нарушатся и спрос, и загрузка ресурсов.

Разбор: поставка после очистки

Есть источник с запасом десять литров сырья, очистка с выходом μ=0.8 и ценой три за входной литр. Покупатель требует восемь литров. Единственный поток x=10 стоит тридцать. Баланс источника x=10 совпадает с b(s)=10; баланс покупателя -0.8x=-8 совпадает с b(t)=-8.

Если спрос равен шести, нужно отправить 7.5 литра, цена 22.5. При прежнем запасе десять нужен способ оставить или утилизировать 2.5 литра: равенство баланса само по себе требует потратить весь запас. Явно добавим у источника бесплатную петлю с множителем 1/2. При потоке y она даёт чистый расход (1-1/2)y=y/2, поэтому y=5 поглощает неиспользованные 2.5 литра. Баланс источника теперь 7.5+5/2=10. У покупателя остаётся -0.8·7.5=-6. Это бухгалтерский отвод свободного сырья, а не повторная очистка.

Входная дуга ёмкости десять от внешнего узла сама по себе не устраняет обязанность выдать десять: надо указать баланс внешнего узла и учесть его остаток. Можно задать там точно 7.5 для данного фиксированного спроса, но это уже расчёт по известной потребности. Если количество отправления выбирает решатель, сохраняем запас десять и явную поглощающую петлю либо другой отвод. Граница ёмкости и равенство баланса решают разные задачи.

# generalized_balance.py
from fractions import Fraction as F
mu = F(4, 5)
source_supply = F(10)
source_loop_mu = F(1, 2)
for demand in [8, 6]:
    sent = F(demand) / mu
    received = mu * sent
    cost = 3 * sent
    unused = source_supply - sent
    loop = unused / (1-source_loop_mu)
    balance = sent + (1-source_loop_mu) * loop
    assert balance == source_supply
    assert -mu * sent == -demand
    print(sent, received, cost, loop)
# 10 8 30 0
# 15/2 6 45/2 5

# Петля каждого станка представляет свободные часы.
for x1, x2 in [[2, 2], [1, 3]]:
    hours1 = 2 * x1
    hours2 = x2
    loop1 = 4 - hours1
    loop2 = 6 - hours2
    assert x1 + x2 == 4
    assert loop1 >= 0 and loop2 >= 0
    assert -hours1 + (1-2)*loop1 == -4
    assert -hours2 + (1-2)*loop2 == -6
    print(x1, x2, loop1, loop2, 3*x1 + 5*x2)
# 2 2 0 4 16
# 1 3 2 3 18

Разбор: загрузка двух станков

Нужно произвести четыре изделия. На первом станке изделие требует два часа и стоит три, на втором один час и стоит пять. Первый доступен четыре часа, второй шесть. Пусть x₁,x₂ - количество изделий. У вершины продукта запас четыре, исходящие дуги несут x₁,x₂. Множители два и один переводят изделия в занятые часы. Вершины станков получают потребности четыре и шесть часов.

Чтобы «доступно четыре и шесть часов» не означало обязательную полную загрузку, добавляем бесплатную петлю с μ=2 у каждого станка. Если на станок пришли h занятых часов, баланс с потоком y по петле равен -h+(1-2)y=-H. Отсюда y=H-h≥0: петля обозначает свободные часы. Она не создаёт физическую мощность для дополнительного выпуска, потому что её поток неотрицателен и требует h≤H.

Оптимально x₁=2,x₂=2: производство стоит 2·3+2·5=16, занято четыре и два часа. Потоки петель равны нулю и четырём. Проверяем: -4+(1-2)·0=-4, -2+(1-2)·4=-6. Петля первого станка пока нулевая, но удалять её из модели нельзя. План x₁=1,x₂=3 тоже физически допустим: занято два и три часа, петли несут два и три. Балансы -2-2=-4 и -3-3=-6 выполнены, цена три плюс пятнадцать равна восемнадцати. Выбор оптимума сравнивает оба плана; ограничения не должны заранее запрещать допустимую недозагрузку первого станка.

Знаки двух видов свободного ресурса различаются из-за направления записанного ограничения. У источника исходящий расход должен быть не больше запаса b: недостающий расход добавляет петля μ<1. У станка приход занятых часов должен быть не больше H, то есть чистый выход -h должен быть не меньше -H: его уменьшает петля μ>1. Общий член петли всегда равен (1-μ)y, а нужный знак выводим из конкретного баланса.

Если вместо изделий распределяют самолёты по маршрутам, множитель может означать число пассажирских мест. Требование сто пассажиров и самолёт на сто пятьдесят мест в дробной модели допускают 2/3 самолёта. Цена такой модели ограничивает снизу цену целого плана. Для реального назначения придётся решать целочисленное расширение или доказывать корректность специального округления.

Что ломается при неверном коэффициенте

Для производства можно направлять дуги от продукта к станку, переводя изделия в часы с μ=a. Можно выбрать обратную интерпретацию, переводя часы в изделия с μ=1/a. Тогда придётся пересчитать цену и ёмкость в часы. Переворот одной стрелки с сохранением остальных чисел создаст другую задачу. Полезная проверка: проведи одну физическую единицу через дугу и назови единицы на обоих концах вслух.

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

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

Теперь сам

Дуга имеет μ=3/2, ёмкость шесть и цену четыре. Сколько максимум придёт, сколько стоит полное использование и какой вход нужен для спроса шесть? Ответ: девять единиц, цена двадцать четыре; для спроса шесть отправляют четыре, цена шестнадцать. Если бы цена четыре относилась к выходной единице, эквивалентная цена отправления была бы шесть.