Взаимодействие видов транспорта при смешанных перевозках

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

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

Федеральное государственное автономное образовательное учреждение

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ

УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА

(национальный исследовательский университет)»

Факультет инженеров воздушного транспорта

Кафедра организации и управления перевозками на транспорте

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине

«Взаимодействие видов транспорта при смешанных перевозках»

Выполнил студент гр.3506

Кутейницына Е.В.

Руководитель проекта

Головнин О.К

САМАРА 2014



РЕФЕРАТ

Пояснительная записка 31 страница, 3 рисунка, 17 таблиц, 2 источника.

ПУНКТ ОТПРАВЛЕНИЯ, ПУНКТ НАЗНАЧЕНИЯ, ПУНКТ ВЗАИМОДЕЙСТВИЯ, ПРОМЕЖУТОЧНЫЕ ПУНКТЫ, ПЕРЕРАБАТЫВАЮЩАЯ СПОСОБНОСТЬ, МОЩНОСТЬ, ЗАПАСЫ, ЗАЯВКА, СТАВКА СЕБЕСТОИМОСТИ, ДВИЖЕНЧКСКАЯ ОПРЕРАЦИЯ, ОПЕРАЦИЯ ПЕРЕВАЛКИ, ЗАТРАТЫ

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



ВВЕДЕНИЕ

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

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

Необходимо определить:

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

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



1.ПОСТАНОВКА ЗАДАЧИ

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

K = 6 - количество пунктов отправления;

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

J = 2 - количество пунктов назначения;

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

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

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

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

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

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

САki - стоимость перевозки одной тонны груза из k-го пункта отправления в i-й пункт взаимодействия первым видом транспорта с учетом затрат на перевалку, ден.ед./т, k = 1...6, i = 1... 4;

СБij - стоимость перевозки одной тонны груза из i-го пункта взаимодействия в j-й пункт назначения вторым видом транспорта, ден.ед./т, i = 1... 4, j = 1... 2;

СВkj - стоимость перевозки одной тонны груза в прямом сообщении из k-го пункта отправления в j-й пункт назначения первым видом транспорта, ден.ед./т, k = 1...6, j = 1... 2;

Значения переменных Ak, Di, Bj известны и входят в состав исходных данных; значения переменных САki, СБij, СВkj рассчитываются; значения переменных Xki, Yij, Zkj определяются в ходе решения задачи.

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

С = САki Xki + СБij Yij + СВkj Zkj ? min.(1)

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

Ak ? Bj.(2)

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

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

транспорт перевозка маршрут суммарный

Yij + Zkj = Bj, j = 1... 2.(3)

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

Yij = Xki,i = 1... 4.(4)



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

Xki Di,i = 1... 4.(5)

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

Xki + Zkj Ak,k = 1... 6.(6)

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



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

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

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

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

	Пункты
Расстояние, км	назначения
	В1	В2
Пункты отправления	А1	24	60
	А2	14	30
	А3	56	17
	A4	98	68
	A5	140	119
	A6	182	170

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

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



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

	Пункты
Расстояние, км	назначения
	В1	В2
Пункты взаимодействия	D1	84	51
	D2	126	102
	D3	186	153
	D4	210	204

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

Из матрицы расстояний видно, что прямых маршрутов между пунктами Ak (k = 1...4) отправления и пунктами Di (i = 3...4) взаимодействия нет. Между пунктами Ak (k = 1...6) отправления и пунктами Di (i = 1...2) взаимодействия есть, пока его учитывать не будем. Необходимо построить кратчайшие маршруты, пролегающие через промежуточные пункты Es (s = 1...9), и определить длины этих маршрутов.

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

2.3.1 Пункт D4

Построим маршруты в узел 19 (пункт D4) из узлов 1 (пункт A1), 2 (пункт A2), 3 (пункт A3),4 (пункт A4) .

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

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



U010 = L14-19 = 9.

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

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

Пункты	А1	А2	А3	А4	А5	А6	E1	E2	E3	E4	E5	E6	E7	E8	E9	D1	D2	D3	D4
	Узлы	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
