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

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

Содержание

Введение

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

1. Определение кратчайшего расстояния между ГО и ГП

1.1 Метод Хичкока

1.2 Метод Моди

2. Оптимизация транспортной работы в Excel

3. Планирование развозочных маршрутов методом Кларка-Райта

Заключение

Библиографический список

Введение

грузоотправитель транспортный кларк райт

Целью курсовой работы является оптимальное закрепление грузоотправителей (ГО) за грузополучателями (ГП) и оптимальное распределение груза для минимизации транспортной работы.

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

Линейное программирование интенсивно разрабатывалось во второй половине XX века. Основные идеи линейного программирования появились во время второй мировой войны, в связи с поиском оптимальных стратегий и проведения военных операций. С тех пор они нашли применение в промышленности, торговли и т.д.

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

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

Транспортная задача применяется не только на транспорте, но и в других отраслях экономики.

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

Часть 1.

В городе N автотранспортное предприятие занимается перевозкой кирпича с заводов силикатного кирпича (Аn) на строительные площадки (Бn).

Потребности строительных площадок в кирпиче и возможности заводов по отгрузке приводятся в таблице 1.



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

Таблица №1

	А1	А2	А3	А4	Б1	Б2	Б3	Б4	Б5	Б6	Б7
часть 1	60	210	110	40	60	40	50	90	60	60	60
часть 2	63	9	8	7	5	3	5	8	8	6	4

Необходимо:

По модели транспортной сети и определить кратчайшие расстояния между грузоотправителями (ГО) и грузополучателями (ГП).

Оптимально закрепить ГП за ГО (минимизировать транспортную работу) используя:

- Метод Хичкока;

- Метод Моди

Часть 2.

С товарного склада (А1) необходимо доставить по предприятиям - грузополучателям (А2, А3, А4, Б1, …Б7) пакетированный груз (крепеж, mбр=100 кг.). Грузовместимость используемых автомобилей 1000 кг (10 пакетов).

Необходимо:

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

1. Определение кратчайшего расстояния между ГО и ГП

Метод потенциалов

Метод основан на приписывании вершинам временных пометок, которые дают верхнюю границу длины от начальной вершины до этой вершины.

Алгоритм определения кратчайших расстояний методом потенциалов:

1. Начальной точке сети, за которую может быть принята любая из вершин, присваивают потенциал, равный нулю (vi = 0).

2. Определяют потенциалы соседних с начальной точкой вершин сети по формуле

vj = vi + lij,

где:

vi - потенциал предшествующей (соседней) вершины;

lij - длина звена, соединяющего вершины i и j.

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

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

Кратчайшие расстояния от точки А1.



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

А1 - А1 = 0

А1 - A2 = 7

А1 - А3 = 11

А1 - А4 = 8

А1 - Б1 = 7

А1 - Б2 = 14

А1 - Б3 = 5

А1 - Б4 = 9

А1 - Б5 = 5

А1 - Б6 = 9

А1 - Б7 = 4

Полученная таблица кратчайших расстояний.

Таблица № 2

	А1	А2	А3	А4	Б1	Б2	Б3	Б4	Б5	Б6	Б7
А1	-	7	11	8	7	14	5	9	5	9	4
А2	7	-	4	7	5	7	4	2	7	2	3
А3	11	4	-	8	7	4	8	2	9	4	7
А4	15	11	8	-	15	8	7	10	17	12	14
Б1	7	5	7	12	-	11	9	5	2	3	9
Б2	14	6	2	8	12	-	9	4	11	6	10
Б3	8	4	8	3	9	9	-	6	11	6	7
Б4	9	2	2	9	5	6	6	-	7	2	5
Б5	5	7	9	13	2	13	10	7	-	5	8
Б6	9	2	4	9	3	8	6	2	5	-	5
Б7	4	3	7	10	8	10	7	5	8	5	-

Построение опорного плана методом двойного предпочтения.

Сначала просматривают все строки матрицы и в каждой из них отмечают элемент с минимальной стоимостью (*). Затем просматривают столбцы и также отмечают в них элемент с минимальной стоимостью (*). В клетки с двумя знаками (**) помещают максимально возможные перевозки.

L(x) = 60*5+4*0+60*5+10*4+20*2+60*2+60*3+40*4+70*2+40*7=1560 т*км

Таблица № 3

ГО	ГП	вывоз, т
	Б1	Б2	Б3	Б4	Б5	Б6	Б7
А1		7		14		5		9		5		9		4	60
						60			0
А2		5		7		4		2		7		2		3	210
	60				10		20			60		60
А3		7	40	4		8		2		9		4		7	110
							70
А4		15		8		7		10		17		12		14	40
					40
ввоз, т	60	40	50	90	60	60	60

1.1 Метод Хичкока

