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

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Постановка задачи

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

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

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

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

2.3.1 Пункт D3

2.3.2 Пункт D2

2.3.3 Пункт D1

3. Определение себестоимости перевозки

3.1 Первый вид транспорта

3.2 Второй вид транспорта

4. Решение задачи

Заключение

Список использованных источников

Введение

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

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

При решении задачи рассматриваются два случая, в зависимости от способа доставки груза. Груз может доставляться из пунктов отправления в пункты назначения:

Одним видом транспорта прямым сообщением

Двумя видами транспорта с перевалкой в нескольких пунктах взаимодействия Di с заданными перерабатывающими мощностями.

Во втором разделе определяются оптимальные расстояния перевозки для первого вида транспорта, для второго вида транспорта и в прямом сообщении

В третьем разделе определяется себестоимость перевозки. Расчет производится для трех случаев:

1 для первого вида транспорта - при перевозке груза между пунктами отправления и пунктами взаимодействия

2 для первого вида транспорта - при перевозке груза между пунктами отправления и пунктами назначения.

3 для второго вида транспорта - при перевозке груза между пунктами взаимодействия и пунктами назначения

Четвертый раздел содержит решение задачи с применением программы MS Excel и схему распределения грузопотоков по маршрутам перевозок.

1. Постановка задачи

Имеется пять пунктов отправления однородного груза с заданными объемами его запасов. Имеется четыре пункта назначения с заданными заявками на получение груза.

Доставка может осуществляться одним видом транспорта прямым сообщением или двумя видами с перевалкой с первого вида транспорта на второй в трех пунктах взаимодействия с заданными перерабатывающими способностями.

Необходимо составить такой план перевозок, чтобы во все пункты назначения заданное количество груза было доставлено, а общая себестоимость перевозок была минимальна.

Введем переменные для описания задачи:

k = 5 - количество пунктов отправления

i = 4 - количество пунктов взаимодействия

j = 3 - количество пунктов назначения

- количество груза, перевозимого из k-го пункта отправлений в i-й пункт взаимодействия первым видом транспорта, т, k=1..5, i=1..3

- количество груза, перевозимого из i-го пункта взаимодействия в j-й пункт назначения вторым видом транспорта, т, i=1..3, j=1..4

- количество груза, перевозимого в прямом сообщении из k-го пункта отправления в j-й пункт назначения первым видом транспорта, т, k=1..5, j=1..4

- запас груза в k-ом пункте отправления, k=1..5

- перерабатывающая способность i-го пункта взаимодействия, т, i=1..3

- заявка на груз для j-го пункта назначения, т, j=1..4

- себестоимость перевозки 1 тонны груза из k-го пункта отправления в i-й пункт взаимодействия первым видом транспорта с учетом затрат на перевалку, рубт, k=1..5, i=1..3

- себестоимость перевозки 1 тонны груза из i-го пункта взаимодействия в j-й пункт назначения вторым видом транспорта, рубт, i=1..3, j=1..4

- себестоимость перевозки 1 тонны груза в прямом сообщении из k-го пункта отправления в j-й пункт назначения первым видом транспорта, рубт, k=1..5, j=1..4.

Значения переменных известны и входят в состав исходных данных; значения переменных рассчитываются; значения переменных определяются в ходе решения задачи.

Целевая функция суммарная себестоимость перевозок записывается следующим образом:

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

2. Ограничения, накладываемые на задачу, формализуются в следующем виде.

Суммарное количество груза, прибывающего в j-й пункт назначения из пунктов взаимодействия и из пунктов отправления прямым сообщением, должно быть равно заявке этого пункта:

j=1..4

3. Суммарное количество груза, отправляемого из i-го пункта взаимодействия, должно быть равно суммарному количеству груза, прибывающего в этот пункт:

i=1..3

4. Суммарное количество груза, прибывающего в i-й пункт взаимодействия, не может превышать перерабатывающей способности этого пункта:

i=1..3

5. Суммарное количество груза, отправляемого из k-го пункта отправления в пункты взаимодействия и в пункты назначения прямым сообщением, не может превышать запас груза в этом пункте:

