Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод Фогеля

Читайте также:
  1. I. ОРГАНИЗАЦИОННО - МЕТОДИЧЕСКИЙ РАЗДЕЛ
  2. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  3. I. Что такое проективные методики
  4. II. Організаційно-Методичні Рекомендації
  5. II. Отнесение опасных отходов к классу опасности для окружающей природной среды расчетным методом
  6. III. Комбинированный метод
  7. III. Отнесение опасных отходов к классу опасности для окружающей природной среды экспериментальным методом

1. Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.

Данный метод состоит в следующем:

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

2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 13, второй минимальный элемент min21 = 21. Их разность равна d = min21 - min11 = 8.

Для строки N=2 первый минимальный элемент min12 = 22, второй минимальный элемент min22 = 25. Их разность равна d = min22 - min12 = 3.

Для строки N=3 первый минимальный элемент min13 = 12, второй минимальный элемент min23 = 26. Их разность равна d = min23 - min13 = 14.

Для строки N=4 первый минимальный элемент min14 = 17, второй минимальный элемент min24 = 29. Их разность равна d = min24 - min14 = 12.

Для строки N=5 первый минимальный элемент min15 = 16, второй минимальный элемент min25 = 21. Их разность равна d = min25 - min15 = 5.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 13. второй минимальный элемент min21 17. Их разность d = min21 - min11 = 4.

Для столбца N=2 первый минимальный элемент min12 = 21. второй минимальный элемент min22 25. Их разность d = min22 - min12 = 4.

Для столбца N=3 первый минимальный элемент min13 = 12. второй минимальный элемент min23 21. Их разность d = min23 - min13 = 9.

Для столбца N=4 первый минимальный элемент min14 = 24. второй минимальный элемент min24 26. Их разность d = min24 - min14 = 2.

 

 

Для столбца N=5 первый минимальный элемент min15 = 16. второй минимальный элемент min25 25. Их разность d = min25 - min15 = 9.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (3). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (3).

            Запасы Разности по строкам
               
               
               
               
               
               
Потребности              
Разности по столбцам              

 

Искомый элемент равен 12

Для этого элемента запасы равны 22, потребности 41. Поскольку минимальным является 22, то вычитаем его.

x33 = min(22,41) = 22.

           
      x    
x x   x x 22 - 22 = 0
  x x x x x
      x    
      x    
    41 - 22 = 19 x    

 

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 13, второй минимальный элемент min21 = 21. Их разность равна d = min21 - min11 = 8.

Для строки N=2 первый минимальный элемент min12 = 22, второй минимальный элемент min22 = 25. Их разность равна d = min22 - min12 = 3.

Для строки N=4 первый минимальный элемент min14 = 17, второй минимальный элемент min24 = 29. Их разность равна d = min24 - min14 = 12.

Для строки N=5 первый минимальный элемент min15 = 16, второй минимальный элемент min25 = 21. Их разность равна d = min25 - min15 = 5.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 13. второй минимальный элемент min21 17. Их разность d = min21 - min11 = 4.

Для столбца N=2 первый минимальный элемент min12 = 21. второй минимальный элемент min22 25. Их разность d = min22 - min12 = 4.

Для столбца N=3 первый минимальный элемент min13 = 21. второй минимальный элемент min23 37. Их разность d = min23 - min13 = 16.

Для столбца N=4 первый минимальный элемент min14 = 24. второй минимальный элемент min24 29. Их разность d = min24 - min14 = 5.

 

 

Для столбца N=5 первый минимальный элемент min15 = 16. второй минимальный элемент min25 25. Их разность d = min25 - min15 = 9.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (3). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (3).

            Запасы Разности по строкам
               
               
              -
               
               
               
Потребности              
Разности по столбцам              

 

Искомый элемент равен 21

Для этого элемента запасы равны 21, потребности 19. Поскольку минимальным является 19, то вычитаем его.

x13 = min(21,19) = 19.

          21 - 19 = 2
  x x x x x
      x    
    x x    
    x x    
      x    
    19 - 19 = 0 x    

 

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 13, второй минимальный элемент min21 = 21. Их разность равна d = min21 - min11 = 8.

Для строки N=2 первый минимальный элемент min12 = 22, второй минимальный элемент min22 = 25. Их разность равна d = min22 - min12 = 3.

Для строки N=4 первый минимальный элемент min14 = 17, второй минимальный элемент min24 = 29. Их разность равна d = min24 - min14 = 12.

