Сущность алгоритма метода дифференциальных рент

     i =1i j =1j

                              

           

                        (4.28)

 

     В  задаче необходимо найти оптимальный  план снабжения лесоматериалами

деревообрабатывающих  предприятий, при котором суммарные  затраты на производство и

доставку всех лесоматериалов были бы минимальными.

     Иными  словами, требуется найти матрицу  неотрицательных чисел хij:

      x11          x12           x13 a1 ,

    x 21          x 22          x 23 a 2 ,                                              (4.29)

     x31           x32            x33 a3 ,

     b1               b2               b3

 

которая минимизировала бы целую функцию

                 3      3

     F = ∑  ∑ cij xij .                                                                  (4.30)

                j =1 j =1

 

при условиях:

      3

 

     ∑x

     i =1

            ij   = ai               i = 1,2,3,                                           ( 4.31)

      3

 

     ∑x

     j =1

            ij   = bj               j = 1,2,3,                                           ( 4.32)

 

            x ij ≥ 0.

     Таким  образом, в условии задачи содержится  шесть ограничений с девятью

неизвестными.

     Отыскание        оптимального плана  поставок   проводится    за    несколько

последовательных приближений (итераций).

     Первая  итерация. Прежде представим исходные  данные в рабочей табл.4.13.

 

Затем в каждом столбце отметим минимальный  показатель затрат1 сij , по которым

каждый потребитель  мог бы получить лесоматериал, если бы мощности поставщиков,

связанных с  ними минимальными сij, не были ограничены.

     Если  в каком-либо столбце окажется  несколько одинаковых (наименьших) значений

себестоимости поставок, то отмечается только одна, причем безразлично какая. Далее

составляется  схема распределения лесоматериалов в соответствии с отмеченными

жирным шрифтом  минимальными затратами.

     Распределение  продукции по клеткам с выделенными  минимальными значениями

себестоимости начинается с первого столбца, при  этом в клетку записывается поставка

      xij = min(a i , b j ).                                             (4.33)

     Если  к моменту записи очередной  поставки исчерпана мощность  соответствующего

поставщика или  полностью удовлетворен спрос соответствующего потребителя, то в

клетку следует  записывать нулевую поставку. Проведем распределение лесоматериалов

применительно к рассматриваемому примеру: в клетку А2В1 записываем поставку

х21=min(300, 200)=200, в  клетку А1В2 - поставку х12=min(200, 280)=200. Поскольку

мощность первого  поставщика А1 оказалась исчерпаной, в клетку А1В3 записывается

поставка х13=0.

     По  окончании распределения схема  проверяется на допустимость, т.е.  исчерпаны ли

мощности поставщиков  и удовлетворен ли спрос потребителей. В нашем примере

целиком распределены лесоматериалы поставщика А1, как наиболее дешевые, и частично

лесоматериалы поставщика А2 (200 из 300 тыс.м3).

     1

       Числа, которые набраны жирным  курсивом.

     По  этой схеме полностью удовлетворяется  спрос лишь потребителя В1 и  частично

потребителя В2 (200 из 280 тыс.м3). Поэтому эта схема распределения не является

допустимым планом поставок, т.е. не является решением задачи. В связи с этим далее

необходимо произвести оценку каждого поставщика в следующем  порядке.

     Если  вся продукция поставщика полностью  распределена, а спрос связанных с ним

потребителей, отмеченных жирным шрифтом, не удовлетворен в полной мере, то такой

поставщик считается  недостаточным и оценкой его  служит недостаток, равный величине

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

распределена  не полностью, он считается избыточным. Оценкой его служит

нераспределенная  часть продукции со знаком плюс.

     Если  в какой-либо строке нет ни  одного значения себестоимости,  отмеченного

кружком или  жирным шрифтом, то оценкой такого избыточного поставщика служит

число, равное его  мощности.

    

 
 
 
 
 
 
 
 
 
 
 
 

Данные оценки поставщика заносятся в последнюю  графу рабочей табл.4.2.

       Табл.4.2

 