k=1..5

6. Сформулированная задача является многопараметрической задачей линейного программирования минимизации критерия 1 с учетом выполнения условия 2 и ограничений 3, 4, 5, 6.

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 Пункты отправления -- пункты взаимодействия. Первый вид транспорта

перевозка груз excel себестоимость

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

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

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

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

Пункты	А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

2.3.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	11	23	9	32	32
Из узла 7	j
7- 13-17	13	56	9	65	65
Из узла 10	j
10- 13- 17	13	10	9	19
10- 11- 17	11	2	9	11	11
Из узла 12	J
12- 13-17	13	4	9	13	13
Из узла 14	j
14- 13-17	13	9	9	18
14- 11 -17	11	8	9	17	17
Из узла 15	j
15- 11-17	11	11	9	20	20

Полученные кратчайшие маршруты из каждого узла в узел 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	10	4	11	15	15
Из узла 3	J
3-10-11-17	10	11	11	22	22
Из узла 6	j
6-12-13-17	12	45	65	110	110
Из узла 7	J
7-10-11-17	10	68	11	79	79
Из узла 8	j
8-12-13-17	12	13	13	26	26
Из узла 9	J
9-10-11-17	10	18	11	29	29
9-12-13-17	12	32	13	45
Из узла 10	j
10-14-11-17	14	12	17	29	29
10-7-13-17	7	68	65	133
Из узла 14	J
14-10-11-17	10	12	11	23	23
Из узла 15	J
15-14-11-17	14	11	17	28	28
Из узла 16	J
16-12-13-17	12	3	13	16	16

Полученные кратчайшие маршруты из каждого узла в узел 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	9	34	29	63
1-8-12-13-17	8	8	26	34	34
Из узла 2	j
2-6-12-13-17	6	5	110	115
2-9-10-11-17	9	44	29	73
2-10-14-11-17	10	4	29	33	33
Из узла 3	J
3-7-10-11-17	7	56	79	135
3-10-14-11-17	10	11	29	40	40
Из узла 7	J
7-10-14-11-17	10	68	29	97	97
Из узла 8	J
8-9-10-11-17	9	12	29	41	41
Из узла 9	J
9-8-12-13-17	8	12	26	38	38
9-10-14-11-17	10	18	29	47
Из узла 12	J
12-9-10-11-17	9	32	29	61	61
Из узла 13	J
13-7-10-11-17	7	56	79	135	135
Из узла 16	J
16-9-10-11-17	9	5	29	34	34

Полученные кратчайшие маршруты из каждого узла в узел 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							1-8-12-13-17	34	1-8-12-13-17	34
2					2-10-11-17	15	2-10-17-17	15	2-10-11-17	15
3			3-11-17	32	3-10-11-17	22	3-10-11-17	22	3-10-11-17	22
4			4-13-17	20	4-13-17	20	4-13-17	20	4-13-17	20
5	5-17	110	5-17	110	5-17	110	5-17	110	5-17	110
6					6-12-13-17	110	6-12-13-17	110	6-12-13-17	110
7			7-13-17	65	7-13-16	65	7-13-16	65	7-13-16	65
8					8-12-13-17	26	8-12-13-17	26	8-12-13-17	26
9					9-10-11-17	29	9-10-11-17	29	9-10-11-17	29
10			10-11-17	11	10-11-17	11	10-11-17	11	10-11-17	11
11	11-17	9	11-17	9	11-17	9	11-17	9	11-17	9
12			12-13-17	13	12-13-17	13	12-13-17	13	12-13-17	13
13	13-17	9	13-17	9	13-17	9	13-17	9	13-17	9
14			14-11-17	17	14-11-17	17	14-11-17	17	14-11-17	17
15			15-11-17	20	15-11-17	20	15-11-17	20	15-11-17	20
16					16-12-13-17	16	16-12-13-17	16	16-12-13-17	16
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

2.3.2 Пункт D2