А1	1									5	16						96	33
А2	2										9	44					75	26
А3	3											9	20				36	25
А4	4												11				20	20
А5	5																80	23	48	120
А6	6																140	92	26	54
E1	7								3
E2	8							3		9				12
E3	9	5							9		11			40
E4	10	16	9							11		4			12	10
E5	11		44	9							4					9
E6	12			20	11									6		2				33
E7	13								12	40			6		9				12
E8	14										12			9		15				9
E9	15										10	9	2		15
D1	16	96	75	36	20	80	140
D2	17	33	26	25	20	23	92									7
D3	18					48	26							12		22
D4	19					120	54						33		9

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

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

L1i-j = Li-j + U0j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ? i.

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

U1i = min {L1i-j}.

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

Из узла 13	j	L13-j	U0j	L113-j	U113
13-14-19	14	9	9	18	18
13-12-19	12	6	33	39
Из узла 15	j	L15-j	U0j	L115-j	U115
15-14-19	14	15	9	24	24
15-12-19	12	2	33	35
Из узла 10	j	L10-j	U0j	L110-j	U110
10-14-12	14	12	9	21	21
Из узла 3	j	L3-j	U0j	L13-j	U13
3-12-19	12	20	33	53	53
Из узла 4	j	L4-j	U0j	L14-j	U14
4-12-19	12	11	33	44	44

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

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

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

L2i-j = Li-j + U1j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ? i.

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



U2i = min {L2i-j}.

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

Из узла 8	j	L8-j	U1j	L28-j	U28
8-13-14-19	13	12	18	30	30
8-13-12-19	13	12	39	51
Из узла 9	j	L9-j	U1j	L29-j	U29
9-13-12-19	13	40	39	79
9-13-14-19	13	40	18	58	58
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-12-19	15	10	35	45
10-15-14-19	15	10	24	34	34
10-14-19	14		21	21	21
Из узла 11	j	L11-j	U1j	L211-j	U211
11-15-14-19	15	9	24	33
11-10-14-19	10	4	21	25	25
Из узла 12	j	L12-j	U1j	L212-j	U212
12-19	12			33
12-15-14-19	15	2	24	26
12-13-14-19	13	6	18	24	24
Из узла 1	j	L1-j	U1j	L21-j	U21
1-10-14-19	10	16	21	37	37
Из узла 2	j	L2-j	U1j	L22-j	U22
2-10-14-19	10	9	21	30	30

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

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

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

L3i-j = Li-j + U2j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ? i.

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

U3i = min {L3i-j}.

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

з узла 1	j	L1-j	U2j	L31-j	U31
1- 10-14-19	10	16	21	37	37
1-9-13-14-19	9	5	58	63
1-10-15-14-19	10	16	34	50
Из узла 2	j	L2-j	U2j	L32-j	U32
2- 10-14-19	10	9	21	30	30
2-10-15-14-19	10	9	34	43
2-11-10-14-19	11	44	25	69
Из узла 3	j	L3-j	U2j	L33-j	U33
3-12-19	12	20	33	53
3-11-10-14-19	11	9	25	34	34
Из узла 4	j	L4-j	U2j	L34-j	U34
4-12-19	12	11	33	44
4-12-15-14-19	12	11	26	37
4-12-13-14-19	12	11	24	35	35
Из узла 8	j	L8-j	U1j	L28-j	U28
8-13-14-19	13	12	18	30	30
8-13-12-19	13	12	39	51
Из узла 9	j	L9-j	U1j	L29-j	U29
9-13-12-19	13	40	39	79
9-13-14-19	13	40	18	58	58
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-14-19	15	10	24	34
10-14-19	14		21	21	21
Из узла 11	j	L11-j	U1j	L211-j	U211
11-15-14-19	15	9	24	33
11-10-14-19	10	4	21	25	25
Из узла 12	j	L12-j	U1j	L212-j	U212
12-13-14-19	13	6	18	24	24



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

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

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

L4i-j = Li-j + U3j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ? i.

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

U4i = min {L4i-j}.

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

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

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

J	k=0	k=1	K=2	k=3	k=4
	Маршрут	U0j	Маршрут	U1j	Маршрут	U2j	Маршрут	U3j	Маршрут	U4j
