Использование метода ветвей и границ

    
     
     
 

ГОсударственный  университет  управления

       
 

институт  туризма  и  развития  рынка

     
 
             

курсовая  работа  по  дисциплине

«логистика»

на  тему:

 
             
      «ПРИМЕНЕНИЕ МЕТОДА  «ВЕТВЕЙ И ГРАНИЦ» ДЛЯ      
      РЕШЕНИЯ ЗАДАЧ »      
         
         
         
         
преподаватель
Рогова  Ирина Александровна      
студентка
Савукова  Екатерина      
группа
ТМ-3-1      
                 
                 
          Москва - 2011      

 

СОДЕРЖАНИЕ 

 

     ЛАБОРАТОРНАЯ  РАБОТА № 1 
 

     Тема: Применение метода «Ветвей и границ» для решения задачи коммивояжера и задачи установления оптимальной последовательности выполнения работ в производстве, сервисе, длительность которых зависит от очередности их выполнения на рабочем месте (4 часа). 

     Цель  работы: изучение комбинаторного метода решения задач дискретного программирования, возникающих в производстве, сервисе, таможенном менеджменте, реализующего нахождение оптимального решения путем частичного перебора возможных решений, и получение практических навыков в его применении. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ИНДИВИДУАЛЬНОЕ  ЗАДАНИЕ № 1 

     Имеется 5 городов, которые должен посетить коммивояжер по одному разу, минимизируя пройденный путь, и вернуться в исходный город. Расстояние между городами заданы матрицей А=[aij], i=1,…,5; j=1,…,5 отражены в таблице 1.1.

     Таблица 1

                                  j

     i

     № последующего города
     1      2      3      4      5       
     № предыдущего города      1      x      3      6      1      4       
     2      9      x      9      3      8       
     3      7      1      x      7      5       
     4      1      4      6      x      1       
     5      2      5      1      8      x       
                                                
 

     Решение

    1. Шаг А1. В исходной матрице А знак × уже проставлен в клетках главной диагонали матрицы с северо-западного угла до юго-восточного.
    2. Шаг А2. Приведение матрицы

     Таблица 2

     i                  j      1      2      3      4      5      hi
     1      x      2      5      0      3      1
     2      6      x      6      0      5      3
     3      6      0      x      6      4      1
     4      0      3      5      x      0      1
     5      1      4      0      7      x      1
                                                
 

     Таблица 3

     i                  j      1      2      3      4      5      hi
     1      x      2      5      0      3      1
     2      6      x      6      0      5      3
     3      6      0      x      6      4      1
     4      0      3      5      x      0      1
     5      1      4      0      7      x      1
     Hi      0      0      0      0      0       
 
 
 
 
 
 
 
 
     
    1. Шаг Б. Вычисление нижней границы

     Таблица 4

     i                  j      1      2      3      4      5      hi
     1      x      2      5      0      3      1
     2      6      x      6      0      5      3
     3      6      0      x      6      4      1
     4      0      3      5      x      0      1
     5      1      4      0      7      x      1
     Hi      0      0      0      0      0      7
 

         Нижняя  граница (оценка) множества Е равно 7.

         (НГЕ= ). 

     
    1. Шаг В. Выбор претендующей коммуникации на ветвление

         Определим дугу, исключение которой максимально увеличило бы полученную оценку. Рассчитаем понижение для элементов (i,j) полученной матрицы, имеющих нулевые значения.

         d(1;4)=2+0=2

         d(2;4)=5+0=5

         d(3;2)=4+2=6

         d(4;1)=1+0=1

         d(4;5)=3+0=3

         d(5;3)=1+5=6 

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

         Выбираем  для ветвления пару (5;3). 

     
    1. Шаг Г. Разделение подмножества (ветвление)

         Производим  ветвление:

         Е=Е(i;j)͝ (i;j), где Е(i;j)={5;3}, (i;j)={ }

         Вычислим  оценку подмножества (i;j).

         Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е и понижения для наиболее перспективного претендента на ветвление, вычисленного на шаге В. Нижняя граница множества полных циклов Е была вычислена на шаге Б. Следовательно:

         НГ (5;3)=НГЕ+d(5;3)=7+6=13 
     

     
    1. Шаг Д. Переход к матрице  меньшего размера (усечение матрицы)

         На  этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij)

         В приведенной матрице (см. 1.2. шаг А2) матрице вычеркивается пятая строка и третий столбец. Для вновь полученной матрицы повторяется шаг А, то есть осуществляется выставление запрета во избежание образования неполного цикла в клетке 5,3 и проводится ее приведение.

     Таблица 5

     i                  j      1      2             4      5      hi
     1      x      2             0      3      0
     2      6      x             0      5      0
     3      6      0             6      x      0
     4      0      3             x      0      0
                                                
     Hi      0      0             0      0       

          

         Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (5;3), как сумма оценки множества Е и значения понижения матрицы, полученного после ее приведения на этом шаге.

         НГЕ(5;3)=НГЕ+ 7+0+0=7

         Так как оценка НГЕ(5;3)=7 меньше, чем оценка НГ (5;3)=13, то можно считать, что искомый оптимальный цикл J* содержит коммуникацию, выбранную в качестве перспективного претендента на ветвление (5;3), и можно осуществлять дальнейшее ветвление дерева из вершины (5;3). 

     
    1. Шаг Е. Построение графа искомого цикла

         Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами  из подмножества Е(i;j) и (i;j).

         

         

    1. Шаг Ж. Продолжение ветвления

         Далее проводятся те же действия, что и на шагах В, Г, Д, Е. 

         2.1.Шаг  В. Выбор претендующей  коммуникации на  ветвление

         Определим дугу, исключение которой максимально  увеличило бы полученную оценку НГЕ(5;3). Рассчитаем понижение для элементов (i;j) полученной матрицы, имеющих нулевые значения.

         d(1;4)=2+0=2

         d(2;4)=5+0=5

         d(3;2)=4+2=6

         d(4;1)=0+6=6

         d(4;5)=0+3=3 

         Максимальную  оценку имеют две пары претендентов на ветвление, а именно: (3;2) и (4;1). В  случае равенства максимальных значений для нескольких претендентов выбор из них перспективной коммуникации на ветвление осуществляется произвольно.

         Выбираем  для ветвления пару (3;2). 

         2.2.Шаг  Г. Разделение  на подмножества (ветвление)

         Произведем  ветвление Е(5;3):

         Е(5;3)=Е(i;j)͝ (i;j),

         где Е(i;j)={(5;3),(3;2)}, (i;j)={( }

         Вычислим  оценку подмножества (i;j).

         Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е(5;3) и понижения для наиболее перспективного претендента на ветвление, вычисленного в 2.1. на шаге В. Нижняя граница множества полных циклов Е(5;3) была вычислена в 1.6. на шаге Б. Следовательно:

         НГ (5;3),(3;2)=НГЕ(5;3)+d(3;2)=7+6=13 

         2.3.Шаг  Д. Переход к  матрице меньшего  размера (усечение  матрицы)

         На  этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij).

         В приведенной см 1.6. матрице вычеркивается  третья стока и второй столбец. Для  вновь полученной матрицы повторяется  шаг А. 
     

     Таблица 6

     i                  j      1                    4      5      hi
     1      x                    0      3      0
     2      6                    0      x      0
                                                
     4      0                    x      0      0
                                                
     Hi      0                    0      0       
 

         Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (3;2), как сумма оценки множества Е(5;3) и значения понижения матрицы, полученного после ее приведения на этом шаге.

         НГЕ(5;3)(3;2)=НГЕ(5;3)+ 7+0+0=7

         Так как оценка НГЕ(5;3)(3;2)=7 меньше, чем  оценка НГ (5;3)(3;2)=13, то стоим графу искомого цикла. 

     2.4. Шаг Е. Построение графа искомого цикла

         Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами из подмножества Е(i;j) и (i;j).

         

         

         5.1.Шаг  В. Выбор претендующей  коммуникации на  ветвление

         Определим дугу, исключение которой максимально  увеличило бы полученную оценку. Рассчитаем понижение для элементов (i;j) полученной матрицы, имеющих нулевые значения.

         d(1;4)=3+0=3

         d(2;4)=0+5=5

         d(4;1)=6+0=6

         d(4;5)=5+0=5 

         Максимальное  значение понижения рассматриваемых  элементов соответствует наиболее перспективному претенденту на ветвление. Перспективный претендент на ветвление – пара (4;1), так как d(4;1)=6 является максимальной оценкой из рассмотренных претендентов на ветвление. 

         5.2.Шаг  Г. Разделение  на подмножества (ветвление)

         Произведем  ветвление Е(3;2):

         Е(3;2)=Е(i;j)͝ (i;j),

         где Е(i;j)={(5;3),(3;2)(4;1)}, (i;j)={( }

         Вычислим  оценку подмножества (i;j).

         Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е(3;2) и понижения для наиболее перспективного претендента на ветвление, вычисленного в 5.1. на шаге В. Нижняя граница множества полных циклов Е(3;2) была вычислена в 2.3. на шаге Д. Следовательно:

         НГ (5;3),(3;2),(4;1)=НГЕ(5;3)(3;2)+d(4;1)=7+6=13 

         5.3.Шаг  Д. Переход к  матрице меньшего  размера (усечение  матрицы)

         На  этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij).

         В приведенной (см 2.3.) матрице вычеркивается четвертая стока и первый столбец. Для вновь полученной матрицы повторяется шаг А. 
     
     
     
     
     
     

     Таблица 7

     i                  j                           4      5      hi
     1                           0      3      0
     2                           0      x      0
                                                
                                                
                                                
     Hi                                          
 

     Таблица 8

     i                  j                           4      5      hi
     1                           0      0      0
     2                           0      x      0
                                                
                                                
                                                
     Hi                           0      3       
 

         Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (4;1), как сумма оценки множества Е(3;2) и значения понижения матрицы, полученного после ее приведения на этом шаге.

         НГЕ(5;3)(3;2)(4;1)=НГЕ(3;2)+ 7+0+3=10

         Так как оценка НГЕ(5;3)(3;2)(4;1)=10 меньше, чем  оценка НГ (5;3)(3;2)(4;1)=13, то можно осуществлять ветвление дерева из вершины (4;1). 

         5.4.Шаг  Е. Построение  графика искомого цикла

         Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами  из подмножества Е(i;j) и (i;j). 
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

         6.1.Шаг  В. Выбор претендующей  коммуникации на  ветвление

         Остались  пары: (1;4),(1;5),(2;4). Все они равны нулю, поэтому дальше соединяем график маршрутов. 
     
     
     
     
     
     
     
     

         7.1. Шаг В. Выбор  претендующей коммуникации на ветвление.

         Искомый полный оптимальный цикл J включает коммуникации:

         J={(5;3),(3;2)(4;1)(2;4)(1;5)},

         Имеет длину F(J)=10, а последовательность объезда  городов, если коммивояжер находился  в городе 5, можно представить  в виде:

         5 − 3 − 2 − 4 − 1 − 5. 

         Выполним  проверочный расчет для полученной последовательности. По исходной матрице  посчитаем F(J):

         F(J):1+1+1+3+4=10. Результат тот же, что и расчетный, следовательно расчеты выполнены правильно. 
     

  
 
 
 
 
 
 
 

Использование метода ветвей и границ