Информатика и выч. техника \ Прикладные методы оптимизации

Построение математической модели задачи о коммивояжере (бродячем торговце), страница 2

     1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2   18  x   10  010  x   11   

3   03   2    x   7     x    1

4    3   03   02  x     x    2

 5    2   7   12  3     x    03

 6    6   1    2   01   x    x    

     1    2    3    4    5    6

 


1    x   7   01   x    x    2

 2   18  x   11  04   1    11   

3   03   2    x   7     1    1

4    3   03   1   x     4     2

 5    2   7   13  3     x    03

 6    6   1    3   01   0    x    

Z=112+1=113                                                Z1(2)=112+3=115

Теперь в таблице, которая соответствует подмножеству с оценкой Z2(1)=113, необходимо выбрать маршрут, по которому это множество будет ветвиться на два.  По максимальной степени нуля в этой таблице определяем, что следующим «кандидатом» в гамильтонов контур будет маршрут (2,4).

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3   03   2    x   x     x    1

4    3   03   02  x     x    2

 5    2   7   12  x     x    03

 6    6   1    2   x   x    x    

     1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2   18  x   10  x     x   11   

3   03   2    x   7     x    1

4    3   03   02  x     x    2

 5    2   7   12  3     x    03

 6    6   1    2   01   x    x    

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3   03   2    x   x     x    1

4    3   00   01  x     x    2

 5    2   7   12  x     x    03

 6    5   01   1   x   x    x    

     1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2   8  x      0  x     x    1     

3   03   2    x   7     x    1

4    3   03   02  x     x    2

 5    2   7   12  3     x    03

 6    6   1    2   01   x    x    

Z3(1)=113+1=114                                                Z3(2)= 113+10=114           

Теперь в таблице, которая соответствует подмножеству с оценкой Z3(1)=114, необходимо выбрать маршрут, по которому это множество будет ветвиться на два.  По максимальной степени нуля в этой таблице определяем, что следующим «кандидатом» в гамильтонов контур будет маршрут (3,1).

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x    x   x   x     x    x

4    x   00   01  x     x    2

 5    x   7   12  x     x   03

 6    x   01   1   x   x    x    

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x   2    x   x     x    1

4    3   00   01  x     x    2

 5    2   7   12  x     x    03

      6    5   01   1   x   x    x     

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x    x   x   x     x    x

4    x   00   01  x     x    2

 5    x   7   12  x     x   09

 6    x   01   1   x   x    x    

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x   2    x   x     x    1

4    1   00   01  x     x    2

 5    0   7   12  x     x    03

      6    3   01   1   x   x    x    

Z4(1)=114+0=114                                                Z3(2)= 114+2=116           

     Теперь в таблице, которая соответствует подмножеству с оценкой Z4(1)=114, необходимо выбрать маршрут, по которому это множество будет ветвиться на два.  По максимальной степени нуля в этой таблице определяем, что следующим «кандидатом» в гамильтонов контур будет маршрут (5,6).

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x    x   x   x     x    x

4    x   00   01  x     x    x

 5    x   x    x  x     x    x

 6    x   01   1   x   x    x    

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x    x   x   x     x    x

4    x   00   01  x     x    2

 5    x   7   12  x     x   x

      6    x   01   1   x   x    x    

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x    x   x   x     x    x

4    x   00   01  x     x    x

 5    x   x    x  x     x    x

 6    x   01   1   x   x    x    

      1    2    3    4    5    6

 


1    x   x   x   x      x    x

 2    x   x   x    x     x    x   

3    x    x   x   x     x    x

4    x   00   01  x     x    0

 5    x   0   5    x     x   x

      6    x   01   1   x   x    x    

      Z4(1)=114+0=114                                                Z4(2)= 114+9=123    

По максимальной степени нуля в этой таблице определяем, что следующим «кандидатом» в гамильтонов контур будет маршрут (4,3), и последним будем маршрут (6,2).

Итак, гамильтонов контур: 1à5à6à2à4à3à1

Осталось только подсчитать затраты на маршрут:

Zmin=114.

Скачать файл