ОПРЕДЕЛЕНИЕ РАССТОЯНИЙ ПЕРЕВОЗКИ

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

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

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

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

Расстояние, км	Пункты назначения
В1	В2	В3	В4
Пункты отправления	А1
А2
А3
A4

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

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

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

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

Расстояние, км	Пункты назначения
В1	В2	В3	В4
Пункты взаимодействия	D1
D2
D3

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 Пункт D₂

Построим маршруты в узел 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

Узлы

А1

А2

А3

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
Из узла 2	j	L₂_-_j	U⁰_j	L¹₂_-_j	U¹₂
2- 8-14
Из узла 3	j	L₃_-_j	U⁰_j	L¹₃_-_j	U¹₃
3- 6-14
Из узла 5	j	L₅_-_j	U⁰_j	L¹₅_-_j	U¹₅
5- 11-14
Из узла 6	j	L_6-_j	U⁰_j	L¹_6-_j	U¹₆
6- 14
Из узла 7	j	L₇_-_j	U⁰_j	L¹₇_-_j	U¹₇
7- 8-14
7- 11-14
Из узла 8	j	L₈_-_j	U⁰_j	L¹₈_-_j	U¹₈
8- 11-14
8- 14
Из узла 9	j	L₉_-_j	U⁰_j	L¹₉_-_j	U¹₉
9- 6-14
9- 8-14
Из узла 11	j	L₁₁_-_j	U⁰_j	L¹₁₁_-_j	U¹₁₁
11- 8-14
11- 14
Из узла 12	j	L₁₂_-_j	U⁰_j	L¹₁₂_-_j	U¹₁₂
12- 6-14
12- 11-14

Полученные кратчайшие маршруты из каждого узла в узел 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
1- 8-14
Из узла 2	j	L₂_-_j	U¹_j	L²₂_-_j	U²₂
2- 5-11-14
2- 8-14
2- 9-8-14
Из узла 3	j	L₃_-_j	U¹_j	L²₃_-_j	U²₃
3- 6-14
3- 9-8-14
Из узла 4	j	L₄_-_j	U¹_j	L²₄_-_j	U²₄
4- 12-11-14
Из узла 5	j	L₅_-_j	U¹_j	L²₅_-_j	U²₅
5- 2-8-14
5- 11-14
Из узла 6	j	L₆_-_j	U¹_j	L²₆_-_j	U²₆
6- 3-6-14
6- 9-8-14
6- 12-11-14
6- 14
Из узла 7	j	L₇_-_j	U¹_j	L²₇_-_j	U²₇
7- 1-8-14
7- 8-14
7- 11-14
Из узла 8	j	L₈_-_j	U¹_j	L²₈_-_j	U²₈
8- 7-11-14
8- 11-14
8- 14
Из узла 9	j	L₉_-_j	U¹_j	L²₉_-_j	U²₉
9- 2-8-14
9- 3-6-14
9- 6-14
9- 8-14
9- 12-11-14
Из узла 10	j	L₁₀_-_j	U¹_j	L²₁₀_-_j	U²₁₀
10- 3-6-14
10- 9-8-14
Из узла 11	j	L₁₁_-_j	U¹_j	L²₁₁_-_j	U²₁₁
11- 8-14
11- 14
Из узла 12	j	L_12-_j	U¹_j	L²_12-_j	U²₁₂
12- 6-14
12- 9-8-14
12- 11-14
Из узла 13	j	L_13-_j	U¹_j	L²_13-_j	U²₁₃
13- 9-8-14
13- 12-11-14
Из узла 15	j	L_15-_j	U¹_j	L²_15-_j	U²₁₅
15- 12-11-14

