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

2. Определим оценку множества G0, вычислив сумму приводящих констант

ξ(G0)= =202+28=230.

Шаг 1.

1.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:

C13=0; C24=0; C26=0; C36=0; C42=0; C45=0; C51=0; C54=0; C65=0.

Для выделенных претендентов подсчитаем оценки по формуле:

Θ(i,j)=.

Θ(1,3)=26; Θ(2,4)=0; Θ(2,6)=0; Θ(3,6)=10; Θ(4,2)=22; Θ(4,5)=0; Θ(5,1)=10; Θ(5,4)=0; Θ(6,5)=8.

Для ветвления выберем пару претендентов с максимальной оценкой Θ(i,j), то есть пару (1,3), так как max Θ(i,j)=Θ(1,3)=26.

1.2. Произведем ветвление: G0=G11 G21, где G11={1,3}, а G21≠{1,3}.

1.3. Вычислим оценку для G21: ξ(G21)=ξ(G0)+Θ(1,3)=230+26=256.

1.4. Построим матрицу С(1) для этого вычеркнем в матрице С(0) первую строку и третий столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 3 в город 1, полагая С31→¥, и выполним процесс приведения. В результате получим матрицу С(1):

С(1) =		1	2	4	5	6	hi
	2	40	∞	0	20	0	0
	3	∞	42	30	60	0	0
	4	30	0	∞	0	90	0
	5	0	38	0	∞	50	0
	6	60	22	70	0	∞	0
	Hj	0	0	0	0	0

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

Производственные подразделения технического обслуживания и ремонта вагонов
* Вагонное депо. * Пункты подготовки вагонов и перевозки и технического обслуживания. * Пункты контрольно-технического обслуживании вагонов (ПКТО). * Контрольные посты (КП), посты опробования автотормозов (ПОТ), пункты технической пере ...

Консервация
При подготовке дизеля к длительной стоянке в межнавигационный период удаляют воду из системы охлаждения и продувают её сжатым воздухом, заполняют топливную систему обезвоженным дизельным топливом, сливают смазочные масла из системы, промы ...

Понятие и состав затрат на выполняемые работы
На основании маркетинговых исследований менеджеры производственных фирм определяют условия производства товаров (услуг), которые будут поставляться на рынок. Значительное внимание при этом уделяют предстоящим затратам. Затраты являются в ...