Обобщённый сетевой симплекс: один проверяемый шаг

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

Крючок: улучшение без изменения одной дуги

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

На что это похоже: согласованный поворот рычагов

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

Механизм: начальная структура и выбор дуги

У каждой вершины вводим искусственную петлю. При b>0 выбираем μ=1/2, при b≤0 μ=2. Поток петли x=b/(1-μ) неотрицателен и даёт баланс (1-μ)x=b. Все петли образуют хороший дополненный лес, реальные дуги стоят на нуле. При нулевом b искусственная петля имеет нулевой поток: начальный базис может быть вырожденным.

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

При r=c-π(i)+μπ(j) дуга из L может входить при r<0 через увеличение, из U - при r>0 через уменьшение. Можно выбирать наибольшее нарушение, первую подходящую дугу с циклическим просмотром списка или лучшую из списка кандидатов. Это правила поиска, они не заменяют требования к шагу и защите от зацикливания.

Правило: направление и величина отдельно

Для входящей k→l на нижней границе ставим Y(k,l)=1. Её вклад в баланс: +1 у k и -μ у l. Поэтому базисные дуги должны иметь противоположный баланс: -1 у k и +μ у l. Вычисли Y на F тем же устранением листьев, что использовал для потоков. Для дуги с Y>0 предел шага (u-x)/Y; с Y<0 предел x/(-Y); с Y=0 ограничителя нет. Включи в минимум и саму входящую дугу.

Разбор: входящая дуга улучшает старый план

В базисе две дуги A→B с μ=2,c=3 и B→A с μ=3/4,c=1. Балансы b(A)=-2,b(B)=0 дают x=4,y=8 и цену двадцать. Потенциалы равны -10 и -6.5. Добавим входящую A→B с μ=1,c=-5, верхней границей десять. Её приведённая цена -1.5, поэтому увеличение может улучшить решение.

Пусть её поток z растёт на δ. Требуем нулевое изменение балансов: Yx-(3/4)Yy+1=0, Yy-2Yx-1=0. Из второго Yy=2Yx+1. Подстановка в первое даёт -Yx/2+1/4=0, значит Yx=1/2,Yy=2. Направление положительно на обеих базисных дугах: x=4+δ/2,y=8+2δ,z=δ.

Возьмём u(x)=6,u(y)=14,u(z)=10. Пределы шага: (6-4)/(1/2)=4, (14-8)/2=3, (10-0)/1=10. Минимум три: y блокирует. Новый план x=5.5,y=14,z=3 стоит 3·5.5+14-5·3=15.5. Улучшение 4.5 равно δ·|r|=3·1.5. Балансы:5.5+3-0.75·14=-2;14-2·5.5-3=0.

# generalized_pivot.py
from fractions import Fraction as F
x = [F(4), F(8), F(0)]
y = [F(1, 2), F(2), F(1)]
u = [F(6), F(14), F(10)]
c = [F(3), F(1), F(-5)]
limits = []
for value, rate, upper in zip(x, y, u):
    if rate > 0:
        limits.append((upper-value) / rate)
    elif rate < 0:
        limits.append(value / (-rate))
delta = min(limits)
new = [a + delta*b for a, b in zip(x, y)]
old_cost = sum(a*b for a, b in zip(c, x))
new_cost = sum(a*b for a, b in zip(c, new))
print(limits, delta)
print(new, old_cost, new_cost)
assert new[0] + new[2] - F(3, 4)*new[1] == -2
assert new[1] - 2*new[0] - new[2] == 0
# [Fraction(4, 1), Fraction(3, 1), Fraction(10, 1)] 3
# [Fraction(11, 2), Fraction(14, 1), Fraction(3, 1)] 20 31/2

Разбор: отрицательная скорость и нижняя граница

Пусть текущие потоки равны [4,3,0], скорости изменения [-2,1,1], верхние границы [10,9,5]. Первая дуга уменьшается: её ограничитель 4/2=2, хотя до верхней границы шесть. Вторая ограничивает шаг шестью, входящая пятёркой. Итак, δ=2, новый поток [0,5,2]. Выходящая первая дуга переходит в L, поскольку достигла нуля.

Если первая дуга уже на нуле, δ=0. Направление формально улучшает цель, но положительный шаг пока невозможен. Базис может смениться без изменения потока. Если сама входящая дуга первой достигла верхней границы, базис F не меняется: она просто переходит L→U. При входе из U выбери ведущую скорость -1 и заново реши систему; это сохраняет ту же процедуру без ручного переворота всех цен.

Механизм: обновление после блокировки

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

Что ломается без проверки всех ограничителей

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

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

Один симплексный шаг можно записать как компактный журнал: входящая дуга, её r, вектор Y, отношения и новая стоимость. Такой журнал проверяется независимо от выбора pivot rule. При спорном результате это гораздо полезнее тысячи строк внутренних структур дерева: каждое число связано с балансом или ограничением.

Теперь сам

Повтори первый разбор с u(y)=20, остальные границы прежние. Пределы равны четыре, шесть и десять. Ответ: δ=4, блокирует x; новый план [6,16,4], цена четырнадцать. Улучшение шесть равно 4·1.5. Если два предела совпали, можно выбрать одну блокирующую дугу, но правило выбора при вырождении влияет на гарантию завершения.