Поставщики и  их                    Потребители и их спрос            Оценка                           мощности                   В1             В2            В3                  поставщиков

                                  200            280           270                                          

     А1           200        9                7             8               -350

                                                      200            0

     А2           300        6                8             10             +100

                                        200

     А3           250        11               9             12             +250

 

Разность

 себестоимости             -              1             2

                                                                

 
 

                                                                                 

 
 
 
 

     В  нашем примере поставщик          А1 является недостаточным, так  как спрос

потребителей  В2В3, связанных с ним минимальными себестоимостями, равен 280+270=550

тыс.м3, а мощность А1 только 200 тыс.м3. Поэтому его оценка будет - 350, величина,

которая характеризует  неудовлетворенную часть спроса потребителей В2 и В3.

     Поставщик  А2 является избыточным, поскольку  не вся его продукция распределена;

его оценка +100 (300 - 200).

     Продукция  поставщика А3 осталась полностью нераспределенной, следовательно, он

избыточный, его  оценка +250.

     Строчку  матрицы с избыточным поставщиком  принято называть положительной,  а с

недостаточным поставщиком - отрицательной.

     Здесь  следует заметить, что при правильной  оценке всех поставщиков

алгебраическая  сумма оценок всегда равна нулю.

     Поскольку  наиболее "дешевых" лесоматериалов  поставщика А1 в связи с его

ограниченными ресурсами недостаточно для удовлетворения всех потребностей

потребителей  В2 и В3 , приходится предусматривать использование свободных ресурсов

поставщиков А2 и А3. При этом сначала будут  использоваться лесоматериалы, затраты  на

которые отличаются от затрат на лесоматериалы, в данном случае поставщика А1, в

наименьшей мере.

     Для  этого в столбцах матрицы себестоимости поставок необходимо определить

разность между  наименьшей себестоимостью сij в одной  из положительных строк с

минимальной себестоимостью, отмеченной жирным шрифтом в этом столбце.

Полученные разности записываются в нижней строке таблицы.

     В  тех столбцах матрицы, где есть хотя бы одна себестоимость, отмеченная жирным

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

       В нашем примере в первом  столбце В1 минимальная себестоимость  с21=6=min

находится в  положительной строке А2, следовательно, для этого столбца В1 разность не

вычисляется. Во втором столбце В2 себестоимость  с12=7=min расположена в

отрицательной строке. Ближайший к ней по величине показатель одной из

положительных строк с22=8. Поэтому разность себестоимости  для данного столбца В2

равна 1 (8—7). Таким  же способом определяется разность себестоимости  и по другим

столбцам.

       Наименьшую из вычисленных разностей  принято называть промежуточной

рентой. В таблице ее следует отметить квадратом (заключить в него). В нашем примере

промежуточная рента равна 1 столбец В2.

       Вторая итерация заключается  в составлении новой таблицы-матрицы  (табл. 4.3)

транспортной  задачи и обработке данных, помещенных в ней. При ее составлении

себестоимости поставок по отрицательным строкам  увеличиваются на величину

исчисленной в  предыдущей итерации промежуточной  ренты. Себестоимости поставок по

положительным строкам переписываются в эту  новую таблицу без изменения. В нашем

примере на промежуточную ренту 1 следует увеличить себестоимости строки А1.

                                                                            Табл.4.3

 

  Поставщики  и их                   Потребители и их спрос                 Оценки

     мощности                В1              В2               В3         поставщиков

                            200             280              270

    А1     200         10               8              9                    -250

                                                0                  200

    А2     300         6                8              10                    -0

                                  200           100

 
 

                                                                                      177

 
 

    А3     250          11              9                12                    +250

 

       Разность           1             5                  3

    себестоимости            

 

        Последовательность выполнения  второй и последующих итераций  остается общей

— подобной первой итерации. Однако есть здесь и свои особенности.

        Сначала отмечаются кружками  или жирным шрифтом все минимальные

себестоимости поставок по столбцам, считая и повторяющиеся  по величине. Затем снова

по минимальным  для каждого потребителя затратам, отмеченным полужирным шрифтом,

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