Проверка оптимальности плана и перераспределение поставок с помощью метода потенциалов

Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления и назначения, называемые потенциалами.

Вычисление потенциалов

Сопоставим каждому поставщику A_i и каждому потребителю B_j величины u_i и v_j соответственно так, чтобы для всех базисных клеток плана были выполнены соотношения

u_i + v_j = c_ij, i = 1,2,...,n, j = 1,2,...,n.

Поскольку число базисных клеток в плане равно m + n - 1 (вырожденные планы должны быть предварительно пополнены), то для определения потенциалов получается система из m + n - 1 уравнений с m + n неизвестными. Такая система имеет бесконечное множество решений. Нам требуется любое ее решение. Обычно для простоты полагают один из потенциалов равным нулю и затем вычисляют остальные. В транспортной таблице для потенциалов v₁,v₂,...,v_n заводится дополнительные строка, а для потенциалов u₁,u₂,...,u_n – дополнительный столбец, куда проставляются найденные значения.

Проверка оптимальности плана

Для каждой свободной клетки плана вычислим разности Δс_ij = c_ij - (u_i + v_j) и запишем полученные значения в левых нижних углах соответствующих клеток. Заметим, что для базисных клеток выполнено соотношение Δс_ij = 0, и этим фактом можно пользоваться для контроля правильности нахождения потенциалов.

План является оптимальным, если все разности Δс_ij ≥ 0. В противном случае план можно улучшить следующим способом.

Перераспределение поставок

Найдем клетку с наибольшей по абсолютной величине отрицательной разностью Δc_ij и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен.

Заметим, что в новом плане суммы элементов по строкам и столбцам должны остаться прежними, поэтому изменение значения в одной клетке цикла повлечет за собой соответствующие изменения значений во всех остальных клетках этого цикла. Так как в свободной клетке значение будет увеличено, то проставим в ее правом нижнем углу знак "+". Теперь пройдем по всей ломаной цикла, проставляя в правых нижних углах клеток поочередно знаки «плюс» и «минус».

Груз будет перераспределен по клеткам цикла на величину Δx = min x_ij следующим образом. В клетках со знаком «плюс» значение перевозки нужно увеличить на величину Δx , а в клетках со знаком «минус» – уменьшить на величину Δx . Так как после пересчета у нас добавилась лишняя базисная клетка, то их количество необходимо сократить, убрав нуль в одной из клеток цикла. Если таких клеток получилось несколько, то свободной делаем ту из них, в которой тариф перевозок максимален.

После этого полученный план проверяется на оптимальность описанным выше способом. Перераспределение груза производится до тех пор, пока очередной план не станет оптимальным. На этом действие алгоритма завершается.

Пример