Логистика
Задание 2.4.
Имеется 5 городов, которые должен посетить коммивояжер по одному разу и вернуться в исходный город. Расстояния между городами заданы матрицей С = (Cij), где i=1,2,…, 5; j=1, 2,…, 5 (рис. 2).
Определите маршрут движения коммивояжера, минимизируя пройденный путь.
Исходные данные по вариантам указаны в табл. 18 и 19.
Рис. 2. Матрица коммивояжера
Таблица 18. Расстояния между городами по маршруту коммивояжера (км)
|
1-я цифра |
С11 |
С12 |
С13 |
С14 |
С15 |
С21 |
С22 |
2-я цифра |
С23 |
С24 |
С25 |
С31 |
С32 |
|
0 |
2 |
4 |
6 |
2 |
4 |
11 |
2 |
0 |
1 |
2 |
3 |
18 |
6 |
|
1 |
11 |
5 |
1 |
5 |
1 |
11 |
5 |
1 |
2 |
2 |
2 |
7 |
2 |
|
2 |
2 |
0 |
24 |
1 |
5 |
0 |
28 |
2 |
1 |
6 |
3 |
25 |
1 |
|
3 |
5 |
72 |
5 |
3 |
1 |
23 |
5 |
3 |
3 |
0 |
3 |
24 |
35 |
|
4 |
0 |
11 |
2 |
5 |
4 |
13 |
0 |
4 |
1 |
4 |
2 |
4 |
5 |
|
5 |
1 |
2 |
7 |
91 |
5 |
8 |
1 |
5 |
2 |
5 |
0 |
17 |
16 |
|
6 |
4 |
5 |
2 |
35 |
1 |
16 |
38 |
6 |
3 |
1 |
1 |
10 |
2 |
|
7 |
14 |
8 |
4 |
10 |
2 |
7 |
1 |
7 |
0 |
1 |
5 |
19 |
24 |
|
8 |
2 |
7 |
3 |
10 |
2 |
1 |
1 |
8 |
5 |
0 |
1 |
9 |
3 |
|
9 |
4 |
2 |
1 |
4 |
0 |
3 |
1 |
9 |
3 |
4 |
4 |
14 |
8 |
