Метод потенциалов. 
Методы нахождения начального решения транспортной задачи

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.

Идея метода потенциалов для решения транспортной задачи сводится к следующему. Представим себе, что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё равно куда) какую-то сумму ai; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму bj. Эти платежи передаются некоторому третьему лицу («перевозчику»). Обозначим ai + bj = иij (i=1. m; j=1. n) и будем называть величину иij «псевдостоимостью» перевозки единицы груза из Ai в Bj. Заметим, что платежи ai и bj не обязательно должны быть положительными; не исключено, что «перевозчик» сам платит тому или другому пункту какую-то премию за перевозку.

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

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

• 1. Взять любой опорный план перевозок, в котором отмечены m +n — 1 базисных клеток (остальные клетки свободные).
• 2. Определить для этого плана платежи (ai и bj) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.
• 3. Подсчитать псевдостоимостииi, j = ai + bj для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.
• 4. Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости).
• 5. После этого заново подсчитываются платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план.

Рассмотрим пример транспортной задачи.

Исходная транспортная матрица

В табл. 2.2 по строкам матрицы представлены пункты (станции) отправления от А1 до А4 и объемы погрузки в тоннах — 100, 150, 90, 30 т, а по столбцам — пункты (станции) назначения от В1 до В5 и объемы выгрузки — 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (ai = bj = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А1 и станцией выгрузки В1, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом — 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, — оптимальным планом перевозок.