Добавил:

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

Вуз:

Самарский национальный исследовательский университет им. ак. С.П. Королёва (бывш. СГАУ, СамГУ)

Предмет:

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

Файл:

ВВТ.docx

Скачиваний:

Добавлен:

16.03.2015

Размер:

105.48 Кб

Скачать

☆

<<< < Предыдущая 12 / 32 3 > Следующая >>>

2 Определение расстояний перевозки

2.1 Пункты отправления – пункты назначения (первый вид транспорта)

Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом отправления единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведенными в матрице расстояний между пунктами (таблица 1).

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

отправления и назначения

Расстояние, км		Пункты назначения
Расстояние, км		В1	В2	В3	В4
Пункты отправления	А1	112	102	90	76
	А2	128	119	108	95
	А3	144	136	126	114
	A4	160	153	144	133

2.2 Пункты взаимодействия – пункты назначения (второй вид транспорта)

Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом взаимодействия единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведенными в матрице расстояний между пунктами (таблица 2).

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

взаимодействия и назначения

Расстояние, км			Пункты назначения
			В1		В2	В3		В4
Пункты взаимодействия	D1	64		51		36	19
	D2	80		68		54	38
	D3	96		85		72	57

2.3 Пункты отправления – пункты взаимодействия (первый вид транспорта)

Из матрицы расстояний видно, что прямых маршрутов между пунктами A_k (k = 1...4) отправления и пунктами D_i (i = 2...3) взаимодействия нет. Необходимо построить кратчайшие маршруты, пролегающие через промежуточные пункты E_s (s = 1...9), и определить длины этих маршрутов.

Сформируем матрицу расстояний между пунктами A_k отправления, промежуточными пунктами E_s, пунктами D_i взаимодействия; введем сквозную нумерацию узлов (таблица 3).

2.3.1 Пункт d2

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

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

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

U⁰₆ = L_6-14 = 4;

U⁰₈ = L_8-14 = 5;

U⁰₁₁ = L_11-14 = 3.

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

Таблица 3 – Матрица расстояний между пунктами отправления,

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

Пункты			А1		А2		А3		A4		E1		E2		E3		E4		E5		E6		E7		E8		E9		D2		D3
	Узлы	1		2		3		4		5		6		7		8		9		10		11		12		13		14		15
А1	1													8		34
А2	2									5						44		4
А3	3											56						11		23
A4	4																							11
E1	5			5																		45
E2	6					56												68						56				4
E3	7	8														12						13
E4	8	34		44										12				18				32						5
E5	9			4		11						68				18				2				10		12
E6	10					23												2								8				9
E7	11									45				13		32								4				3
E8	12							11				56						10				4				9				9
E9	13																	12		8				9
D2	14											4				5						3
D3	15																			9				9

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

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

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

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

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

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

Из узла 1	j	L₁_-_j	U⁰_j	L¹₁_-_j	U¹₁
1- 8-14	8	34	5	39	39
Из узла 2	j	L₂_-_j	U⁰_j	L¹₂_-_j	U¹₂
2- 8-14	8	44	5	49	49
Из узла 3	j	L₃_-_j	U⁰_j	L¹₃_-_j	U¹₃
3- 6-14	6	56	4	60	60
Из узла 5	j	L₅_-_j	U⁰_j	L¹₅_-_j	U¹₅
5- 11-14	11	45	3	48	48
Из узла 6	j	L_6-_j	U⁰_j	L¹_6-_j	U¹₆
6- 14	14	4		4	4
Из узла 7	j	L₇_-_j	U⁰_j	L¹₇_-_j	U¹₇
7- 8-14	8	12	5	17
7- 11-14	11	13	3	16	16
Из узла 8	j	L₈_-_j	U⁰_j	L¹₈_-_j	U¹₈
8- 11-14	11	32	3	35
8- 14	14	5		5	5
Из узла 9	j	L₉_-_j	U⁰_j	L¹₉_-_j	U¹₉
9- 6-14	6	68	4	72
9- 8-14	8	18	5	23	23
Из узла 11	j	L₁₁_-_j	U⁰_j	L¹₁₁_-_j	U¹₁₁
11- 8-14	8	32	5	37
11- 14	14	3		3	3
Из узла 12	j	L₁₂_-_j	U⁰_j	L¹₁₂_-_j	U¹₁₂
12- 6-14	6	56	4	60
12- 11-14	11	4	3	7	7

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

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

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

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

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

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

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

Из узла 1	j	L_1-_j	U¹_j	L²_1-_j	U²₁
1- 7-11-14	7	8	16	24	24
1- 8-14	8	34	5	39
Из узла 2	j	L₂_-_j	U¹_j	L²₂_-_j	U²₂
2- 5-11-14	5	5	48	53
2- 8-14	8	44	5	49
2- 9-8-14	9	4	23	27	27
Из узла 3	j	L₃_-_j	U¹_j	L²₃_-_j	U²₃
3- 6-14	6	56	4	60
3- 9-8-14	9	11	23	34	34
Из узла 4	j	L₄_-_j	U¹_j	L²₄_-_j	U²₄
4- 12-11-14	12	11	7	18	18
Из узла 5	j	L₅_-_j	U¹_j	L²₅_-_j	U²₅
5- 2-8-14	2	5	49	54
5- 11-14	11	45	3	48	48
Из узла 6	j	L₆_-_j	U¹_j	L²₆_-_j	U²₆
6- 3-6-14	3	56	60	116
6- 9-8-14	9	68	23	91
6- 12-11-14	12	56	7	63
6- 14	14	4		4	4
Из узла 7	j	L₇_-_j	U¹_j	L²₇_-_j	U²₇
7- 1-8-14	1	8	39	47
7- 8-14	8	12	5	17
7- 11-14	11	13	3	16	16
Из узла 8	j	L₈_-_j	U¹_j	L²₈_-_j	U²₈
8- 7-11-14	7	12	16	28
8- 11-14	11	32	3	35
8- 14	14	5		5	5
Из узла 9	j	L₉_-_j	U¹_j	L²₉_-_j	U²₉
9- 2-8-14	2	4	49	53
9- 3-6-14	3	11	60	71
9- 6-14	6	68	4	72
9- 8-14	8	18	5	23	23
9- 12-11-14	12	10	7	17	17
Из узла 10	j	L₁₀_-_j	U¹_j	L²₁₀_-_j	U²₁₀
10- 3-6-14	3	23	60	83
10- 9-8-14	9	2	23	25	25
Из узла 11	j	L₁₁_-_j	U¹_j	L²₁₁_-_j	U²₁₁
11- 8-14	8	32	5	37
11- 14	14	3		3	3
Из узла 12	j	L_12-_j	U¹_j	L²_12-_j	U²₁₂
12- 6-14	6	56	4	60
12- 9-8-14	9	10	23	33
12- 11-14	11	4	3	7	7
Из узла 13	j	L_13-_j	U¹_j	L²_13-_j	U²₁₃
13- 9-8-14	9	12	23	35
13- 12-11-14	12	9	7	16	16
Из узла 15	j	L_15-_j	U¹_j	L²_15-_j	U²₁₅
15- 12-11-14	12	9	7	16	16

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

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

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

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

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

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

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

