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

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

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

Выбор системы отопления, освещения и вентиляции
Вагоноремонтный завод в том числе вагоносборочный цех является крупными потребителями энергии, пара и сжатого воздуха, трёхфазный переменный ток частотой 50 Гц, напряжением 380 и 220 В используется для питания электродвигателя, сварочных ...

ТПА с распределительными насосами
Одноплунжерные ТНВД с приводом от торцевой кулачковой шайбы типа VE начали производиться фирмой R.Bosch с 1976 г. ТНВД VE служат для обслуживания дизелей с числом цилиндров 2,4,6 цилиндровой мощностью до 25 кВт, частотой до 5000 мин – 1 ...

Расчет вентиляции
Определяем производительность вентилятора. Wвент = V ● Kвозд, м/час (5.5) где: Kвозд - кратность обмена воздуха в час. V -объем помещения V = Fцеха ● h (5.6) h -высота помещения (3 - 4 м) V = 99 ● 4 = 396 Wвент = ...