Метод потенциалов предназначен для решения транспортной задачи в матричной постановке. Потенциалы — это двойственные переменные. Сам метод — прямой, на каждом шаге выбирается одно из двойственных ограничений, которое не выполняется и исправляется таким образом, чтобы не нарушить ограничения прямой задачи. Постепенно в двойственной задаче ограничения будут выполнены, что будет означать оптимальность
в прямой задаче.
Таблица для метода потенциалов имеет следующий вид:
Каждая ячейка (i, j) таблицы хранит информацию о цене (cij) и о количестве перево-
зимого товара (xij). В процессе решения задачи часть клеток будем называть базисными (их всегда будет m + n − 1), а остальные — небазисными (или свободными).
Aлгоритм
Шаг 0 Замкнуть задачу, если она не замкнута. Перейти на шаг 1.
Шаг 1 Нарисовать начальную таблицу. Перейти на шаг 2.
Шаг 2 Рассчитать начальный план перевозок (например, методом северо-западного угла)
и выделить базисные клетки. Вычислить значение целевой функции. Перейти на
шаг 3.
Шаг 3 Рассчитать значения потенциалов. Положить u1 = 0 (или любому другому числу). Остальные потенциалы рассчитать с помощью базисных клеток, исходя из
уравнения ui + vj = cij. Перейти на шаг 4.
Шаг 4 Для свободных клеток рассчитать оценки sij = cij − ui − vj
. Если все sij > 0, то найдено оптимальное решение. Перейти на шаг 6.
Иначе выполнить шаг 5.
Шаг 5 Из небазисных клеток выбрать ту, у которой оценка sij минимальна и для нее
выполнить следующую процедуру:
∙ Построить цикл для этой клетки. Цикл — это замкнутая ломаная линия, кото-
рая чередует вертикальное и горизонтальное направления и проходит только
по базисным клеткам. В исходной клетке поставить « + » и далее по циклу
расставить, чередуя, « + » и « − ».
∙ Вычислить λ = min{xij : «-»}. Клетку, на которой достигается этот минимум,
убрать из базиса (только одну), а клетку (i, j) (у которой минимальная оцен-
ка sij) сделать базисной.
∙ Нарисовать новую таблицу, с пересчитанным планом перевозок: для клеток
с « + » прибавить λ к xij а для клеток с « − » — вычесть. Остальные клетки
остаются как были. Пересчитать целевую функцию: z′ = z + min sij · λ.
Перейти на шаг 3.
Шаг 6 Конец алгоритма.
