Решения транспортной задачи методом потенциалов

Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.

Процедура построения потенциального (оптимального) плана состоит в следующем. В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m + n - 1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (ai и bj), так, чтобы в каждой базисной клетке выполнялось условие: ai + bj = сij (3)

Уравнений всего m+n-1, а число неизвестных равно m+n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений можно найти остальные платежи ai, bj, а по ним вычислить псевдостоимости, иi,j= ai + bj для каждой свободной клетки.

Таблица №5

4 = 0,

b4 = 6, так как a4 + b4 = С44 = 6,1= 0, так как a1 + b4 = С14 = 6,3 = 5, так как a1 + b3 = С13 = 5,1 = 7, так как a4 + b1 = С41 = 7,2= - 1, так как a2 + b1 = С21 = 6,5 = 6, так как a2 + b5 = С25 = 5,3= 1, так как a3 + b5 = С35 = 7,2 = 6, так как a3 + b2 = С25 = 7.

Если оказалось, что все эти псевдостоимости не превосходят стоимостей иij и сij, и і то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке. В таблице № 5 мы получили в двух клетках иij и сij, теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность иij - сij максимальна. В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2):