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

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

1) ,-для занятых клеток

2) для свободных клеток .(S_ij = c_ij - (u _i+ v_j) )

I шаг (вычисление потенциалов).
Условие (1) представляет собой систему из (m + n – 1) линейных уравнений с (m + n) неизвестными потенциалами. Поэтому одно из неизвестных полагаем равным 0 для определенности, затем последовательно находим остальные потенциалы.

II шаг (проверка плана на оптимальность).
Для проверки плана на оптимальность необходимо проверить условие (2), т.е. проверить оценки . Для занятых клеток S_ij=0. Если для свободных клеток выполняется условие S_ij = c_ij - (u _i+ v_j) , то план является оптимальным и задача решена.

Если же хоть одна оценка отрицательна – то план не оптимальный.

Отрицательные оценки показывают, насколько возрастет целевая функция, если в эту клетку сделать поставку, равную 1.

III шаг (улучшение плана).
Опр. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

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

Примеры циклов:

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

 

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

Среди клеток с «-» ищем минимальную поставку, обозначим эту величину за Δ

Строим новый план по правилу:

 

Так как после пересчета у нас добавилась лишняя занятая клетка, то их количество необходимо сократить, убрав нуль в одной из клеток цикла. Если таких клеток получилось несколько, то свободной делаем ту из них, в которой тариф перевозок максимален.

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