Автор работы: Пользователь скрыл имя, 06 Июня 2013 в 19:23, практическая работа
Цель выполнения данной практической работы состоит в следующем:
• Найти кратчайшие расстояния между пунктами транспортной сети и заполнить ими соответствующую таблицу;
• Найти кратчайшие пути проезда между пунктами и отразить их на соответствующем рисунке.
Ряд 1 6 7 11 9 11 16 16 12 9 12 5
Строка А А А А А А А А А А А
Из чисел этого ряда найдем наименьшее (2), соответствующее ему звено А-Б занесем в табл11. сравним соответствующие числа ряда 1 и строки Б табл.1. Из каждой сопоставляемой пары выберем наименьшее, получим ряд II.
Столбец В Г Д Е Ж З И К Л М
Ряд II 4 7 9 7 11 16 16 10 7 10
Строка Б А Б Б А А А Б Б Б
Наименьше число 3 соответствует звену Б-Н, заносим его в табл.11. Сравним числа строки Н с числами ряда II, и получим ряд III.
Столбец В Г Д Е Ж З И К Л М
Ряд III 4 7 9 7 11 16 16 9 7
Строка Б А Б Б А А А Н Н
Наименьшее число 4 соответствует звену Н-Л, занесем его в табл.11. Сравним числа строки Л с числами ряда III, получим ряд IV.
Столбец Г Д Е Ж З И К М
Ряд IV 7 9 7 11 14 16 5 7
Строка А Б Б А Л А Л Н
Наименьшее число 4 соответствует звену Б-В, занесем его в табл.11. Сравним числа строки В с числами ряда IV, получим ряд V.
Столбец Г Д Е Ж З И К М
Ряд V 7
5
11 14 16 5
7
Строка А В А Л А Л Н
Наименьшее число 3 соответствует звену В-Е, занесем его в табл.11. Сравним числа строки Е с числами ряда V, получим ряд VI.
Столбец Г Д Ж З И К М
Ряд VI 7 9 14 15 5 7
Строка А Е Е Е Л Н
Наименьшее число 4 соответствует звену Е-Д, занесем его в табл.11. Сравним числа строки Д с числами ряда VI, получим ряд VII.
Столбец Г Ж З И К М
РядVII 7 9 14 15 7
Строка А Е Е Е Н
Наименьшее число 5 соответствует звену Л-К, занесем его в табл.11. Сравним числа строки К с числами ряда IIV, получим ряд VIII.
Столбец Г Ж З И
РядVIII 7 9 9 12
Строка А Е К К
Наименьшее число 6 соответствует звену К-М, занесем его в табл.11. Сравним числа строки М с числами ряда VIII, получим ряд IХ.
Столбец Ж З И
Ряд IХ 9 9 12
Строка Е К К
Наименьшее число 7 соответствует звену А-Г, занесем его в табл.11. Сравним числа строки Г с числами ряда IХ, получим ряд Х.
Столбец Ж З И
Ряд Х 9 9
Строка Г Г
Наименьшее число 4 соответствует звену Г-Ж, занесем его в табл.11. Сравним числа строки Ж с числами ряда Х, получим ряд ХI.
Столбец И
Ряд ХI 6
Строка Ж
Наименьшее число 5 соответствует звену Ж-З, занесем его в табл.11. Сравним числа строки З с числами ряда ХI, получим ряд ХII.
Столбец
Ряд ХII
Строка
Таблица 11. Звенья кратчайшей связывающей сети.
Порядковый номер звена |
Звено |
Длина звена, км |
Порядковый номер звена |
Звено |
Длина звена, км |
1 |
А - Б |
2 |
7 |
Л - К |
5 |
2 |
Б - Н |
3 |
8 |
К - М |
6 |
3 |
Н - Л |
4 |
9 |
А - Г |
7 |
4 |
Б - В |
4 |
10 |
Г - Ж |
4 |
5 |
В - Е |
3 |
11 |
Ж - З |
5 |
6 |
Е - Д |
4 |
12 |
З - И |
3 |
Рисунок 5. Кратчайшая связывающая сеть.
Таблица 12. Развозочные маршруты движения автомобилей, полученные по кратчайшей связывающей сети.
Маршрут движения |
Загрузка, т. |
Длина маршрута, км. |
0,3+0,3+0,1+0,3+0,2+0,1+0,4 1.А-В-Е-Д-И-З-Ж-Г-А 6+3+4+16+3+5+4 |
= 1,7 |
= 41 |
0,2+0,3+0,1+0,4+0,2 2.А-Б-Н-Л-К-М-А 2+3+4+5+6+12 |
= 1,2 |
= 32 |
ИТОГО |
2,9 |
73 |
Таким образом, маршруты, полученные с помощью кратчайшей связывающей сети, оказались короче на 25 км, чем маршруты, составленные визуально по исходной транспортной сети. Это, однако, не говорит о том, что маршруты в табл.12 самые короткие. Поэтому каждый из них целесообразно проверить на оптимальность последовательности объезда пунктов.
Для решения этой
задачи можно применить метод
«ветвей и границ»,
Рассмотрим метод «суммирования по столбцам», который также можно использовать для оптимизации последовательности объезда пунктов развозочного маршрута при симметричной матрице расстояний. Составим матрицу расстояний для 1го маршрута и подсчитаем сумму расстояний по каждому столбцу.
Таблица 13. Матрица расстояний и суммы столбцов для 1го маршрута.
А |
В |
Е |
Д |
И |
З |
Ж |
Г | |
А |
6 |
9 |
11 |
16 |
16 |
11 |
7 | |
В |
6 |
3 |
5 |
21 |
20 |
12 |
13 | |
Е |
9 |
3 |
4 |
15 |
14 |
9 |
12 | |
Д |
11 |
5 |
4 |
16 |
15 |
10 |
8 | |
И |
16 |
21 |
15 |
16 |
3 |
6 |
9 | |
З |
16 |
20 |
14 |
15 |
3 |
5 |
9 | |
Ж |
11 |
12 |
9 |
10 |
6 |
5 |
4 | |
Г |
7 |
13 |
12 |
8 |
9 |
9 |
4 |
|
Сумма |
76 |
80 |
65 |
69 |
86 |
82 |
57 |
62 |
Составление маршрута
начинается с выбора трех
И – З – В – И , его длина 44 км.
В него включаем пункт А (сумма расстояний равна 76) таким образом, чтобы приращение длины исходного маршрута было минимальным:
Таким образом, пункт А включаем в исходный маршрут между В и И.
Следующим включаем пункт Д (сумма 69)
Таким образом, пункт Д включаем в исходный маршрут между пунктами З и В.
Следующим включаем пункт Е (сумма 65)
Выгоден вариант 3, берем его за основу и включаем в маршрут между пунктами Д и В, следующим включаем пункт Г (сумма 62).
Наиболее целесообразен 6 вариант, где приращение равно 0. Это и будет окончательный маршрут. Заметим, что он стал длиннее выбранного по кратчайшей связывающей сети на 6км., значит необходимо оставить первоначальный маршрут.
Определим последовательность объезда пунктов во 2ом маршруте таким же образом. Матрица кратчайших расстояний и сумма столбцов представлены в таблице 14.
Таблица 14. Матрица расстояний и суммы столбцов для 2го маршрута.
А |
Г |
З |
И |
К |
Ж |
Д | |
А |
8 |
13 |
17 |
22 |
19 |
7 | |
Г |
8 |
5 |
9 |
14 |
13 |
9 | |
З |
13 |
5 |
4 |
9 |
8 |
14 | |
И |
17 |
9 |
4 |
6 |
12 |
18 | |
К |
22 |
14 |
9 |
6 |
10 |
22 | |
Ж |
19 |
13 |
8 |
12 |
10 |
12 | |
Д |
7 |
9 |
14 |
18 |
22 |
12 |
|
Сумма |
86 |
58 |
53 |
66 |
83 |
74 |
82 |
Исходный маршрут А-К-М-А, его длина 31 км., в него включаем пункт Л с суммой 35.
Пункт Л включаем в маршрут между пунктами А
и К и включаем в него пункт Б с суммой
32.
Пункт Б включаем в маршрут между пунктами А и Л, его длина составит 32 км. В него включаем пункт Н с суммой 28.
Длина маршрута не изменилась, изменился лишь порядок объезда пунктов таблица 12.
Следует заметить,
что при использовании метода
« суммирования по столбцам
» наибольшая сумма не всегда
соответствует пункту А.
Таблица 13. Маршруты с уточненным порядком объезда пунктов.
Маршрут движения |
Загрузка, т. |
Длина маршрута, км. |
0,3+0,3+0,1+0,3+0,2+0,1+0,4 1. А-В-Е-Д-И-З-Ж-Г-А 6+3+4+16+3+5+4 |
= 1,7 |
= 41 |
0,2+0,1+0,4+0,2+0,3 2.А-Б-Л-К-М-Н-А 2+7+5+6+7+5 |
= 1,2 |
= 32 |
ИТОГО |
2,9 |
73 |
Рисунок 6. Развозочные маршруты, составленные с использованием кратчайшей сети и оптимизированные методом «суммирования по столбцам».
Вывод: Таким образом, использование кратчайшей связывающей сети (для набора пунктов в маршруты) и метода « суммирования по столбцам » (для уточнения последовательности их объезда) позволило получить развозочные маршруты на 25км. короче, чем без их использования.
ЛИТЕРАТУРА:
Информация о работе Определение кратчайших расстояний между пунктами транспортной сети