Прикладная математика

     Постановка  задачи:

     Однородный  продукт, сосредоточенный в трех пунктах производства (хранения) в количествах   35, 55  и 80  единиц, необходимо распределить между n-четырьмя  пунктами потребления, которым необходимо соответственно   30,  55,  44,  42  единиц. Стоимость перевозки единицы продукта из i-го пункта отправления  ( ) в j-ый пункт назначения ( ) равна с_ij  и известна для всех маршрутов.  Она  задана матрицей  С:

     

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

  Обозначим через х_ij количество груза, планируемого к перевозке от i-го поставщика ( ) j-му ( ) потребителю. При наличии баланса производства и потребления     (1)

     Общий объем производства åа_i = 80+50+35= 170 меньше , требуется всем потребителям åb_i = 30+55+44+42=171.

     Таким  образом,  имеет  место  дисбаланс  между  запасами  и  запросами.  В  математическом  плане  это  означает,  что   наша  задача – это задача  открытого типа.  Для устранения   дисбаланса (приведения  задачи  к закрытому типу),  введем  фиктивный пункт производства  с объемом производства,   равным  указанному  дисбалансу т.е. единице, причем тарифы на перевозку из  этого пункта условимся считать равными нулю  ( ).

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

     

     Четырьмя  условиями  того,  что  каждому  потребителю   доставляется  затребованное  им  количество  продукта  являются:

       

 

     В качестве  показателя  эффективности  выступает  суммарная  стоимость  перевозок   (L):

   ;

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

                                                             (1) 

     Решение:

     Сформулированная  задача  является  задачей  линейного  программирования, которая  обладает  двумя  особенностями,  а  именно

1. коэффициент  при  каждой  из  неизвестных  в  системе  ограничений  (1)  равен  1;
2. одно  из  уравнений  системы  ограничений  линейно  зависит  от  других,  в  силу  чего  число  базисных  неизвестных  в  системе  равно  .

     Эти особенности позволяют решить  задачу  специально  разработанными методами:  методом северо-западного угла  или методом наименьших  затрат.  Мы  решим ее  двумя способами. 

     Метод  наименьших  затрат 

 

     

     Обозначим через   m )  вектор симплексных множителей или потенциалов. Тогда .

     Один  из потенциалов можно выбрать  произвольно, так как в системе (1) одно уравнение линейно зависит от остальных. Положим, что р₁ = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем:

     D₁₁ = 0,   p₁ + q₁ - c₁₁ = 0, q₁ = 2

     D₁₄ = 0,   p₁ + q₄ - c₁₄ = 0, q₄ = 4

     D₃₄ = 0,  p₃ + q₄ – c₃₄ = 0, p₃ = -1

     D₃₃ = 0,  p₃ + q₃ – c₃₃ = 0,  q₃= 4

     D₂₁ = 0,  p₂ + q₁ – c₂₁ = 0,  p₂ = 2

     D₂₂ = 0,  p₂ + q₂ – c₂₂ = 0,     q₂ = -1

     D₄₄ = 0,  p₄ + q₄ – c₄₄ = 0,  p₄=-4

     Теперь  по формуле вычисляем оценки всех свободных клеток:

     D₁₂ =  p₁ + q₂ – c₁₂ = 0-1-3=-4

     D₁₃ =  p₁ + q₃ – c₁₃ = 0+4-6 =-2

     D₂₃ =  p₂ + q₃ – c₂₃ = 2+4-5 = 1                 - max

     D₂₄ =  p₂ + q₄ – c₂₄ = 2+4-7 = -1

     D₃₁ =  p₃ + q₁ - c₃₁ = -1+2-5 = -4

     D₃₂ =  p₃ + q₂ – c₃₂ = -1-1-2 = -4

     D₄₁ =  p₄ + q₁ – c₄₁ = -4+2-0 = -2

     D₄₂ =  p₄ + q₂ – c₄₂ = -4-1-0 = -5

     D₄₃ =  p₄ + q₃ – c₄₃ = -4-4-0 = -8

     Находим наибольшую положительную оценку  max ( ) = 1 = D₂₃

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

     Это будет 23-21-11-14-34-33-23:

 

        min =0 

 

     D₁₄ = 0,   p₁ + q₄ - c₁₄ = 0,  q₄ =4

     D₃₄ = 0,  p₃ + q₄ – c₃₄ = 0,  p₃ = -1

     D₃₃ = 0,  p₃ + q₃ – c₃₃ = 0,  q₃= 4

     D₂₃ = 0,  p₂ + q₃ – c₂₃ = 0,  p₂ = 1

     D₂₂ = 0,  p₂ + q₂ – c₂₂ = 0,      q₂ = 0

     D₄₄ = 0,  p₄ + q₄ – c₄₄ = 0,  p₄=-4 

     Теперь  по формуле вычисляем оценки всех свободных клеток: 

     D₁₂ =  p₁ + q₂ – c₁₂ = 0-3=-3

     D₁₃ =  p₁ + q₃ – c₁₃ = 0+4-6 =-2

     D₂₁ =  p₂ + q₃ – c₂₃ = 1+2-4 = -1

     D₂₄ =  p₂ + q₄ – c₂₄ = 1+4-7=-2

     D₃₁ =  p₃ + q₁ - c₃₁ = -1+2-5 = -4

     D₃₂ =  p₃ + q₂ – c₃₂ = -1+0-2=-3

     D₄₁ =  p₄ + q₁ – c₄₁ = -4+2=-2

     D₄₂ =  p₄ + q₂ – c₄₂ = -4+0=-4

     D₄₃ =  p₄ + q₃ – c₄₃ = -4+4-0 = 0

     Итак, ,      при    

      Таким образом,  пришли  к  оптимальному  решению  

       Общая стоимость перевозок:   денежных  единиц.

     Для  проверки полученного  результата   теперь  решим  задачу  методом  северо-западного  угла.

  Метод  Северо-западного  угла