Расчет оптимального замкнутого маршрута
Определим оценку для множества G11:
ξ(G11)=ξ(G0)+
=230+0=230.
Так как ξ(G11)=ξ(G21), то на следующем шаге производим ветвление подмножества G11.
Шаг 2.
2.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:
C24=0; C26=0; C36=0; C42=0; C45=0; C51=0; C54=0; C65=0.
Для выделенных претендентов подсчитаем оценки по формуле:
Θ(i,j)=
.
Θ(2,4)=0; Θ(2,6)=0; Θ(3,6)=30; Θ(4,2)=22; Θ(4,5)=0; Θ(5,1)=30; Θ(5,4)=0; Θ(6,5)=22.
Для ветвления выберем пару претендентов с максимальной оценкой Θ(i,j), то есть пару (5,1), так как max Θ(i,j)=Θ(5,1)=30.
2.2. Произведем ветвление: G11=G12 G22, где G12={(1,3), (5,1)}, а G22≠{(1,3), (5,1)}.
2.3. Вычислим оценку для G22: ξ(G22)=ξ(G11)+Θ(5,1)=230+30=260.
2.4. Построим матрицу С(2) для этого вычеркнем в матрице C(1) пятую строку и первый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 3 в город 5, полагая С53→¥, и выполним процесс приведения. В результате получим матрицу С(2):
|
С(2) = |
2 |
4 |
5 |
6 |
hi | |
|
2 |
∞ |
0 |
20 |
0 |
0 | |
|
3 |
42 |
30 |
∞ |
0 |
0 | |
|
4 |
0 |
∞ |
0 |
90 |
0 | |
|
6 |
22 |
70 |
0 |
∞ |
0 | |
|
Hj |
0 |
0 |
0 |
0 |
Определим оценку для множества G12:
ξ(G12)=ξ(G11)+
=230+0=230.
Шаг 3.
3.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:
C24=0; C26=0; C36=0; C42=0; C45=0; C65=0.
Для выделенных претендентов подсчитаем оценки по формуле:
Популярные материалы:
Разработка вопросов техники безопасности и охраны труда
Контроль за состоянием охраны должен осуществляться согласно стандарту предприятия СТП 18.Н.001–2000 «Организация системы контроля за состоянием охраны труда на Московской железной дороге». Обеспечение безопасности труда при ремонте подви ...
Основные производственные вредности
Основными производственными вредностями являются ушибы, попадание смазочных веществ в организм человека. В моторном цехе наибольшему воздействию вредных веществ подвергаются руки рабочих. В соответствии с этим все виды работ должны провод ...
Расчёт деталей двигателя
Расчёт поршня
Наиболее напряжённым элементом поршневой группы является поршень, воспринимающий высокие газовые, инерционные и тепловые нагрузки. Его основными функциями являются уплотнение внутрицилиндрового пространства и передача газов ...
