5462
.pdf91
Таблица 16
P153
|
|
j |
|
|
|
|
|
|
|
|
i |
1 |
2 |
|
|
4 |
|
5 |
|||
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
19 |
|
9 |
|
|||
|
|
|
|
|
0 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
2 |
|
0 |
|
|
|
0 |
2 |
||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
16 |
|
|
3 |
|
16 |
24 |
|
0 |
|
|||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
19 |
|
|
0 |
|||
|
4 |
|
17 |
|
|
|||||
|
|
0 |
|
|
|
0 |
||||
|
|
|
|
|
|
|
Максимальная степень нуля для клетки (4,2). Претендентом на включение в маршрут будет дуга (4,2). Разбиваем множество P531 на два подмножества
Р2 |
и |
|
422 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р |
(табл. 17 и 18). |
|
|
|
|
|
|
|
|
|
|
|
|
||||
42 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
42 |
|
||
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
1 |
|
|
4 |
|
|
5 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
||
|
|
|
|
1 |
|
|
|
9 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
0 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
0 |
|
|
|
2 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
25 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
16 |
0 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
92
Таблица 18
|
|
|
|
|
|
|
|
|
|
|
|
|
422 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Р |
||
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
1 |
2 |
|
|
4 |
|
|
5 |
ui |
|
|
|
||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
19 |
|
9 |
|
|
0 |
0 |
|
|
|
||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2 |
|
0 |
|
|
|
0 |
|
|
0 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
16 |
24 |
|
0 |
|
|
|
0 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
4 |
|
17 |
|
|
|
0 |
|
0 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
vj |
|
0 |
19 |
|
0 |
|
|
0 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
h2 |
|
|
|
422 |
|
|||||
Определяем константы |
приведения |
для |
этих |
матриц |
0 , |
|
h |
19 . |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
42 |
|
|
|
|
|
|
Следовательно, |
P2 |
34 , |
|
|
|
422 |
|
|
|
|
|
|
|
|
53 . |
Так |
как |
34 |
53 , |
|
то |
|||||
|
|
P |
34 |
19 |
|
|
||||||||||||||||||||
|
|
|
42 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
дальнейшему ветвлению подлежит множество Р2 |
(табл. 17). Вычисляем |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
42 |
|
|
|
|
|
|
|
|
степени нулей |
матрицы Р2 . |
Претендентом |
на включение |
в |
маршрут |
|||||||||||||||||||||
|
|
|
|
|
42 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
станет дуга (3,4). Разбиваем множество |
Р2 |
на два подмножества Р3 |
и |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
42 |
|
|
|
|
|
34 |
|
|||||
|
|
343 (табл. 19 и 20). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Р |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 19 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
34 |
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
i |
1 |
|
|
5 |
|
|
|
ui |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
0 |
|
|
2 |
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
vj |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
P2 |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
h3 |
0 , |
|
34 |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
34 |
|
|
|
|
42 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
93
Таблица 20
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
343 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
1 |
|
4 |
|
5 |
|
ui |
|
|||||||
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
9 |
|
0 |
|
0 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
2 |
0 |
|
|
|
2 |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
3 |
16 |
|
|
|
|
|
16 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
vj |
0 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
343 |
|
|
|
|
343 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
h |
25 , |
|
P |
34 |
25 |
59. |
|
|
|
|
|
|||||
Следовательно, ветвлению |
нужно подвергнуть |
множество Р3 |
. Но его |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
34 |
|
||||
матрица имеет размерность 2 |
2 . Поэтому в маршрут следует включить |
дуги (1,5) и (2,1), соответствующие нулевым элементам. Окончательно в маршрут коммивояжера вошли дуги (5,3), (4,2), (3,4), (1,5), (2,1).
1
10 |
|
Длина маршрута |
|
С53 С34 С42 С15 С21 7 1 10 |
|
|
6 |
|
|
|
|
|
|
3 |
2
1
7
10
4 |
5 |
6 10 34.
Так как границы оборванных ветвей больше длины контура 5 3 4 2 1 5 , то этот контур
имеет наименьшую длину.
Если оборванная ветвь имеет меньшую длину маршрута, нужно к ней вернуться и продолжить ветвление.
На рис. 9 приводится дерево ветвлений маршрута коммивояжера.
|
|
|
|
|
|
|
|
|
|
94 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
0 |
31 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
34 |
|
|
|
|
|
|
|
1 |
41 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
53 |
|
|
||||||||
|
|
53 |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
153 |
|
|
|
Р1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Р |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
53 |
|
|
|
|
|
53 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
42 |
|
|
|
|
|
|
|
|
|
||
|
34 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
42 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
422 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р |
||||
|
|
2 |
|
|
3 |
|
59 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
Р42 |
|
34 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
3 |
34 |
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
34 |
|
|
|
|
|
|
|
|
Р34 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
Р3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
34 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1,5)
(2,1)
Рис. 9. Дерево ветвлений маршрута
Вопросы для самопроверки
1.Какова постановка задачи коммивояжера?
2.Как приводится матрица расстояний по строкам и столбцам?
3.Как определяется константа приведения полностью приведенной матрицы?
4.Как определяется степень нулей матрицы приведенной по строкам и столбцам?
5.В каком случае дуга (i, j) включается в маршрут коммивояжера?
6.До каких пор снижается порядок матрицы маршрута?
7.Как проверить правильность построения маршрута?
8.Как построить дерево ветвлений?
9.В каком случае необходимо вернуться к оборванной ветви?
95
Задачи для самостоятельного решения
1.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
1 |
|
9 |
|
10 |
|
8 |
12 |
||||
|
|
|
|
|
|
|
|
|
8 |
|
24 |
|
|
|
|
|
|
|
|
|
|||
2 |
10 |
|
|
|
6 |
|
13 |
||||
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
6 |
24 |
|
|
|
|
5 |
24 |
|||
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
||
4 |
12 |
3 |
|
14 |
|
|
15 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
13 |
12 |
|
|
|
12 |
|||
5 |
|
6 |
|
||||||||
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
||||
|
|
6 |
10 |
|
5 |
|
7 |
|
|
||
|
|
|
|
|
|||||||
|
|
|
|
|
|
||||||
|
6 |
|
|
14 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
1 |
|
25 |
|
30 |
|
16 |
20 |
|||||
|
|
|
|
|
|
|
|
|
9 |
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
18 |
|
|
|
10 |
|
12 |
|||||
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
35 |
40 |
|
|
|
|
15 |
20 |
||||
|
|
|
|
|
|
|
|
|
|
16 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
30 |
10 |
|
25 |
|
|
19 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
10 |
8 |
|
|
|
6 |
||||
5 |
|
17 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
7 |
5 |
|
6 |
|
10 |
|
|
|
||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
||||||
|
6 |
|
|
15 |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
96
3.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
1 |
|
10 |
|
15 |
|
17 |
18 |
|||||
|
|
|
|
|
|
|
|
|
40 |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
25 |
|
|
|
30 |
|
15 |
|||||
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
27 |
30 |
|
|
|
|
43 |
50 |
||||
|
|
|
|
|
|
|
|
|
|
45 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
17 |
18 |
|
29 |
|
|
30 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
35 |
40 |
|
|
|
27 |
||||
5 |
|
15 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
34 |
40 |
|
15 |
20 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
10 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
1 |
|
30 |
|
16 |
|
18 |
20 |
|||||
|
|
|
|
|
|
|
|
|
25 |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
15 |
|
|
|
17 |
|
18 |
|||||
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
10 |
30 |
|
|
|
|
40 |
25 |
||||
|
|
|
|
|
|
|
|
|
|
24 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
35 |
70 |
|
30 |
|
|
20 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
18 |
16 |
|
|
|
13 |
||||
5 |
|
10 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
15 |
25 |
|
40 |
20 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
30 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
97
5.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30 |
|
1 |
|
20 |
|
30 |
|
50 |
40 |
|||||
|
|
|
|
|
|
|
|
|
25 |
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
40 |
|
|
|
15 |
|
15 |
|||||
|
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
25 |
35 |
|
|
|
|
35 |
40 |
||||
|
|
|
|
|
|
|
|
|
|
25 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
30 |
40 |
|
20 |
|
|
15 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
30 |
40 |
|
|
|
40 |
||||
5 |
|
50 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
10 |
15 |
|
35 |
40 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
25 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
1 |
|
20 |
|
30 |
|
45 |
15 |
|||||
|
|
|
|
|
|
|
|
|
40 |
|
25 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
10 |
|
|
|
15 |
|
30 |
|||||
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
15 |
18 |
|
|
|
|
13 |
13 |
||||
|
|
|
|
|
|
|
|
|
|
30 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
25 |
30 |
|
45 |
|
|
15 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
10 |
20 |
|
|
|
40 |
||||
5 |
|
30 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
45 |
20 |
|
30 |
15 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
20 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
98
7.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
1 |
|
8 |
|
16 |
|
20 |
12 |
|||||
|
|
|
|
|
|
|
|
|
18 |
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
15 |
|
|
|
17 |
|
19 |
|||||
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
20 |
17 |
|
|
|
|
13 |
12 |
||||
|
|
|
|
|
|
|
|
|
|
16 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
9 |
10 |
|
15 |
|
|
20 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
14 |
10 |
|
|
|
15 |
||||
5 |
|
11 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
10 |
30 |
|
18 |
12 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
14 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
1 |
|
25 |
|
40 |
|
30 |
15 |
|||||
|
|
|
|
|
|
|
|
|
15 |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
20 |
|
|
|
25 |
|
40 |
|||||
|
|
|
|
|
|
|
|
|
|
|
50 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
15 |
40 |
|
|
|
|
35 |
30 |
||||
|
|
|
|
|
|
|
|
|
|
30 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
25 |
10 |
|
15 |
|
|
20 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
35 |
40 |
15 |
|
|
|
20 |
||||
5 |
|
25 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
10 |
20 |
|
40 |
50 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
30 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
99
9.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
1 |
|
8 |
|
9 |
|
7 |
6 |
|||||
|
|
|
|
|
|
|
|
|
8 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
10 |
|
|
|
4 |
|
7 |
|||||
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
11 |
12 |
|
|
|
|
4 |
6 |
||||
|
|
|
|
|
|
|
|
|
|
5 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
7 |
9 |
|
10 |
|
|
8 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
9 |
|
12 |
|
|
|
9 |
|||
5 |
|
|
10 |
|
||||||||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|||||
|
|
8 |
10 |
|
14 |
10 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
13 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10.
|
|
1 |
2 |
|
|
3 |
|
4 |
5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
1 |
|
25 |
|
18 |
|
10 |
12 |
|||||
|
|
|
|
|
|
|
|
|
25 |
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
15 |
|
|
|
30 |
|
10 |
|||||
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
20 |
30 |
|
|
|
|
28 |
14 |
||||
|
|
|
|
|
|
|
|
|
|
13 |
||
|
|
|
|
|
|
|
|
|
|
|||
4 |
16 |
18 |
|
20 |
|
|
17 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
25 |
30 |
20 |
|
|
|
10 |
||||
5 |
|
15 |
|
|||||||||
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||
|
|
17 |
20 |
|
15 |
10 |
|
|
|
|||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
6 |
|
18 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Глава 12. Решение транспортной задачи на персональном компьютере с использованием ППП QM for Windows (Transportation)
Алгоритм решения транспортной задачи разработан для закрытых моделей, для которых выполнено условие баланса. В случае открытой
100
модели в программе предусмотрено приведение к закрытой в автоматическом режиме.
Решение задачи начинается с нахождения первоначального опорного плана перевозок. В программе рассматриваются три метода определения первоначального плана: метод северо-западного угла (Northwest Corner Method), метод минимальной стоимости (Minimum Cost Method),
приближенный метод Вогеля (Vogel’s Approximation Method), и если при выборе метода указать процедуру «Any Starting Method», то в автоматическом режиме выбирается лучший из трех перечисленных с точки зрения целевой функции.
Далее задача решается методом потенциалов. Характеристики
свободных клеток Eij |
Cij |
(ui |
v j ) |
не зависят от того, на каком уровне |
|
зафиксирована одна |
из переменных |
ui или v j , поэтому в |
отчетах о |
||
решении задачи указываются только характеристики. |
|
||||
Транспортная задача |
имеет |
команду «Step», дающую |
пошаговый |
процесс решения от итерации к итерации. Если задача имеет не единственное оптимальное решение, то все базисные оптимальные решения можно получить, используя только эту команду. Если задачу решить с помощью команды «Solve», то в отчете о решении будет указано последнее оптимальное решение.
Покажем решение задачи с использованием рассматриваемой программы. В диалоговом окне для создания нового файла необходимо, кроме заголовка (Title), указать число источников (поставщиков) (Number of Sources) и число потребителей (Number of Destinations). После ввода этой информации необходимо заполнить появившуюся таблицу исходных данных задачи. В клетки таблицы вносим данные тарифы Сij , в
последнюю строку (DEMAND) заносим спрос потребителей, а в последний столбец (SUPPLY) – мощность поставщиков.
|
Пусть решается задача |
|
|
|
|
|
ai |
(200;160;140; 220) ; |
|
|
|
|
|
|
|
|
2 |
3 |
9 |
7 |
bj |
(160;180;120;150) ; |
C |
3 |
4 |
6 |
1 . |
|
|
|
5 |
1 |
2 |
2 |
|
|
|
4 |
5 |
8 |
1 |