Три модели: переназначение, таблицы и электрическое сопротивление

Если умеешь строить эти модели, переходи к «Теперь сам».

Крючок: почему отказ от линии имеет цену

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

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

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

Механизм: три разных значения дуги

Для переназначения строим слой центров и слой районов. Поток x(i,j) - число линий центра i, отданных району j. Вводим общий источник с запасом D, равным суммарному спросу районов. Из него в каждый центр ведём бесплатную дугу ёмкости B(i), где B(i) - доступная мощность. Сам центр имеет баланс ноль: сколько источник ему направил, столько он распределяет районам. Район получает отрицательный баланс, равный его спросу. Так центр использует до B(i), а не обязательно B(i). Баланс b(i)=B(i) без отвода означал бы обязанность отдать всю мощность.

Другой корректный вариант: выдать центрам запасы B(i) и добавить фиктивный район с потребностью ΣB(i)-D; бесплатные дуги туда учитывают неиспользованную мощность. Это требует ΣB(i)≥D и всё равно не отменяет ограничений реальных подключений. В первом варианте при мощностях четыре и четыре, спросе пять источник распределяет четыре и одну; три неиспользованных линии второго центра не создают ни потока, ни спроса. При запасах четыре и четыре без фиктивного района сумма балансов была бы три вместо нуля, и задача стала бы противоречивой.

Пусть w - действующие линии, s - резерв. Тогда на участке x<w наклон полной цены равен -a, где a - плата за отключение: добавление линии сокращает число отключений. На участке от w до w+s наклон равен b, после него d, где -a≤b≤d. Эти неубывающие наклоны дают выпуклую цену.

Для балансировки матрицы создаём вершину для каждой строки и каждого столбца. Дуга строки i в столбец j переносит новое значение ячейки x(i,j). Запасы строк равны новым суммам строк, потребности столбцов - новым суммам столбцов. Суммы двух сторон должны совпадать. Старое значение a(i,j) входит в штраф w(i,j)·(x(i,j)-a(i,j))². Вес w должен быть неотрицательным: отрицательный вес разрушает выпуклость и поощряет отклонение.

Для проводящей сети ток удовлетворяет узловым балансам: суммарный приход равен уходу вне источника и стока. На сопротивлении r положительная мощность потерь равна r·x². При заданном вводе тока распределение минимизирует сумму таких потерь. Здесь нужно разрешить току идти против выбранной ориентации дуги: ориентация служит знаком переменной. В модели с x≥0 можно добавить обратное направление с той же квадратичной ценой. При положительном r встречные токи оптимуму не нужны: их взаимное сокращение сохраняет баланс и уменьшает потери.

Правило: не теряй ограничения приложения

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

Разбор: диапазоны тарифов и выбор центра

В исходном примере полная цена равна 2(4-x) при 0≤x≤4, затем 3(x-4) при 4≤x≤6, затем 6+7(x-6). Считаем: C(2)=4, C(4)=0, C(5)=3, C(6)=6, C(7)=13. При переходе от трёх к четырём линиям цена меняется на -2, от четырёх к пяти на 3, от шести к семи на 7. Возрастающий поток проходит разные тарифы, поэтому нельзя назначить всей дуге одну постоянную цену.

Если район требует пять линий, а первый центр может выделить не более четырёх, одну надо взять у другого. Пусть у второго центра цена новых линий равна 5x. При x₁=4,x₂=1 цена 0+5=5. При x₁=3,x₂=2 цена 2+10=12. Отказ от существующей линии и новое подключение оплачиваются вместе. Сравнение только цены нового центра дало бы неполный бюджет.

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

Есть старая таблица [[3,1],[1,3]]. Новые суммы строк равны [5,3], столбцов [4,4]. Обозначим левую верхнюю ячейку t. Балансы вынуждают остальные значения: 5-t,4-t,t-1. Неотрицательность даёт 1≤t≤4. При единичных весах сумма квадратов отклонений равна (t-3)²+(4-t)²+(3-t)²+(t-4)². Это 2(t-3)²+2(t-4)².

Непрерывный минимум достигается при t=3.5, получается [[3.5,1.5],[0.5,2.5]], цена один. Для целых ячеек t=3 и t=4 дают цену два. Выбирая t=3, получаем [[3,2],[1,2]]. Суммы действительно равны новым значениям. Простое масштабирование старых строк дало бы правильные строки, но могло бы нарушить столбцы: здесь оба набора ограничений проверяют вместе.

# balance_table.py
best = None
plans = []
t = 1
while t <= 4:
    matrix = [[t, 5-t], [4-t, t-1]]
    old = [[3, 1], [1, 3]]
    cost = 0
    i = 0
    while i < 2:
        j = 0
        while j < 2:
            delta = matrix[i][j] - old[i][j]
            cost = cost + delta * delta
            j = j + 1
        i = i + 1
    if best is None or cost < best:
        best = cost
        plans = [matrix]
    elif cost == best:
        plans.append(matrix)
    t = t + 1
print(best, plans)
# 2 [[[3, 2], [1, 2]], [[4, 1], [0, 3]]]

Разбор: две проводящие ветви

Единичный ток делится между двумя параллельными сопротивлениями 1 и 3. Через первое идёт x, через второе 1-x. Потери равны x²+3(1-x)²=4(x-0.75)²+0.75. Значит, токи 0.75 и 0.25 дают потери 0.75. Падения напряжения совпадают: 1·0.75=3·0.25. Это физическая проверка оптимума независимо от выделения квадрата.

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

Что ломается без единиц измерения

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

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

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

Теперь сам

Два параллельных сопротивления равны 2 и 2, общий ток два. Найди токи и мощность. Ответ: x²·2+(2-x)²·2=4(x-1)²+4, поэтому по единице на каждую ветвь, потери четыре. Если требовать целые токи, ответ совпадёт. Затем проверь, почему ограничение «через первую ветвь минимум 1.5» меняет оптимум: допустимая область больше не содержит прежнюю точку.