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

Размещено на 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-й узел, с числом промежуточных узлов не более трех как сумму расстояния от i-го узла до j-го узла и длины маршрута из j-го узла в узел 15 с числом узлов не более двух:

, i=1,2,…17, j=1,2,…17, i15, j15, ij.

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

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

Из узла 1	J
1-9-10-11-15	9	34	31	65	65
Из узла 2	j
2-9-10-11-15	9	44	31	75	75
Из узла 3	J
3-7-13-14-15	7	56	76	132	132
Из узла 6	j
6-12-13-14-15	12	45	24	69	69
Из узла 8	j
8-9-10-11-15	9	12	31	43	43
8-12-13-14-15	12	13	24	37	37
Из узла 9	j
9-12-13-14-15	12	32	24	56	56
Из узла 10	j
10-7-13-14-15	7	68	76	144	144
Из узла 12	j
12-9-10-11-15	9	32	31	63	63
Из узла 13	j
13-7-13-14-15	7	56	76	132
Из узла 16	J
16-7-13-14-15	7	4	76	80
16-9-10-11-15	9	5	31	36
16-12-13-14-15	12	3	24	27	27

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

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

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

, i=1,2,…17, j=1,2,…17, i15, j15, ij.

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

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

Из узла 1	J
1-8-12-13-14-15	8	8	37	45	45
Из узла 7	j
7-16-12-13-14-15	16	4	27	31	31
Из узла 9	J
9-16-12-13-14-15	16	5	27	32	32
9-8-12-13-14-15	8	12	37	49

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

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

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

, i=1,2,…17, j=1,2,…17, i15, j15, ij.

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

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

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

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

Из узла 1 пункт A1: 1-15 A1 -- D1; расстояние перевозки 45

Из узла 2 пункт A2: 2-15 A2 -- D1; расстояние перевозки 17

Из узла 3 пункт A3: 3-15 A3 - D1; расстояние перевозки 24

Из узла 4 пункт A4: 4-15 A4 - D1; расстояние перевозки 31

Из узла 5 пункт A5: 5-15 A5-D1; расстояние перевозки 150

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

J	k=0	k=1	K=2	k=3	k=4	k=5
	Маршрут	U0j	Маршрут	U1j	Маршрут	U2j	Маршрут	U3j	Маршрут	U4j	Маршрут	U5j
1	1-15	45	1-15	45	1-15	45	1-15	45	1-15	45	1-15	45
2	2-15	17	2-15	17	2-15	17	2-15	17	2-15	17	2-15	17
3	3-15	24	3-15	24	3-15	24	3-15	24	3-15	24	3-15	24
4	4-15	31	4-15	31	4-15	31	4-15	31	4-15	31	4-15	31
5	5-15	150	5-15	150	5-15	150	5-15	150	5-15	150	5-15	150
6	6-12-13-14-15	69	6-12-13-14-15	69	6-12-13-14-15	69	6-12-13-14-15	69
7	7-13-14-15	76	7-13-14-15	76	7-16-12-13-114-15	76	7-16-12-13-114-15	76
8	8-12-13-14-15	37	8-12-13-14-15	37	8-12-13-14-15	37
9	9-10-11-15	31	9-10-11-15	31	9-10-11-15	31	9-10-11-15	31
10	10-11-15	13	10-11-15	13	10-11-15	13	10-11-15	13	10-11-15	13
11	11-15	11	11-15	11	11-15	11	11-15	11	11-15	11	11-15	11
12	12-13-14-15	24	12-13-14-15	24	12-13-14-15	24	12-13-14-15	24
13	13-14-15	20	13-14-15	20	13-14-15	20	13-14-15	20	13-14-15	20
14	14-15	11	14-15	11	14-15	11	14-15	11	14-15	11	14-15	11
15
16	16-12-13-14-15	27	16-12-13-14-15	27	16-12-13-14-15	27	16-12-13-14-15	27
17	17-11-15	20	17-11-15	20	17-11-15	20	17-11-15	20	17-11-15	20

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

Таблица 17 -- Расстояния между пунктами отправления и взаимодействия

Расстояние, км	Пункты взаимодействия
	D1	D2	D3
Пункты отправления	А1	45	24	34
	А2	17	21	15
	А3	24	28	22
	A4	31	18	20
	A5	150	126	110

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

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

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

, k=1..5, i=1..3;

Где a=9 руб.т - ставка себестоимости начальной операции на первом виде транспорта

b1=3 руб.т -- ставка себестоимости движенческой операции на первом виде транспорта

- расстояние перевозки первым видом транспорта из k-го пункта отправления в i-й пункт взаимодействия, км таблица 18

d=11 руб.т - ставка себестоимости операции перевалки с первого вида транспорта на второй в пункте взаимодействия.

Результаты расчетов по формуле 7 приведены в таблице 19.

Таблица 19 -- Себестоимость перевозки из пунктов отправления в пункты взаимодействия

Руб. тонна	Пункты взаимодействия
	D1	D2	D3
Пункты отправления	А1	155	92	122
	А2	71	83	65
	А3	92	104	86
	A4	113	74	80
	A5	470	398	350

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

, k=1..5, j=1..4;

Где -- расстояние перевозки первым видом транспорта из k-го пункта отправления в j-й пункт назначения, км таблица 19

руб.т - ставка себестоимости конечной операции на первом виде транспорта.

Результаты расчетов по формуле 8 приведены в таблице 20.

