Метод потенциалов в транспортной задаче: алгебраическая теория и алгоритмы

Математическим ядром метода потенциалов является теория двойственности. Для закрытой транспортной задачи (где суммарное предложение равно суммарному спросу) с $m$ поставщиками и $n$ потребителями строится двойственная задача. Двойственные переменные $u_i$ (связанные с поставщиками) и $v_j$ (связанные с потребителями) называются потенциалами. Фундаментальное условие оптимальности гласит: базисное распределение поставок является оптимальным тогда и только тогда, когда для всех базисных (заполненных) клеток выполняется равенство $u_i + v_j = c_{ij}$, где $c_{ij}$ — удельная стоимость перевозки.

Алгоритм стартует с поиска начального опорного плана. Чаще всего используются метод северо-западного угла, метод минимального элемента или метод аппроксимации Фогеля (VAM). Последний предпочтительнее, так как формирует план, близкий к оптимальному. Для найденного базиса (состоящего ровно из $m+n-1$ ненулевых поставок) составляется система линейных уравнений для вычисления потенциалов. Поскольку уравнений на одно меньше, чем переменных, один из потенциалов произвольно приравнивается к нулю, что позволяет мгновенно вычислить все остальные значения.

Следующий шаг — оценка свободных (пустых) клеток. Для каждой небазисной клетки вычисляется оценка $\Delta_{ij} = u_i + v_j - c_{ij}$. Если для всех свободных клеток $\Delta_{ij} \le 0$, план признается оптимальным. Если хотя бы одна оценка положительна, текущий план можно улучшить. Алгоритм выбирает клетку с максимальной положительной оценкой в качестве вводимой в базис. Начинается процесс перераспределения: строится замкнутый цикл (цикл пересчета), состоящий из горизонтальных и вертикальных звеньев, вершины которого лежат в базисных клетках, а стартовая точка — в новой выбранной клетке.

Построенный цикл позволяет переместить максимально возможный объем груза $\theta$ в новую клетку, не нарушая ограничений по строкам и столбцам. Величина $\theta$ определяется как минимум среди объемов поставок в клетках цикла, из которых груз изымается. Этот процесс итеративно повторяется, строго монотонно уменьшая общую стоимость перевозок. Особым случаем является проблема вырожденности, когда базисный план содержит менее $m+n-1$ поставок. Математически она решается введением бесконечно малых (или нулевых) поставок $\epsilon$, что восстанавливает связность графа и позволяет алгоритму корректно продолжать работу до достижения абсолютного экономического оптимума.

Список литературы:
1. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. — М.: Изд-во АН СССР, 1959.
2. Данциг Д. Линейное программирование, его обобщения и применения. — М.: Прогресс, 1966.
3. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения. — М.: Наука, 1969.