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

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

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

     .       

     Стоимость  перевозки  единицы  груза  из A_i в  B_j равна  C _ij; таблица  стоимостей  задана. Требуется  найти  план  перевозок x_ij, который  удовлетворял  бы   балансовым  условиям  и  при  этом  стоимость  всех перевозок бала минимальна.       Идея  метода  потенциалов  для  решения  транспортной задачи  сводиться  к  следующему. Представим  себе что  каждый  из пунктов  отправления  A_i вносит  за  перевозку  единицы  груза (всё  равно  куда)  какую-то  сумму  α_i ;

  в  свою  очередь  каждый  из  пунктов  назначения  B_j   также  вносит  за  перевозку  груза  (куда  угодно)  сумму  β_j. Эти платежи передаются некоторому третьему лицу(“перевозчику“).Обозначим    a_i +b_j  =  č_ij  (i=1..m; j=1..n)  и  будем  называть  величину č_ij “псевдостоимостью” перевозки единицы груза из A_i в B_j.

Заметим,что  платежи   α_i и β_j не  обязательно  должны  быть  положительными;не исключено,что  “перевозчик”  сам  платит  тому  или  другому  пункту  какую-то премию за перевозку.

Также надо отметить,что суммарная псевдостоимость любого допустимого плана перевозок  при  заданных  платежах  (α_i и β_j)  одна  и  та  же  и  от  плана  к  плану не меняется.      До сих пор  мы никак не связывали  платежи (α_i и β_j) и псевдостоимости  č_ij с истинными стоимостями перевозок C_ij. Теперь мы  установим  между ними связь. Предположим, что план x_ij невырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех  этих  клеток  x_ij>0. Определим платежи (α_i и β_j) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям: 

     č_ij=α_i+β_j=с_ij, при x_ij>0.      Что касается свободных клеток (где x_ij=0), то  в  них  соотношение  между  псевдостоимостями  и  стоимостями  может  быть,какое угодно.       Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает,является ли план оптимальным или же он может быть улучшен. Существует  специальная  теорема:  Если  для  всех  базисных  клеток плана  x_ij>0,      α_i+β_j=č_ij=с_ij, а для всех свободных клеток x_ij=0,       α_i+β_j=č_ij≤с_ij, ,то  план является оптимальным  и никакими способами улучшен быть не может. Нетрудно показать, что  это  теорема  справедлива  также  для вырожденного  плана, и  некоторые из базисных переменных  равны  нулю. План обладающий свойством:        č_ij= с_ij  (для всех базисных клеток)               (2.35)       č_ij ≤ с_ij  (для всех свободных клеток)             (2.36)  

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

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

(α_iи β_j) удовлетворяющая  условию (2.35),для  каждой  свободной  клетки  цена  цикла  пересчёта  равна  разности  между стоимостью и псевдостоимостью в данной клетке: 

γ_i,j=с_i,j - č_i,j.      Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее  трудоёмкий  элемент распределительного  метода: поиски  циклов  с  отрицательной  ценой.       Процедура  построения  потенциального  (оптимального)  плана  состоит  в  следующем.      В  качестве  первого  приближения  к  оптимальному  плану    берётся  любой  допустимый  план (например,  построенный  способом  минимальной стоимости по строке).В этом плане  m+n-1 базисных клеток,где m - число строк, n –число столбцов транспортной таблицы.

Для этого плана можно определить платежи (α_i и β_j), так,чтобы  в  каждой  базисной клетке выполнялось условие: 

     α_i+β_j=с_ij         (2.37)     Уравнений(2.37) всего  m+n-1,а число неизвестных равно m+n. 

Следовательно,одну из этих неизвестных можно задать произвольно(например, равной  нулю).

После этого из  m+n-1 уравнений 

(2.37)  можно  найти  остальные  платежи   α_i, β_j,

а  по  ним  вычислить  псевдостоимости, č_i,j=α_i+β_j  для  каждой свободной  клетки. 

Таблица 2.7

	В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

      α₄ =0,=> β₄=6, так как  α₄+β₄=С₄₄=6,

=>      α₁=0, так как  α₁+β₄=С₁₄=6, 

=>      β₃=5, так как  α₁+β₃=С₁₃=5, 

=>      β₁=7, так как  α₄+β₁=С₄₁=7, 

=>      α₂=-1, так как  α₂+β₁= С₂₁=6, 

=>      β₅=6, так как  α₂+β₅=С₂₅=5,

=>      α₃=1, так как  α₃+β₅=С₃₅=7, 

=>      β₂=6, так как  α₃+β₂=С₂₅=7.

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

Таблица 2.8

	10	8	5 42	6 6	9	0
	6 + 4	7	8	6	5 - 26	-1
	8	7 27	10	8	7 + 0	1
	7 - 14	5 +	4	6 6	8	0
	7	6	5	6	6

          Теперь будем перемещать по циклу число 14,так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком  -.При перемещении мы будем вычитать 14 из клеток со знаком  -  и прибавлять к клеткам со знаком +.      После этого необходимо подсчитать потенциалы α_iи β_j и цикл расчетов повторяется.     Итак,мы приходим к следующему алгоритму  решения  транспортной  задачи  методом  потенциалов:

1. Взять  любой  опорный  план  перевозок, в  котором  отмечены m+n-1 базисных клеток (остальные клетки свободные).

2. Определить для этого плана платежи (α_iи β_j)исходя  из  условия,  чтобы  в  любой  базисной клетке псевдостоимости были равны стоимостям.Один из платежей можно назначить произвольно, например , положить равным нулю.

3. Подсчитать  псевдостоимости  č_i,j=α_i+β_j для  всех  свободных  клеток. Если  окажется, что  все они не превышают стоимостей, то план  оптимален.

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

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

     Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F₀=723,F₁=709,F₂=F_min=703.      Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же F_min = 703.