1					1-10-14-19	37	1-10-14-19	37	1-10-14-19	37
2					2-10-14-19	30	2-10-14-19	30	2-10-14-19	30
3			3-12-19	53	3-12-19	53	3-11-10-14-19	34	3-11-10-14-19	34
4			4-12-19	44	4-12-19	44	4-12-13-14-19	35	4-12-13-14-19	35
5
6
7
8					8-13-14-19	30	8-13-14-19	30	8-13-14-19	30
9					9-13-14-19	58	9-13-14-19	58	9-13-14-19	58
10			10-14-19	21	10-14-19	21	10-14-19	21	10-14-19	21
11					11-10-14-19	25	11-10-14-19	25	11-10-14-19	25
12	12-19	33	12-19	33	12-13-14-19	24	12-13-14-19	24	12-13-14-19	24
13			13-14-19	18	13-14-19	18	13-14-19	18	13-14-19	18
14	14-19	9	14-19	9	14-19	9	14-19	9	14-19	9
15			15-14-19	24	15-14-19	24	15-14-19	24	15-14-19	24
16
17
18

Искомые кратчайшие маршруты в узел 19 (пункт D4)

из узла 1 (пункт А1): 1-10-14-19 (А1-Е4-Е8-D4); расстояние перевозки 37;

из узла 2 (пункт А2): 2-10-14-19 (A2-E4-E8-D4); расстояние перевозки 30;

из узла 3 (пункт А3): 3-11-10-14-19 (A3-E5-E4-E8-D4); расстояние перевозки34;

из узла 4 (пункт А4 ): 4-12-13-14-19 (A4-E6-E7-E8-D4 ); расстояние перевозки 35.

2.3.2 Пункт D1

Построим маршруты в узел 18 (пункт D3) из узлов 1 (пункт A1), 2 (пункт A2), 3 (пункт A3),4 (пуект A4) .

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

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

U08 = L13-18 = 12;

U09 = L15-18 = 22.

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

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

Определим длину L1i-j возможного маршрута из i-го узла в узел 18 (пункт D3), проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния Li-j от i-го узла до j-го узла и длины U0j прямого маршрута из этого узла в узел 18 (пункт D3):



L1i-j = Li-j + U0j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ? 18, j ? 18, j ? i.

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

U1i = min {L1i-j}.

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

Из узла 14	j	L14-j	U0j	L114-j	U114
14- 13-18	13	9	12	21	21
14-15-18	15	15	22	37
Из узла 17	j	L17-j	U0j	L117-j	U117
17- 15-18	15	7	22	29	29
Из узла 12	j	L6-j	U0j	L16-j	U16
12-13-18	13	6	12	18	18
12-15-18	15	2	22	24
Из узла 11	j	L11-j	U0j	L111-j	U111
11-15-18	15	9	22	31	31
Из узла 9	j	L9-j	U0j	L19-j	U19
9-13-18	13	40	12	52	52
Из узла 10	j	L10-j	U0j	L110-j	U110
10-15-18	15	10	22	32	32
Из узла 8	j	L8-j	U0j	L18-j	U18
8-13-18	13	12	12	24	24

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

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

Определим длину L2i-j возможного маршрута из i-го узла в узел 18 (пункт D3), проходящего через j-й узел, с числом промежуточных узлов не более двух как сумму расстояния Li-j от i-го узла до j-го узла и длины U1j маршрута из этого узла в узел 18 (пункт D3) с числом узлов не более одного:



L2i-j = Li-j + U1j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ? 18, j ? 18, j ? i.

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

U2i = min {L2i-j}.

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

Из узла 1	j	L1-j	U1j	L21-j	U21
1-10-15-18	10	16	32	48	48
1-9-13-18	9	5	52	57
Из узла 2	j	L2-j	U1j	L22-j	U22
2-11-15-18	11	44	31	75
2-10-15-18	10	9	32	41	41
Из узла 3	j	L3-j	U1j	L23-j	U23
3-12-13-18	12	20	18	38	38
3-11-15-18	11	9	31	40
Из узла 4	j	L4-j	U1j	L24-j	U24
4-12-13-18	12	11	18	29	29
Из узла 7	j	L7-j	U1j	L27-j	U27
7-8-13-18	8	3	24	27	27
Из узла 8	j	L8-j	U1j	L28-j	U28
8-9-13-18	9	9	52	61
8-13-18	13	12	12	24	24
Из узла 9	j	L9-j	U1j	L29-j	U29
9-10-15-18	10	11	32	43

