Метод потенциалов: решение транспортной задачи

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

Постановка транспортной задачи

В транспортной задаче есть $m$ поставщиков с запасами $a_1, \dots, a_m$ и $n$ потребителей с потребностями $b_1, \dots, b_n$. Стоимость перевозки единицы груза из пункта $i$ в пункт $j$ задана тарифом $c_{ij}$. Нужно составить план перевозок $x_{ij} \ge 0$ так, чтобы вывезти весь запас, удовлетворить весь спрос и минимизировать суммарную стоимость:

$Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}\, x_{ij} \to \min.$

Задача называется закрытой (сбалансированной), если суммарный запас равен суммарной потребности:

$\sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j.$

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

Опорный план: метод северо-западного угла

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

Рассчитать для своей задачи

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

Потенциалы строк и столбцов

Сердце метода - потенциалы. Каждой строке $i$ приписывают число $u_i$, каждому столбцу $j$ - число $v_j$. Для всех базисных (занятых) клиток выполняется условие:

$u_i + v_j = c_{ij}.$

Базисных клеток ровно $m + n - 1$, а потенциалов $m + n$, поэтому система недоопределена на одно уравнение. Это решается просто: один потенциал задают произвольно, обычно $u_1 = 0$. После этого остальные потенциалы однозначно находятся цепочкой: зная $u_i$, из занятой клетки $(i, j)$ получают $v_j = c_{ij} - u_i$, и наоборот. Заполняя потенциалы от занятой клетки к занятой клетке, доходят до всех строк и столбцов.

Рассчитать для своей задачи

Удобно записывать потенциалы прямо на полях таблицы: $u_i$ - справа от строк, $v_j$ - под столбцами. Тогда оценка любой свободной клетки читается с таблицы за секунды. В калькуляторе выше потенциалы показаны синими ярлыками по краям таблицы - видно, как они пересчитываются при любом изменении тарифов.

Оценки свободных клеток и признак оптимальности

Для каждой свободной (незанятой) клетки считают оценку - разность между её тарифом и суммой потенциалов:

$\Delta_{ij} = c_{ij} - (u_i + v_j).$

Смысл оценки прямой: $\Delta_{ij}$ показывает, на сколько изменится стоимость плана, если в клетку $(i, j)$ ввести одну единицу перевозки и перераспределить груз по циклу. Отсюда признак оптимальности: если все оценки свободных клеток неотрицательны $\Delta_{ij} \ge 0$, план оптимален - удешевить его нельзя. Если хотя бы одна оценка отрицательна, план можно улучшить, причём начинать выгоднее с клетки, где оценка минимальна (самая отрицательная).

В калькуляторе нижняя диаграмма показывает все оценки столбиками: красные - отрицательные (план улучшаем), зелёные - неотрицательные. Когда все столбики становятся зелёными, признак оптимальности выполнен.

Улучшение плана по циклу пересчёта

Нашлась отрицательная оценка - значит, в эту клетку нужно ввести перевозку. Делают это через цикл пересчёта. Из выбранной свободной клетки строят замкнутый цикл по занятым клеткам: ходы идут только по горизонтали и вертикали, повороты - под прямым углом, вершины цикла чередуют знаки плюс и минус (свободная клетка получает плюс). В клетках со знаком минус находят наименьшую перевозку $\theta$ - это объём перераспределения. Затем по циклу прибавляют $\theta$ к плюсовым клеткам и вычитают из минусовых. Клетка с найденным минимумом обнуляется и выходит из базиса, а свободная клетка входит в него.

После пересчёта снова считают потенциалы и оценки. Цикл повторяют, пока все оценки не станут неотрицательными. Каждый шаг строго уменьшает стоимость (на $|\Delta_{ij}| \cdot \theta$), поэтому метод сходится за конечное число итераций к оптимальному плану.

Разбор примера из калькулятора

Возьмём задачу из калькулятора: запасы $a = (60, 40, 50)$, потребности $b = (50, 40, 60)$ (сумма по 150, задача закрытая), тарифы по строкам $3, 5, 7$; $6, 4, 2$; $8, 3, 5$. Метод северо-западного угла даёт занятые клетки $(1,1)=50$, $(1,2)=10$, $(2,2)=30$, $(2,3)=10$, $(3,3)=50$ - ровно $m + n - 1 = 5$ клеток. Стоимость этого плана:

