Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.
Пусть имеется транспортная задача с балансовыми условиями
 
 .
Стоимость перевозки единицы груза из Ai в Bj равна C ij; таблица стоимостей задана. Требуется найти план перевозок xij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.
Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё равно куда) какую-то сумму αi; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму βj. Эти платежи передаются некоторому третьему лицу ("перевозчику"). Обозначим ai + bj = č ij (i=1..m; j=1..n) и будем называть величину č ij "псевдостоимостью” перевозки единицы груза из Ai в Bj. Заметим, что платежи αi и βj не обязательно должны быть положительными; не исключено, что "перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (αi и βj) одна и та же и от плана к плану не меняется.
До сих пор мы никак не связывали платежи (αi и βj) и псевдостоимости č ij с истинными стоимостями перевозок Cij. Теперь мы установим между ними связь. Предположим, что план 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 (для всех базисных клеток) (2.36)
č ij ≤ с ij (для всех свободных клеток) (2.37)
называется потенциальным планом, а соответствующие ему платежи (αi и βj) — потенциалами пунктов Ai и Bj (i=1,...,m; j=1,..., n). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так:
Всякий потенциальный план является оптимальным.
Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (2.36). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (αi и βj) удовлетворяющая условию (2.36), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке: γi,j=сi,j - č i,j.
Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.
Процедура построения потенциального (оптимального) плана состоит в следующем.
В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m+n-1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (αi и βj), так, чтобы в каждой базисной клетке выполнялось условие:
αi+βj= с ij (2.38)
Уравнений (2.38) всего m+n-1, а число неизвестных равно m+n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m+n-1 уравнений (2.38) можно найти остальные платежи αi, βj, а по ним вычислить псевдостоимости, č i,j=αi+βj для каждой свободной клетки.
Таблица № 2.5
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
αi
| |
А1
|
č= 7
|
č= 6
|
|
|
č= 6
| α1= 0
| |
А2
|
|
č= 5
|
č= 4
|
č= 5
|
| α2= -1
| |
А3
|
č= 8
|
|
č= 6
|
č= 7
|
| α3= 1
| |
А4
|
|
č= 6
|
č= 5
|
|
č= 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,
то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке.
В таблице № 2.5 мы получили в двух клетках č ij≥ с ij, теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность č ij- с ij максимальна. В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2):
Таблица № 2.6
Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком -. При перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к клеткам со знаком +.
После этого необходимо подсчитать потенциалы αi и βj и цикл расчетов повторяется.
Итак, мы приходим к следующему алгоритму решения транспортной задачи методом потенциалов:
1. Взять любой опорный план перевозок, в котором отмечены m+n-1 базисных клеток (остальные клетки свободные).
2. Определить для этого плана платежи (αi и βj) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.
3. Подсчитать псевдостоимости č i,j=αi+βj для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.
4. Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости).
5. После этого заново подсчитываются платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план.
Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F0=723, F1=709, F2=Fmin=703.
Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же Fmin = 703.
|
