Метод математического моделирования

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

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

      В  качестве  первого  приближения  к  оптимальному  плану    берётся  любой  допустимый  план (например,  построенный  способом  минимальной стоимости по строке). В этом плане  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. 

3.2. Практическая реализация  модифицированным распределительным методом

Задача : У поставщиков A1 , A2 , находится соответственно 600 , 450 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 ,   Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 6 , 8 , 10 , 20 , 13 ден.ед.     B5 в количествах 150 , 200 , 350 , 250 , 100 единиц соответственно.

 

Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 8 , 10 , 8 , 14 , 10 ден.ед.

Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.

Решение :

Что мы будем делать?   Найдем начальное решение методом северо-западного угла. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя модифицированный распределительный метод, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.

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

В нашем  случае, потребность всех потребителей - 1050 единиц продукции равна запасам  всех поставщиков .

1)

Согласно  условию задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)

B 1 B 2 B 3 B 4 B 5   A 1 -     6     -     8     -     10     -     20     -     13     600 A 2 -     8     -     10     -     8     -     14     -     10     450 Потребность 150 200 350 250 100