Маршруты в узел 18 с числом промежуточных узлов не более двух

9-13-18	13	40	12	52
9-8-13-18	9	24	33	33	33
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-18	15	10	22	32	32
10-11-15-18	11	4	31	34
10-14-13-18	14	12	21	33
Из узла 15	j	L15-j	U1j	L215-j	U215
15-12-13-18	12	2	18	20	20
Из узла 14	j	L14-j	U1j	L214-j	U214
14-13-18	13	9	12	21	21
Из узла 12	j	L12-j	U1j	L212-j	U212
12-13-18	13	6	12	18	18
Из узла 11	j	L11-j	U1j	L211-j	U211
11-15-18	15	9	22	31	31

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

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

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

L3i-j = Li-j + U2j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ? 18, j ? 18, j ? i.

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

U3i= min {L3i-j

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

Из узла 1	j	L1-j	U2j	L31-j	U31
1-10-15-18	10	16	32	48
1-9-8-13-18	9	5	33	38	38
Из узла 2	j	L2-j	U2j	L32-j	U32
2-10-15-18	10	9	32	41	41
2-10-14-13-18	10	9	33	42
Из узла 3	j	L2-j	U2j	L32-j	U32
3-12-13-18	12	20	18	38	38
Из узла 4	j	L4-j	U2j	L34-j	U34
4-12-13-18	12	11	18	29	29
Из узла 7	j	L7-j	U1j	L27-j	U27
7-8-13-18	8	3	24	27	27
Из узла 8	j	L8-j	U1j	L28-j	U28
8-13-18	13	12	12	24	24
Из узла 9	j	L9-j	U1j	L29-j	U29
9-8-13-18	9	24	33	33	33
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-12-13-18	15	10	20	30	30
10-15-18	15	10	22	32
Из узла 11	j	L11-j	U1j	L211-j	U211

Маршруты в узел 18 с числом промежуточных узлов не более трех

11-15-18	15	9	22	31	31
11-10-14-13-18	10	4	33	37
Из узла 12	j	L12-j	U1j	L212-j	U212
12-13-18	13	6	12	18	18
Из узла 15	j	L15-j	U1j	L215-j	U215
15-12-13-18	12	2	18	20	20

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

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

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

L4i-j = Li-j + U3j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ? 18, j ? 18, j ? i.

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

U4i = min {L4i-j}.

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

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

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

J	k=0	k=1	K=2	k=3	k=4
	Маршрут	U0j	Маршрут	U1j	Маршрут	U2j	Маршрут	U3j	Маршрут	U4j
1					1-10-15-18	48	1-9-8-13-18	38	1-9-8-13-18	38
2					2-10-15-18	41	2-10-15-18	41	2-10-15-12-13-18	39
3					3-12-13-18	38	3-12-13-18	38	3-12-13-18	38
4					4-12-13-18	29	4-12-13-18	29	4-12-13-18	29
5
6
7					7-8-13-18	27	7-8-13-18	27	7-8-13-18	27
8			8-13-18	24	8-13-18	24	8-13-18	24	8-13-18	24
9			9-13-18	52	9-8-13-18	33	9-8-13-18	33	9-8-13-18	33
10			10-15-18	32	10-15-18	32	10-15-12-13-18	30	10-15-12-13-18	30
11			11-15-18	31	11-15-18	31	11-15-18	31	11-15-18	31
12			12-13-18	18	12-13-18	18	12-13-18	18	12-13-18	18
13	13-18	12	13-18	12	13-18	12	13-18	12	13-18	12
14			14-13-18	21	14-13-18	21	14-13-18	21	14-13-18	21
15	15-18	22	15-18	22	15-12-13-18	20	15-12-13-18	20	15-12-13-18	20

Искомые кратчайшие маршруты в узел 18 (пункт D3)

из узла 1 (пункт А1): 1-9-8-13-18 (А1-Е3-Е2- Е7-D3); расстояние перевозки 38;

из узла 2 (пункт А2): 2-10-15-12-13-18 (A2-E4-E9-E6- E7-D3); расстояние перевозки 39;

из узла 3 (пункт А3): 3-12-13-18 (A3-E6-E7-D3); расстояние перевозки 38;

из узла 4 (пункт А4): 4-12-13-18 (A4-E6-E7-D3); расстояние перевозки 29.

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

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

	Пункты
Расстояние, км	взаимодействия
	D1	D2	D3	D4
Пункт отправления	A1	96	33	38	37
	A2	75	26	39	30
	A3	36	25	38	34
	A4	20	20	29	35
	A5	80	23	48	120
	A6	140	92	26	54

3. ОПРЕДЕЛЕНИЕ СТОИМОСТИ ПЕРЕВОЗКИ

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

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

СВkj = a + b1 LВkj + c1, k = 1...6, j = 1... 2, (7)

где a = 20 ден.ед./т - ставка себестоимости начальной операции на первом виде транспорта;

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

LВkj - расстояние перевозки первым видом транспорта из k-го пункта отправления в j-й пункт назначения, км (таблица 1);

с1 = 18 ден.ед./т.- ставка себестоимости конечной операции на первом виде транспорта.

Рассмотрим детально определение стоимости перевозки первым видом транспорта одной тонны груза в прямом сообщении из 1-го пункта отправления в 1-ый пункт назначения. По формуле (7):

СВ11 = a + b1 LВ11 + c1 = 20 + 5 · 24 + 18 = 158 ден.ед./т.

Для остальных пунктов отправления и пунктов назначения расчет проводится аналогично. Результаты расчетов приведены в таблице 13.



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

СВkj, ден.ед./т	пункт назначения
	B1	B2
пункт отправления	A1	158	338
	A2	108	188
	A3	318	123
	A4	528	378
	A5	738	633
	A6	948	888

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

САki = a + b1 LАki + d,k = 1... 6, i = 1...4;(8)

где LАki - расстояние перевозки первым видом транспорта из k-го пункта отправления в i-ый пункт взаимодействия, км (таблица 12);

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

Рассмотрим детально определение стоимости перевозки первым видом транспорта одной тонны груза из 1-го пункта отправления в 1-ый пункт взаимодействия с учетом затрат на перевалку. По формуле (8)

СА11 = a + b1 LА11 + d = 20 + 5 · 96 + 26 = 526 ден.ед./т.

Для остальных пунктов отправления и пунктов взаимодействия расчет проводится аналогично. Результаты расчетов приведены в таблице 14.



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

САki, ден.ед./т	Пункты взаимодействия
	D1	D2	D3	D4
Пункты отправления	A1	526	211	236	231
	A2	421	176	241	196
	A3	226	171	236	216
	A4	146	146	191	221
	A5	446	161	286	646
	A6	746	506	176	316

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

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

СБij = b2 LБij + с2, i = 1...4, j = 1...2,(9)

где b2 = 2 ден.ед./т км - ставка себестоимости движенческой операции на втором виде транспорта;

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

с2 = 12 ден.ед./т. - ставка себестоимости конечной операции на втором виде транспорта.

Рассмотрим детально определение стоимости перевозки вторым видом транспорта одной тонны груза из 1-го пункта взаимодействия в 1-ый пункт назначения. По формуле (9)

СБ11 = b2 LБ11 + с2 = 2 · 84 + 12 = 180 ден.ед./т.



Для остальных пунктов взаимодействия и пунктов назначения расчет проводится аналогично. Результаты расчетов приведены в таблице 15.

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

СБij, ден.ед./т	пункт назначения
	B1	B2
пункт взаимодействия	D1	180	114
	D2	264	216
	D3	384	318
	D4	432	420



4. РЕШЕНИЕ ЗАДАЧИ

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

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

A1 + A2 + A3 + A4 + A5 + A6 = 70+75+80+85+90+95= 495 т.

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

B1 + B2 = 100+370 = 470 т.

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

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

С = 526X11 + 421X21 + 226X31 + 146X41+ 446X51 + 746X61 +211X12 + 176X22 + 171X32 + 146X42+ 161X52 + 506X62+236X13 + 241X23 + 236X33 + 191X43+ 286X53 + 176X63+231X14 + 196X24 + 216X34 + 221X44+ 646X54 + 316X64+ 180Y11 + 264Y12 + 384Y13 + 432Y14 + 114Y21 + 216Y22 + 318Y23 + 420Y24 + 158Z11 + 338Z12 + 108Z21 + 188Z22 + 318Z31 + 123Z32 + 528Z41 + 378Z42 + 738Z51 + 633Z52 + 948Z61 + 888Z62 ? min.

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

Z11 + Z12 + Z13+ Z14 + Z15 + Z16 + Y12 + Y11 + Y13 + Y14 =100,

Z21 +Z22 + Z23 + Z24 + Z25 + Z26 + Y21 + Y22 + Y23 + Y24 = 370.

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

Y11 + Y12 = X11 + X21 + X31+X41 + X51 + X61,

Y21 + Y22 = X12 + X22 + X32+X42 + X52 + X62,

Y31 + Y32 = X13 + X23 + X33+X43 + X53 + X63,

Y41 + Y42 = X14 + X24 + X34+X44 + X54 + X64.

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

X11 + X21 + X31+X41 + X51 + X61 40,

X12 + X22 + X32+X42 + X52 + X62 45,

X13 + X23 + X33+X43 + X53 + X63

X14 + X24 + X34+X44 + X54 + X64 .

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

X11 + X12 + X13 + X14 + Z11 + Z12 70,

X21 + X22 + X23 + X24 + Z21 + Z22 75,

X31 + X32 + X33 + X34 + Z31 + Z32 80,

X41 + X42 + X43 + X44 + Z41 + Z42 85,

X51 + X52 + X53 + X54+ Z51 + Z52 90,

X61 + X62 + X63 + X64+ Z61 + Z62 95.

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

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

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

значения ставок себестоимости расположены в ячейках:

начальной операции a на первом виде транспорта - в ячейке N3,

операции перевалки d с первого вида транспорта на второй - в ячейке N10,

движенческой операции b1 на первом виде транспорта - в ячейке N4,

движенческой операции b2 на втором виде транспорта - в ячейке N14,

конечной операции с1 на первом виде транспорта - в ячейке N5 ,

конечной операции с2 на втором виде транспорта - в ячейке N15;

значения запасов груза Ak (k = 1... 6) в пунктах отправления расположены в ячейках F3:F8,

заявок на груз Вj (j = 1... 2) в пунктах назначения - в ячейках G9;K9,

перерабатывающих способностей Di (i = 1...4) в пунктах взаимодействия - в ячейках B9:E9;

значения расстояний Lkj перевозки из пунктов отправления в пункты назначения расположены в ячейках J3:K8,

Lij из пунктов взаимодействия в пункты назначения- в ячейках S3:T6,

Lki из пунктов отправления в пункты взаимодействия Lki - в ячейках B3:E8.

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

переменные Xki, (k = 1...6, i = 1... 4) - количество груза, перевозимого из k-го пункта отправления в i-ый пункт взаимодействия первым видом транспорта, - расположены в ячейках C28:H31;

переменные Yij, (i = 1... 4, j = 1... 2) - количество груза, перевозимого из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта, - расположены в ячейках I26:L27;

переменные Zkj, (k = 1...6, j = 1... 2) - количество груза, перевозимого в прямом сообщении из k-го пункта отправления в j-ый пункт назначения первым видом транспорта, - расположены в ячейках C26:H27.

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

значения стоимости САki (k = 1...6, i = 1... 4) перевозки одной тонны груза из k-го пункта отправления в i-ый пункт взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитаны по формуле (8) в ячейках B14:E19;

значения стоимости СБij (i = 1... 4, j = 1... 2) перевозки одной тонны груза из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта рассчитаны по формуле (9) в ячейках S14:T17;

значения стоимости СВkj (k = 1...6, j = 1... 2) перевозки одной тонны груза в прямом сообщении из k-го пункта отправления в j-ый пункт назначения первым видом транспорта рассчитаны по формуле (7) в ячейках J14:K19;

значения затрат на перевозку груза из k-го пункта отправления в i-ый пункт взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитаны как произведение САki и Xki в ячейках C39:H42;

значения затрат на перевозку груза из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта рассчитаны как произведение СБij и Yij в ячейках I37:L38;

значения затрат на перевозку груза в прямом сообщении из k-го пункта отправления в j-ый пункт назначения первым видом транспорта рассчитаны как произведение СВkj и Zkj в ячейках C37:H38;

разности между заявками пунктов назначения и количеством груза, прибывающего в эти пункты, рассчитаны в ячейках N26:N27;

разности между количеством груза, убывающего из пунктов взаимодействия, и количеством груза, прибывающего в эти пункты, рассчитаны в ячейках I32:L32;

разности между перерабатывающими мощностями пунктов взаимодействия и количеством груза, прибывающего в эти пункты, рассчитаны в ячейках I34:L34;

разности между запасами груза в пунктах отправлении и количеством груза, убывающего из этих пунктов, рассчитаны в ячейках C33:H33.

4) Целевая функция рассчитана в ячейке N37 по формуле (1) как сумма ячеек C39:H42; I37:L38; C37:H38.

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

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

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

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

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

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

