2 Определение кратчайших расстояний и кратчайших путей следования

На основании исходных данных и построенной транспортной сети найдем матрицу кратчайших расстояний между грузообразующими и грузопоглащающими пунктами транспортной сети (таблица 2.1) и матрицу кратчайших путей следования между ними (таблица 2.2). Для этого рассчитаем значения потенциалов конечных пунктах j каждого звена по следующей формуле:

u_j(i) = v_i + l_ij , (1.1)

где u_j(i) – потенциал конечного пункта j-го звена i-j;

l_ij – длина звена i-j.

Начальному пункту Б1 присваиваем потенциал v_i = 0.

1.v₁ = 0;

2.u₉₍₁₎ = 0+570 = 570; min;

u₇₍₁₎ = 0+600 = 600;

3.u₇₍₁₎ = 600; min;

u₆₍₉₎ = 570+930 = 1500;

u₁₀₍₉₎ = 570+840 = 1410;

u₁₄₍₉₎ = 570+495 = 1065;

4.u₆₍₉₎ = 570+930 = 1500;

u₁₀₍₉₎ =570+840 = 1410;

u₁₄₍₉₎ = 570+495 = 1065; min;

u₁₃₍₇₎ = 600+735 =1335;

u₈₍₇₎ = 600+480 = 1080;

5.u₆₍₉₎ = 570+930 = 1500;

u₁₀₍₉₎ = 570+840 = 1410;

u₁₃₍₇₎ = 600+735 =1335;

u₈₍₇₎ = 600+480 = 1080; min;

u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₁₍₁₄₎ = 1065+450 =1515;

u₁₃₍₁₄₎ = 1065+210 = 1275;

6.u₆₍₉₎ = 570+930 = 1500;

u₁₀₍₉₎ = 570+840 = 1410;

u₁₃₍₇₎ = 600+735 =1335;

u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₁₍₁₄₎ = 1065+450 =1515;

u₁₃₍₁₄₎ = 1065+210 = 1275; min;

u₁₂₍₈₎ = 1080+510 = 1590;

7.u₆₍₉₎ = 570+930 = 1500;

u₁₀₍₉₎ = 570+840 = 1410;

u₁₃₍₇₎ = 600+735 =1335; min;

u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₁₍₁₄₎ = 1065+450 =1515;

u₁₂₍₈₎ = 1080+510 = 1590;

u₇₍₁₃₎ = 1275+735 = 2010;

u₁₂₍₁₃₎ = 1275+390 = 1665;

8.u₆₍₉₎ = 570+930 = 1500;

u₁₀₍₉₎ = 570+840 = 1410; min;

u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₁₍₁₄₎ = 1065+450 =1515;

u₁₂₍₁₃₎ = 1275+390 = 1665;

u₁₂₍₈₎ = 1080+510 = 1590;

9.u₆₍₉₎ = 570+930 = 1500; min;

u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₁₍₁₄₎ = 1065+450 =1515;

u₁₂₍₈₎ = 1080+510 = 1590;

u₁₂₍₁₃₎ = 1275+390 = 1665;

u₅₍₁₀₎ = 1410+825 = 2235;

u₆₍₁₀₎ = 1410+360 = 1770;

10.u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₁₍₁₄₎ = 1065+450 =1515; min;

u₁₂₍₈₎ = 1080+510 = 1590;

u₁₂₍₁₃₎ = 1275+390 = 1665;

u₅₍₁₀₎ = 1410+825 = 2235;

u₆₍₁₀₎ = 1410+360 = 1770;

u₁₀₍₆₎ = 1500+360 = 1860;

11.u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₂₍₈₎ = 1080+510 = 1590; min;

u₁₂₍₁₃₎ = 1275+390 = 1665;

u₅₍₁₀₎ = 1410+825 = 2235;

u₆₍₁₀₎ = 1410+360 = 1770;

u₁₀₍₆₎ = 1500+360 = 1860;

u₄₍₁₁₎ = 1515+705 = 2215;

u₁₂₍₁₁₎ = 1515+480 = 1995;

u₃₍₁₁₎ = 1515+705 = 2215;

u₂₍₁₁₎ = 1515+705 = 2215;

12.u₅₍₁₄₎ = 1065+1230 = 2295;

u₁₂₍₁₃₎ = 1275+390 = 1665; min;

u₅₍₁₀₎ = 1410+825 = 2235;

u₆₍₁₀₎ = 1410+360 = 1770;

u₁₀₍₆₎ = 1500+360 = 1860;

