Транспортна задача · метод потенціалів
Як движок Канторовича знаходить точно найдешевший план перевезень — не перебором, а перетіканням тонн по замкнутому кільцю. Приклад: два елеватори везуть зерно на два судна.
Тіньова ціна кожної точки (u для елеватора, v для судна) — це «скільки насправді варта тонна тут з погляду всієї системи». Для порожньої клітини оцінка вартість − u − v каже, наскільки план подешевшає, якщо почати возити цим маршрутом. Поки хоч одна оцінка від'ємна — є куди покращувати; кільце переливає тонни туди рівно на стільки, скільки дозволяє найменша клітина зі знаком «−».
Коли всі оцінки стають ≥ 0, дешевше вже неможливо — і це доведено, а не вгадано. Саме тому транспортну задачу розв'язують точно за секунди, тоді як маршрутну (об'їзд точок автомобілем) — лише евристиками. За цей клас задач Леонід Канторович отримав Нобелівську премію.
optimize/flows.py · solve_transportation() — метод потенціалів (MODI) поверх старту Фогеля. Тут показано мінімальне кільце 2×2; у коді джерел і суден більше, кільце знаходиться як шлях у базисному дереві.