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

 

      Будем  заполнять  таблицу  перевозками  постепенно  начиная  с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать  при этом  следующим образом. Пункт В₁   подал заявку    на  18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося  в пункте  А₁ , и запишем перевозку 18 в клетке (1,1). После этого заявка  пункта  В₁ удовлетворена, а в пункте  А₁  осталось  ещё 30  единиц  груза. Удовлетворим  за  счёт  них заявку  пункта  В₂ (27  единиц), запишем 27  в клетке (1,2); оставшиеся  3  единицы пункта  А₁  назначим  пункту  В₃. В составе заявки  пункта  В₃  остались  неудовлетворёнными  39  единиц.  Из  них 30  покроем за  счёт  пункта А₂, чем его запас будет исчерпан, и   ещё 9  возьмём из  пункта  А₃. Из  оставшихся  18  единиц  пункта  А₃ 12  выделим пункту В₄;  оставшиеся  6  единиц  назначим  пункту  В₅,  что вместе  со  всеми 20  единицами пункта  А₄  покроет его заявку.  На  этом  распределение запасов закончено;  каждый  пункт назначения   получил груз,  согласно  своей заявки. Это выражается  в том, что сумма перевозок в каждой  строке  равна   соответствующему   запасу, а в столбце - заявке. Таким образом, нами  сразу же  составлен план  перевозок,  удовлетворяющий  балансовым  условиям. Полученное  решение  является  опорным  решением  транспортной  задачи:    

            Таблица № 2 

ПН ПО   В1   В2   В3   В4   В5 Запасы аi А1 10 18 8 27 5 3 6 9 48 А2 6 7 8 30 6 5 30 А3 8 7 10 9 8 12 7 6 27 А4 7 5 4 6 8 20 20 Заявки bj 18 27 42 12 26 125

 

      Составленный  нами план перевозок, не является оптимальным  по  стоимости, так  как  при  его   построении  мы  совсем  не  учитывали  стоимость   перевозок  С_ij .

      Другой  способ - способ минимальной стоимости  по строке - основан на том, что мы распределяем продукцию от пункта A_i не в любой из пунктов B_j, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов B_j. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке выглядит, так как показано  в таблице № 3.

      При этом методе может получиться, что  стоимости перевозок C_ij и C_ik от пункта A_i к пунктам B_j и B_k равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2:  C₂₁ = C₂₄, но заявка b₁ больше заявки b₄, поэтому 4 единицы продукции мы распределим в клетку (2,1).

Таблица № 3

 

ПН ПО   В1   В2   В3   В4   В5 Запасы аi А1 10 8 5 42 6 6 9 48 А2 6 4 7 8 6 5 26 30 А3 8 7 27 10 8 7 0 27 А4 7 14 5 4 6 6 8 20 Заявки bj 18 27 42 12 26 125

 

      Способ  минимальной стоимости по столбцу  аналогичен предыдущему способу. Их отличие состоит в том, что  во втором способе мы распределяем продукцию от пунктов B_i к пунктам A_j по минимальной стоимости C_ji.

      Опорный план, составленный способами минимальных  стоимостей, обычно более близок к  оптимальному решению. Так в нашем  примере общие затраты на транспортировку  по плану, составленному первым способом F₀ = 1039, а по второму F₀ = 723.

      Клетки  таблицы, в  которых  стоят  ненулевые  перевозки,  являются  базисными. Их  число должно  равняться   m + n - 1.  Необходимо отметить  также, что встречаются такие ситуации, когда количество  базисных    клеток  меньше  чем m + n - 1. В этом   случае распределительная задача    называется  вырожденной.  И следует в одной из  свободных клеток поставить количество  перевозок равное нулю. Так, например, в таблице № 3:

      m + n - 1 = 4 + 5 - 1 = 8,

      а базисных клеток 7, поэтому нужно  в одну из клеток строки 3 или столбца 2 поставить значение “0”. Например в клетку (3,5).

      Составляя план по способам минимальных стоимостей в отличии от плана по способу северо-западного угла мы учитываем стоимости перевозок C_ij, но все же не можем утверждать, что составленный нами план является оптимальным.  

Глава III 

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

          С помощью рассмотренных методов построения первоначального опорного плана можно получить вырожденный или невырожденный опорный план. Построенный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, содержащих тп неизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распределительный метод) и метод дифференциальных рент.

Модифицированный  распределительный метод. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить  отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).       

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

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

       

        

      

      

             

      Стоимость  перевозки  единицы  груза  из 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.