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

Имеется 6 городов, соединенных между собой дорогами так, что из любого транспортного узла можно проехать в любой другой пункт. Выезжая из одного пункта, коммивояжер должен побывать в других пунктах по одному разу и вернуться в исходный пункт. Поэтому маршрут коммивояжера образует замкнутый цикл без петель. Требуется найти такой маршрут, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы пройденное расстояние (время поездки) было минимальным. Расстояния между городами заданы матрицей C=(Сij); i=1÷6; j=1÷6.

Таблица 2.2 – Расстояние между пунктами

С =	∞	112	32	60	80	110
	80	∞	64	50	60	40
	30	80	∞	60	80	20
	60	48	80	∞	30	120
	40	96	128	50	∞	90
	100	80	48	120	40	∞

1. Осуществим приведение матрицы С по строкам и столбцам. Приведенную матрицу С(0) представим в виде таблицы, приводящие константы по строкам и столбцам запишем соответственно справа матрицы и снизу.

С(0) =		1	2	3	4	5	6	hi
	1	∞	62	0	18	48	78	32
	2	40	∞	24	0	20	0	40
	3	10	42	∞	30	60	0	20
	4	30	0	50	∞	0	90	30
	5	0	38	88	0	∞	50	40
	6	60	22	8	70	0	∞	40
	Hj	0	18	0	10	0	0	28 202

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

Монтаж и настройка оборудования УСП КП на АДМ
Установка БОМ и БЭ на автомотрисе, прокладка и стыковка соединительных кабелей производится в соответствии с инструкцией по монтажу и схемой подключений. БОМ калибруется на предприятии-изготовителе вместе с БЭ и калибровочные таблицы хра ...

Функции и роль в производственном процессе
тормозной кулак восстановление автомобильный Республиканское унитарное дочернее транспортное предприятие «Автобусный парк №1» - это предприятие осуществляет как внутригородские, так и пригородные перевозки людей. Отдел эксплуатации - за ...

Выбор и корректирование нормативных трудоемкостей
Расчетная трудоемкость ТО-1 и ТО-2 (ВАЗ-2101): tтo-1 = tтo-1(H) * K2 *К4 = 4,0 * 1,25 * 1,19 = 6 чел. ч tтo-2 = tтo-2(H) * K2 *К4 = 20,0 * 1,25 * 1,19 = 29,75 чел. ч где tтo-1(H), tтo-2(H) – соответственно нормативная трудоемкость ТО-1 ...