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

Имеется 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

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

Анализ структуры текущих расходов вагонного депо
После расчета затрат по всем статьям и заполнения таблицы «Смета эксплуатационных расходов» (приложение 2) проанализируем структуру эксплуатационных расходов вагонного депо по элементам затрат, установив удельный вес каждого элемента (зар ...

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

Характеристика груза и правила перевозок
В данном дипломном проекте осуществляется перевозка зерна. По физическим свойствам груз – навалочный, по весу груза – нормальный, по размеру – габаритный, по степени опасности – неопасный, по условиям перевозки – обычный, по условиям хран ...