Пункт D3. Решение задачи распределения имеющегося однородного груза из нескольких пунктов отправления в несколько пунктов назначения по заданным заявкам на его получение

РефератПомощь в написанииУзнать стоимостьмоей работы

Построим маршруты в узел 17 пункт D3 из узлов 1 пункт А1, 2 пункт А2, 3 пункт А3, 4 пункт А4, 5 пункт А5. Таблица 6 — Маршруты в узел 17 с числом промежуточных узлов не более 3. Таблица 5 — Маршруты в узел 17 с числом промежуточных узлов не более 2. Таблица 4 — Маршруты в узел 17 с числом промежуточных узлов не более 1. Полученные маршруты и значения их длин занесем в таблицу 8. Из узла 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 принимается минимальное из возможных значений:

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


Из узла 3.	j.
3- 11−17.
Из узла 7.	j.
7- 13−17.
Из узла 10.	j.
10- 13- 17.
10- 11- 17.
Из узла 12.	J.
12- 13−17.
Из узла 14.	j.
14- 13−17.
14- 11 -17.
Из узла 15.	j.
15- 11−17.

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

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

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

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

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

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


Из узла 2.	j.
2- 10−11−17.
Из узла 3.	J.
3−10−11−17.
Из узла 6.	j.
6−12−13−17.
Из узла 7.	J.
7−10−11−17.
Из узла 8.	j.
8−12−13−17.
Из узла 9.	J.
9−10−11−17.
9−12−13−17.
Из узла 10.	j.
10−14−11−17.
10−7-13−17.
Из узла 14.	J.
14−10−11−17.
Из узла 15.	J.
15−14−11−17.
Из узла 16.	J.
16−12−13−17.

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

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

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

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

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

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


Из узла 1.	J.
1−9-10−11−17.
1−8-12−13−17.
Из узла 2.	j.
2−6-12−13−17.
2−9-10−11−17.
2−10−14−11−17.
Из узла 3.	J.
3−7-10−11−17.
3−10−14−11−17.
Из узла 7.	J.
7−10−14−11−17.
Из узла 8.	J.
8−9-10−11−17.
Из узла 9.	J.
9−8-12−13−17.
9−10−14−11−17.
Из узла 12.	J.
12−9-10−11−17.
Из узла 13.	J.
13−7-10−11−17.
Из узла 16.	J.
16−9-10−11−17.

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

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

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

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

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

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

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

Таблица 7.


J.	k=0.	k=1.	K=2.	k=3.	k=4.
Маршрут.	U0j.	Маршрут.	U1j.	Маршрут.	U2j.	Маршрут.	U3j.	Маршрут.	U4j.
	1−8-12−13−17.		1−8-12−13−17.
	2−10−11−17.		2−10−17−17.		2−10−11−17.
	3−11−17.		3−10−11−17.		3−10−11−17.		3−10−11−17.
	4−13−17.		4−13−17.		4−13−17.		4−13−17.
	5−17.		5−17.		5−17.		5−17.		5−17.
	6−12−13−17.		6−12−13−17.		6−12−13−17.
	7−13−17.		7−13−16.		7−13−16.		7−13−16.
	8−12−13−17.		8−12−13−17.		8−12−13−17.
	9−10−11−17.		9−10−11−17.		9−10−11−17.
	10−11−17.		10−11−17.		10−11−17.		10−11−17.
	11−17.		11−17.		11−17.		11−17.		11−17.
	12−13−17.		12−13−17.		12−13−17.		12−13−17.
	13−17.		13−17.		13−17.		13−17.		13−17.
	14−11−17.		14−11−17.		14−11−17.		14−11−17.
	15−11−17.		15−11−17.		15−11−17.		15−11−17.
	16−12−13−17.		16−12−13−17.		16−12−13−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.

Показать весь текст

Заполнить форму текущей работой

Другие работы

Меры защиты от вирусов

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

Реферат