Расчет оптимального замкнутого маршрута
Имеется 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 |
Популярные материалы:
Выбор метода организации технологического на
объекте проектирования
Метод комплексных бригад предусматривает формирование производственных подразделений по признаку их предметной специализации т.е. закрепления за бригадой определенной группы автомобилей (например, автомобилей одной колонны, автомобилей од ...
Безопасность в чрезвычайных ситуациях. Дезактивация
объекта, загрязненного радиоактивными веществами
В результате запроектной аварии на РОО с выбросом радиоактивных веществ произошло радиоактивное загрязнение объекта, рассматриваемого в дипломном проекте, а именно подвижного состава.
Исходные данные для расчета радиационной разведки:
Н ...
Электробезопасность
Поражение человека электрическим током может произойти при прикосновении к открытым токоведущим изоляции оборудования и проводом корпуса электрической установки, случайно оказавшимся под напряжением, и в других с случаев. С увеличением дл ...
