Строим аналогично третью симплекс таблицу

  - - - -
0.34 -1.64 -0.008 0.49 155.2
0.24 -1.64 -0.18 0.19
0.06 -0.57 -0.57 0.05 12.86
0.23
0.32 0,2
C 7,65 -0,25 -3,4 0,15 48,61

Строим 4 симплекс таблицу

  - - - -
-5 0,35 -3,6 -0.05 213.8
-0,65 0,026 -0,3 0.11 9.7
0,65 4,77 1.05 21.2
-1,05 -0,14 -0.22 3.6
1,15 0.23
C 7,65 -0,25 3,9 0.15 49.39

 

Строим 5 симплекс таблицу

 

  - - - -
-7.69 -0.54 -6.2 -0.62 202.4
-0.85 -0.04 -0.49 0.07 8.8
7.69 1.54 7.34 1.62 32.6
0.03 0.22 2.03 0.006 8.2
1.15 0.23
C 9.57 0.38 5.73 0.55 57.52

 

Мы пришли к критерию оптимальности, при котором С = 57,52 ,

 


Транспортная задача

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

Задачу решить как транспортную в матричной постановке, используя приведенную матрицу:

 

             
                           
             
                           
             
                           
             
                           
             
                           
             
                           
             
                           
             
                           
 

Начальный план построить тремя способами, а для решения задачи выбрать наилучший.

Метод наименьшей стоимости

              200/170/10/к
                     
              180/134/к
                       
              300/124/44/к
                     
              50/к
                         
              220/к
                         
              80/30/к
                       
              20/к
                         
              100/к
                         
50/к 176/к 180/80/к 150/120/76/ 56/46/к 184/134/к 160/к 250/30/к  

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

              200/150/к
                       
              180/154/к
                       
              300/274/124/к
                     
              50/к
                         
              220/210/50/
                     
              80/к
                         
              20/к
                         
              100/к
                         
50/к 176/26/к 180/26/к 150/к 184/60/10/к 160/к 250/200/120/ 100/к  

 

Метод двойного предпочтения

              200/170/10/к
                     
              180/134/к
                       
              300/124/44/к
                     
              50/к
                         
              220/к
                         
              80/30/к
                       
              20/к
                         
              100/к
                         
50/к 176/к 180/80/к 150/120/76/ 56/46/к 184/134/к 160/к 250/30/к  

По методу наименьшей стоимости С = 10784 , по методу северо-западного угла С = 15258, по методу двойного предпочтения С = 10784. Отсюда следует, что наилучшим планом для решения задачи будет план, найденный методом двойного предпочтения и метод наименьшей стоимости, так как у них функции цели равны.

 

Определяем потенциалы

Потенциалы строк записываем слева. Одному из потенциалов строки или столбца присваиваем значение 0.

Проверяем по условию оптимальности не загруженные клетки. Клетки с «нарушениями» называются потенциальными. Это значит, что если в эту потенциальную клетку поместить единицу перевозки, то стоимость по общему плану улучшиться на величину этой перевозки умноженной на величину нарушения.

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

Решение всех этих действий (одной операции) продолжаем до тех пор, пока в матрице не будет потенциальных клеток.

 

  -4 -2 -6  
+4 +4     +4    
                     
+15 +7 +7       +7
                       
             
                     
-5              
                         
             
                         
        +4    
                       
+8       +4    
                         
      +1 +8    
                         
   

 

С = 10784

 

 

  -4 -2 -6  
+4 +4     +19    
                     
             
                       
        +14    
                     
-20              
                         
        +12    
                         
        +19    
                       
        +19    
                         
      +1 +23    
                         
   

 

С = 10094

  -22 -4 -2 -1 -6  
  +4          
                     
  +15 +15 +4   +7 +15
                       
             
                     
             
                         
             
                         
             
                         
+5            
                         
      +1      
                       
   

С = 10002

  -7 -4 -2 -6  
  +4     +11    
                     
             
                     
        +6    
                     
-16              
                         
        +4    
                         
             
                         
        +11    
                         
-9              
                         
   

С = 8562

  -7 -4 -2  
             
                     
          +3 +11
                     
        +6 +2  
                     
-12              
                       
-2              
                           
        +11    
                         
        +11 +3 +9
                           
-9              
                         
   

С = 8452

  -7 -4 -2 -6  
  +4          
                     
             
                     
             
                     
-1              
                         
             
                         
             
                         
             
                         
             
                         
   

С = 8188