Метод потенциалов

Каждому поставщику поставим в соответствие некоторый потенциал α _i, а каждому потребителю – потенциал β _j (таблица 3.2.5.).

Таблица 3.2.5 – Оптимизация плана перевозок методом потенциалов

Присвоим любому потенциалу произвольное значение, например α₃ = 0. Остальные потенциалы легко определяются из условия, что для любой занятой клетки α _i + β _j = Z _ij.

Для каждой свободной клетки вычислим псевдостоимость P _ij = α _i + β _j и разность между стоимостью и псевдостоимостью Δ _ij = Z _ij – P _ij.

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

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

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

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

Процедура повторяется до тех пор, пока есть отрицательные циклы.