Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Самарский Государственный Технический Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

сохранить!!!!.doc

Скачиваний:

Добавлен:

01.05.2025

Размер:

962 Кб

Скачать

☆

<<< < Предыдущая 1 2 34 / 74 5 6 7 > Следующая >>>

2.3.2 Пункт d2

Построим маршруты в узел 1 (пункт D₂) из узлов 1 (пункт A₁), 2 (пункт A₂), 3 (пункт A₃); 4 (пункт A₄).

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

Определим длины прямых (без посещения промежуточных узлов) маршрутов в узел 15. Для каждого j-го узла (j = 6;8;11), который соединен дугой с узлом 15 (т.е. имеется прямой маршрут), длина U⁰_j кратчайшего маршрута принимается равной расстоянию L_j_-15 между этим узлом и узлом 15; для остальных узлов значения U⁰_j принимаются равными бесконечности:

U⁰₆= L_6-15 = 10;

U⁰₈ = L_8-15 = 9;

U⁰₁₁ = L_11-15 = 3.

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

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

Определим длину L¹_i_-_j возможного маршрута из i-го узла в узел 15 (пункт D₂), проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния L_i_-_j от i-го узла до j-го узла и длины U⁰_j прямого маршрута из этого узла в узел 15 (пункт D₂):

L¹_i-j = L_i-j + U⁰_j , i = 1, 2, ... 16, j = 1, 2, ... 16, i ≠ 15, j ≠ 15, j ≠ i.

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

U¹_i = min {L¹_i_-_j}.

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

Из узла 2	j	L₂_-_j	U⁰_j	L¹₂_-_j	U¹₂
2-8-15	8	34	3	37	37
Из узла 3	j	L₃_-_j	U⁰_j	L¹₃_-_j	U¹₃
3-6-15	6	56	10	66	66
Из узла 5	j	L₅_-_j	U⁰_j	L¹₅_-_j	U¹₅
5-11-15	11	31	9	40	40
Из узла 7	j	L₇_-_j	U⁰_j	L¹₇_-_j	U¹₇
7-11-15	11	3	9	12	12
7-8-15	8	12	3	15	15
Из узла 8	j	L₈_-_j	U⁰_j	L¹₈_-_j	U¹₈
8-11-15	11	18	9	27	27
Из узла 9	j	L₉_-_j	U⁰_j	L¹₉_-_j	U¹₉
9-6-15	6	68	10	78	78
9-8-15	8	18	3	21	21
Из узла 11	j	L₁₁_-_j	U⁰_j	L¹₁₁_-_j	U¹₁₁
11-8-15	8	18	3	21	21
Из узла 12	j	L₁₂_-_j	U⁰_j	L¹₁₂_-_j	U¹₁₂
12-11-15	11	4	9	13	13
12-6-15	6	42	10	52	52

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

Определим длину L²_i_-_j возможного маршрута из i-го узла в узел 15 (пункт D₂), проходящего через j-й узел, с числом промежуточных узлов не более двух как сумму расстояния L_i_-_j от i-го узла до j-го узла и длины U¹_j маршрута из этого узла в узел 15 (пункт D₂) с числом узлов не более одного:

L²_i-j = L_i-j + U¹_j , i = 1, 2, ... 16, j = 1, 2, ... 16, i ≠ 15, j ≠ 15, j ≠ i.

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

U²_i = min {L²_i_-_j}.

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

Из узла 1	j	L_1-_j	U¹_j	L²_1-_j	U²₁
1-7-11-15	7	12	12	24	24
1-7-8-15	7	12	15	27	27
Из узла 2	j	L₂_-_j	U¹_j	L²₂_-_j	U²₂
2-5-11-15	5	15	40	55	55
2-8-11-15	8	34	27	61	61
Из узла 3	j	L₃_-_j	U¹_j	L²₃_-_j	U²₃
3-9-6-15	9	26	78	104	104
3-9-8-15	9	26	21	47	47
Из узла 4	j	L₄_-_j	U¹_j	L²₄_-_j	U²₄
4-12-11-15	12	8	13	21	21
4-12-6-15	12	8	52	60	60
Из узла 5	j	L₅_-_j	U¹_j	L²₅_-_j	U²₅
5-2-8-15	2	15	37	52	52
5-11-8-15	11	31	21	52	52
Из узла	j	L₆_-_j	U¹_j	L²₆_-_j	U²₆
6-9-8-15	9	68	21	89	89
6-12-11-15	12	42	13	55	55
Из узла 7	j	L₇_-_j	U¹_j	L²₇_-_j	U²₇
7-11-8-15	11	3	21	25	25
7-8-11-15	8	12	27	39	39
Из узла 8	j	L₈_-_j	U¹_j	L²₈_-_j	U²₈
8-7-11-15	7	12	12	24	24
8-9-6-15	9	18	78	96	96
Из узла 9	j	L₉_-_j	U¹_j	L²₉_-_j	U²₉
9-8-11-15	8	18	27	45	45
9-12-11-15	12	5	13	18	18
9-3-6-15	3	26	66	92	92
Из узла 10	j	L₁₀_-_j	U¹_j	L²₁₀_-_j	U²₁₀
10-9-6-15	9	2	78	80	80
10-12-11-15	12	5	13	18	18
10-3-6-15	3	6	66	72	72
10-9-8-15	9	2	21	23	23
Из узла 11	j	L₁₁_-_j	U¹_j	L²₁₁_-_j	U²₁₁
11-7-8-15	7	3	15	18	18
11-12-6-15	12	4	52	56	56
Из узла 12	j	L₁₂_-_j	U¹_j	L²₁₂_-_j	U²₁₂
12-11-8-15	11	4	21	25	25
12-9-8-15	9	5	21	26	26
Из узла 13	j	L₁₃_-_j	U¹_j	L²₁₃_-_j	U²₁₃
13-12-11-15	12	9	13	22	22
13-9-8-15	9	4	21	25	25
13-12-6-15	12	9	52	61	61
Из узла 16	j	L₁₆_-_j	U¹_j	L²₁₆_-_j	U²₁₆
16-12-11-15	12	9	13	22	22
16-12-6-15	12	9	52	61	61