Рисунок 1 - Вид таблицы MS Excel решения задачи

Рисунок 2 - Вид таблицы MS Excel расчет целевой функции

Первым видом транспорта из пункта отправления A1 груз доставляется в пункт назначения B1 (70т) и в пункты взаимодействия груз не доставляется. Из пункта отправления A2 груз доставляется в пункты назначения B1 (30т) и B2 (45т), в пункты взаимодействия из пункта A2 груз не доставляется. Из пункта отправления A3 груз доставляется в пункт назначения B2 (45т), в пункты взаимодействия из пункта A3 груз не доставляется. Из пункта отправления А4 груз доставляется в пункт назначения В2 (45т) и в пункт взаимодействия D1 (40т). Из пункта отправления А5 груз доставляется в пункт назначения B2 (45т) и в пункт взаимодействия D2 (45т). Из пункта отправления A6 груз доставляется только в пункты взаимодействия D3 (55т) и D4 (15т). (таблица 16).

Таблица 16 - Доставка груза первым видом транспорта

Перевозимый груз, т	Пункты отправления
	А1	А2	А3	A4	A5	A6
Пун. Назнач	В1	70	30
	В2		45	80	45	45
Пункты взаимодействия	D1				40
	D2					45
	D3						55
	D4						15
Итого	70	75	80	85	90	70

