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

Содержание

Введение

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

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

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

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

1.3 Метод Моди

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

Часть 1.

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

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

Таблица № 1

Необходимо:

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

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

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

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

Метод Моди

Часть 2.

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

Необходимо:

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

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

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

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

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

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

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

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

v_j = v_i + l_ij,

где:

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

l_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

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

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

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.1 Метод Хичкока

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

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

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

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

Таблица № 4

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 наименьших расстояния и разница между ними записывается в строку разностей, а разницу между двумя наименьшими расстояниями по строкам записывается в столбец разностей.

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

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

Таблица № 6

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

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, то потенциал для некоторых строк и столбцов будет невозможно найти, недостающее количество клеток загружаем нулями. Загружать нулями, следует клетки, которые лежат на пересечении строк и столбцов, не имеющих потенциалов, со строками и столбцами для которых потенциалы уже определены. При этом наиболее целесообразно выбирать из этих клеток такие, в которых имеются наименьшие расстояния. После того как потенциалы всех строк и столбцов определены, определяется их сумма для каждой свободной клетки, сумма потенциалов указывается в верхнем левом углу свободной клетки. При решении задач на минимум оптимальный вариант получится в том случае, когда в каждой свободной клетке сумма потенциалов для этой клетке не превышает указанного в ней расстояния.

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

Таблица № 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 т*км

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

Выбираем наибольшее значение из таблицы "выигрышей", равное 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 т*км.

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

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

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

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

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

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

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