Построим маршруты в узел 16 пункт D2 из узлов 1 пункт А1, 2 пункт А2, 3 пункт А3, 4 пункт А4, 5 пункт А5.

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

Определим длины прямых без посещения промежуточных узлов маршрутов в узел 16. Для каждого j-го узла j=5, 7, 9, 12, который соединен дугой с узлом 16 т.е. имеется прямой маршрут, длина кратчайшего маршрута принимается равной расстоянию между этим узлом и узлом 16; для остальных узлов значения принимаются равными бесконечности:

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

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

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

, i=1,2, …17, j=1,2, …17, i16, j16, .

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

Таблица 8 -- Маршруты в узел 16 с числом промежуточных узлов не более 1

Из узла 1	J
1-9-16	9	34	5	39	39
Из узла 2	j
2-9-16	9	44	5	49	49
Из узла 3	J
3-7-16	7	56	7	63	63
Из узла 6	J
6-12-16	12	45	3	48	48
Из узла 8	J
8-9-16	9	12	5	17
8-12-16	12	13	3	16	16
Из узла 9	j
9-12-16	12	32	3	35	35
Из узла 10	J
10-7-16	7	68	7	75
10-9-16	9	18	5	23	23
Из узла 12	j
12-9-16	12	32	5	37	37
Из узла 13	j
13-7-16	7	56	7	63
13-12-16	12	4	3	7	7

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

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

Определим длину возможного маршрута из i-го узла в узел 16, проходящего через j-й узел, с числом промежуточных узлов не более двух, как сумму расстояния от i-го узла до j-го узла и длины маршрута из j-го узла в узел 16 с числом узлов не более одного: , i=1,2,…17, j=1,2,…17, i16, j16, ij.

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

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

Из узла 1	J
1-8-12-16	8	8	16	24	24
Из узла 2	j
2-6-12-16	6	5	48	53
2-10-9-16	10	4	23	27	27
Из узла 3	J
3-10-9-16	10	11	23	34	34
Из узла 4	j
4-13-12-16	13	11	7	18	18
Из узла 7
7-13-12-16	13	56	7	63	63
7-10-9-16	10	68	23	91
Из узла 10	J
10-13-12-16	13	10	7	17	17
Из узла 11	j
11-10-9-16	10	2	23	25	25
Из узла 13	j
13-10-9-16	10	10	23	33
Из узла 14	j
14-10-9-16	10	12	23	35
14-13-12-16	13	9	7	16	16
Из узла 17	j
17-13-12-16	13	9	7	16	16

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

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

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

, i=1,2,…17, j=1,2,…17, i16, j16, ij.

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

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

Из узла 2	J
2-10-13-12-16	10	4	17	21	21
Из узла 3	j
3-11-10-9-16	11	23	25	48
3-10-13-12-16	10	11	17	28	28
Из узла 7	J
7-10-13-12-16	10	68	17	85	85
Из узла 9	j
9-10-13-12-16	10	18	17	35	35
Из узла 10	j
10-14-13-12-16	14	12	16	28	28
Из узла 11	j
11-14-13-12-16	14	8	16	24
11-10-13-12-16	10	2	17	19	19
11-17-13-12-16	17	9	16	25
Из узла 14	j
14-11-10-9-16	11	8	25	33
14-10-13-12-16	10	12	17	29	29
Из узла 15	j
15-11-10-9-16	11	11	25	36
15-14-13-12-16	14	11	16	27	27
Из узла 17	j
17-11-10-9-16	11	9	25	34	34

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

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

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

, i=1,2,…17, j=1,2,…17, i16, j16, ij.

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

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

В связи с этим дальнейшие расчеты прекращаются.

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

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

J	k=0	k=1	K=2	k=3	k=4
	Маршрут	U0j	Маршрут	U1j	Маршрут	U2j	Маршрут	U3j	Маршрут	U4j