Таблица 20 -- Себестоимость перевозки из пунктов отправления в пункты назначения

Руб. тонна	Пункты назначения
	B1	B2	B3	B4
Пункты отправления	А1	353	323	287	245
	А2	401	374	341	302
	А3	449	425	395	359
	A4	497	476	449	416
	A5	545	527	503	473

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

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

Где руб.т - ставка себестоимости движенческой операции на втором виде транспорта

- расстояние перевозки вторым видом транспорта из i-го пункта взаимодействия в j-й пункт назначения, км таблица 2

руб.т - ставка себестоимости конечной операции на первом виде транспорта.

Результаты расчетов по формуле 9 приведены в таблице 21.

Таблица 21- Себестоимость перевозки из пунктов взаимодействия в пункты назначения

Руб. тонна	Пункты назначения
	B1	B2	B3	B4
Пункты взаимодействиия	D1	133	107	77	43
	D2	165	141	113	81
	D3	197	175	149	119

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

Проверим выполнение необходимого условия 2 решения задачи.

Суммарный запас груза в пунктах отправки:

A1+A2+A3+A4+A5=100+109+118+127+136=590.

Сумма заявок пунктов назначения:

1+B2+B3+B4=50+100+150+280=580

Условие выполняется: суммарный запас груза в пунктах отправления превышает сумму заявок пунктов назначения.

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

Ограничения 1 на количество груза 3, прибывающего в пункты назначения, записываются следующим образом:

Ограничения 2 на количество груза 4, прибывающего и убывающего из пунктов взаимодействия, записываются следующим образом:

Ограничения 3 на количество груза 5, перерабатываемого в пунктах взаимодействия, записываются следующим образом:

Ограничения 4 на количество груза 6, убывающего из пункта отправления, записываются следующим образом:

Решение сформулированной задачи целочисленного линейного программирования осуществляется с использованием средства "Поиск решения" пакета MS Exel методом "ветвей и границ".

На рисунке 1 представлена таблица MS Exel поиска решения, в которой находятся следующие данные:

Исходные данные:

Значения запасов груза Ak k=1..5 в пунктах отправления расположены в ячейках D9:H9; заявок на груз Bj j=1..4 в пунктах назначения -- в ячейках C10:13, перерабатывающих способностей Di i=1..3 в пунктах взаимодействия - в ячейках I9:K9

Значения расстояний перевозки из пунктов отправления в пункты назначения расположены в ячейках D10:H13, из пунктов взаимодействия в пункты назначения - в ячейках I10:K13, из пунктов отправления в пункты взаимодействия

- в ячейках D14:H16.

Проектные переменные:

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

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

Переменные k=1..5, j=1..4 - количество груза, перевозимого из k-го пункта отправления в j-й пункт назначения первым видом транспорта - расположены в ячейках D32:H35.

Расчетные данные:

Значения себестоимости k=1..5, i=1..3 перевозки 1 тонны груза из k-го пункта отправления в i-й пункт взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитанны по формуле 7 в ячейках D25:H27

Значения себестоимости j=1..4, i=1..3 перевозки 1 тонны груза, перевозимого из i-го пункта взаимодействия в j-й пункт назначения вторым видом транспорта рассчитанны по формуле 9 в ячейках I21:K24

Значения себестоимости k=1..5, j=1..4 перевозки 1 тонны груза, перевозимого из k-го пункта отправления в j-й пункт назначения первым видом транспорта рассчитанны по формуле 8 в ячейках D21:H24

Значения затрат на перевозку груза из k-го пункта отправления в i-й пункт взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитанны как произведение и в ячейках D49:H51

Значения затрат на перевозку груза из i-го пункта взаимодействия в j-й пункт назначения вторым видом транспорта рассчитанны как произведение и в ячейках I45:K48

Значения затрат на перевозку груза из k-го пункта отправления в j-й пункт назначения первым видом транспорта рассчитанны как произведение и в ячейках D45:H48

Разности между заявками пунктов назначения C10:13 и количеством груза, прибывающего в эти пункты L31:35, рассчитанны в ячейках M24:M27

Разности между количеством груза, убывающего из пунктов взаимодействия I36:K36 и количеством груза, прибывающего в эти пункты L36:38, рассчитанны в ячейках I40:K40

Разности между перерабатывающими мощностями пунктов взаимодействия I9:K9 и количеством груза, прибывающего в эти пункты I36:K36, рассчитанны в ячейках I41:K41

Разности между запасами груза в пунктах отправления D9:H9 и количеством груза, убывающего из этих пунктов D39:H39, рассчитанны в ячейках D40:H40.

Целевая функция рассчитанна в ячейке O11 по формуле 1 как сумма ячеек D45:H48; I45:H48; D49:H51.

Ограничения задаются следующим образом:

Ограничение 1: разности в ячейках M32:35 должны быть равны нулю

Ограничение 2: разности в ячейках I40:K40 должны быть равны нулю

Ограничение 3: разности в ячейках I41:K41 должны быть неотрицательны

Ограничение 4: разности в ячейках D40:H40 должны быть неотрицательны.

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

Заключение

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

Были определены:

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

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

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

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

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

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

Решение задачи проведено с применением программы MS Excel.

Все таблицы и рисунки вынесены в приложения.

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

1. Общие требования к учебным текстовым документам. СТО СГАУ 02068410-004-2007

Размещено на Allbest.ru