Задание №4.
Граф состоит из 10 вершин. Расстояния между вершинами заданы в таблице 2. Найти кратчайший путь между вершинами 1 и 10. Сделать чертеж.
|
начало |
конец |
Длина ребра | |||||||||
|
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |
50 | ||
|
1 |
2 |
1 |
17 |
20 |
12 |
17 |
9 |
14 |
13 |
10 |
4 |
|
1 |
5 |
1 |
11 |
13 |
10 |
13 |
2 |
12 |
13 |
14 |
13 |
|
2 |
3 |
3 |
19 |
14 |
8 |
1 |
13 |
15 |
9 |
20 |
1 |
|
2 |
4 |
3 |
10 |
7 |
9 |
12 |
17 |
14 |
11 |
14 |
6 |
|
3 |
4 |
6 |
15 |
10 |
6 |
7 |
17 |
13 |
5 |
3 |
19 |
|
4 |
6 |
7 |
20 |
12 |
11 |
1 |
2 |
8 |
10 |
13 |
18 |
|
5 |
6 |
8 |
15 |
7 |
7 |
1 |
16 |
1 |
12 |
5 |
2 |
|
5 |
7 |
8 |
4 |
19 |
1 |
8 |
8 |
13 |
14 |
3 |
3 |
|
6 |
7 |
9 |
13 |
7 |
14 |
16 |
14 |
18 |
7 |
19 |
16 |
|
6 |
9 |
9 |
7 |
4 |
2 |
17 |
18 |
19 |
20 |
17 |
3 |
|
7 |
8 |
9 |
12 |
10 |
17 |
10 |
14 |
15 |
2 |
3 |
16 |
|
7 |
10 |
9 |
9 |
10 |
16 |
9 |
15 |
7 |
7 |
4 |
1 |
|
8 |
10 |
10 |
1 |
7 |
2 |
15 |
14 |
4 |
11 |
13 |
10 |
|
9 |
10 |
10 |
2 |
13 |
3 |
11 |
2 |
20 |
16 |
18 |
14 |
Задание №5.
51-60.
На
три станции
поступил однородный груз в количестве:
а1
- на станцию А1
, а2
- на станцию А2
, а3
- на станцию А3
. Полученный груз требуется перевезти
в 5 пунктов: b1
– в пункт В1,
b2
– в пункт В2,
b3
– в пункт В3,
b4
– в пункт В4,
b5
– в пункт В5.
Расстояния между пунктами отправления и пунктами назначения указаны в матрице расстояний
|
Пункты отправления |
Пункты назначения | ||||
|
В1 |
В2 |
В3 |
В4 |
В5 | |
|
А1 |
d11 |
d21 |
d31 |
d41 |
d51 |
|
А2 |
d21 |
d22 |
d23 |
d24 |
d25 |
|
А3 |
d31 |
d32 |
d33 |
d34 |
d35 |
Стоимость перевозок пропорциональна количеству груза и расстоянию на которое этот груз перевозится. Спланировать перевозки так чтобы их стоимость была минимальной (ввиду пропорциональности затрат количеству груза и расстоянию достаточно минимизировать общий объем, выраженный в тонно-километрах).
a1=200 a2=150 a3=150 b1=180 b2=100 b3=70 b4=130 b5=110
a1=300 a2=280 a3=220 b1=180 b2=140 b3=190 b4=12 b5=170
52.
a1=250 a2=200 a3=150 b1=180 b2=120 b3=90 b4=105 b5=105
a1=400 a2=250 a3=350 b1=200 b2=170 b3=230 b4=225 b5=175
a1=150 a2=200 a3=150 b1=160 b2=70 b3=90 b4=80 b5=100
a1=280 a2=300 a3=220 b1=170 b2=120 b3=190 b4=140 b5=180
a1=150 a2=250 a3=200 b1=180 b2=120 b3=90 b4=105 b5=105
a1=250 a2=400 a3=350 b1=300 b2=160 b3=220 b4=180 b5=140
a1=150 a2=150 a3=200 b1=100 b2=70 b3=130 b4=110 b5=90
a1=280 a2=220 a3=300 b1=190 b2=140 b3=180 b4=120 b5=170
56.
57.
58.
59.
60.
Литература
Волкова, Виолетта Николаевна. Теория систем и системный анализ: учебник/ В. Н. Волкова, А. А. Денисов. - 2-е изд., перераб. и доп.. - М.: Издательство Юрайт, 2013. - 616 с.
Давыдов, Иван Степанович. Информатика: учебное пособие/ И. С. Давыдов. - СПб.: Проспект Науки, 2009. - 480 с.
Гуда А.Н. Информатика. Общий курс: учебник/ А. Н. Гуда, М. А. Бутакова, Н. М. Нечитайло, А. В. Чернов. - 4-е изд.. - М.: Издательско-торговая корпорация "Дашков К"; Ростов н/Д: Наука Спектр, 2011. - 400 с.
Степанов, Анатолий Николаевич. Информатика: учебник/ А. Н. Степанов. - 6-е изд.. - СПб.: Питер, 2010. - 720 с.