Получены кратчайшие маршруты из каждого узла в узел 15 и значения их длин U²_j (выделены заливкой) занесем в таблицу 11.

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

Определим длину L³_i_-_j возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более трех как сумму расстояния L_i_-_j от i-го узла до j-го узла и длины U²_j маршрута из этого узла в узел 15 с числом узлов не более одного:

L³_i-j = L_i-j + U²_j , i = 1, 2, ... 16, j = 1, 2, ... 16, i ≠ 15, j ≠ 15, j ≠ i.

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

U³_i = min {L³_i_-_j}.

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

Из узла 1	j	L_1-_j	U²_j	L³_1-_j	U³₁
1-7-8-11-15	7	12	39	51	51
1-7-11-8-15	7	12	24	36	36
Из узла 2	j	L₂_-_j	U²_j	L³₂_-_j	U³₂
2-8-7-11-15	8	34	24	58	58
2-5-11-8-15	5	15	52	67	67
2-9-8-11-15	9	6	45	51	51
Из узла 3	j	L₂_-_j	U²_j	L³₂_-_j	U³₂
3-6-12-11-15	6	56	55	111	111
3-9-8-11-15	9	26	45	71	71
3-10-9-6-15	10	6	80	86	86
3-10-9-8-15	10	6	23	29	29
Из узла 4	j	L₄_-_j	U²_j	L³₄_-_j	U³₄
4-12-9-6-15	12	8	83	91	91
4-12-9-8-15	12	8	26	34	34
4-12-11-8-15	12	8	25	33	33
Из узла 5	j	L₅_-_j	U²_j	L³₅_-_j	U³₅
5-11-7-8-15	11	31	18	49	49
5-2-8-11-15	2	15	61	76	76
5-2-9-8-15	2	15	27	42	42
5-2-9-6-15	2	15	84	99	99
Из узла 6	j	L₆_-_j	U²_j	L³₆_-_j	U³₆
6-3-9-8-15	3	56	47	103	103
6-12-11-8-15	12	42	25	67	67
6-9-8-11-15	9	68	45	113	113
6-9-12-11-15	9	68	18	86	86
Из узла 7	j	L₇_-_j	U²_j	L³₇_-_j	U³₇
7-8-9-6-15	8	12	96	108	108
7-11-12-6-15	11	3	56	59	59
Из узла 8	j	L₈_-_j	U²_j	L³₈_-_j	U³₈
8-2-5-11-15	2	34	55	89	89
8-9-12-6-15	9	18	57	75	75
8-9-3-6-15	9	18	92	110	110
8-2-9-6-15	2	34	84	118	118
Из узла 9	j	L₉_-_j	U²_j	L³₉_-_j	U³₉
9-8-7-11-15	8	18	24	42	42
9-13-12-11-15	13	4	22	26	26
9-6-12-11-15	6	68	55	123	123
9-2-5-11-15	2	6	55	61	61
9-13-12-6-15	13	4	61	65	65
Из узла 10	j	L₁₀_-_j	U²_j	L³₁₀_-_j	U³₁₀
10-9-8-11-15	9	2	45	47	47
10-9-12-11-15	9	2	18	20	20
10-9-12-6-15	9	2	57	59	59
10-13-12-11-15	13	6	22	28	28
10-13-12-6-15	13	6	61	67	67
10-9-3-6-15	9	2	92	94	94
Из узла 11	j	L₁₁_-_j	U²_j	L³₁₁_-_j	U³₁₁
11-5-2-8-15	5	31	52	83	83
11-12-9-8-15	12	4	26	30	30
11-8-9-6-15	8	18	96	114	114
Из узла 12	j	L₁₂_-_j	U²_j	L³₁₂_-_j	U³₁₂
12-9-3-6-15	9	5	92	97	97
12-13-9-6-15	13	9	82	91	91
12-10-9-8-15	10	5	23	28	28
Из узла 13	j	L₁₃_-_j	U²_j	L³₁₃_-_j	U³₁₃
13-9-8-11-15	9	4	45	49	49
13-10-3-6-15	10	6	72	78	78
13-10-9-6-15	10	6	80	86	86
13-9-12-11-15	9	4	18	24	24
13-9-12-6-15	9	4	57	61	61
Из узла 14	j	L₁₄_-_j	U²_j	L³₁₄_-_j	U³₁₄
14-13-12-11-15	13	11	22	33	33
14-10-12-11-15	10	3	18	21	21
14-13-12-6-15	13	11	61	72	72
14-10-12-6-15	10	3	57	60	60
14-13-9-6-15	13	11	82	93	93
14-10-9-8-15	10	3	23	26	26
14-10-9-6-15	10	3	80	83	83
Из узла 16	j	L₁₆_-_j	U²_j	L³₁₆_-_j	U³₁₆
16-10-12-11-15	10	5	18	23	23
16-10-9-8-15	10	5	23	28	28
16-10-3-6-15	10	5	72	77	77
16-10-9-6-15	10	5	80	85	85
16-10-12-6-15	10	5	57	62	62

