2.3.1 Пункт d3

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

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

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

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

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

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

, i=1,2, …16, j=1,2, …16, .

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

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

Из узла 3	j
3- 11-17	11	23	9	32	32
Из узла 7	j
7- 13-17	13	56	9	65	65
Из узла 10	j
10- 13- 17	13	10	9	19
10- 11- 17	11	2	9	11	11
Из узла 12	J
12- 13-17	13	4	9	13	13
Из узла 14	j
14- 13-17	13	9	9	18
14- 11 -17	11	8	9	17	17
Из узла 15	j
15- 11-17	11	11	9	20	20

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

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

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

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

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

, i=1,2,…16, j=1,2,…16, ij.

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

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

Из узла 2	j
2- 10-11-17	10	4	11	15	15
Из узла 3	J
3-10-11-17	10	11	11	22	22
Из узла 6	j
6-12-13-17	12	45	65	110	110
Из узла 7	J
7-10-11-17	10	68	11	79	79
Из узла 8	j
8-12-13-17	12	13	13	26	26
Из узла 9	J
9-10-11-17	10	18	11	29	29
9-12-13-17	12	32	13	45
Из узла 10	j
10-14-11-17	14	12	17	29	29
10-7-13-17	7	68	65	133
Из узла 14	J
14-10-11-17	10	12	11	23	23
Из узла 15	J
15-14-11-17	14	11	17	28	28
Из узла 16	J
16-12-13-17	12	3	13	16	16

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

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

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

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

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

i=1,2,…16, j=1,2,…16, ij.

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

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

Из узла 1	J
1-9-10-11-17	9	34	29	63
1-8-12-13-17	8	8	26	34	34
Из узла 2	j
2-6-12-13-17	6	5	110	115
2-9-10-11-17	9	44	29	73
2-10-14-11-17	10	4	29	33	33
Из узла 3	J
3-7-10-11-17	7	56	79	135
3-10-14-11-17	10	11	29	40	40
Из узла 7	J
7-10-14-11-17	10	68	29	97	97
Из узла 8	J
8-9-10-11-17	9	12	29	41	41
Из узла 9	J
9-8-12-13-17	8	12	26	38	38
9-10-14-11-17	10	18	29	47
Из узла 12	J
12-9-10-11-17	9	32	29	61	61
Из узла 13	J
13-7-10-11-17	7	56	79	135	135
Из узла 16	J
16-9-10-11-17	9	5	29	34	34

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

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

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

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

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

, i=1,2,…16, j=1,2,…16, ij.

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

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

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

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

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

Таблица 8.

J	k=0		k=1		K=2		k=3		k=4
	Маршрут	U^0j	Маршрут	U^1j	Маршрут	U^2j	Маршрут	U^3j	Маршрут		U^4j
1							1-8-12-13-17	34	1-8-12-13-17		34
2					2-10-11-17	15	2-10-17-17	15	2-10-11-17		15
3			3-11-17	32	3-10-11-17	22	3-10-11-17	22	3-10-11-17		22
4			4-13-17	20	4-13-17	20	4-13-17	20	4-13-17		20
5	5-17	110	5-17	110	5-17	110	5-17	110	5-17		110
6					6-12-13-17	110	6-12-13-17	110	6-12-13-17		110
7			7-13-17	65	7-13-16	65	7-13-16	65	7-13-16		65
8					8-12-13-17	26	8-12-13-17	26	8-12-13-17		26
9					9-10-11-17	29	9-10-11-17	29	9-10-11-17		29
10			10-11-17	11	10-11-17	11	10-11-17	11	10-11-17		11
11	11-17	9	11-17	9	11-17	9	11-17	9	11-17		9
12			12-13-17	13	12-13-17	13	12-13-17	13	12-13-17		13
13	13-17	9	13-17	9	13-17	9	13-17	9	13-17		9
14			14-11-17	17	14-11-17	17	14-11-17	17	14-11-17		17
15			15-11-17	20	15-11-17	20	15-11-17	20	15-11-17		20
16					16-12-13-17	16	16-12-13-17	16	16-12-13-17		16
17

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

Из узла 1 пункт A1: 1-8-12-13-17 A1-E3-E7-E8-D3; расстояние перевозки 34

Из узла 2 пункт A2: 2-10-11-17 A2-E5-E6-D3; расстояние перевозки 15

Из узла 3 пункт A3: 3-10-11-17 A3-E5-E6 -D3; расстояние перевозки 22

Из узла 4 пункт A4: 4-13-17 A4-E8-D3; расстояние перевозки 20

Из узла 5 пункт A5: 5-17 A5-D3; расстояние перевозки 110