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
	A5	176	170	162		152

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

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

Таблица 2 — Расстояние между пунктами взаимодействия и назначения

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

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

Из матрицы расстояний видно, что существуют прямые маршруты между пунктами Ak k=1..5 отправления и пунктами Di i=1..3 взаимодействия таблица 3. Эти маршруты также учитываются при выборе кратчайших расстояний между пунктами отправления Ak k=1..5 и пунктами взаимодействия Di i-1..3.

Таблица 3 — расстояния между пунктами отправления и пунктами взаимодействия.ёНеобходимо определить, являются ли расстояния прямых маршрутов оптимальными, построить кратчайшие маршруты, пролегающие через промежуточные пункты Es s=1..9, и определить длины этих маршрутов.

Сформируем матрицу расстояний между пунктами Ak отправления, промежуточными пунктами Es, пунктами Di взаимодействия; введем сквозную нумерацию узлов таблица 4.

Таблица 4 — Матрица расстояний между пунктами отправления, взаимодействия и промежуточными пунктами

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