ВИХІДНІ ДАНІ
З пункту А (база) доставляється вантаж у 11 інших пунктів, перерахованих у вихідних даних, з яких у свою чергу необхідно в пункт А доставити вантаж, наприклад поворотну тару (малюнок 1). Кількість одиниць вантажу доставляється з пункту А в кожен з них, даний у вихідних даних.
Місткість одного автомобіля складає не більше 250 од. вантажу. Необхідно організувати перевезення між пунктами найменшим пробігом автомобіля.
Таблиця 1 - Вихідні дані
Пункт
Ввезення
Вивіз
Б
10
30
В
30
20
Г
50
55
Д
20
80
Е
15
40
Ж
70
30
З
45
70
І
20
25
К
100
40
Л
50
20
М
30
30
ПІДСУМОК
440
440
Рисунок 1 - Схема розміщення пунктів і відстані між ними
РІШЕННЯ:
Рішення знаходиться шляхом послідовного розрахунку по декількох етапах.
1 етап - знаходження найкоротшою зв'язує мережі.
Нехай всі пункти, зазначені на малюнку 1, називаються вершинами мережі, а лінія, з'єднує дві сусідні вершини, - ланкою; незамкнута мережа, що зв'язує дві і більше вершини з мінімальної сумарною довжиною усіх з'єднують їх ланок; найкоротшою зв'язує мережею.
Вона визначається наступним чином:
1) на мережі знаходимо меншу ланка В-Г = 2 км;
2) розглянемо всі ланки, пов'язані з одній зі своїх вершин з обраним ланкою, т. Е. ланки В-А = 9; В-Б = 3; В-Д = 4; Г-Б = 2; Г-Д = 4; Г-Е = 4;
3) з них вибираємо ланки з найменшим відстанню Г-Б = 2;
4) розглянемо ланки, пов'язані з вершинами отриманої лінії В-Г-Б, і з них виберемо найменше (при цьому не можна вибирати ланка, що з'єднує дві раніше включені в мережу вершини), така ланка - В-Б;
5) іншими ланками пов'язаними своїми вершинами з вже обраною мережею є ланки В-А, В-Д, Г-Д, Г-Е, Б-Е (Останні 4 мають = найменші відстані);
6) приймемо найменшу Б-Е і отримаємо мережу В-Г-Б-Е. На малюнку 2 представлена ​​найкоротша зв'язує мережу;
100
30
Малюнок 2 - Найкоротша зв'язує мережу
7) умовами задачі встановлено, що місткість автомобіля - 250 од. вантажу; виходячи з цього пункти, зазначені на малюнку 2 можна згрупувати, так як це зроблено в таблиці 2;
Таблиця 2 - Групування маршрутів
Пункти
Маршрут № 1
Пункти
Маршрут № 2
Кількість вантажу, од.
Кількість вантажу, од.
Ввезення
Вивіз
Ввезення
Вивіз
Б
10
30
Д
20
80
В
30
20
І
20
25
Г
50
55
К
100
40
Ж
70
30
Л
50
20
Е
15
40
М
30
30
З
45
70
РАЗОМ
220
195
РАЗОМ
220
245
2 етап - набір пунктів у маршрути
За кожної гілки мережі, починаючи з тієї, яка має найбільше число ланок, групують пункти в маршрути з урахуванням кількості ввезеного і вивозиться і місткості рухомого складу. Якщо всі пункти даної гілки не можуть бути включені в один маршрут, то найближчі до іншої гілки пункти групуються разом з пунктами цієї гілки.
У нашому випадку умовами задачі встановлено, що максимальна місткість автомобіля складає 250 од. вантажу. Виходячи з цього пункти, вказані на малюнку 2, можна згрупувати так, як це зроблено в таблиці 2.
3 етап - визначення черговості об'їзду пунктів маршруту
На цьому етапі всі пункти маршруту, починаючи з А, зв'язуються тонкої замкненою лінією, яка відповідає найкоротшому шляху об'їзду цих пунктів.
Для маршруту № 1
Рисунок 3 - Маршрут № 1
Для маршруту № 2
20
|
