2.3.2 Пункт d2

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

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

Определим длины прямых без посещения промежуточных узлов маршрутов в узел 16. Для каждого j-го узла j=5, 7, 9, 12, который соединен дугой с узлом 16 т.е. имеется прямой маршрут, длина кратчайшего маршрута принимается равной расстоянию между этим узлом и узлом 16; для остальных узлов значения принимаются равными бесконечности:

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

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

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

, i=1,2, …17, j=1,2, …17, i16, j16, .

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

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

Из узла 1	J
1-9-16	9	34	5	39	39
Из узла 2	j
2-9-16	9	44	5	49	49
Из узла 3	J
3-7-16	7	56	7	63	63
Из узла 6	J
6-12-16	12	45	3	48	48
Из узла 8	J
8-9-16	9	12	5	17
8-12-16	12	13	3	16	16
Из узла 9	j
9-12-16	12	32	3	35	35
Из узла 10	J
10-7-16	7	68	7	75
10-9-16	9	18	5	23	23
Из узла 12	j
12-9-16	12	32	5	37	37
Из узла 13	j
13-7-16	7	56	7	63
13-12-16	12	4	3	7	7

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

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

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

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

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

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

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

Из узла 1	J
1-8-12-16	8	8	16	24	24
Из узла 2	j
2-6-12-16	6	5	48	53
2-10-9-16	10	4	23	27	27
Из узла 3	J
3-10-9-16	10	11	23	34	34
Из узла 4	j
4-13-12-16	13	11	7	18	18
Из узла 7
7-13-12-16	13	56	7	63	63
7-10-9-16	10	68	23	91
Из узла 10	J
10-13-12-16	13	10	7	17	17
Из узла 11	j
11-10-9-16	10	2	23	25	25
Из узла 13	j
13-10-9-16	10	10	23	33
Из узла 14	j
14-10-9-16	10	12	23	35
14-13-12-16	13	9	7	16	16
Из узла 17	j
17-13-12-16	13	9	7	16	16

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

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

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

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

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

, i=1,2,…17, j=1,2,…17, i16, j16, ij.

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

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

Из узла 2	J
2-10-13-12-16	10		4		17	21	21
Из узла 3	j
3-11-10-9-16	11		23		25	48
3-10-13-12-16	10		11		17	28	28
Из узла 7	J
7-10-13-12-16	10		68		17	85	85
Из узла 9	j
9-10-13-12-16	10		18		17	35	35
Из узла 10		j
10-14-13-12-16		14		12	16	28	28
Из узла 11		j
11-14-13-12-16		14		8	16	24
11-10-13-12-16		10		2	17	19	19
11-17-13-12-16		17		9	16	25
Из узла 14		j
14-11-10-9-16		11		8	25	33
14-10-13-12-16		10		12	17	29	29
Из узла 15		j
15-11-10-9-16		11		11	25	36
15-14-13-12-16		14		11	16	27	27
Из узла 17		j
17-11-10-9-16		11		9	25	34	34

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

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

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

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

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

, i=1,2,…17, j=1,2,…17, i16, j16, ij.

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

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

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

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

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

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

J	k=0		k=1		K=2		k=3		k=4
	Маршрут	U0j	Маршрут	U1j	Маршрут	U2j	Маршрут	U3j	Маршрут		U4j
1			1-9-16	39	1-8-12-16	24	1-8-12-16	24	1-8-12-16		24
2			2-9-16	49	2-10-9-16	27	2-10-12-13-16	21	2-10-12-13-16		21
3			3-7-16	63	3-10-9-16	34	3-10-13-12-16	28	3-10-13-12-16		28
4			4-13-12-16	18	4-13-12-16	18	4-13-12-16	18
5	5-16	126	5-16	126	5-16	126	5-16	126	5-16		126
6			6-12-16	48	6-12-16	48	6-12-16	48	6-12-16		48
7	7-16	7	7--16	7	7-16	7	7-16	7	7-16		7
8			8-12-16	16	8-12-16	16	8-12-16	16	8-12-16		16
9	9-16	5	9-16	5	9-16	5	9-16	5	9-16		5
10	10-9-16	23	10-13-12-16	17	10-13-12-16	17	10-13-12-16	17	10-13-12-16		17
11	11-10-9-16	25	11-10-13-12-16	19	11-10-13-12-16	19
12	12-16	3	12-16	3	12-16	3	12-16	3	12-16		3
13	13-12-16	7	13-12-16	7	13-12-16	7	13-12-16	7
14	14-13-12-16	16	14-13-12-16	16	14-13-12-16	16
15	15-14-13-12-16	27	15-14-13-12-16	27
16
17	17-13-12-16	16	17-13-12-16	16	17-13-12-16	16

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

Из узла 1 пункт A1: 1-8-12-16 A1-E3-E7-D2; расстояние перевозки 24

Из узла 2 пункт A2: 2-10-13-12-16 A2-E5-Е8-E7-D2; расстояние перевозки 21

Из узла 3 пункт A3: 3-10-13-12-16 A3-E5-Е8-E7-D2; расстояние перевозки 28

Из узла 4 пункт A4: 4-13-12-16 A4-E8-Е7-D2; расстояние перевозки 18

Из узла 5 пункт A5: 5-16 A5-D2; расстояние перевозки 126