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

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

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями Стоимость перевозки единицы груза из Ai в Bj равна C ij ; таблица стоимостей задана.

Требуется найти план перевозок xij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна. Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё равно куда) какую-то сумму i ; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму j. Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим i + j = čij ( i=1 m ;j=1 n) и будем называть величину čij “псевдостоимостью” перевозки единицы груза из Ai в Bj. Заметим, что платежи i и j не обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку.

Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (i и j ) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи (i и j) и псевдостоимости čij с истинными стоимостями перевозок C ij. Теперь мы установим между ними связь. Предположим, что план xij невырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех этих клеток xij >0. Определим платежи (i и j) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям: čij = i + j = сij, при xij >0. Что касается свободных клеток (где xij = 0), то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно.

Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана xij > 0, i + j = čij= сij, а для всех свободных клеток xij =0, i + j = čij≤ сij, то план является оптимальным и никакими способами улучшен быть не может.

Нетрудно показать, что это теорема справедлива также для вырожденного плана, и некоторые из базисных переменных равны нулю. План обладающий свойством : čij= сij (для всех базисных клеток ) (1) čij≤ сij ( для всех свободных клеток ) (2) называется потенциальным планом, а соответствующие ему платежи (i и j ) — потенциалами пунктов Ai и Bj ( i=1 m ; j=1 n ). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так: Всякий потенциальный план является оптимальным.

Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей.

Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (i и j ) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке : i, j= сi, j - či, j. Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.

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

Таблица №5 ПН ПО В1 В2 В3 В4 В5 i А1 10 č = 7 8 č = 6 5 42 6 6 9 č = 6 1= 0 А2 6 4 7 č = 5 8 č = 4 6 č = 5 5 26 2= -1 А3 8 č = 8 7 27 10 č = 6 8 č = 7 7 0 3= 1 А4 7 14 5 č = 6 4 č = 5 6 6 8 č = 6 4= 0 j 1= 7 2= 6 3= 5 4= 6 5= 6 4 = 0,  4 = 6, так как 4 + 4 = С44 = 6,  1= 0, так как 1 + 4 = С14 = 6,  3 = 5, так как 1 + 3 = С13 = 5,  1 = 7, так как 4 + 1 = С41 = 7,  2= -1, так как 2 + 1 = С21 = 6,  5 = 6, так как 2 + 5 = С25 = 5,  3= 1, так как 3 + 5 = С35 = 7,  2 = 6, так как 3 + 2 = С25 = 7. Если оказалось, что все эти псевдостоимости не превосходят стоимостей čij  сij , &amp ;#61472; то план потенциален и, значит, оптимален.

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

Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке.

В таблице № 5 мы получили в двух клетках čij  сij, теперь можно построить цикл в любой из этих двух клеток.

Выгоднее всего строить цикл в той клетке, в которой разность čij  сij максимальна.

В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2): Таблица №6 ПН ПО В1 В2 В3 В4 В5 i А1 10 8 5 42 6 6 9 0 А2 6 + 4 7 8 6 5 - 26 -1 А3 8 7 - 27 10 8 7 + 0 1 А4 7 - 14 5 +  4 6 6 8 0 j 7 6 5 6 6 Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком При перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к клеткам со знаком + . После этого необходимо подсчитать потенциалы i и j и цикл расчетов повторяется.

Итак, мы приходим к следующему алгоритму решения транспортной задачи методом потенциалов. 1. Взять любой опорный план перевозок, в котором отмечены m + n - 1 базисных клеток (остальные клетки свободные). 2. Определить для этого плана платежи (i и j ) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю. 3. Подсчитать псевдостоимости či, j = i + j для всех свободных клеток.

Если окажется, что все они не превышают стоимостей, то план оптимален. 4. Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости). 5. После этого заново подсчитываются платежи и.