Каждому поставщику поставим в соответствие некоторый потенциал α i, а каждому потребителю – потенциал β j (таблица 3.2.5.).
Таблица 3.2.5 – Оптимизация плана перевозок методом потенциалов
Присвоим любому потенциалу произвольное значение, например α3 = 0. Остальные потенциалы легко определяются из условия, что для любой занятой клетки α i + β j = Z ij.
Для каждой свободной клетки вычислим псевдостоимость P ij = α i + β j и разность между стоимостью и псевдостоимостью Δ ij = Z ij – P ij.
Запишем псевдостоимость в левых нижних уголках свободных клеток, а разность в кружках. Сравнивая эти разности с результатами, полученными в предыдущем разделе, убеждаемся, что они характеризуют оценки соответствующих циклов.
Для клетки с наибольшей по модулю отрицательной разностью составляется единственный цикл, по которому и производится перестановка.
Перестановки могут осуществляться и сразу по нескольким циклам, но только в том случае, если они охватывают разные клетки.
По циклам, как и ранее, переставляется минимальное количество грузов, стоящее в отрицательных клетках.
Процедура повторяется до тех пор, пока есть отрицательные циклы.