2. Визначення найкоротших відстаней між пунктами транспортної мережі

1. На підставі вихідних даних, наведених на рисунку 2.1, розрахувати найкоротші відстані від кожного пункту мережі до всіх інших методом потенціалів.

2. За даними отриманих розрахунків побудувати матрицю найкоротших відстаней.

Рисунок 2.1 – Граф транспортної мережі

Транспортна мережа надається у вигляді графа. Довжини ланок графу, тобто ділянок транспортної мережі, розраховуються шляхом додавання першої або другої цифри залікової книжки: i – передостання цифра номеру залікової книжки, j – остання цифра номеру залікової книжки.

Задача визначення найкоротших відстаней між пунктами транспортної мережі має досить велике значення, оскільки вирішується з метою найбільш раціонального використання рухомого складу та скорочення транспортних витрат шляхом мінімізації загального пробігу та часу доставки вантажів або поїздки пасажирів.

Транспортна мережа найбільш часто представляється у вигляді графа (рисунок 2.1), в якому вершини являють собою перехрестя, вантажо- або пасажироутворюючі чи поглинаючі пункти та ін., а ланки – ділянки доріг які поєднують згадані вершини.

Для визначення найкоротших відстаней застосовуються математичні методи, які дозволяють робити розрахунки як вручну, так і на ЕОМ. Одним з найбільш поширених методів є метод потенціалів.

При використанні даного методу задача визначення найкоротших відстаней вирішується наступним чином:

1 етап – вершина графу, від котрої необхідно визначити найкоротші відстані, обирається як початкова і їй присвоюється потенціал v_i=0;

2 етап – визначаються усі ланки, початкові вершини i котрих мають потенціали v_i, а кінцеві j – не мають. Значення потенціалу кінцевих вершин визначаються за наступною формулою:

(2.1)

де – шуканий потенціал кінцевої вершини;

– відомий потенціал початкової вершини;

– довжина ланки, яка поєднує вершини i та j.

Із усіх отриманих потенціалів на всіх етапах розрахунку обирається найменший, його значення привласнюється відповідній кінцевій вершині та записується на графі у квадрат поряд з нею. Ланка (i–j) позначається стрілкою. Розрахунок потенціалу обраної кінцевої вершини закреслюється.

Етап 2 повторюється до тих пір, поки усім вершинам графу не будуть привласнені потенціали. Порівнюються усі розраховані значення потенціалів, в тому числі отримані на усіх попередніх етапах розрахунку.

Коли визначені потенціали усіх вершин, задача вважається розв’язаною.

Значення потенціалів відповідних вершин являють собою найкоротшу відстань від обраного початкового пункту до інших. Ланки зі стрілками утворюють найкоротший маршрут руху від початкового пункту до усіх інших.

Приймаючи за початкову вершину послідовно кожну з вершин графа та виконуючи розрахунки за описаними вище етапами, можна отримати матрицю найкоротших відстаней між пунктами мережі.

Результати треба представити у вигляді таблиці 2.1 (приклад для варіанта i = 0, j = 0).

Таблиці 2.1 – Найкоротші відстані між транспортними районами, км

Номер транспортного району	1	2	3	4	5	6	7	8	9	10
1	-	0,9	0,9	1,5	2,4	1,9	1,7	2,6	2,2	2,0
2	0,9	-	0,7	0,6	1,5	1,0	0,8	1,7	1,3	1,8
3	0,9	0,7	-	0,7	2,0	1,2	0,9	1,9	1,4	1,1
4	1,5	0,6	0,7	-	1,3	0,5	2,0	1,2	0,7	1,2
5	2,4	1,5	2,0	1,3	-	0,8	1,5	1,1	2,0	2,5
6	1,9	1,0	1,2	0,5	0,8	-	0,7	0,7	1,2	1,7
7	1,7	0,8	0,9	0,2	1,5	0,7	-	1,2	0,5	1,0
8	2,6	1,7	1,9	1,2	1,1	0,7	1,2	-	1,4	2,1
9	2,2	1,3	1,4	0,7	2,0	1,2	0,5	1,4	-	0,7
10	2,0	1,8	1,1	1,2	2,5	1,7	1,0	2,1	0,7	-