Полученные кратчайшие маршруты из каждого узла в узел 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
1- 8-14
Из узла 2	j	L₂_-_j	U²_j	L³₂_-_j	U³₂
2- 5-11-14
2- 8-14
2- 9-12-11-14
Из узла 3	j	L_3-_j	U²_j	L³_3-_j	U³₃
3- 6-14
3- 9-12-11-14
3- 10-9-8-14
Из узла 4	j	L₄_-_j	U²_j	L³₄_-_j	U³₄
4- 12-11-14
Из узла 5	j	L₅_-_j	U²_j	L³₅_-_j	U³₅
5- 2-9-8-14
5- 11-14
Из узла 6	j	L₆_-_j	U²_j	L³₆_-_j	U³₆
6- 3-9-8-14
6- 9-12-11-14
6- 12-11-14
6- 14
Из узла 7	j	L₇_-_j	U²_j	L³₇_-_j	U³₇
7- 8-14
7- 11-14
Из узла 8	j	L₈_-_j	U²_j	L³₈_-_j	U³₈
8- 1-7-11-14
8- 2-9-8-14
8- 7-11-14
8- 9-12-11-14
8- 11-14
8- 14
Из узла 9	j	L₉_-_j	U²_j	L³₉_-_j	U³₉
9- 6-14
9- 8-14
9- 12-11-14
9- 13-12-11-14
Из узла 10	j	L₁₀_-_j	U²_j	L³₁₀_-_j	U³₁₀
10- 3-9-8-14
10- 9-12-11-14
10- 13-12-11-14
10- 15-12-11-14
Из узла 11	j	L₁_1-_j	U²_j	L³₁_1-_j	U³₁₁
11- 8-14
11- 14
Из узла 12	j	L_12-_j	U²_j	L³_12-_j	U³₁₂
12- 6-14
12- 11-14
Из узла 13	j	L_13-_j	U²_j	L³_13-_j	U³₁₃
13- 9-12-11-14
13- 10-9-8-14
13- 12-11-14
Из узла 15	j	L_15-_j	U²_j	L³_15-_j	U³₁₅
15- 10-9-8-14
15- 12-11-14

Полученные кратчайшие маршруты из каждого узла в узел 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
1- 8-14
Из узла 2	j	L₂_-_j	U³_j	L⁴₂_-_j	U⁴₂
2- 5-2-9-8-14
2- 8-14
2- 9-12-11-14
Из узла 3	j	L_3-_j	U³_j	L⁴_3-_j	U⁴₃
3- 6-14
3- 9-12-11-14
3- 10-9-12-11-14
Из узла 4	j	L₄_-_j	U³_j	L⁴₄_-_j	U⁴₄
4- 12-11-14
Из узла 5	j	L₅_-_j	U³_j	L⁴₅_-_j	U⁴₅
5- 2-9-12-11-14
5- 11-14
Из узла 6	j	L₆_-_j	U³_j	L⁴₆_-_j	U⁴₆
6- 3-9-12-11-14
6- 9-12-11-14
6- 12-11-14
6- 14
Из узла 7	j	L₇_-_j	U³_j	L⁴₇_-_j	U⁴₇
7- 8-14
7- 11-14
Из узла 8	j	L₈_-_j	U³_j	L⁴₈_-_j	U⁴₈
8- 1-7-11-14
8- 2-9-12-11-14
8- 7-11-14
8- 9-12-11-14
8- 11-14
8- 14
Из узла 9	j	L₉_-_j	U³_j	L⁴₉_-_j	U⁴₉
9- 6-14
9- 8-14
9- 12-11-14
9- 13-12-11-14
Из узла 10	j	L₁₀_-_j	U³_j	L⁴₁₀_-_j	U⁴₁₀
10- 3-9-12-11-14
10- 9-12-11-14
10- 13-12-11-14
10- 15-12-11-14
Из узла 11	j	L₁_1-_j	U³_j	L⁴₁_1-_j	U⁴₁₁
11- 5-2-9-8-14
11- 8-14
11- 14
Из узла 12	j	L_12-_j	U³_j	L⁴_12-_j	U⁴₁₂
12- 6-14
12- 11-14
Из узла 13	j	L_13-_j	U³_j	L⁴_13-_j	U⁴₁₃
13- 9-12-11-14
13- 10-9-12-11-14
13- 12-11-14
Из узла 15	j	L_15-_j	U³_j	L⁴_15-_j	U⁴₁₅
15- 10-9-12-11-14
15- 12-11-14

Полученные кратчайшие маршруты из каждого узла в узел 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
Маршрут	U⁰_j	Маршрут	U¹_j	Маршрут	U²_j	Маршрут	U³_j	Маршрут	U⁴_j
			1-8-14		1-7-11-14		1-7-11-14		1-7-11-14
			2-8-14		2-9-8-14		2-9-12-11-14		2-9-12-11-14
			3-6-14		3-9-8-14		3-9-12-11-14		3-9-12-11-14
					4-12-11-14		4-12-11-14		4-12-11-14
			5-11-14		5-11-14		5-2-9-8-14		5-2-9-12-11-14
	6-14		6-14		6-14		6-14		6-14
			7-11-14		7-11-14		7-11-14		7-11-14
	8-14		8-14		8-14		8-14		8-14
			9-8-14		9-12-11-14		9-12-11-14		9-12-11-14
					10-9-8-14		10-9-12-11-14		10-9-12-11-14
	11-14		11-14		11-14		11-14		11-14
			12-11-14		12-11-14		12-11-14		12-11-14
					13-12-11-14		13-12-11-14		13-12-11-14
					15-12-11-14		15-12-11-14		15-12-11-14