1			1-9-16	39	1-8-12-16	24	1-8-12-16	24	1-8-12-16	24
2			2-9-16	49	2-10-9-16	27	2-10-12-13-16	21	2-10-12-13-16	21
3			3-7-16	63	3-10-9-16	34	3-10-13-12-16	28	3-10-13-12-16	28
4			4-13-12-16	18	4-13-12-16	18	4-13-12-16	18
5	5-16	126	5-16	126	5-16	126	5-16	126	5-16	126
6			6-12-16	48	6-12-16	48	6-12-16	48	6-12-16	48
7	7-16	7	7--16	7	7-16	7	7-16	7	7-16	7
8			8-12-16	16	8-12-16	16	8-12-16	16	8-12-16	16
9	9-16	5	9-16	5	9-16	5	9-16	5	9-16	5
10	10-9-16	23	10-13-12-16	17	10-13-12-16	17	10-13-12-16	17	10-13-12-16	17
11	11-10-9-16	25	11-10-13-12-16	19	11-10-13-12-16	19
12	12-16	3	12-16	3	12-16	3	12-16	3	12-16	3
13	13-12-16	7	13-12-16	7	13-12-16	7	13-12-16	7
14	14-13-12-16	16	14-13-12-16	16	14-13-12-16	16
15	15-14-13-12-16	27	15-14-13-12-16	27
16
17	17-13-12-16	16	17-13-12-16	16	17-13-12-16	16

Искомые кратчайшие маршруты в узел 16 пункт D2:

Из узла 1 пункт A1: 1-8-12-16 A1-E3-E7-D2; расстояние перевозки 24

Из узла 2 пункт A2: 2-10-13-12-16 A2-E5-Е8-E7-D2; расстояние перевозки 21

Из узла 3 пункт A3: 3-10-13-12-16 A3-E5-Е8-E7-D2; расстояние перевозки 28

Из узла 4 пункт A4: 4-13-12-16 A4-E8-Е7-D2; расстояние перевозки 18

Из узла 5 пункт A5: 5-16 A5-D2; расстояние перевозки 126

2.3.2 Пункт D1

Построим маршруты в узел 15 пункт D1 из узлов 1 пункт А1, 2 пункт А2, 3 пункт А3, 4 пункт А4, 5 пункт А5.

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

Определим длины прямых без посещения промежуточных узлов маршрутов в узел 15. Для каждого j-го узла j=1, 2, 3, 4, 11, 14, который соединен дугой с узлом 15 т.е. имеется прямой маршрут, длина кратчайшего маршрута принимается равной расстоянию между этим узлом и узлом 15; для остальных узлов значения принимаются равными бесконечности:

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

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

Определим длину возможного маршрута из i-го узла в узел 15 пункт D1, проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния от i-го узла до j-го узла и длины прямого маршрута из этого узла в узел 15 пункт D1: , i=1,2, …17, j=1,2, …17, i15, j15, .

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

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

Из узла 3	J
3-11-15	11	23	11	34	34
Из узла 10	j
10-11-15	11	2	11	13	13
10-14-15	14	12	11	23
Из узла 11	J
11-14-15	14	8	11	19	19
Из узла 13	j
13-14-15	14	9	11	20	20
Из узла 14	j
14-11-15	11	8	11	19	19
Из узла 17	j
17-11-15	11	9	11	20	20

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

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

Определим длину возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более двух, как сумму расстояния от i-го узла до j-го узла и длины маршрута из j-го узла в узел 15 с числом узлов не более одного: , i=1,2,…17, j=1,2,…17, i15, j15, ij.

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

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

Из узла 2	J
2-10-11-15	10	4	13	17	17
Из узла 4	j
4-13-14-15	13	11	20	31	31
Из узла 7	J
7-10-11-15	10	68	13	81
7-13-14-15	13	56	20	76	76
Из узла 9	j
9-10-11-15	10	18	13	31	31
Из узла 10	j
17-11-15	11	9	11	20	20
Из узла 12	J
12-13-14-15	13	4	20	24	24
Из узла 13	j
13-10-11-15	10	10	13	23	23
Из узла 14	j
14-10-11-15	10	12	13	25	25
Из узла 17	j
17-13-14-15	13	9	20	29	29

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

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

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