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

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

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

 

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

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

å x_i,j  = a_i  ( i=1..m ; j=1..n );   

å x_i,j =b_j  ( j=1..n ; 1..m ),

причём  å a_i = å b_j 

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

Рекомендуемые материалы

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

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

č_i,j = a_i  + b_j  = с_i,j ,  при   x_i,j  >0.

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

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

a_i  + b_j  = č_i,j= с_i,j ,

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

a_i  + b_j  = č_i,j≤ с_i,j ,

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

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

                       č_i,j≤ с_i,j ( для  всех  свободных  клеток ) (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  = с_i,j   (3)

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

Таблица 6

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

č_i,j £ с_i,j ,                            £ ³

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

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

Таблица 7

Теперь будем перемещать по циклу число 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.

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

В  предыдущих  случаях  мы  рассматривали  только  такую  задачу  о  перевозках, в  которой  сумма  запасов  ровна  сумме  заявок:

           å а_i = å b_j ( где i=1,...,m ; j=1,...,n )   (4)

Это  класическая  транспортная  задача, иначе  называемая, транспортной  задачей  с  правильным  балансом. Встречаются  такие   варианты  транспортной  задачи  где  условие  (4)  нарушено. В  этих  случаях  говорят  о  транспортной  задаче    с  неправильным  балансом.

Баланс  транспортной  задачи  может  нарушаться  в  2-ух  направлениях:

         1. Сумма  запасов  в  пунктах  отправления  превышает  сумму  поданных  заявок

           å а_i > å b_j  ( где i=1,...,m ; j=1,...,n );

         2. Сумма  поданных  заявок  превышает  наличные  запасы

                   å а_i < å b_j  ( где i=1,...,m ; j=1,...,n );

Условимся  первый  случай  называть “Транспортной  задачей  с  избытком  запасов“, а  второй — “Транспортной  задачей  с  избытком  заявок”.

Рассмотрим  последовательно  эти  два  случая:

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

В  пунктах  A₁, A₂, ... , A_m  имеются  запасы груза  a₁, a₂, ... , a_m;  пункты  B₁, B₂, ... , B_n   подали  заявки  b₁, b₂, ... , b_n, причём

 å а_i > å b_j ( где i=1..m ; j=1..n ).

Требуется  найти  такой  план  перевозок (X), при  котором  все  заявки  будут  выполнены, а  общая  стоимость  перевозок  минимальна. Очевидно  при  этой  постановке  задачи некоторые условия-равенства транспортной задачи превращаются  в  условия-неравенства, а  некоторые —  остаются  равенствами.

 _n

å X_i,j ≤ a_i  (i=1, ... , m);  

        ^j=1

            _m

å X_i,j = b_j  (j=1, ... , n). 

Вместе с этой лекцией читают "4.1 Исторический поворот России".

        ⁱ⁼¹

Мы  умеем  решать  задачу  линейного  программирования, в  какой  бы  форме — равенств  или  неравенств  ни  были  бы  заданы  её  условия. Поставленная  задача   может  бать  решена, например, обычным  симплекс-методом. Однако, задачу  можно  решить  проще, если  искусственным  приёмом  свести  её  к  ранее  рассмотренной  транспортной  задаче  с  правильным  балансом.  Для  этого, сверх  имеющихся  n  пунктов  назначения  В₁, B₂, ... , B_n,  введём  ещё   один, фиктивный, пункт  назначения   B_n+1, которому   припишем  фиктивную  заявку, равную  избытку  запасов  над  заявками  

           b_n+1 = å а_i - å b_j   ( где i=1,...,m ; j=1,...,n ) ,

а  стоимость  перевозок  из  всех  пунктов  отправления  в  фиктивный  пункт  назначения  b_n+1  будем  считать  равным  нулю. Введением  фиктивного  пункта  назначения  B _n+1  с  его  заявкой  b _n+1  мы  сравняли  баланс транспортной задачи и теперь его можно решать как обычную  транспортную  задачу  с  правильным  балансом.

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

Эту задачу можно свести к обычной транспортной задаче с правильным  балансом,  если  ввести  фиктивный пункт отправления A_m+1 с  запасом a_m+1 равным недостающему запасу и стоимость перевозок из  фиктивного  пункта  отправления  во  все  пункты  назначения  принять  равным  нулю.