Алгоритм метода потенциалов

Предположим, у нас имеется некоторый план перевозок. Производим следующие действия:

1. Для каждого поставщика и каждого потребителя найдем потенциалы и по следующим правилам:

а) ;

б) для каждой загруженной клетки должно выполняться равенство .

Другими словами, по загруженным клеткам составляем, затем решаем систему уравнений

2. Для каждой незагруженной клетки вычисляем разность . Если разности неотрицательны, процесс решения прекращается – имеющийся план перевозок оптимальный. Если же найдется хотя бы одна разность , то среди всех отрицательных значений выберем наибольшее по модулю и в соответствующей клетке поставим знак «+».

3. В имеющейся распределительной таблице построим замкнутый контур одного из видов

а) ; б) ; в)

с углами в загруженных клетках и в этой клетке со знаком «+». На практике при построении такого контура можно руководствоваться следующими правилами: нужно «выйти» из клетки, помеченной знаком «+»; «передвигаться» только по горизонтали и вертикали; «поворачивать» только в загруженных клетках и только на 90^о; «вернуться» в клетку со знаком «+». При этом следует иметь в виду, что, во-первых, стараться «обойти» все загруженные клетки не нужно; во-вторых, «проходить», не «поворачивая», можно как через загруженные, так и через незагруженные клетки, важно только «поворачивать» в загруженных клетках; в-третьих, такой замкнутый контур всегда существует и является единственным.

4. «Обходя» построенный контур в каком-нибудь направлении, в его углах ставим поочередно знаки «–» и «+», при этом «обход» начинаем из клетки, которую мы пометили знаком «+» на шаге 2 данного алгоритма. Обратите особое внимание на то, что знаки «–» и «+» ставятся только в клетках, в которых контур «поворачивает». Признаком правильности расстановки этих знаков может служить то, что на любых двух соседних «поворотах» знаки должны быть различными.

5. Строим следующую распределительную таблицу, в которую перенесем без изменений, во-первых, тарифы перевозок, во-вторых, загрузки клеток, не помеченных знаками «–» и «+». Новые загрузки клеток со знаками «–» и «+» найдем по следующим правилам. Среди загрузок клеток со знаком «–» выберем минимальную, затем выбранную минимальную загрузку нужно в клетках со знаком «+» прибавить, а в клетках со знаком «–» отнять от имеющихся там загрузок. При этом хотя бы в одной из клеток со знаком «–» появится нулевая загрузка. Если такая клетка со знаком «–» с нулевой загрузкой одна, то в новой таблице в данной клетке нулевую загрузку не пишем; если же таких клеток несколько, в новой таблице нулевую загрузку не пишем только в одной из этих клеток, а именно, в клетке с максимальным тарифом.

6. Снова вычисляем потенциалы и (см. шаг 1) и т. д. Процесс продолжается до тех пор, пока все разности (см. шаг 2) не окажутся неотрицательными.