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

Транспортная задача с правильным балансом.

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

Пусть имеется транспортная задача с балансовыми условиями

∑xi,j = ai ( i=1 m ; j=1 n );

∑xi,j =bj ( j=1 n ; 1 m ),

причём ∑ ai = ∑ bj .

Стоимость перевозки единицы груза из Ai в Bj равна C i,j таблица стоимостей задана. Требуется найти план перевозок (xi,j), который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.

Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё ровно куда) какую-то сумму αi ; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму βj . Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим αi + βj = c

i,j (i=1 m ;j=1 n) и будем называть величину c

i,j “псевдостоимостью” перевозки единицы груза из Ai в Bj . Заметим, что платежи αi и βj не обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (αi и βj ) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи (αi и βj ) и псевдостоимости c

i,j с истинными стоимостями перевозок C i,j. Теперь мы установим между ними связь. Предположим, что план (xi,j) невырожденный (число базисных клеток в таблице перевозок ровно (m + n -1). Для всех этих клеток xi,j >0. Определим платежи (αi и βj ) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:

c

шбо = αш + βо = с

шбо б при чшбо Ю0ю

Что касается свободных клеток (где xi,j = 0), то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана (xi,j > 0)

αi + βj = c

i,j= с

i,j ,

а для всех свободных клеток ( xi,j =0)

αi + βj = c

i,j? с

i,j ,

то план является оптимальным

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

c

i,j= с

i,j (для всех базисных клеток ) (1)

c

i,j? с

i,j ( для всех свободных клеток ) (2)

называется потенциальным

планом, а соответствующие ему платежи (αi и βj ) - потенциалами пунктов Ai и Bj ( i=1, .,m ; j=1, .,n ). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так: Всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (αi и βj ) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке :