2.3.2 Пункт d1

Построим маршруты в узел 15 пункт D1 из узлов 1 пункт А1, 2 пункт А2, 3 пункт А3, 4 пункт А4, 5 пункт А5.

Приближение k = 0.

Определим длины прямых без посещения промежуточных узлов маршрутов в узел 15. Для каждого j-го узла j=1, 2, 3, 4, 11, 14, который соединен дугой с узлом 15 т.е. имеется прямой маршрут, длина кратчайшего маршрута принимается равной расстоянию между этим узлом и узлом 15; для остальных узлов значения принимаются равными бесконечности:

Полученные маршруты и значения их длин занесем в таблицу 17.

Приближение k = 1.

Определим длину возможного маршрута из i-го узла в узел 15 пункт D1, проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния от i-го узла до j-го узла и длины прямого маршрута из этого узла в узел 15 пункт D1: , i=1,2, …17, j=1,2, …17, i15, j15, .

В качестве длины кратчайшего маршрута из i-го узла в узел 15 принимается минимальное из возможных значений: .

Таблица 13 — Маршруты в узел 15 с числом промежуточных узлов не более 1

Из узла 3	J
3-11-15	11	23	11	34	34
Из узла 10	j
10-11-15	11	2	11	13	13
10-14-15	14	12	11	23
Из узла 11	J
11-14-15	14	8	11	19	19
Из узла 13	j
13-14-15	14	9	11	20	20
Из узла 14	j
14-11-15	11	8	11	19	19
Из узла 17	j
17-11-15	11	9	11	20	20

Полученные кратчайшие маршруты из каждого узла в узел 15 и значения их длин

выделены голубой заливкой занесем в таблицу 17.

Приближение k = 2.

Определим длину возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более двух, как сумму расстояния от i-го узла до j-го узла и длины

маршрута из j-го узла в узел 15 с числом узлов не более одного: , i=1,2,…17, j=1,2,…17, i15, j15, ij.

В качестве длины кратчайшего маршрута из i-го узла в узел 15 принимается минимальное значение из возможных: .

Таблица 14 — Маршруты в узел 15 с числом промежуточных узлов не более 2

Из узла 2	J
2-10-11-15	10	4	13	17	17
Из узла 4	j
4-13-14-15	13	11	20	31	31
Из узла 7	J
7-10-11-15	10	68	13	81
7-13-14-15	13	56	20	76	76
Из узла 9	j
9-10-11-15	10	18	13	31	31
Из узла 10	j
17-11-15	11	9	11	20	20
Из узла 12	J
12-13-14-15	13	4	20	24	24
Из узла 13	j
13-10-11-15	10	10	13	23	23
Из узла 14	j
14-10-11-15	10	12	13	25	25
Из узла 17	j
17-13-14-15	13	9	20	29	29

Полученные кратчайшие маршруты из каждого узла в узел 15 и значения их длин

выделено голубой заливкой занесем в таблицу 17.

Приближение k=3.

Определим длину возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более трех как сумму расстояния от i-го узла до j-го узла и длины

маршрута из j-го узла в узел 15 с числом узлов не более двух:

, i=1,2,…17, j=1,2,…17, i15, j15, ij.

В качестве длины кратчайшего маршрута из i-го узла в узел 15 принимается минимальное из возможных значение: .

Таблица 15 — Маршруты в узел 15 с числом промежуточных узлов не более 3

Из узла 1	J
1-9-10-11-15	9	34	31	65	65
Из узла 2	j
2-9-10-11-15	9	44	31	75	75
Из узла 3	J
3-7-13-14-15	7	56	76	132	132
Из узла 6	j
6-12-13-14-15	12	45	24	69	69
Из узла 8	j
8-9-10-11-15	9	12	31	43	43
8-12-13-14-15	12	13	24	37	37
Из узла 9	j
9-12-13-14-15	12	32	24	56	56
Из узла 10	j
10-7-13-14-15	7	68	76	144	144
Из узла 12	j
12-9-10-11-15	9	32	31	63	63
Из узла 13	j
13-7-13-14-15	7	56	76	132
Из узла 16	J
16-7-13-14-15	7	4	76	80
16-9-10-11-15	9	5	31	36
16-12-13-14-15	12	3	24	27	27

Полученные кратчайшие маршруты из каждого узла в узел 15 и значения их длин