Алгоритм определения оптимальности: во всех загруженных клетках получаем нулевой потенциал, для этого по строчкам и столбцам таблицы, ко всем расстояниям, поставленным в верхних правых углах загруженных клеток, прибавляем такие числа, которые в сумме с расстояниями дают 0. Т. е. расстояние каждой загруженной клетки должно быть равно обратному значению суммы потенциалов строки и столбца, в которой находится данная клетка.

Определяя потенциалы для всех свободных клеток, находят для каждой свободной клетки сумму указанного в ней расстояния с ранее полученными по загруженным клеткам потенциалами строки и столбца

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

Наибольшая потенциальная клетка получает загрузку, чтобы это сделать, необходимо перераспределить груз в таблице. Это выполняется следующим образом: количество загруженных клеток в предыдущем шаге должно равняться m+n-1, если количество загруженных клеток менее m+n-1, то недостающее число клеток получают путем загрузки соответствующего количества клеток нулями. Клетка, в которой поставлена загрузка равная 0, считается загруженной. Для наиболее потенциальной клетки строится контур. Строится контур так, чтобы все углы кроме одного располагались в загруженных клетках, а один единственный находился в свободной наиболее потенциальной клетке. При соблюдении этого правила для каждой свободной клетки можно построить только один единственный контур. Определяются положительные и отрицательные углы контура, считается, что первый положительный угол лежит в свободной клетке, для которой построен контур, отрицательные и положительные углы чередуются, и их количество должно быть равно. Выявляется наименее загруженная клетка, занятая отрицательным углом в нашем контуре. Количество груза указанное в этой клетке отнимается из всех клеток с отрицательными углами и прибавляется во все клетки с положительными углами. В результате одна или несколько ранее загруженных клеток становятся свободными, а наиболее потенциальная клетка становится загруженной.

Таблица № 4

ГО	ГП	вывоз,т	потенциал
	Б1	Б2	Б3	Б4	Б5	Б6	Б7
А1	1	7	9	14	0	5	6	9		5		9		4	60	0
						60			0
А2		5	3	7		4		2	3	7		2		3	210	1
	60				10		20			60		60
А3	2	7		4	4	8		2	5	9	2	4	4	7	110	1
			40				70
А4	7	15	1	8		7	5	10	10	17	7	12	8	14	40	-2
					40
ввоз, т	60	40	50	90	60	60	60
потенциал	-6	-5	-5	-3	-5	-3	-4

L(x) = 60*5+4*0+60*5+10*4+20*2+60*2+60*3+40*4+70*2+40*7=1560 т*км

Условие m+n-1 соблюдается- 7+4-1=10.

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

1.2 Метод Моди

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

Находим потенциалы для всех строчек и столбцов таблицы. Если число загруженных клеток будет меньше, чем условие m+n-1, то потенциал для некоторых строк и столбцов будет невозможно найти, недостающее количество клеток загружаем нулями. Загружать нулями, следует клетки, которые лежат на пересечении строк и столбцов, не имеющих потенциалов, со строками и столбцами для которых потенциалы уже определены. При этом наиболее целесообразно выбирать из этих клеток такие, в которых имеются наименьшие расстояния. После того как потенциалы всех строк и столбцов определены, определяется их сумма для каждой свободной клетки, сумма потенциалов указывается в верхнем левом углу свободной клетки. При решении задач на минимум оптимальный вариант получится в том случае, когда в каждой свободной клетке сумма потенциалов для этой клетке не превышает указанного в ней расстояния.

Если оптимальное решение не получено, то выявляется наиболее потенциальная клетка. Наиболее потенциальной клеткой при решении задач на минимум является та клетка, у которой имеется наибольшая разность между суммой потенциалов и указанного в ней расстояния. Далее строится контур для этой клетки и по данному контуру производится перераспределение груза. Действие повторяется до тех пор, пока не будет найден оптимальный вариант.

Таблица № 5

ГО	ГП	вывоз,т	потенциал
	Б1	Б2	Б3	Б4	Б5	Б6	Б7
А1	6	7	5	14	5	5	3	9		5	3	9		4	60	0
						60			0
А2		5	4	7		4		2	4	7		2		3	210	-1
	60				10		20				60		60
А3	5	7		4	4	8		2	4	9	2	4	3	7	110	-1
			40				70
А4	4	15	3	8		7	1	10	3	17	1	12	2	14	40	-2
					40
ввоз, т	60	40	50	90	60	60	60
потенциал	6	5	5	3	5	3	4

Условие m+n-1 соблюдается- 7+4-1=10

L(x) = 60*5+4*0+60*5+10*4+20*2+60*2+60*3+40*4+70*2+40*7=1560 т*км

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

2. Оптимизация транспортной работы в Excel

