Алгоритм метода потенциалов состоит из следующих этапов:

1. Определение типа транспортной задачи (открытая или закрытая).

2. Построение первого опорного плана транспортной задачи .

3. Проверка плана транспортной задачи на оптимальность.

4. Если условие оптимальности выполняется, то имеем оптимальный план транспортной задачи. Если условие оптимальности не выполняется, необходимо перейти к следующему опорному плану.

5. Проверка нового плана транспортной задачи на оптимальность, т.е. повторение 3 и т.д.

Для построения начального опорного плана транспортной задачи используется несколько методов.

- метод северо-западного угла

Заполнение клеток таблицы начинается с верхней левой клетки. Размер поставки в эту клетку определяется меньшей из величин (a₁, b₁). Отсюда будет определена величина недопоставки продукции первому потребителю или остаток продукции у первого поставщика. В зависимости от этого заполняется клетка справа (A₁, B₂) или снизу (A₂, B₁), для которой сравнивается остаток продукции поставщика с величиной b₂ или недопоставки с величиной a₂. Каждый раз при сравнении в соответствующую клетку заносится меньшая из двух величин. Процесс распределения продолжается до тех пор, пока не будет распределена продукция всех поставщиков и удовлетворенны потребности всех потребителей.

- метод минимального элемента

Вначале заполняют те клетки таблицы, в которых стоимости перевозок самые малые. Такие действия повторяют до тех пор пока не будет распределен весь груз между пунктами назначения.

- метод двойного предпочтения

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

- метод Фогеля

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

После построения начального опорного плана транспортной задачи одним из рассмотренных методов в таблице число заполненных клеток должно быть равно т + п – 1.

Замечание.

• Если число заполненных клеток больше т + п – 1, начальный план построен неправильно и он не является опорным.

• Заполненных клеток должно быть ровно т + п – 1. Если заполненных клеток меньше, чем т + п – 1, то недостающие нужно заполнить нулями. Нулей берут столько, сколько не достает поставок. Их записывают в клетки с наименьшими тарифами, при этом нельзя допускать образования замкнутого цикла (ломаной линии с прямыми углами, в углах которого содержатся заполненные клетки).

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

Каждой строке таблицы поставим в соответствие потенциал u_i, каждому столбцу – потенциал v_j. Потенциал u₁ всегда берем равным нулю, т.е. u₁ = 0. Сумма потенциалов для заполненной клетки (A_i, B_j) должна быть равной тарифу c_ij:

u_i + v_j = c_ij . (3.4.1)

Потенциалы u_i записываем в столбце справа от таблицы, потенциалы v_j записываем в строке внизу таблицы.

Для незаполненных клеток рассчитываем оценки оптимальности как сумму потенциалов минус тариф по формуле (3.4.2):

= u_i + v_j – c_ij . (3.4.2)

Оценки оптимальности записываем в скобках в левом нижнем углу каждой незаполненной клетки таблицы. Если значение < 0, то записываем (–).