Расчет оптимального замкнутого маршрута
Определим оценку для множества 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.
Для выделенных претендентов подсчитаем оценки по формуле:
Популярные материалы:
Определение осевых размеров стрелочного перевода
Осевые размеры стрелочного перевода а0 и в0 необходимы для раз бивки его на местности. Откладываются они от центра стрелочного пере вода О, т.е. от точки пересечения оси прямого пути и оси бокового пути, по направлению прямого пути. Согла ...
Беспосадочный перелет через Гренландию
28—29 апреля 1939 лётчик В. К. Коккинаки и штурман М. Х. Гордиенко на самолёте конструкции Ильюшина ЦКБ-30 « Москва» совершили беспосадочный перелёт из Москвы через Гренландию в Северную Америку о. Мискоу (Миску) в заливе Святого Лавренти ...
Техника безопасности при монтаже валопровода
До начала монтажа следует: установить и смонтировать все средства механизации работ — грузоподъемные машины и механизмы, предусмотренные проектом производства работ; подготовить необходимые инструменты, приспособления и материалы.
Грузоп ...