Чтобы минимизировать транспортные расходы, используем функцию « Поиск решения » в Excel.

Ограничения по заказам ( по ввозу), ограничения по запасам ( по вывозу), ограничение по плановым объёмам ( план не может быть отрицательным).

Рисунок 1. Поиск оптимального решения

Рисунок 2. Поиск решения

Рисунок 3 Поиск решения

Рисунок 4 Результат решения

Результатом решения является план (заполненные плановые ячейки), транспортные расходы (заполненная целевая ячейка), объёмы вывоза от ГО и ввоза ГП (заполненные ячейки с формулами ограничений).

3. Планирование развозочных маршрутов методом Кларка-Райта

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

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

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

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

Для решения задач маршрутизации перевозок мелкопартийных грузов существует 2 группы методов:

- получение точных результатов

- получение приблизительных результатов.

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

Идея метода Кларка-Райта заключается в том, что маятниковые маршруты, исходящие из одного пункта ГО, попарно группируются в кольцевые маршруты по принципу получения на каждом максимальных «выигрыша» от этого объединения.

«Выигрыш» от объединения пунктов i и j маршрутов определяется по формуле

,

где li,o--кратчайшее расстояние от пункта i до ГО, lo,j-- кратчайшее расстояние от ГО до j пункта, li,j-- кратчайшее расстояние от пункта i до пункта j.

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

По оценке всех возможных комбинаций объединений пунктов i и j в пары (в таблице оценок), в первую очередь включают в маршрут пару вершин, имеющих максимальное значение в «выигрыше». При следующем шаге подключение производится либо на входе в маршрут (в точке i), либо на выходе из него (в точке j).

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

При построении маршрута осуществляется проверка на удовлетворение ограничения (по грузовместимости автомобиля, времени нахождения в наряде, сроков доставки груза и т.д.). Формирование маршрута заканчивается при исчерпании списка вершин или отсутствия возможности подключения пункта без нарушения заданных ограничений. В последнем случае приступают к построению очередного маршрута. Процедура повторяется до получения всего плана маршрутизации.

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

Пример заполнения таблицы «выигрышей»:

f 1-2=7+11-4=11, f 1-6=7+8-4=11,

f 1-3=7+15-7=15, f 1-7=7+9-2=14,

f 1-4=7+7-5=9, f 1-8=7+5-7=5,

f 1-5=7+14-7=14, f 1-9=7+9-2=14,

f 1-10=7+5-3=9.

Таблица «выигрышей»

объём груза	ГП	А2	А3	А4	Б1	Б2	Б3	Б4	Б5	Б6	Б7
9	А2	-	14	15	9	14	11	14	5	14	9
8	А3	14	-	18	11	21	11	18	7	16	8
7	А4	15	18	-	7	21	16	14	3	12	5
5	Б1	9	11	7	-	10	6	11	10	13	2
3	Б2	14	21	21	10	-	13	19	8	17	8
5	Б3	11	11	16	6	13	-	11	2	11	5
8	Б4	14	18	14	11	19	11	-	7	16	8
8	Б5	5	7	3	10	8	2	7	-	9	1
6	Б6	14	16	12	13	17	11	16	9	-	8
4	Б7	9	8	5	2	8	5	8	1	8	-

Выбираем наибольшее значение из таблицы «выигрышей», равное 14 из ячеек Б2Б45. Потребность в грузе этих ГП Б2=3 пакета, А4=15 пакетов. У Б2 вывоз составит 3 пакета, у А4- 7 пакетов, так как грузоподъёмность автомобиля равна 10 пакетам. Получим:

М1: ГО- Б2-А4-ГО (3+7)

М2: ГО-А3-Б4-ГО (6+4)

М3: ГО-Б4-Б6-ГО (4+6)

М4: ГО-А2-Б3-ГО (5+5)

М5: ГО-А2-А3-Б7- ГО (4+2+4)

М6: ГО-Б1-Б5-ГО (5+5)

М7:ГО-Б5-ГО (3)

Суммарный пробег по маятниковому маршруту составляет

Lм=7+11+15+7+14+8+9+5+9+4=178 км

Суммарный пробег по сформированным кольцевым маршрутам составляет 144 км. Пробег автомобилей сократился на 34 км.

Заключение

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

Суммарный пробег по сформированным кольцевым маршрутам составил 144 км.

Библиографический список

1. Багандов К.А. Методические указания к практическим занятиям «Экономико-математические модели в управлении транспортом»; ТГТУ, 2006

2. Банди Б. «Основы линейного программирования», М., Радиосвязь, 1989

3. Геронимус Б.Л., Царфин Л.В. « Экономико-математические методы на автомобильном транспорте», М., Транспорт, 1988

4. Громов Н.Н, Персианов В.Л. «Управление на транспорте», М., Транспорт, 1990

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

...