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

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

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

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

Распределительный  метод  решения  транспортной  задачи, с  которым мы познакомились, обладает одним недостатком: нужно  отыскивать  циклы  для   всех  свободных  клеток  и  находить  их  цены. От  этой  трудоёмкой  работы  нас  избавляет  специальный  метод  решения  транспортной  задачи, который  называется  методом  потенциалов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

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

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

 

 

      

Стоимость  перевозки  единицы  груза  из A_i  в  B_j равна C _ij ; таблица  стоимостей  задана. Требуется  найти  план  перевозок x_ij, который  удовлетворял  бы   балансовым  условиям  и  при  этом  стоимость  всех  перевозок  бала  минимальна.

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

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

č_ij = a_i  + b_j  = с_ij ,  при   x_ij  >0.

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

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

a_i  + b_j  = č_ij= с_ij ,

а  для  всех  свободных  клеток x_ij =0,

a_i  + b_j  = č_ij≤ с_ij ,

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

č_ij= с_ij (для всех  базисных  клеток ) (1)

č_ij≤ с_ij ( для всех  свободных клеток ) (2) 

называется  потенциальным  планом, а соответствующие   ему платежи (a_i  и b_j ) — потенциалами  пунктов A_i и B_j ( i=1,...,m ; j=1,...,n ). Пользуясь  этой  терминологией  вышеупомянутую  теорему  можно  сформулировать  так:

            Всякий  потенциальный  план  является  оптимальным.

 

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

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

Процедура  построения  потенциального  (оптимального)  плана  состоит  в  следующем.

В  качестве  первого  приближения  к  оптимальному  плану    берётся  любой  допустимый  план (например,  построенный  способом минимальной стоимости по строке). В этом плане  m + n - 1 базисных клеток, где m - число строк, n - число столбцов  транспортной  таблицы. Для  этого  плана  можно  определить  платежи  (a_i  и b_j ),  так, чтобы в каждой  базисной  клетке  выполнялось  условие :

a_i  + b_j  = с_ij   (3)

 

Уравнений (3)  всего  m + n - 1, а число неизвестных равно m + n.  Следовательно, одну  из  этих  неизвестных можно задать  произвольно  (например, равной  нулю). После  этого  из  m + n - 1 уравнений (3)  можно  найти  остальные  платежи   a_i, b_j, а по  ним вычислить псевдостоимости,  č_i,j= a_i  + b_j  для каждой  свободной клетки.

Таблица №5

 

ПН   ПО	В1	В2	В3	В4	В5	ai
А1	10 č = 7	8 č = 6	5      42	6 6	9 č = 6	a1= 0
А2	6 4	7 č = 5	8 č = 4	6 č = 5	5 26	a2= -1
А3	8 č = 8	7 27	10 č = 6	8 č = 7	7 0	a3= 1
А4	7 14	5 č = 6	4 č = 5	6 6	8 č = 6	a4= 0
bj	b1= 7	b2= 6	b3= 5	b4= 6	b5= 6

 

 a₄ = 0, ®

 b₄ = 6, так как a₄ + b₄  = С₄₄ = 6,  ®

a₁= 0, так как a₁ + b₄  = С₁₄ = 6,  ®

b₃ = 5, так как a₁ + b₃  = С₁₃ = 5,  ®

b₁ = 7, так как a₄ + b₁  = С₄₁ = 7,  ®

a₂= -1, так как a₂ + b₁  = С₂₁ = 6,  ®

b₅ = 6, так как a₂ + b₅  = С₂₅ = 5, ®

a₃= 1, так как a₃ + b₅  = С₃₅ = 7,  ®

b₂ = 6, так как a₃ + b₂  = С₂₅ = 7.

 

Если  оказалось, что все  эти псевдостоимости  не  превосходят  стоимостей

č_ij £ с_ij ,                            £ ³

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

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

 

Таблица №6

 

ПН   ПО	В1	В2	В3	В4	В5	ai
А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
bj	7	6	5	6	6

 

Теперь будем перемещать по циклу  число 14, так как оно является минимальным из чисел, стоящих в  клетках, помеченных знаком  - . При  перемещении мы будем вычитать 14 из клеток со знаком  -  и прибавлять к клеткам со знаком  + .

После этого необходимо подсчитать потенциалы a_i  и b_j и цикл расчетов повторяется.

Итак, мы  приходим  к следующему алгоритму  решения  транспортной  задачи  методом  потенциалов.

 

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

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

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

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

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

 

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

 

Следует отметить так  же, что оптимальный план может  иметь и другой вид, но его стоимость останется такой же F_min = 703.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы:

 

1. Еремин И.И., Астафьев  Н.Н. Введение в теорию линейного  и выпуклого программирования  М.; Наука, 1976г.

 

2. Карманов В.Г. Математическое  программирование. – М.; Наука, 1986г.

 

3. Моисеев Н.Н., Иванов  Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г.

 

4. Иванов Ю.П., Лотов А.В. Математические  модели в экономике. – М.; Наука, 1979г.

 

5. Бронштейн И.Н., Семендяев  К.А. Справочник по математике. – М.; Наука, 1986г