Для строки N=5 первый минимальный элемент min15 = 16, второй минимальный элемент min25 = 24. Их разность равна d = min25 - min15 = 8.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 13. второй минимальный элемент min21 17. Их разность d = min21 - min11 = 4.

Для столбца N=2 первый минимальный элемент min12 = 21. второй минимальный элемент min22 25. Их разность d = min22 - min12 = 4.

Для столбца N=4 первый минимальный элемент min14 = 24. второй минимальный элемент min24 29. Их разность d = min24 - min14 = 5.

 

Для столбца N=5 первый минимальный элемент min15 = 16. второй минимальный элемент min25 25. Их разность d = min25 - min15 = 9.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (1).

            Запасы Разности по строкам
               
               
              -
               
               
               
Потребности              
Разности по столбцам     -        

 

 

Искомый элемент равен 17

Для этого элемента запасы равны 15, потребности 36. Поскольку минимальным является 15, то вычитаем его.

x41 = min(15,36) = 15.

           
  x        
  x        
  x   x x 15 - 15 = 0
  x x x x x
  x        
36 - 15 = 21 x        

 

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 13, второй минимальный элемент min21 = 21. Их разность равна d = min21 - min11 = 8.

Для строки N=2 первый минимальный элемент min12 = 22, второй минимальный элемент min22 = 25. Их разность равна d = min22 - min12 = 3.

Для строки N=5 первый минимальный элемент min15 = 16, второй минимальный элемент min25 = 24. Их разность равна d = min25 - min15 = 8.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 13. второй минимальный элемент min21 22. Их разность d = min21 - min11 = 9.

Для столбца N=2 первый минимальный элемент min12 = 21. второй минимальный элемент min22 25. Их разность d = min22 - min12 = 4.

Для столбца N=4 первый минимальный элемент min14 = 24. второй минимальный элемент min24 29. Их разность d = min24 - min14 = 5.

Для столбца N=5 первый минимальный элемент min15 = 16. второй минимальный элемент min25 25. Их разность d = min25 - min15 = 9.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу

 