Из узла 1	j	L_1-_j	U²_j	L³_1-_j	U³₁
1- 7-11-14	7	8	16	24	24
1- 8-14	8	34	5	39
Из узла 2	j	L₂_-_j	U²_j	L³₂_-_j	U³₂
2- 5-11-14	5	5	48	53
2- 8-14	8	44	5	49
2- 9-12-11-14	9	4	17	21	21
Из узла 3	j	L_3-_j	U²_j	L³_3-_j	U³₃
3- 6-14	6	56	4	60
3- 9-12-11-14	9	11	17	28	28
3- 10-9-8-14	10	23	25	48
Из узла 4	j	L₄_-_j	U²_j	L³₄_-_j	U³₄
4- 12-11-14	12	11	7	18	18
Из узла 5	j	L₅_-_j	U²_j	L³₅_-_j	U³₅
5- 2-9-8-14	2	5	27	32	32
5- 11-14	11	45	3	48
Из узла 6	j	L₆_-_j	U²_j	L³₆_-_j	U³₆
6- 3-9-8-14	3	56	34	90
6- 9-12-11-14	9	68	17	85
6- 12-11-14	12	56	7	63
6- 14	14	4		4	4
Из узла 7	j	L₇_-_j	U²_j	L³₇_-_j	U³₇
7- 8-14	8	12	5	17
7- 11-14	11	13	3	16	16
Из узла 8	j	L₈_-_j	U²_j	L³₈_-_j	U³₈
8- 1-7-11-14	1	34	24	58
8- 2-9-8-14	2	44	27	71
8- 7-11-14	7	12	16	28
8- 9-12-11-14	9	18	17	35
8- 11-14	11	32	3	35
8- 14	14	5		5	5
Из узла 9	j	L₉_-_j	U²_j	L³₉_-_j	U³₉
9- 6-14	6	68	4	72
9- 8-14	8	18	5	23
9- 12-11-14	12	10	7	17	17
9- 13-12-11-14	13	12	16	28
Из узла 10	j	L₁₀_-_j	U²_j	L³₁₀_-_j	U³₁₀
10- 3-9-8-14	3	23	34	57
10- 9-12-11-14	9	2	17	19	19
10- 13-12-11-14	13	8	16	24
10- 15-12-11-14	15	9	16	25
Из узла 11	j	L₁_1-_j	U²_j	L³₁_1-_j	U³₁₁
11- 8-14	8	32	5	37
11- 14	14	3		3	3
Из узла 12	j	L_12-_j	U²_j	L³_12-_j	U³₁₂
12- 6-14	6	56	4	60
12- 11-14	11	4	3	7	7
Из узла 13	j	L_13-_j	U²_j	L³_13-_j	U³₁₃
13- 9-12-11-14	9	12	17	29
13- 10-9-8-14	10	8	25	33
13- 12-11-14	12	9	7	16	16
Из узла 15	j	L_15-_j	U²_j	L³_15-_j	U³₁₅
15- 10-9-8-14	10	9	25	34
15- 12-11-14	12	9	7	16	16

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

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

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

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

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

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

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

Из узла 1	j	L_1-_j	U³_j	L⁴_1-_j	U⁴₁
1- 7-11-14	7	8	16	24	24
1- 8-14	8	34	5	39
Из узла 2	j	L₂_-_j	U³_j	L⁴₂_-_j	U⁴₂
2- 5-2-9-8-14	5	5	32	37
2- 8-14	8	44	5	49
2- 9-12-11-14	9	4	17	21	21
Из узла 3	j	L_3-_j	U³_j	L⁴_3-_j	U⁴₃
3- 6-14	6	56	4	60
3- 9-12-11-14	9	11	17	28	28
3- 10-9-12-11-14	10	23	19	42
Из узла 4	j	L₄_-_j	U³_j	L⁴₄_-_j	U⁴₄
4- 12-11-14	12	11	7	18	18
Из узла 5	j	L₅_-_j	U³_j	L⁴₅_-_j	U⁴₅
5- 2-9-12-11-14	2	5	21	26	26
5- 11-14	11	45	3	48
Из узла 6	j	L₆_-_j	U³_j	L⁴₆_-_j	U⁴₆
6- 3-9-12-11-14	3	56	28	84
6- 9-12-11-14	9	68	17	85
6- 12-11-14	12	56	7	63
6- 14	14	4		4	4
Из узла 7	j	L₇_-_j	U³_j	L⁴₇_-_j	U⁴₇
7- 8-14	8	12	5	17
7- 11-14	11	13	3	16	16
Из узла 8	j	L₈_-_j	U³_j	L⁴₈_-_j	U⁴₈
8- 1-7-11-14	1	34	24	58
8- 2-9-12-11-14	2	44	21	65
8- 7-11-14	7	12	16	28
8- 9-12-11-14	9	18	17	35
8- 11-14	11	32	3	35
8- 14	14	5		5	5
Из узла 9	j	L₉_-_j	U³_j	L⁴₉_-_j	U⁴₉
9- 6-14	6	68	4	72
9- 8-14	8	18	5	23
9- 12-11-14	12	10	7	17	17
9- 13-12-11-14	13	12	16	28
Из узла 10	j	L₁₀_-_j	U³_j	L⁴₁₀_-_j	U⁴₁₀
10- 3-9-12-11-14	3	23	28	51
10- 9-12-11-14	9	2	17	19	19
10- 13-12-11-14	13	8	16	24
10- 15-12-11-14	15	9	16	25
Из узла 11	j	L₁_1-_j	U³_j	L⁴₁_1-_j	U⁴₁₁
11- 5-2-9-8-14	5	45	32	77
11- 8-14	8	32	5	37
11- 14	14	3		3	3
Из узла 12	j	L_12-_j	U³_j	L⁴_12-_j	U⁴₁₂
12- 6-14	6	56	4	60
12- 11-14	11	4	3	7	7
Из узла 13	j	L_13-_j	U³_j	L⁴_13-_j	U⁴₁₃
13- 9-12-11-14	9	12	17	29
13- 10-9-12-11-14	10	8	19	27
13- 12-11-14	12	9	7	16	16
Из узла 15	j	L_15-_j	U³_j	L⁴_15-_j	U⁴₁₅
15- 10-9-12-11-14	10	9	19	28
15- 12-11-14	12	9	7	16	16

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

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

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

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

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

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

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

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

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