Вторым видом транспорта груз доставляется из пункта взаимодействия D2 в пункты назначения B1 (40 т), B2 (45 т), В3 (55т) и В4 (15 т), из пункта взаимодействия D1 груз не доставляется (таблица 17).

Таблица 17 - Доставка груза вторым видом транспорта

Перевозимый груз, т	Пункты взаимодействия
	D1	D2	D3	D4
Пункты назначения	В1
	В2	40	45	55	15
	итого	40	45	55	15

На рисунке 3 показана схема распределения грузопотоков по маршрутам перевозки от пунктов.

Рисунок 3 - Схема распределения грузопотоков по маршрутам перевозки

Таким образом, в пункт B1 весь груз (100 т) доставляется первым видом транспорта из пункта отправления A1, А2; в пункт B2 - первым видом транспорта из пункта отправления А2 (45 т), А4 (45т), А5 (45т), А3 (80т) и вторым видом транспорта из пункта взаимодействия D1 (40 т), D2(45 т), D3 (55т) и D4 (15т), таким образом сумма перевезенного груза в пункт назначения В2 (370 т). Ни в одном пункте отправления груза не остается, заявка выполнена полностью.



ЗАКЛЮЧЕНИЕ

В данной работе был найден оптимальный план перевозки с минимальными расстояниями и затратами. Использовалось два вида транспорта со своими стоимостными характеристиками. С помощью функции MC Excel «Поиск решения» нашли минимальные затраты и то количество груза которое необходимо перевезти наиболее удобным способом.

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