Искомые кратчайшие маршруты в узел 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.

2.3.2Пункт D₃

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

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

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

U⁰₁₀ = L_10-15 = 9;

U⁰₁₂ = L_12-15 = 9.

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

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,... 14, j = 1, 2,... 14, j ≠ i.

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

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

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

Из узла 3	j	L₃_-_j	U⁰_j	L¹₃_-_j	U¹₃
3- 10-15
Из узла 4	j	L₄_-_j	U⁰_j	L¹₄_-_j	U¹₄
4- 12-15
Из узла 6	j	L_6-_j	U⁰_j	L¹_6-_j	U¹₆
6- 12-15
Из узла 9	j	L₉_-_j	U⁰_j	L¹₉_-_j	U¹₉
9- 10-15
9- 12-15
Из узла 10	j	L_10-_j	U⁰_j	L¹_10-_j	U¹₁₀
10- 15
Из узла 11	j	L₁₁_-_j	U⁰_j	L¹₁₁_-_j	U¹₁₁
11- 12-15
Из узла 12	j	L_12-_j	U⁰_j	L¹_12-_j	U¹₁₂
12- 15
Из узла 13	j	L₁₃_-_j	U⁰_j	L¹₁₃_-_j	U¹₁₃
13- 10-15
13- 12-15

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

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,... 14, j = 1, 2,... 14, j ≠ i.

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

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

Из узла 2	j	L₂_-_j	U¹_j	L²₂_-_j	U²₂
2- 9-10-15
Из узла 3	j	L₃_-_j	U¹_j	L²₃_-_j	U²₃
3- 6-12-15
3- 9-10-15
3- 10-15
Из узла 4	j	L₄_-_j	U¹_j	L²₄_-_j	U²₄
4- 12-15
Из узла 5	j	L₅_-_j	U¹_j	L²₅_-_j	U²₅
5- 11-12-15
Из узла 6	j	L₆_-_j	U¹_j	L²₆_-_j	U²₆
6- 3-10-15
6- 9-10-15
6- 12-15
Из узла 7	j	L₇_-_j	U¹_j	L²₇_-_j	U²₇
7- 11-12-15
Из узла 8	j	L₈_-_j	U¹_j	L²₈_-_j	U²₈
8- 9-10-15
8- 11-12-15
Из узла 9	j	L₉_-_j	U¹_j	L²₉_-_j	U²₉
9- 3-10-15
9- 6-12-15
9- 10-15
9- 12-15
9- 13-10-15
Из узла 10	j	L₁₀_-_j	U¹_j	L²₁₀_-_j	U²₁₀
10- 15
Из узла 11	j	L_11-_j	U¹_j	L²_11-_j	U²₁₁
11- 12-15
Из узла 12	j	L₁₂_-_j	U¹_j	L²₁₂_-_j	U²₁₂
12- 9-10-15
12- 13-10-15
12- 15
Из узла 13	j	L_13-_j	U¹_j	L²_13-_j	U²₁₃
13- 9-10-15
13- 10-15
13- 12-15
Из узла 14	j	L_14-_j	U¹_j	L²_14-_j	U²₁₄
14- 6-12-15
14- 11-12-15

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

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,... 14, j = 1, 2,... 14, j ≠ i.

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

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

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

Из узла 1	j	L_1-_j	U²_j	L³_1-_j	U³₁
1- 7-11-12-15
1- 8-9-10-15
Из

⇐ Предыдущая 12

Дата добавления: 2015-10-19; просмотров: 409. Нарушение авторских прав; Мы поможем в написании вашей работы!

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при которых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Этические проблемы проведения экспериментов на человеке и животных В настоящее время четко определены новые подходы и требования к биомедицинским исследованиям...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

Факторы, влияющие на степень электролитической диссоциации Степень диссоциации зависит от природы электролита и растворителя, концентрации раствора, температуры, присутствия одноименного иона и других факторов...

Дезинфекция предметов ухода, инструментов однократного и многократного использования Дезинфекция изделий медицинского назначения проводится с целью уничтожения патогенных и условно-патогенных микроорганизмов - вирусов (в т...

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

Классификация и основные элементы конструкций теплового оборудования Многообразие способов тепловой обработки продуктов предопределяет широкую номенклатуру тепловых аппаратов...

Studopedia.info - Студопедия - 2014-2024 год . (0.012 сек.) русская версия | украинская версия