4434
.pdf31
d i min d i , d d a d, i min , 6 .
Поскольку величина d(b) = 11 является минимальной из величин d(a), d(b), d(c), d(e), d(f), d(g), d(h) и d(i), то вершина b окрашивается. Также окрашивается и дуга (a, b), которая и определяет величину d(b). Текущее дерево кратчайших путей состоит из дуг (a, d) и (a, b) (рисунок 4 б).
Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.
Шаг 2. (у = b).
d c min d c , d b a b, c min , 11 20 31,
d e min d e , d b a b, e min 13, 11 12 13,
d f min d f , d b a b, f min , 11 18 29,
d g min d g , d b a b, g min 18, 11 18,
d h min d h , d b a b, h min 14, 11 14,
d i min d i , d b a b, i min , 11 .
Поскольку величина d(e) = 13 является минимальной из величин d(a), d(c), d(e), d(f), d(g), d(h) и d(i), то вершина e окрашивается. Также окрашивается и дуга (d, e), которая и определяет величину d(e). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b) и (d, e) (рисунок 4 в).
Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.
Шаг 2. (у = e).
d c min d c , d e a e, c min 31, 13 31,
32
d f min d f , d e a e, f min 29, 13 3 16,
d g min d g , d e a e, g min 18, 13 18,
d h min d h , d e a e, h min 14, 13 19 14,
d i min d i , d e a e, i min , 13 7 20.
Поскольку величина d(h) = 14 является минимальной из величин d(a), d(c), d(f), d(g), d(h) и d(i), то вершина h окрашивается. Также окрашивается
и дуга (d, h), которая и определяет величину d(h). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e) и (d, h) (рисунок 4 г).
Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.
Шаг 2. (у = h).
d c min d c , d h a h, c min 31, 14 31, d f min d f , d h a h, f min 16, 14 16,
d g min d g , d h a h, g min 18, 14 11 18,
d i min d i , d h a h, i min 20, 14 29 20.
Поскольку величина d(f) = 16 является минимальной из величин d(a), d(c), d(f), d(g), и d(i), то вершина f окрашивается. Также окрашивается и дуга (e, f), которая и определяет величину d(f). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e), (d, h) и (e, f) (рисунок 4 д).
Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.
Шаг 2. (у = f).
d c min d c , d f a f , c min 31, 16 11 27,
33
d g min d g , d f a f , g min 18, 16 18,
d i min d i , d f a f , i min 20, 16 24 20.
Поскольку величина d(g) = 18 является минимальной из величин d(a), d(c), d(g) и d(i), то вершина g окрашивается. Также окрашивается и дуга (a, g), которая и определяет величину d(g). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e), (d, h), (e, f) и (a, g) (рисунок 4 е).
Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.
Шаг 2. (у = g).
d c min d c , d g a g, c min 27, 18 27, d i min d i , d g a g, i min 20, 18 20.
34
|
|
|
|
|
|
|
(a) |
|
|
|
(a) |
|
|
|
(b) |
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
11 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
а) |
6 |
(d) |
|
|
6 |
(d) |
|
|
|
|
|
|
|
|
|
|
|
5 |
|
б) |
5 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
(a) |
|
|
|
(b) |
|
(a) |
|
(b) |
|
(a) |
|
|
|
(b) |
|
|
1 |
11 |
|
|
|
|
|
|
|
|
|
||||||
|
|
2 |
|
1 |
11 |
2 |
|
1 |
11 |
|
|
2 |
|
|||
6 (d) |
|
|
|
6 (d) |
|
|
|
|
||||||||
|
|
|
|
|
|
|
6 |
(d) |
|
|
|
|
||||
|
|
|
|
(e) |
|
|
|
|
|
|
|
|
|
|
||
5 |
|
7 |
|
|
5 |
7 |
(e) |
|
|
5 7 |
|
|
(e) |
3 |
||
|
|
|
|
6 |
|
6 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
||
|
в) |
|
|
|
|
|
|
8 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
8 |
|
||||
|
|
|
|
|
|
|
|
г ) |
|
12 |
|
д) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
(h) |
|
|
|
|
(h) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
(a) |
|
|
|
(b) |
|
|
|
(a) |
|
|
(b) |
|
|||
|
1 |
|
|
11 |
|
2 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
1 |
11 |
|
|
|
|
|||
|
6 |
|
|
|
|
|
|
|
|
|
2 |
|
||||
|
|
(d) |
|
|
|
|
|
(f) |
|
|
|
|
||||
|
|
|
|
|
|
|
|
6 (d) |
|
|
|
|
||||
|
|
|
|
|
(e) |
3 |
7 |
|
|
|
|
|
|
|||
|
18 |
|
5 |
|
7 |
|
|
|
|
5 |
7 |
(e) |
3 |
|||
|
|
|
|
|
6 |
|
|
|
18 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
6 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
(g) |
|
|
|
12 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
(g) |
|
|
|
12 |
|||||
|
|
|
|
|
е) |
|
(h) |
|
|
ж) |
||||||
|
|
|
|
|
|
|
|
|
|
(h) |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
(f)
7
(f)
7
13 (i)
Рисунок 4 – Применение алгоритма Дейкстры для поиска кратчайшего пути между вершинами 1 и 13
35
Поскольку величина d(i) = 20 является минимальной из величин d(a), d(c),
иd(i) то вершина i окрашивается, что и требуется в задаче. Также окрашивается
идуга (e, i), которая и определяет величину d(i). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e), (d, h), (e, f), (a, g) и (e, i) (рисунок 4 ж).
Суммарное расстояние от вершины a (1) до вершины i (13) составляет 20 км и пролегает через вершины 1, 5, 6, 13. Кроме того, можно отметить, что попутно было определено расстояние от вершины a (1) до вершины f (7), которое составляет 16 км и пролегает через вершины 1, 5, 6, 7.
Кратчайшее расстояние между вершинами 7 и 13 можно определить из треугольника, состоящего из вершин 7, 13 и 6. Кратчайший путь составит 10 км и пролегает через вершины 7, 6, 13.
Аналогично определяем кратчайшие пути между остальными вершинами транспортной сети и заносим их в таблицу 2.1.
Примечание: число пар вершин, между которыми определяются кратчайшие пути, должно быть достаточным для составления транспортной сети между 14 вершинами, указанными в индивидуальном задании.
Таблица 2.1 – Кратчайшие пути между вершинами транспортной сети
Вер- |
Путь |
Рас- |
|
шины |
стояние, км |
||
|
|||
|
|
|
|
1 |
2 |
3 |
|
|
|
|
|
1-4 |
1, 5, 6, 7, 3, 4 |
41 |
|
|
|
|
|
1-7 |
1, 5, 6, 7 |
16 |
|
|
|
|
|
1-13 |
1, 5, 6, 13 |
20 |
|
|
|
|
|
1-22 |
1, 11, 17, 22 |
49 |
|
|
|
|
|
4-7 |
4, 3, 7 |
25 |
|
|
|
|
|
4-10 |
4, 10 |
1 |
|
|
|
|
|
7-10 |
7, 3, 4, 10 |
26 |
|
|
|
|
|
7-13 |
7, 6, 13 |
10 |
|
|
|
|
|
10-16 |
10, 16 |
9 |
|
|
|
|
|
10-19 |
10, 15, 20, 19 |
38 |
|
|
|
|
|
10-13 |
10, 15, 8, 13 |
28 |
|
|
|
|
|
13-16 |
13, 8, 15, 10, 16 |
37 |
|
|
|
|
|
13-19 |
13, 6, 5, 12, 19 |
49 |
|
|
|
|
36
1 |
2 |
|
3 |
|
|
|
|
13-22 |
13, 6, 5, 12, 18, 23, 28, 22 |
63 |
|
|
|
|
|
16-19 |
16, 21, 20, 19 |
41 |
|
|
|
|
|
16-25 |
16, 21, 20, 25 |
42 |
|
|
|
|
|
16-31 |
16, 27, 26, 31 |
46 |
|
|
|
|
|
16-37 |
16, 27, |
37 |
23 |
|
|
|
|
19-22 |
19, 18, 23, 28, 22 |
45 |
|
|
|
|
|
19-25 |
19, 25 |
29 |
|
|
|
|
|
22-25 |
22, 28, 23, 18, 24, 25 |
53 |
|
|
|
|
|
22-28 |
22, 28 |
9 |
|
|
|
|
|
25-28 |
25, 24, 18, 23, 28 |
44 |
|
|
|
|
|
25-31 |
25, 31 |
14 |
|
|
|
|
|
28-31 |
28, 23, 18, 24, 25, 31 |
58 |
|
|
|
|
|
28-34 |
28, 32, 34 |
34 |
|
|
|
|
|
28-37 |
28, 23, 18, 19, 20, 26, 37 |
62 |
|
|
|
|
|
28-40 |
28, 32, 33, 44, 38, 40 |
73 |
|
|
|
|
|
31-34 |
31, 36, 35, 39, 34 |
50 |
|
|
|
|
|
31-37 |
31, 36, 37 |
23 |
|
|
|
|
|
31-40 |
31, 36, 37, 42, 41, 40 |
67 |
|
|
|
|
|
34-37 |
34, 39, 35, 36, 37 |
55 |
|
|
|
|
|
34-40 |
34, 38, 40 |
40 |
|
|
|
|
|
37-40 |
37, 42, 41, 40 |
44 |
|
|
|
|
|
Нанесем полученные кратчайшие пути на транспортную сеть (рисунок
2.6).
Примечание: рекомендуется выделять кратчайшие пути утолщенными линиями, что особенно удобно при использовании программы КОМПАС-3D.
|
|
|
|
|
|
|
37 |
|
|
|
|
|
|
|
1 |
|
11 |
|
|
20 |
|
3 |
|
|
14 |
|
|
|
4 |
|
2 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
24 |
|
|
|
|
||||
|
6 |
23 |
|
|
|
11 |
|
|
|
|
13 |
|
||
|
18 |
|
|
|
|
|
|
|
1 |
|||||
|
|
|
|
|
|
25 |
|
|||||||
|
|
|
12 |
|
|
7 |
|
|
8 |
9 |
||||
|
|
|
|
|
|
|
22 |
|
|
|
||||
|
|
|
|
|
3 |
|
|
|
|
|
||||
|
5 |
|
|
|
|
|
|
|
|
|
|
|
||
18 |
|
7 |
|
|
24 |
20 |
|
|
|
|
|
10 |
||
|
|
6 |
|
|
|
|
|
|
23 |
|||||
|
|
|
|
|
|
|
2 |
7 |
|
|
||||
|
|
|
|
7 |
|
|
|
|
|
|
||||
|
30 |
8 |
|
|
25 |
|
29 |
|
1 |
|||||
|
19 |
|
|
13 |
14 |
|
||||||||
|
|
|
11 |
|
|
|
|
|
|
15 |
9 |
|||
|
11 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
29 |
|
28 |
20 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
15 |
|
||||
19 |
|
|
12 |
|
|
|
|
|
|
|
|
|
||
|
|
|
27 |
19 |
17 |
|
|
|
23 |
16 |
||||
|
|
|
|
12 |
|
20 |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
1 |
21 |
|
|
|
|
17 |
|
|
18 |
|
|
16 |
29 |
|
|
|
|
||
12 |
|
|
|
|
|
|
|
|
|
|
30 |
4 |
||
|
|
|
|
|
|
|
|
1 |
|
|
||||
|
3 |
15 |
|
|
|
|
18 |
|
|
|||||
|
|
15 |
|
|
|
4 |
|
|
|
|||||
22 |
|
|
|
|
|
9 |
25 |
|
|
|
|
|
||
24 |
23 |
|
|
24 |
|
|
26 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
14 |
|
|
27 |
|
|
9 |
|
|
5 |
21 |
|
|
22 |
|
21 |
|
21 |
|
||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
30 |
|
|
|
|
|
|
|
||
|
28 |
|
|
|
|
|
31 |
|
19 |
|
||||
|
|
|
|
|
|
|
|
8 |
|
|||||
|
|
|
|
|
|
30 |
|
|
|
7 |
||||
|
|
|
17 |
|
|
|
15 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
25 |
|
29 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
4 |
|
9 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
26 |
|
|
|
37 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
32 |
|
19 |
|
13 |
|
|
36 |
14 |
|
14 |
|
||
6 |
|
|
|
|
|
|
|
24 |
|
15 |
|
|
||
|
9 |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
35 |
|
|
|
|
|
43 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
33 |
|
|
34 |
4 |
|
|
13 |
|
25 |
|
42 |
12 |
|
|
|
|
|
|
|
|
24 |
|
3 |
|
|
|
|
||
|
|
|
21 |
|
|
|
|
|
|
|
|
17 |
||
|
28 |
|
39 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
7 |
|
38 |
28 |
|
|
26 |
26 |
41 |
11 |
50 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
9 |
|
|
|||
|
|
|
13 |
19 |
|
|
40 |
|
|
|
|
|
|
|
|
16 |
|
|
6 |
|
23 |
|
|
|
23 |
||||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
44 |
|
|
45 |
|
|
|
6 |
|
|
|
|
48 |
14 |
|
|
19 |
|
|
|
|
|
47 |
23 |
|
|
|
|||
|
|
15 |
|
46 |
|
|
|
|
49 |
|||||
|
|
|
|
|
26 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
38
Рисунок 5 – Сеть кратчайших путей на транспортной сети
Далее исключим из сети невыделенные дуги, а также узлы, которые не входят в задание и не являются точками пересечения кратчайших путей и получим итоговою транспортную сеть, на которой будет производиться распределение поставок грузов (рисунок 6).
Примечание: после исключения узлов возможна ситуация, когда вершина, входящая в задание, соединена с сетью лишь одной дугой; в этом случае следует искусственно оставить одну из дуг, не входящей в кратчайший путь, для соединения этой вершины с сеть, так как в противном случае для указанной вершины невозможно будет составить замкнутый контур.
1 |
|
|
|
|
|
|
|
25 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
7 |
|
|
8 |
|
|
|
|
|
3 |
|
22 |
|
|
|
||
5 |
|
|
|
|
|
|
|
|
||
7 |
|
|
20 |
|
|
|
|
10 |
||
|
|
|
|
|
|
|
|
|||
|
|
6 |
|
|
|
|
|
|
||
|
|
|
|
|
|
7 |
|
|
||
|
|
7 |
|
|
|
|
|
|
||
|
8 |
|
|
|
|
|
|
|
1 |
|
|
|
|
13 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
15 |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
|
49 |
|
12 |
27 |
|
19 |
17 |
|
|
24 |
16 |
|
|
12 |
|
20 |
|
|||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
16 |
29 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
||
|
|
|
|
|
|
1 |
|
|
||
|
|
|
|
|
|
18 |
|
|
||
|
|
|
|
|
|
|
|
|
||
|
|
|
24 |
|
|
|
|
|
||
|
|
|
25 |
|
|
|
|
|
||
22 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
26 |
|
27 |
|
9 |
20 |
|
|
|
|
21 |
21 |
|||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
||
28 |
|
|
|
|
|
|
31 |
8 |
19 |
|
|
|
|
|
|
|
|
|
|||
25 |
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
37 |
|
32 |
|
|
|
|
|
36 |
14 |
|
|
|
|
9 |
|
41 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
29 |
34 |
|
|
|
|
44 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
21 |
|
|
|
|
|
|
|
|
|
|
38 |
|
|
|
|
|
|
|
|
|
|
|
19 |
|
40 |
|
|
|
|
|
|
Рисунок 2.7 – Итоговая транспортная сеть
39
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Основная литература
1. Горев А. Э. Основы теории транспортных систем [Электронный ресурс] : учеб. пособие. - СПб.: СПбГАСУ, 2010. - 214 с. - ЭБС "Единое окно".
Дополнительная литература:
1.Моделирование транспортных процессов [Электронный ресурс] : тексты лекций / Д. В. Лихачев, В. П. Белокуров, В. А. Зеликов, Г.А. Денисов ; ВГЛТУ. - 2016. - ЭБС ВГЛТУ.
2.Моделирование транспортных процессов [Электронный ресурс] : методические указания к практическим занятиям для студентов по направлению подготовки 23.03.01 – Технология транспортных процессов / Д.В. Лихачев, Г.А. Денисов, Ю.В. Струков, Р.А. Сподарев, А.Ю. Артемов ; ВГЛТУ. - 2016. - ЭБС ВГЛТА.
3.Моделирование транспортных процессов [Электронный ресурс] : методические указания к расчетно-графической работе для студентов по направлению подготовки 23.03.01 – Технология транспортных процессов / Д. В. Лихачев, А.Ю. Артемов, Ю.В. Струков, Р.А. Кораблев, Э.Н. Бусарин ; ВГЛТА. - 2016. - ЭБС ВГЛТА.
4.Моделирование дорожного движения [Электронный ресурс] : тексты лекций / Д.В. Лихачев, В. П. Белокуров, В. А. Зеликов, Р. А. Кораблѐв ; ВГЛТУ. - 2016. - ЭБС ВГЛТУ.
5.Петров В. В. Управление движением транспортных потоков в городах [Текст] : монография / В. В. Петров; Фед. агентство по образованию, Сиб. гос. автомобил.-дорож. акад. - Омск : СибАДИ, 2007. - 92 с.
6.Советов Б. Я. Моделирование систем [Текст] : учеб. для бакалавров
:рек. М-вом образования Рос. Федерации в качестве учеб. / Б. Я. Советов, С. А. Яковлев. - 7-е изд. - М. : Юрайт, 2012. - 343 с.
7.Бюллетень транспортной информации [Текст] : журнал. - М. : ИТАР
- ТАСС, 1995 -.
8.Вестник Московского автомобильно-дорожного института [Текст] : журнал / М-во образования Рос. Федерации, Моск. автомоб.-дорож. ин-т (гос. техн. ун-т). - М. : Изд-во МАДИ (ГТУ), 2003 -.
40
Приложение А
Темы рефератов
1.Виды моделей.
2.Исследовании операций.
3.Детерминированные и стохастические системы.
4.Математические методы обследования и анализа транспортного
процесса.
5.Приведение задачи линейного программирования к канонической
форме.
6.Решение задачи линейного программирования графическим мето-
дом.
7.Задача об использовании ограниченного ресурса.
8.Задача о ранце.
9.Метод аппроксимации Фогеля.
10.Двойственность в линейном программировании.
11.Математическая модель транспортной задачи.
12.Решение задачи с использованием симплекс-метода.
13.Решение транспортной задачи в процессе организации перевозок.
14.Решение транспортной задачи методом потенциалов.
15.Задачи, сводимые к транспортной
16.Решение задачи коммивояжера.
17.Процесс Маркова и процесс размножения и гибели.
18.Решение задачи теории массового обслуживания.
19.Системы массового обслуживания, классификация, показатели.
20.Применение теоремы Форда-Фолкерсона.
21.Решение задачи о кратчайшем маршруте при организации оптимального плана перевозок.
22.Математическое моделирование в решении задач организации перево-
зок.
23.Предмет и область применения теории игр.
24.Теории статистических решений ее применение при моделировании транспортных процессов.
25.Кооперативные игры.
26.Имитационное моделирование процессов транспортного обслуживания клиентов.
27.Имитационное моделирование процессов обслуживания автомобильного транспорта.
28.Метод статистических испытаний и его применение при моделировании случайных величин.
29.Имитационное моделирование задач массового обслуживания.