Графы и сети. Харитонова Е.В. - 76 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

75
Рис. 3.22
Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут:
1 – 2 – 5 – 7.
Задача замены автомобильного парка
Фирма по прокату автомобилей планирует замену автомобильного парка на очеред-
ные 5 лет. Автомобиль должен проработать не менее 1 года, прежде чем фирма поставит во-
прос о его замене. На рис. 3.23 приведены стоимости замены автомобилей (усл. ед.), завися-
щие от времени замены и количества лет, в течение которых автомобиль находился в экс-
плуатации.
Рис. 3.23
Определить план замены автомобилей, обеспечивающий при этом минимальные рас-
ходы.
РЕШЕНИЕ. Найдем минимальные расстояния:
U
1
= 0,
U
2
= U
1
+ d
12
= 0 + 4 = 4,
U
3
= min{U
1
+ d
13
; U
2
+ d
23
} = min{0 + 5,4; 4 + 4, 3} = 5,4,
U
4
= min{U
1
+ d
14
; U
2
+ d
24
; U
3
+ d
34
} = min{0 + 9,8; 4 + 6,2; 5, 4 + 4, 8} = 9,8,
U
5
= min{U
1
+ d
15
; U
2
+ d
25
; U
3
+ d
35
; U
4
+ d
45
} =min{0 + 13,7; 4 + 8, 1; 5,4 + 7, 1; 9, 8 +
4, 9} = 12,1.
Кратчайший путь 1– 2 – 5 со стоимостью 12,1 усл. ед. Это означает, что каждый авто-
мобиль заменяется через 2 года, а через 5 – списывается.
2
1
5
63
4
11
5
2
10
3
1
7
4
8
7
9
6
8
,
1
1 2 3 4 5
13,7
9,8 5,4
4
4,3 4,8 4,9
6,2
7,1

Страницы