u₄₍₁₁₎ = 1515+705 = 2215;

u₁₂₍₁₁₎ = 1515+480 = 1995;

u₃₍₁₁₎ = 1515+705 = 2215;

u₁₁₍₁₂₎ = 1590+480 = 2070;

13.u₅₍₁₄₎ = 1065+1230 = 2295;

u₅₍₁₀₎ = 1410+825 = 2235;

u₆₍₁₀₎ = 1410+360 = 1770; min;

u₁₀₍₆₎ = 1500+360 = 1860;

u₄₍₁₁₎ = 1515+705 = 2215;

u₁₂₍₁₁₎ = 1515+480 = 1995;

u₃₍₁₁₎ = 1515+705 = 2215;

u₂₍₁₁₎ = 1515+705 = 2215;

u₁₁₍₁₂₎ = 1590+480 = 2070;

14. u₅₍₁₄₎ = 1065+1230 = 2295;

u₅₍₁₀₎ = 1410+825 = 2235;

u₄₍₁₁₎ = 1515+705 = 2215;

u₁₂₍₁₁₎ = 1515+480 = 1995; min;

u₃₍₁₁₎ = 1515+705 = 2215;

u₂₍₁₁₎ = 1515+705 = 2215;

u₁₁₍₁₂₎ = 1590+480 = 2070;

15. u₅₍₁₄₎ = 1065+1230 = 2295;

u₅₍₁₀₎ = 1410+825 = 2235;

u₄₍₁₁₎ = 1515+705 = 2215; min;

u₃₍₁₁₎ = 1515+705 = 2215; min;

u₂₍₁₁₎ = 1515+705 = 2215;min;

u₁₁₍₁₂₎ = 1590+480 = 2070;

16. u₅₍₁₄₎ = 1065+1230 = 2295;

u₅₍₁₀₎ = 1410+825 = 2235;

u₁₁₍₁₂₎ = 1590+480 = 2070; min;

17. u₅₍₁₄₎ = 1065+1230 = 2295;

u₅₍₁₀₎ = 1410+825 = 2235;min;

18. u₅₍₁₄₎ = 1065+1230 = 2295;

В результате выполненных операция величина потенциалов у вершин показывает кратчайшие расстояния от выбранного начального пункта до каждой вершины, а звенья со входящими друг в друга стрелками образуют кратчайшие пути движения от начального пункта до всех остальных. Если два пункта сети соединены такими путями, то кратчайшее расстояние между ними равно разности потенциалов у их вершин.

Принимая за начальный последовательно каждый из пунктов транспортной сети и выполняя действия по вышеописанному методу, получаем таблицу кратчайших расстояний между всеми пунктами транспортной сети.

Таблица 2.1 - Матрица кратчайших расстояний между грузообразующими и грузопоглащающими узлами транспортной сети, м

Из/В	Б1	М2	М3	М4	М5	М6	М7	М8
Б1	-	2625	2220	2220	2235	1500	600	1080
М2	2625	-	1815	1815	2790	2985	2506	2100
М3	2220	1815	-	1410	2385	2580	2100	1695
М4	2220	1815	1410	-	1140	2325	2100	1695
М5	2235	2790	2385	1140	-	1185	2175	2340
М6	1500	2985	2580	2325	1185	-	2100	2580
М7	600	2505	2100	2100	2175	2100	-	480
М8	1080	2100	1695	1695	2340	2580	480	-

Получаем таблицу кратчайших путей следования между всеми пунктами транспортной сети.

Таблица 2.2 – Матрица кратчайших путей следования между грузообразующими и грузопоглащающими узлами транспортной сети

Из/В	Б1	М2	М3	М4	М5	М6	М7	М8
Б1	-	Б1-9-14-11-М2	Б1-9-14-11-М3	Б1-9-14-11-М4	Б1-9-10-М5	Б1-9-М6	Б1-М7	Б1-М7-М8
М2		-	М2-11-М3	М2-11-М4	М2-11-14-М5	М2-11-14-9-М6	М2-11-14-14-13-М7	М2-11-12-М8
М3			-	М3-11-М4	М3-11-14-М5	М3-11-14-9-М6	М3-11-14-13- М7	М3-11-12-М8
М4				-	М4-М5	М4-М5-10-М6	М4-11-14-13-М7	М4-11-12-М8
М5					-	М5-10-М6	М5-14-13-М7	М5-14-13-12-М8
М6						-	М6-9-Б1-М7	М6-9-Б1-М7-М8
М7							-	М7-М8
М8								-