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

      Обозначив потенциалы строк через u_i , потенциалы столбцов v_j , а показатели оптимальности   в базисных клетках через C_ij , можно записать

                             C_ij= u_i + v_j;   u_i = C_ij - v_j ;  v_j = C_ij - u_i                        (6)

      Характеристики цепей к свободным клеткам обозначим Е_ij. Зная потенциалы их строк и столбцов,

                                                Е_ij = C_ij – (u_i + v_j) .                                 (7)

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

      Если  же характеристик Е_ij  будет равна нулю, то перераспределение поставок по данной цепи не изменит значения целевой функции. Для базисных клеток характеристики равны нулю.

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

          Е₁₃ = 3;   Е₁₄ = 4;  Е₁₅ = 4;     Е₂₁ =  – 4;   Е₂₅ = 3  –(5+( – 3)) =1;

                          Е₃₁ =  – 5;  Е₃₂ =  0;  Е₃₃ =  – 2.

      Видно, что отрицательных характеристик  три: А₂ - В₁ , А₃ - В₁ и А₃ – В₃ . Наибольшая по абсолютной величине отрицательная характеристика в А₃ - В₁ , которая составляет – 5. перераспределим поставки по цепи к этой клетке. Для этого составим цепь с вершинами: А₁ - В₁, А₁ – В₂, А₂ – В₂ , А₂ – В₄, , А₃ – В₄ , 

А₃ - В₁. Положительными вершинами в этой цепи будут А₃– В₁, , А₁ – В₂, , А₂ – В₄ (так как увеличение поставок в этих клетках приводит к уменьшению значения целевой функции), а остальные отрицательными.

      Наименьшая  по величине  поставка в отрицательных  вершинах цнпи равна 7 (в А₂ – В₂). Прибавляем по 7 к объемам поставки в положительных вершинах и вычитаем из поставок в отрицательных также по 7. Получившийся план перевозок записываем в таблицу 4 и определяем новые потенциалы, произвольно приняв потенциал строки А₁ равным 1. Значение целевой функции при новом плане поставок будет на 7 5=35 у.е. меньше, т.е.:

      Z=363 – 35=328 у.е.

        Характеристики свободных клеток  для вновь созданного плана  будут следующими:

          Е₁₃ = -2;   Е₁₄ = -1;  Е₁₅ = -1;     Е₂₁ =  1;   Е₂₂ =5;  Е₂₅ =1;

                                               Е₃₂ =  5;  Е₃₃ =  – 2. 

      В таблице 4 отрицательных характеристик  свободных клеток четыре:   А₁ – В₃, А₁ – В₄, А₁ – В₅ , А₃ – В₃. Перераспределим поставки по цепи к любой из этих клеток, допустим к  А₁ – В₅, по цепи: А₁ – В₅, А₃ – В₅, А₃ – В₁, А₁ – В₁. Положительные вершины цепи А₁ – В₅ и А₃ – В₁, а отрицательные А₃ – В₅ и          А₁ – В₁, минимальная поставка равна 15  от поставщика А₁ к потребителю В₁, т.е. А₁ – В₁ (таблица 4/1).

              Таблица 4.

    

          Таблица 4/1.

   

      Прибавляем  по 15 к поставкам в положительных  вершинах и отнимаем по 15 в отрицательных  вершинах цепи. Получившийся план перевозок представлен в таблице 5.

      Значение  целевой функции при новом  плане:

      Z=328 – 15

1 =313 у.е.

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

          Е₁₁ = 1;   Е₁₄ = 0;  Е₁₃ = -1;     Е₂₁ =  1;   Е₂₂ =4;  Е₂₃ =1;

                                               Е₃₂ = 4;  Е₃₃ =  – 2. 

             Таблица 5.

      

      Принимаем перераспределение поставок по цепи к А₃ – В₃, т.к. характеристика данной клетки отрицательная и наибольшая по абсолютному значению. Составляем цепь перераспределения: А₃ – В₃,  А₂ – В₃ , А₃ – В₄ , А₃ – В₄ (таблица 5/1).  

 Таблица 5/1.

      Минимальная поставка в отрицательных вершинах (А₃ – В₄) равна 3. Получившийся план перевозок представлен в таблице 6.

      Значение  целевой функции при новом  плане:

      Z=313 – 3

2=307 у.е.

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

          Е₁₁ = 1;   Е₁₄ = 2;  Е₁₃ = 1;     Е₂₁ = -1;   Е₂₂ =2;  Е₂₅ = -1;

                                               Е₃₂ = 4;  Е₃₄ = 2. 

      Отрицательными  характеристиками обладают две клетки: А₂ – В₁ и        А₂ – В₅.  Произведем поставку 17 т из  А₂ в В₁ (таблица 7).

            Таблица 6.

        

           Таблица 7.

        

      При таком плане перевозок значение целевой функции:

      Z=307 – 17=209 у.е.

      Характеристики  цепей к свободным клеткам:

          Е₁₁ = 1;   Е₁₄ = 2;  Е₁₃ = 1;     Е₂₂ = 3;   Е₂₃ =2;  Е₂₅ = 0;

                                               Е₃₂ = 4;  Е₃₄ = 1.

      Таким образом, в данном плане перевозок нет ни одной отрицательной характеристики. Нулевая оценка клетки  А₂ – В₅  указывает на то, что данную программу можно изменить так, что эта клетка станет базисной, но при этом получится равноценный план с той же величиной затрат.

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

      Оптимальный план перевозок даст снижение стоимости перевозок по сравнению с исходным:

      

%. 

        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      ИСХОДНЫЕ  ДАННЫЕ К ЛАБОРАТОРНОЙ РАБОТЕ №2 

      Таблица 1.

 
 
 

      Таблица 2.