Два цикла, вырождение и граница симплексной гарантии

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

Крючок: конечное число состояний и бесконечный запуск

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

На что это похоже: перелив между двумя насосами

Представь цикл, который создаёт избыточный ресурс, и другой, который его поглощает. Между ними есть трубопровод. Первый цикл создаёт столько, сколько нужно для нового движения по трубопроводу; второй расходует полученный избыток. В каждой вершине итоговый баланс ноль, хотя каждый цикл отдельно его изменил бы. Эта пара объясняет, почему простая «отмена одного отрицательного цикла» не переносится на обобщённую сеть без изменений.

Механизм: форма направления

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

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

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

Правило: строгий спуск требует δ>0

Для входа с нижней границы r<0 изменение цели равно δr. Для входа с верхней границы r>0 и ведущей скорости -1 изменение равно -δr. В обоих случаях при δ>0 улучшение строго положительно по модулю, равному δ|r|. При δ=0 цель не меняется. Следовательно, доказательство через конечное число базисов требует невырождения всех шагов либо правила, исключающего повторение при равной цели.

Разбор: велосипед с двумя петлями

Пусть у A есть петля множителя два, у B петля множителя 1/2, а A→B имеет множитель три. Хотим увеличить поток соединяющей дуги на δ. В A она требует δ, поэтому увеличивающая петля должна создать δ: её поток увеличиваем на δ, поскольку (2-1)δ=δ.

В B приходит 3δ. Поглощающая петля тратит половину собственного входа, поэтому её поток увеличиваем на 6δ: (1-1/2)·6δ=3δ. Проверяем изменения балансов: у A (1-2)δ+δ=0; у B (1-1/2)·6δ-3δ=0. Скорости Y равны [1,6,1], если записывать петлю A, петлю B и соединение. Разные коэффициенты делают общий «добавим единицу по всем рёбрам» неверным.

При остатке ёмкости петли B равном двенадцати, соединения пяти и петли A десяти пределы шага 2,5,10. Значит, можно увеличить соединение только на два. Если вторая петля имела множитель один, она не поглотила бы никакого избытка, и такое направление не существовало бы.

# bicycle_direction.py
from fractions import Fraction as F
mu_a = F(2)
mu_b = F(1, 2)
mu_link = F(3)
y_link = F(1)
y_a = y_link / (mu_a - 1)
y_b = mu_link * y_link / (1 - mu_b)
assert (1-mu_a)*y_a + y_link == 0
assert (1-mu_b)*y_b - mu_link*y_link == 0
remaining_a = F(10)
remaining_b = F(12)
remaining_link = F(5)
limits = [remaining_a/y_a, remaining_b/y_b,
          remaining_link/y_link]
print(y_a, y_b, y_link)
print(min(limits))
# 1 6 1
# 2

Разбор: нулевой шаг и выбор при равенстве

Текущие потоки [0,3], направление [-1,1], верхние границы [10,10]. Первая дуга уже на нуле и должна уменьшаться. Тест отношений даёт ноль, новая точка совпадает со старой. Допустим, приведённая цена входа -2. Формально направление дешевеет со скоростью два, но реального улучшения 0·2=0 нет. Запись «на каждой итерации цена уменьшается» для этого примера ложна.

Лексикографическое возмущение придаёт правым частям разные символические добавки ε,ε²,…,εⁿ. Сравнение идёт по первому различающемуся коэффициенту, как сравнение слов по первой разной букве. Для примера два равных обычных отношения могут стать 2+ε и 2+2ε². При положительном достаточно малом ε второй меньше: его коэффициент при ε равен нулю, у первого единица. Значит, правило выбирает одну блокирующую дугу без численной ничьей.

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

Что ломается при «очень маленьком» float

Поставив ε=10⁻¹², ты не реализовал символическое правило. При одном масштабе число округлится к нулю, при другом изменит настоящий порядок цен. Полный набор ε,ε²,… быстро уйдёт ниже машинной точности. Для доказательства завершения нужны точные символические сравнения или другое доказанное антициклическое правило. Случайный выбор блокирующей дуги может работать на примерах, но не даёт такой гарантии.

Механизм: оценка одной итерации и всего запуска

Просмотр всех небазисных дуг для выбора входа занимает O(m). Вычисление Y, тест отношений, обновление потоков, пересчёт потенциалов и индексов укладываются в O(n+m) арифметических операций при простом полном пересчёте. Для связной расширенной сети это O(m) на итерацию. Но число возможных базисов может быть большим, и доказательство строгого спуска даёт только конечность, а не полиномиальный предел по n и m.

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

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

В журнале оптимизатора полезно считать отдельно число смен базиса и число положительных перемещений. Длинная серия δ=0 указывает на вырождение или дефект антициклического правила. Уменьшение невязки балансов при неизменной цене не заменяет проверку завершения. Для воспроизводимости сохраняй порядок просмотра дуг и правило разрыва равенств вместе с результатом.

Теперь сам

В первом велосипеде замени μ(B) на 3/4, остальные числа оставь. Найди скорость второй петли и предел при её остатке ёмкости двенадцать. Ответ: YB=3/(1-3/4)=12, поэтому δ≤1. Чем ближе поглощающий множитель к единице, тем больший внутренний оборот нужен для того же чистого поглощения. При μ(B)=1 знаменатель ноль, такой способ восстановления баланса исчезает.