выделено голубой заливкой занесем в таблицу 17.

Приближение k=4

Определим длину возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более четырех как сумму расстояния от i-го узла до j-го узла и длины

маршрута из j-го узла в узел 15 с числом узлов не более трех:

, i=1,2,…17, j=1,2,…17, i15, j15, ij.

В качестве длины кратчайшего маршрута из i-го узла в узел 15 принимается минимальное из возможных значение:

Таблица 16 — Маршруты в узел 15 с числом промежуточных узлов не более 4

Из узла 1	J
1-8-12-13-14-15	8	8	37	45	45
Из узла 7	j
7-16-12-13-14-15	16	4	27	31	31
Из узла 9	J
9-16-12-13-14-15	16	5	27	32	32
9-8-12-13-14-15	8	12	37	49

Полученные кратчайшие маршруты из каждого узла в узел 15 и значения их длин

выделено голубой заливкой занесем в таблицу 17.

Приближение k=5

Определим длину возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более пяти как сумму расстояния от i-го узла до j-го узла и длины

маршрута из j-го узла в узел 15 с числом узлов не более четырех:

, i=1,2,…17, j=1,2,…17, i15, j15, ij.

В качестве длины кратчайшего маршрута из i-го узла в узел 15 принимается минимальное из возможных значение:

Результаты расчетов показывают, что длины кратчайших маршрутов

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

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

В таблице 17 для каждого приближения приведены полученные кратчайшие маршруты в узел 15 и их длины.

Искомые кратчайшие маршруты в узел 15 пункт D1:

Из узла 1 пункт A1: 1-15 A1 — D1; расстояние перевозки 45

Из узла 2 пункт A2: 2-15 A2 — D1; расстояние перевозки 17

Из узла 3 пункт A3: 3-15 A3 – D1; расстояние перевозки 24

Из узла 4 пункт A4: 4-15 A4 – D1; расстояние перевозки 31

Из узла 5 пункт A5: 5-15 A5-D1; расстояние перевозки 150

Таблица 17 — Кратчайшие маршруты в узел 15

J	k=0		k=1		K=2		k=3		k=4		k=5
	Маршрут	U0j	Маршрут	U1j	Маршрут	U2j	Маршрут	U3j	Маршрут	U4j	Маршрут		U5j
1	1-15	45	1-15	45	1-15	45	1-15	45	1-15	45	1-15		45
2	2-15	17	2-15	17	2-15	17	2-15	17	2-15	17	2-15		17
3	3-15	24	3-15	24	3-15	24	3-15	24	3-15	24	3-15		24
4	4-15	31	4-15	31	4-15	31	4-15	31	4-15	31	4-15		31
5	5-15	150	5-15	150	5-15	150	5-15	150	5-15	150	5-15		150
6	6-12-13-14-15	69	6-12-13-14-15	69	6-12-13-14-15	69	6-12-13-14-15	69
7	7-13-14-15	76	7-13-14-15	76	7-16-12-13-114-15	76	7-16-12-13-114-15	76
8	8-12-13-14-15	37	8-12-13-14-15	37	8-12-13-14-15	37
9	9-10-11-15	31	9-10-11-15	31	9-10-11-15	31	9-10-11-15	31
10	10-11-15	13	10-11-15	13	10-11-15	13	10-11-15	13	10-11-15	13
11	11-15	11	11-15	11	11-15	11	11-15	11	11-15	11	11-15		11
12	12-13-14-15	24	12-13-14-15	24	12-13-14-15	24	12-13-14-15	24
13	13-14-15	20	13-14-15	20	13-14-15	20	13-14-15	20	13-14-15	20
14	14-15	11	14-15	11	14-15	11	14-15	11	14-15	11	14-15		11
15
16	16-12-13-14-15	27	16-12-13-14-15	27	16-12-13-14-15	27	16-12-13-14-15	27
17	17-11-15	20	17-11-15	20	17-11-15	20	17-11-15	20	17-11-15	20

В таблице 18 приведены расстояния между пунктами отправления и пунктами взаимодействия.

Таблица 18 — Расстояния между пунктами отправления и взаимодействия

Расстояние, км		Пункты взаимодействия
		D1	D2		D3
Пункты отправления	А1	45	24		34
	А2	17	21		15
	А3	24	28		22
	A4	31	18		20
	A5	150	126		110