Расчет оптимального замкнутого маршрута

Θ(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

Популярные материалы:

Определение мощности затрачиваемой на преодоление силы сопротивления дороги
Определение коэффициента сопротивления качению ψv=fo+kf•(Vмах/3,6)2=0,018+7•10-6•(90/3,6)2=0,022374 (2.1) где fo=0,018 - коэффициент сопротивления качению при малой скорости, kf=7•10-6 - коэффициент учитывающий влияние скорости, ...

Прочие детали рулевого устройства
Гайки баллера, съемного рудерпоста, штыря. Срыв, смятие, коррозионные повреждения резьбы устраняют калиброванием, если общая длина участков резьбы неполного профиля не будет превышать 15% длины всех витков. При больших дефектах изготовляю ...

Расчет годового пробега парка
Расчет годового пробега по марке подвижного состава производится по формуле: Lг = 365 ∙ Аи · 1сс · αи ,(2.12) где: Аи – списочное число подвижного состава. Lг = 365 ∙ 142 · 87 · 0.53 = 2390, тыс. км. После приведения ...