Склад, деньги и питание: границы обобщённой сети

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

Крючок: купить сегодня на завтрашние деньги

Как думаешь, достаточно ли вычесть все покупки из всех продаж, чтобы проверить стратегию склада? Есть десять рублей сегодня, цена товара пять, завтра он стоит восемь. Закупить три единицы сегодня и продать завтра даёт положительную прибыль девять, но сегодня не хватает пяти рублей. Суммарная прибыль скрыла нарушение ликвидности. Сеть по времени держит отдельный денежный баланс каждого периода и не допускает такую покупку без явной кредитной дуги.

На что это похоже: два ряда конвертов

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

Механизм: типы дуг и общая цель

Для периода k создаём вершины товара Gₖ и денег Mₖ. Дуга Gₖ→Gₖ₊₁ имеет ёмкость H, стоимость хранения за отправленную единицу и множитель σₖ≤1, если есть порча. Дуга Mₖ→Mₖ₊₁ имеет множитель 1+rₖ, где r - ставка за период. Ставка 5% означает множитель 1.05, а не 0.05: после периода остаётся и основной вклад, и начисление.

При цене покупки p дуга Mₖ→Gₖ имеет множитель 1/p. При цене продажи q дуга Gₖ→Mₖ имеет множитель q. При равных ценах круг «купить-продать» имеет множитель один. Спред q

p и обе дуги неограниченны, модель допускает бесконечный арбитраж в один момент; это нужно исправить в данных или ограничениях, а не прятать ограничением числа итераций.

Чтобы максимизировать конечные деньги, выводим их дугой цены -1 и множителя один в выделенную внешнюю вершину с b=0. Если туда пришло z, баланс с петлёй потока y равен (1-μ)y-z=0. Выбираем бесплатную поглощающую петлю μ=1/2, тогда y=2z и баланс выполнен. Например, приход шестнадцать поглощает петля потока тридцать два: (1-1/2)·32-16=0. Петля μ=2 дала бы -y-z=0 и при z>0 потребовала бы отрицательный y, что запрещено.

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

Правило: отношение переменных не является ёмкостью

Чистая обобщённая сеть допускает фиксированную границу l≤x≤u и фиксированный коэффициент преобразования. Ограничение x≤a·z при двух свободных переменных связывает две дуги и обычно не укладывается в такой вид. Если приложение требует это соотношение, сохраняй его как отдельное ограничение. Отбрасывание условия даёт ослабленную модель и оценку, а не решение исходной задачи.

Разбор: склад на один переход

Начальные деньги десять, товаров нет. Сегодня покупка стоит пять, завтра продажа восемь, вместимость H=2. Денежная дуга даёт рост 10%, порчи нет. Пусть покупаем x единиц, 0≤x≤2. Сегодня остаётся 10-5x рублей, завтра они превращаются в 1.1(10-5x). Продажа приносит 8x. Конечная касса равна 11+2.5x.

Максимум при x=2: касса шестнадцать. Если ничего не купить, будет одиннадцать. Если H=1, максимум 13.5. Значит, ограничение склада надо поставить на перенос товара, а не только на покупку: товар мог существовать ещё до первого периода. Если порча σ=0.75, завтра продаём 0.75x; конечная касса 11+0.5x, при двух единицах двенадцать. Если σ=0.5, коэффициент становится -1.5 и выгоднее оставить деньги на счёте.

# warehouse_one_period.py
from fractions import Fraction as F
money = F(10)
buy_price = F(5)
sell_price = F(8)
growth = F(11, 10)
for survival in [F(1), F(3, 4), F(1, 2)]:
    values = []
    for bought in range(3):
        cash_today = money - buy_price * bought
        assert cash_today >= 0
        goods_tomorrow = survival * bought
        cash_tomorrow = growth * cash_today
        cash_tomorrow += sell_price * goods_tomorrow
        terminal_loop = 2 * cash_tomorrow
        assert F(1, 2)*terminal_loop - cash_tomorrow == 0
        values.append(cash_tomorrow)
    print(survival, values, max(values))
# 1 [Fraction(11, 1), Fraction(27, 2), Fraction(16, 1)] 16
# 3/4 [Fraction(11, 1), Fraction(23, 2), Fraction(12, 1)] 12
# 1/2 [Fraction(11, 1), Fraction(19, 2), Fraction(8, 1)] 11

Разбор: два вида животных и два вида корма

Пусть животное типа A требует два килограмма корма, типа B три. Есть четыре килограмма травы и четыре килограмма зерна. Дуги от внешнего источника к типам животных несут их число zA,zB, множители два и три переводят число в пищевую потребность. Затем обычные дуги распределяют корм по видам. Цена -1 за входное животное выражает максимизацию их общего числа. Для полностью заданной схемы можно дать внешнему источнику запас четыре условных места под животных: при минимальном рационе два килограмма и суммарном корме восемь животных заведомо не больше четырёх. Неиспользованные места поглощает петля μ=1/2 у источника. У каждой вершины корма задаём b=-4 и петлю μ=2: если пришёл фактически потребляемый объём h, петля несёт 4-h и баланс -h-(4-h)=-4. Поэтому расход каждого корма ограничен четырьмя, но не обязан достигать четырёх. Сами петли не представляют дополнительных животных или физический корм.

Если доли питания свободны и верхние границы каждой пары не мешают, можно поддержать четыре животных A, используя восемь килограммов корма. Это лучше, чем 8/3 животных B. Теперь требуется, чтобы каждое A получало не менее 75% зерна. Тогда для четырёх A нужно минимум шесть килограммов зерна, но доступно четыре. Прежний оптимум нарушает новое требование.

Запишем его как x(A,зерно)≥0.75·2zA. Если зерна четыре, zA≤8/3. Это условие связывает выбор количества животных и распределение корма; одной фиксированной ёмкостью дуги его не заменить. Модель общего линейного программирования сохраняет условие напрямую. Для ослабления запишем g=1.5zA-x(A,зерно)≤0. При минимизации добавим к цели λg с λ≥0. На любом допустимом плане добавка неположительна, поэтому минимум ослабленной задачи даёт нижнюю оценку исходного минимума. При максимизации числа животных знаки оценок надо перевести через отрицательную цель.

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

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

Максимизация суммы животных при одинаковой цене -1 не максимизирует число представленных видов. Для разнообразия видов нужны индикаторы присутствия или другие требования. Допустимость дробных 8/3 животных также требует отдельного решения: это ресурсная оценка для стада большого масштаба, но не инструкция разместить дробное животное. При экологической модели нормы питания относятся к условиям постановки, а алгоритм их не устанавливает.

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

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

Теперь сам

Сегодня есть двенадцать рублей, цена покупки четыре, завтра продажа пять, банковский множитель 1.25, порчи нет, H=3. Найди конечную кассу для любого x∈[0,3]. Ответ: 1.25(12-4x)+5x=15, все планы одинаковы по цели. Существование нескольких оптимумов не означает, что можно убрать ограничения ликвидности или склада: они по-прежнему определяют допустимые x.