(5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (5) и столбца (5).

 

 

            Запасы Разности по строкам
               
               
              -
              -
               
               
Потребности              
Разности по столбцам     -        

 

Искомый элемент равен 16

Для этого элемента запасы равны 8, потребности 17. Поскольку минимальным является 8, то вычитаем его.

x55 = min(8,17) = 8.

           
          x
          x
          x
x x   x   8 - 8 = 0
  x x x x x
        17 - 8 = 9 x

 

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 13, второй минимальный элемент min21 = 21. Их разность равна d = min21 - min11 = 8.

Для строки N=2 первый минимальный элемент min12 = 22, второй минимальный элемент min22 = 25. Их разность равна d = min22 - min12 = 3.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 13. второй минимальный элемент min21 22. Их разность d = min21 - min11 = 9.

Для столбца N=2 первый минимальный элемент min12 = 21. второй минимальный элемент min22 25. Их разность d = min22 - min12 = 4.

Для столбца N=4 первый минимальный элемент min14 = 29. второй минимальный элемент min24 53. Их разность d = min24 - min14 = 24.

Для столбца N=5 первый минимальный элемент min15 = 25. второй минимальный элемент min25 51. Их разность d = min25 - min15 = 26.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (5).

 

            Запасы Разности по строкам
               
               
              -
              -
              -
               
Потребности              
Разности по столбцам     -        

Искомый элемент равен 25

Для этого элемента запасы равны 46, потребности 9. Поскольку минимальным является 9, то вычитаем его.

x25 = min(46,9) = 9.

        x  
          46 - 9 = 37
  x x x x x
          x
          x
          x
        9 - 9 = 0 x

 

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 13, второй минимальный элемент min21 = 21. Их разность равна d = min21 - min11 = 8.

Для строки N=2 первый минимальный элемент min12 = 22, второй минимальный элемент min22 = 25. Их разность равна d = min22 - min12 = 3.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 13. второй минимальный элемент min21 22. Их разность d = min21 - min11 = 9.

Для столбца N=2 первый минимальный элемент min12 = 21. второй минимальный элемент min22 25. Их разность d = min22 - min12 = 4.

Для столбца N=4 первый минимальный элемент min14 = 29. второй минимальный элемент min24 53. Их разность d = min24 - min14 = 24.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (4). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (4).

            Запасы Разности по строкам
               
               
              -
              -
              -
               
Потребности              
Разности по столбцам     -   -    

 

 

Искомый элемент равен 29

Для этого элемента запасы равны 37, потребности 53. Поскольку минимальным является 37, то вычитаем его.

x24 = min(37,53) = 37.

           
x x     x 37 - 37 = 0
  x x x x x
        x  
        x  
        x  
      53 - 37 = 16 x  

 

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 13, второй минимальный элемент min21 = 21. Их разность равна d = min21 - min11 = 8.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 13. второй минимальный элемент min21 13. Их разность d = min21 - min11 = 0.

Для столбца N=2 первый минимальный элемент min12 = 21. второй минимальный элемент min22 21. Их разность d = min22 - min12 = 0.

Для столбца N=4 первый минимальный элемент min14 = 53. второй минимальный элемент min24 53. Их разность d = min24 - min14 = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (1). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (1).

            Запасы Разности по строкам
               
              -
              -
              -
              -
               
Потребности              
Разности по столбцам     -   -    

 

Искомый элемент равен 13

Для этого элемента запасы равны 2, потребности 21. Поскольку минимальным является 2, то вычитаем его.

x11 = min(2,21) = 2.

  x   x   2 - 2 = 0
  x x x x x
  x        
  x        
  x        
  x        
21 - 2 = 19 x        

 

Находим разности по строкам.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 0. второй минимальный элемент min21 0. Их разность d = min21 - min11 = 0.

Для столбца N=2 первый минимальный элемент min12 = 0. второй минимальный элемент min22 0. Их разность d = min22 - min12 = 0.

Для столбца N=4 первый минимальный элемент min14 = 0. второй минимальный элемент min24 0. Их разность d = min24 - min14 = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (6). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (6) и столбца (1).

            Запасы Разности по строкам
              -
              -
              -
              -
              -
               
Потребности              
Разности по столбцам     -   -    

 

Искомый элемент равен 0

Для этого элемента запасы равны 68, потребности 19. Поскольку минимальным является 19, то вычитаем его.

x61 = min(68,19) = 19.

           
  x        
  x        
  x        
  x        
  x       68 - 19 = 49
19 - 19 = 0 x x x x x

 

Находим разности по строкам.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=2 первый минимальный элемент min12 = 0. второй минимальный элемент min22 0. Их разность d = min22 - min12 = 0.

Для столбца N=4 первый минимальный элемент min14 = 0. второй минимальный элемент min24 0. Их разность d = min24 - min14 = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (6). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (6) и столбца (2).

 

            Запасы Разности по строкам
              -
              -
              -
              -
              -
               
Потребности              
Разности по столбцам -   -   -    

 

Искомый элемент равен 0

Для этого элемента запасы равны 49, потребности 33. Поскольку минимальным является 33, то вычитаем его.

x62 = min(49,33) = 33.

 

           
    x      
    x      
    x      
    x      
    x     49 - 33 = 16
  33 - 33 = 0 x x x x

 

Находим разности по строкам.

Для строки N=6 первый минимальный элемент min16 = 0, второй минимальный элемент min26 = 0. Их разность равна d = min26 - min16 = 0.

Находим разности по столбцам.

Для столбца N=4 первый минимальный элемент min14 = 0. второй минимальный элемент min24 0. Их разность d = min24 - min14 = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (6). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (6) и столбца (4).

 

            Запасы Разности по строкам
              -
              -
              -
              -
              -
               
Потребности              
Разности по столбцам - - -   -    

 

Искомый элемент равен 0

 

Для этого элемента запасы равны 16, потребности 16. Поскольку минимальным является 16, то вычитаем его.

x64 = min(16,16) = 16.

           
        x  
        x  
        x  
        x  
        x 16 - 16 = 0
  x x 16 - 16 = 0 x x

 

Матрица распределения запасов

 

            Запасы
  13[2]   21[19]      
        29[37] 25[9]  
      12[22]      
  17[15]          
          16[8]  
  0[19] 0[33]   0[16]    
Потребности            

 

Сведем все вычисления в одну таблицу.

            Запасы d1 d2 d3 d4 d5 d6 d7 d8
  13[2]   21[19]                     -
        29[37] 25[9]               - -
      12[22]         - - - - - - -
  17[15]                 - - - - -
          16[8]           - - - -
  0[19] 0[33]   0[16]                    
Потребности                            
d1                            
d2                            
d3     -                      
d4     -                      
d5     -                      
d6     -   -                  
d7     -   -                  
d8     -   -                  

 

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

 

 

2. Подсчитаем число занятых клеток таблицы, их 10, а должно быть m + n - 1 = 10. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 13*2 + 21*19 + 29*37 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*33 + 0*16 = 2370

Сравнение значений целевой функции для опорных планов, полученных методом:

· Метод Фогеля: Значение целевой функции для этого опорного плана равно:

F(x) = 13*2 + 21*19 + 29*37 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*33 + 0*16 = 2370

· Метод северо-западного угла: Значение целевой функции для этого опорного плана равно:

F(x) = 13*21 + 22*15 + 25*31 + 38*2 + 12*20 + 51*15 + 21*6 + 24*2 + 0*51 + 0*17 = 2633

· Метод наименьших стоимостей: Значение целевой функции для этого опорного плана равно:

F(x) = 21*21 + 22*21 + 25*12 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2191

Наименьшее значение целевой функции получено методом наименьших стоимостей. В дальнейшем будет использоваться матрица распределения ресурсов полученная именно этим планом.

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v2 = 21; 0 + v2 = 21; v2 = 21

u2 + v2 = 25; 21 + u2 = 25; u2 = 4

u2 + v1 = 22; 4 + v1 = 22; v1 = 18

u4 + v1 = 17; 18 + u4 = 17; u4 = -1

u2 + v4 = 29; 4 + v4 = 29; v4 = 25

u6 + v4 = 0; 25 + u6 = 0; u6 = -25

u6 + v3 = 0; -25 + v3 = 0; v3 = 25

u3 + v3 = 12; 25 + u3 = 12; u3 = -13

u2 + v5 = 25; 4 + v5 = 25; v5 = 21

u5 + v5 = 16; 21 + u5 = 16; u5 = -5

  v1=18 v2=21 v3=25 v4=25 v5=21
u1=0   21[21]      
u2=4 22[21] 25[12]   29[4] 25[9]
u3=-13     12[22]    
u4=-1 17[15]        
u5=-5         16[8]
u6=-25     0[19] 0[49]  

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(1;1): 0 + 18 > 13; ∆11 = 0 + 18 - 13 = 5

(1;3): 0 + 25 > 21; ∆13 = 0 + 25 - 21 = 4

max(5,4) = 5

Выбираем максимальную оценку свободной клетки (1;1): 13

 

 

Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

            Запасы
  13[+] 21[21][-]        
  22[21][-] 25[12][+]   29[4] 25[9]  
      12[22]      
  17[15]          
          16[8]  
      0[19] 0[49]    
Потребности            

 

Цикл приведен в таблице (1,1; 1,2; 2,2; 2,1;).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 21. Прибавляем 21 к объемам грузов, стоящих в плюсовых клетках и вычитаем 21 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

            Запасы
  13[21]          
  22[0] 25[33]   29[4] 25[9]  
      12[22]      
  17[15]          
          16[8]  
      0[19] 0[49]    
Потребности            

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u2 + v1 = 22; 13 + u2 = 22; u2 = 9

u2 + v2 = 25; 9 + v2 = 25; v2 = 16

u2 + v4 = 29; 9 + v4 = 29; v4 = 20

u6 + v4 = 0; 20 + u6 = 0; u6 = -20

u6 + v3 = 0; -20 + v3 = 0; v3 = 20

u3 + v3 = 12; 20 + u3 = 12; u3 = -8

u2 + v5 = 25; 9 + v5 = 25; v5 = 16

u5 + v5 = 16; 16 + u5 = 16; u5 = 0

u4 + v1 = 17; 13 + u4 = 17; u4 = 4

 

  v1=13 v2=16 v3=20 v4=20 v5=16
u1=0 13[21]        
u2=9 22[0] 25[33]   29[4] 25[9]
u3=-8     12[22]    
u4=4 17[15]        
u5=0         16[8]
u6=-20     0[19] 0[49]  

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 13*21 + 25*33 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2086

 


Дата добавления: 2015-09-03; просмотров: 104 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Метод северо-западного угла| СХЕМА ЭЛЕКТРОСНАБЖЕНИЯ

mybiblioteka.su - 2015-2024 год. (0.059 сек.)