Расчет оптимального замкнутого маршрута
Θ(i,j)= (2.4)
Θ(2,4)=30; Θ(2,6)=0; Θ(3,6)=30; Θ(4,2)=22; Θ(4,5)=0; Θ(6,5)=22.
Для ветвления выберем пару претендентов с максимальной оценкой Θ(i,j), то есть пару (2,4), так как max Θ(i,j)=Θ(2,4)=30.
3.2. Произведем ветвление: G12=G13 G23, где G13={(1,3), (5,1), (2,4)}, а G22≠{(1,3), (5,1), (2,4)}.
3.3. Вычислим оценку для G23: ξ(G23)=ξ(G12)+Θ(2,4)=230+30=260.
3.4. Построим матрицу С(3) для этого вычеркнем в матрице C(2) вторую строку и четвертый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 4 в город 2, полагая С42→¥, и выполним процесс приведения. В результате получим матрицу С(3):
С(3) = |
2 |
5 |
6 |
hi | |
3 |
42 |
∞ |
0 |
0 | |
4 |
∞ |
0 |
90 |
0 | |
6 |
0 |
0 |
∞ |
0 | |
Hj |
22 |
0 |
0 |
22 0 |
Определим оценку для множества G13:
ξ(G13)=ξ(G12)+=230+22=252.
Так как ξ(G13)<ξ(G23), то на следующем шаге производим ветвление подмножества G13.
Шаг 4.
4.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:
C36=0; C45=0; C62=0; C65=0.
Для выделенных претендентов подсчитаем оценки по формуле:
Θ(i,j)=.
Θ(3,6)=110; Θ(4,5)=90; Θ(6,2)=20; Θ(6,5)=0.
Для ветвления выберем пару претендентов с максимальной оценкой Θ(i,j), то есть пару (3,6), так как max Θ(i,j)=Θ(3,6)=110.
4.2. Произведем ветвление: G13=G14 G24, где G14={(1,3), (5,1), (2,4), (3,6)}, а G22≠{(1,3), (5,1), (2,4), (3,6)}.
4.3. Вычислим оценку для G24: ξ(G24)=ξ(G13)+Θ(3,6)=252+110=362.
4.4. Построим матрицу С(4) для этого вычеркнем в матрице C(3) третью строку и шестой столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 6 в город 3, полагая С63→¥, и выполним процесс приведения. В результате получим матрицу С(4):
С(3) = |
2 |
5 |
hi | |
4 |
∞ |
0 |
0 | |
6 |
0 |
∞ |
0 | |
Hj |
0 |
0 |
Популярные материалы:
Система
освещения и сигнализации
двигатель реле автомобиль зажигание
Система освещения занимает особое место в электрооборудовании автомобилей, так как эффективность автономного освещения и сигнализации в условиях роста автомобилизации и возрастающей роли автомобильных ...
Корректировка нормативов по трудоемкости технического обслуживания
Корректирование нормативных трудоемкостей ежедневных и плановых технических обслуживании производится по выражению
ti=ti(H)K2K5
где ti - скорректированная трудоемкость i-ro вида обслуживания, чел.-ч; V, - нормативная трудоемкость i-ro в ...
Техника безопасности
При техническом обслуживании и текущем ремонте автомобилей возникают следующие опасные и вредные производственные факторы: движущихся автомобилей, незащищенных подвижных элементов производственного оборудования, повышенной загазованности ...