$Z = 3\cdot 50 + 5\cdot 10 + 4\cdot 30 + 2\cdot 10 + 5\cdot 50 = 590.$

Берём $u_1 = 0$ и разворачиваем потенциалы по занятым клеткам: $v_1 = 3$, $v_2 = 5$, далее $u_2 = c_{22} - v_2 = 4 - 5 = -1$, потом $v_3 = c_{23} - u_2 = 2 - (-1) = 3$ и $u_3 = c_{33} - v_3 = 5 - 3 = 2$. Итог: $u = (0, -1, 2)$, $v = (3, 5, 3)$. Теперь оценки свободных клеток:

$\Delta_{13} = 7 - (0 + 3) = 4, \quad \Delta_{21} = 6 - (-1 + 3) = 4,$

$\Delta_{31} = 8 - (2 + 3) = 3, \quad \Delta_{32} = 3 - (2 + 5) = -4.$

Оценка $\Delta_{32} = -4$ отрицательна, значит, план не оптимален: выгодно ввести перевозку в клетку $(3, 2)$. Построив для неё цикл пересчёта и перераспределив груз, стоимость снизится. После пересчёта все оценки станут неотрицательными - это и будет оптимальный план. Калькулятор показывает ровно эту цепочку чисел: стоимость 590, минимальную оценку -4 и пометку, что план ещё не оптимален.

Частые ошибки

• Несбалансированная задача. Если сумма запасов не равна сумме потребностей, метод потенциалов применять нельзя напрямую. Сначала вводят фиктивный пункт с нулевыми тарифами.
• Неполный базис. В опорном плане должно быть ровно $m + n - 1$ занятых клеток. При вырождении добавляют нулевую перевозку, иначе потенциалы не определятся.
• Потенциалы по свободным клеткам. Условие $u_i + v_j = c_{ij}$ записывают только для занятых клеток. По свободным считают оценки, а не потенциалы.
• Знак оценки. Признак оптимальности - все $\Delta_{ij} \ge 0$. Если ищут максимум стоимости, признак зеркальный, но классическая транспортная задача - на минимум.
• Цикл не из занятых клеток. В цикле пересчёта все вершины, кроме вводимой, должны быть занятыми клетками; ходы строго по строкам и столбцам с поворотами под прямым углом.

FAQ

Чем метод потенциалов отличается от метода северо-западного угла? Метод северо-западного угла строит лишь начальный опорный план - любой допустимый, без оглядки на стоимость. Метод потенциалов берёт этот план и доводит его до оптимального, проверяя оценки свободных клеток и улучшая план по циклу. Это два последовательных этапа решения, а не альтернативы.

Почему один потенциал задают равным нулю? Базисных клеток $m + n - 1$, а потенциалов $m + n$, то есть на единицу больше уравнений. Система имеет один свободный параметр, поэтому один потенциал (обычно $u_1 = 0$) выбирают произвольно. На оценки $\Delta_{ij}$ это не влияет - в разности $c_{ij} - (u_i + v_j)$ сдвиг потенциалов сокращается.

Когда план транспортной задачи оптимален? План оптимален, когда все оценки свободных клеток неотрицательны: $\Delta_{ij} \ge 0$ для каждой незанятой клетки. Это означает, что любое введение новой перевозки только увеличит стоимость, поэтому дешевле уже не сделать.

Коротко

Метод потенциалов решает транспортную задачу в два этапа: сначала строят опорный план (например, методом северо-западного угла из $m + n - 1$ занятых клеток), затем по потенциалам $u_i$ и $v_j$, найденным из условия $u_i + v_j = c_{ij}$, считают оценки свободных клеток $\Delta_{ij} = c_{ij} - (u_i + v_j)$. Если все оценки неотрицательны - план оптимален; отрицательная оценка указывает клетку, в которую вводят перевозку, после чего план улучшают по циклу пересчёта и повторяют до оптимума.