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

Курсовая работа

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

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

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

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

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

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

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

Часть 1.

n ) на строительные площадки (Бn).

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

Таблица № 1

А1А2А3А4Б1Б2Б3Б4Б5Б6Б7часть 11008012070608010030402040часть 2 472244387764

Необходимо:

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

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

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

  • Метод Фогеля;

Метод Моди

Часть 2.

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

Грузовместимость используемых автомобилей 1000 кг (10 пакетов).

Необходимо:

1 ) грузополучателям. Потребности в грузе приводятся в таблице 1.

линейное программирование грузоперевозка

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

5 стр., 2147 слов

Транспортная задача

... ”. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что ...

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

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

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

vi = 0

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

j = vi + lij,

где:

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

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

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

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

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

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

А1 — А1 = 0

А1 — A2 = 4

А1 — А3 = 5 + 7 = 12

А1 — А4 = 5 + 4 = 9

А1 — Б1 = 5 + 3 = 8

А1 — Б2 = 4 + 8 = 12

А1 — Б3 = 4 + 8 + 4 = 16

А1 — Б4 = 4

А1 — Б5 = 5 + 4 = 9

А1 — Б6 = 7

А1 — Б7 = 5

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

Таблица № 2

А1А2А3А4Б1Б2Б3Б4Б5Б6Б7А1-4129841612975А24-107481281157А31210-1314571214516А49713-58911 5124Б184145-121410793Б2485812-4131198Б3161249144-16171213Б4 1281211101316-547Б591114 5711175-94Б675512991249-11Б75716438137411-

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

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

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

В клетки с двумя знаками (**) помещают максимально возможные перевозки.

L (x) = 4*60+ 5*80+ 16*80+4*20 +12*20+11*10 +14*20+5*20+5*20 +4*40=2990 т*км

Таблица № 3

ГОГПвывоз, т Б1 Б2Б3Б4Б5Б6Б7 А1 8 4 16 **12 9 7 51008020 А2**48 12811 *578060 20 А3 14**5*412 14 **5 17120 8020 20 А4 5 89 11 *512 **470 10 20 40ввоз, т608010030402040370

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

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

5 стр., 2453 слов

Транспорт через мембрану клетки

... кальция. Концентрация АТФаз в плазматической мембране нейронов и мышечных клеток довольно низка, поэтому эффективность этой транспортной системы не слишком высока. Тем не менее, с задачей ... порядка +50 мВ. Таким образом, существует большой электрохимический потенциал, стремящийся перенести ионы натрия внутрь клетки. Такой перенос осуществляется при помощи многочисленных механизмов. Кроме того, ...

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

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

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

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

Таблица № 4

Б1Б2Б3Б4Б5Б6Б7

L (x) =50*4+10*5+80*4+0*5+100*4+30*8+40*5+20*5+20*5+20*4=1690 т*км

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

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

1.2 Метод аппроксимации Фогеля

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

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

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

23 стр., 11127 слов

Организация перевозок скоропортящихся грузов на заданном направлении

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

В соответствии с выше указанным алгоритмом выполняется загрузка клеток с учетом имеющихся ограничений по спросу и предложению. Оставшиеся разницы столбцов или строк перечеркиваются и ставиться знак «К», т.е. окончание проверки, означающей, что перераспределение груза закончено. Определяются новые разницы для всех строк и столбцов таблицы, при этом загруженные и свободные клетки, расположенные в строках или столбцах, в которых исчерпаны ограничения по спросу или предложению во внимание не принимаются. Если вновь полученная разница отличается от полученной ранее, то последняя зачеркивается и пишутся новые. Действие повторяется до тех пор, пока весь груз не будет распределен. Последнюю одну или две клетки загружают без определения разностей, полученный по методу аппроксимации Фогеля план перевозки проверяется на оптимальность по методу Моди, если полученное распределение груза окажется не оптимальным, то дальнейшее решение производится по алгоритму метода Моди.

Таблица № 6

Б1Б2Б3Б4Б5Б6Б7

Транспортная работа согласно полученному допустимому решению —

L (x) =50*4+10*5 +80*4+0*5 +4*100 +8*30 +5*40 +5*200 +4*20 +5*20=1690 т*км

1.3 Метод Моди

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

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

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

47 стр., 23095 слов

Централизованная перевозка инертных грузов

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

Таблица № 7

Б1Б2Б3Б4Б5Б6Б7

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

L (x) = 50*4+10*5+100*4+80*4+30*8+40*5+20*5+0*5+20*5+20*4=1690 т*км

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«Выигрыш» от объединения пунктов i и j маршрутов определяется по формуле , где li,o-кратчайшее расстояние от пункта i до ГО, lo,j — кратчайшее расстояние от ГО до j пункта, li,j — кратчайшее расстояние от пункта i до пункта j.

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

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

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

7 стр., 3023 слов

Особенности, тарифы и документы перевозки грузов на воздушном транспорте

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

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

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

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

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

f 1-2=4+12-10=6,f 1-6=4+16-12=8,f 1-3=4+9-7=6,f 1-7=4+12-8=8,f 1-4=4+8-4=8,f 1-8=4+9-11=2,f 1-5=4+4-8=0,f 1-9=4+7-5=6,f 1-10=4+5-7=2.

Таблица № 9.

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

объём грузаГПА2А3А4Б1Б2Б3Б4Б5Б6Б72А2-6680882622А36-86112412 71414А468-125161013 4104Б18612-01010106103Б201150-1632218Б3824161016-1281187Б48121010312-1615107Б52713102816-7106Б66144621115 7-04Б72110101810100-

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

М1: ГО — Б3-А3-ГО (8+2)

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

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

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

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

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

Lм=4+4+8+8+6+16+14+14+12+8=94км

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

Заключение

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

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

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

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

[Электронный ресурс]//URL: https://obzone.ru/kursovaya/modelirovanie-optimizatsii-gruzoperevozok/

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

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

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

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