Получены кратчайшие маршруты из каждого узла в узел 15 и значения их длин U³_j (выделены заливкой) занесем в таблицу 11.

5). Приближение k=4

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

L⁴_i-j = L_i-j + U³_j , i = 1, 2, ... 16, j = 1, 2, ... 16, i ≠ 15, j ≠ 15, j ≠ i.

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

U⁴_i = min {L⁴_i_-_j}.

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

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

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

j	k=0		k=1		k=2		k=3		k=4
j	Маршрут	U⁰_j	Маршрут	U¹_j	Маршрут	U²_j	Маршрут	U³_j	Маршрут	U⁴_j
1					1-7-11-15	24	1-7-11-8-15	36	1-7-11-8-15	36
2			2-8-15	37	2-5-11-15	55	2-9-8-11-15	51	2-9-8-11-15	51
3			3-6-15	66	3-9-8-15	47	3-10-9-8-15	29	3-10-9-8-15	29
4					4-12-11-15	21	4-12-11-8-15	33	4-12-11-8-15	33
5			5-11-15	40	5-2-8-15	52	5-2-9-8-15	42	5-2-9-8-15	42
6	6-15	10			6-12-11-15	55	6-12-11-8-15	67	6-12-11-8-15	67
7			7-11-15	12	7-11-8-15	25	7-11-12-6-15	59	7-11-12-6-15	59
8	8-15	9	8-11-15	27	8-7-11-15	24	8-9-12-6-15	75	8-9-12-6-15	75
9			9-8-15	21	9-12-11-15	18	9-13-12-11-15	26	9-13-12-11-15	26
10					10-12-11-15	18	10-9-12-11-15	20	10-9-12-11-15	20
11	11-15	3	11-8-15	21	11-7-8-15	18	11-12-9-8-15	30	11-12-9-8-15	30
12			12-11-15	13	12-11-8-15	25	12-10-9-8-15	28	12-10-9-8-15	28
13					13-12-11-15	22	13-9-12-11-15	24	13-9-12-11-15	24
14							14-10-12-11-15	21	14-10-12-11-15	21
15					16-12-11-15	22	16-10-12-11-15	23	16-10-12-11-15	23

Искомые кратчайшие маршруты в узел 15 (пункт D₂)

из узла 1 (пункт А₁): 1-7-11-15 (А₁-Е₃-Е₇-D₂); расстояние перевозки 24;

из узла 2 (пункт А₂): 2-8-15 (A₂-E₄-D₂); расстояние перевозки 37;

из узла 3 (пункт А₃): 3-10-9-8-15 (A₃-E₆-E₅-E₄-D₂); расстояние перевозки 29;

из узла 4 (пункт А₄): 4-12-11-15 (A₄-E₈-E₇-D₂); расстояние перевозки 21.

Таблица 12 – Расстояния между пунктами

отправления и взаимодействия

Расстояние, км		Пункты взаимодействия
Расстояние, км		D1	D2	D3
Пункты отправления	A1	29	24	28
	A2	11	37	13
	A3	9	29	11
	A4	18	21	15
	A5	126	112	96

<<< < Предыдущая 1 2 34 / 74 5 6 7 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
01.07.2025222 Кб2сокр ГОСЫ - копия.docx
#
15.04.2019905 Кб12сокрашеные.doc
#
08.06.201530 Кб91Соловьев Сергей Михайлович.docx
#
17.11.2019181 Кб29соответствия.rtf
#
01.03.202565 Кб4Сопоставительное языкозн-е.doc
#
01.05.2025962 Кб1сохранить!!!!.doc
#
01.07.202559 Кб1Соц методы в ГМУ_задания.docx
#
22.11.201897 Кб11СОЦ. ОБСЛУЖИВАНИЕ.doc
#
01.05.2025744 Кб3социальная философия.doc
#
01.05.2025733 Кб0Социально-трудовые права молодого специалиста С...docx
#
01.03.2025128 Кб1социология 20-30.doc