J	k=0		k=1		k=2			k=3			k=4
J	Маршрут	U⁰_j	Маршрут	U¹_j	Маршрут	U²_j	Маршрут		U³_j	Маршрут		U⁴_j
1			1-8-14	39	1-7-11-14	24	1-7-11-14		24	1-7-11-14		24
2			2-8-14	49	2-9-8-14	27	2-9-12-11-14		21	2-9-12-11-14		21
3			3-6-14	60	3-9-8-14	34	3-9-12-11-14		28	3-9-12-11-14		28
4					4-12-11-14	18	4-12-11-14		18	4-12-11-14		18
5			5-11-14	48	5-11-14	48	5-2-9-8-14		32	5-2-9-12-11-14		26
6	6-14	4	6-14	4	6-14	4	6-14		4	6-14		4
7			7-11-14	16	7-11-14	16	7-11-14		16	7-11-14		16
8	8-14	5	8-14	5	8-14	5	8-14		5	8-14		5
9			9-8-14	23	9-12-11-14	17	9-12-11-14		17	9-12-11-14		17
10					10-9-8-14	25	10-9-12-11-14		19	10-9-12-11-14		19
11	11-14	3	11-14	3	11-14	3	11-14		3	11-14		3
12			12-11-14	7	12-11-14	7	12-11-14		7	12-11-14		7
13					13-12-11-14	16	13-12-11-14		16	13-12-11-14		16
15					15-12-11-14	16	15-12-11-14		16	15-12-11-14		16

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

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

из узла 2 (пункт А₂): 2-9-12-11-14 (A₂-E₅- E₈-E₇-D₂); расстояние перевозки 21;

из узла 3 (пункт А₃): 3-9-12-11-14 (A₃- E₅- E₈-E₇-D₂); расстояние перевозки 28;

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

<<< < Предыдущая 12 / 32 3 > Следующая >>>

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

#
07.06.2015150.89 Кб9ВВЕДЕНИЕ.docx19.docx
#
07.06.2015100.37 Кб28Вводная лекция по риторике.docx
#
16.03.2015159.74 Кб26Вводное_занятие_по_Прологу_(старое).doc
#
16.03.2015813.01 Кб8ВВС-ЛабРабота-03-ВнешнНагрузкиТраектория.pdf
#
16.03.2015290.14 Кб6ВВТ-курсач2013.docx
#
16.03.2015105.48 Кб8ВВТ.docx
#
28.03.2016304.32 Кб21Ведясова О.А., Анатомия человека.pdf
#
07.06.2015103.85 Кб63Великие географические открытия.docx
#
07.06.201581.88 Кб57Виды судебных речей.docx
#
16.03.201515.48 Кб37Викторина о спорте.docx
#
28.03.2016223.74 Кб18Винникотт Д.В. - Разговор с родителями.doc