- •Экономико-математическая модель транспортной сети
- •Определение кратчайших расстояний между пунктами транспортной сети
- •1.2 Решение транспортной задачи методом потенциалов
- •2 Маршрутизация перевозок
- •2.1 Разработка рациональных маршрутов перевозки методом совмещенных планов
- •2.2 Оптимальное закрепление маршрутов за атп
- •Расчет маршрутов
- •3.1 Расчет количества подвижного состава и технико-эксплуатационных показателей его работы для разработанных маршрутов
1.2 Решение транспортной задачи методом потенциалов
Транспортная задача решается на минимизацию холостого пробега и состоит в определении оптимального варианта закрепления потребителей за поставщиком однородной продукции.
Если обозначить объем вывоза груза через некоторого поставщика Qi, требуемый объем завоза груза некоторому потребителю черезQj,объем груза, перевозимого от некоторогоi-ого поставщикаj-ому потребителю, черезQij и кратчайшее расстояние перевозки отi-ого поставщика доj-ого потребителя черезlij. То математическая модель поставленной задачи имеет вид:
, (1.3)
(1.4)
(1.5)
Qij ≥ 0. (1.6)
В случае, если количество груза у поставщиков равно общему объему завоза груза всем потребителям, то имеет место условие:
=(1.7)
Поставленная таким образом задача (целевая функция (1.3) и ограниченная (1.4)-(1.7)) является закрытой моделью классической транспортной задачи линейного программирования, в результате решения которой по известным значениям Qi, Qj, lij находятся неизвестные значения объемов перевозок междуi-ым поставщиком иj-ым потребителемQij.
Для составления транспортной задачи из исходных данных (вариант №14) выбираем грузы, перевозимые одним типом подвижного состава. Перечень этих грузов представлен в таблице 1.12.
Таблица 1.12 – Грузы, перевозимые одним типом подвижного состава
Грузопотоки |
Род груза |
Объем перевозок, т |
Класс груза и способ перевозки | |
Из пункта |
В пункт | |||
А1 |
Б1 |
Грунт |
500 |
1 (навалом) |
А1 |
Б1 |
Рельсы |
500 |
1 (без упаковки) |
Б1 |
А1 |
Доски |
200 |
1 (без упаковки) |
А2 |
Б2 |
Песок |
1000 |
1 (навалом) |
Б2 |
А3 |
Овощи |
200 |
2 (ящики) |
А2 |
Б2 |
Фанера |
200 |
1 (пачки) |
А3 |
Б2 |
Щебень |
250 |
1 (навалом) |
А3 |
Б2 |
Овощи |
200 |
1 (ящики) |
Б3 |
А4 |
Тара разная |
250 |
3 (без упаковки) |
Б5 |
А5 |
Кожа |
500 |
1 (ящики) |
А4 |
Б2 |
Песок |
1000 |
1 (навалом) |
А4 |
Б1 |
Фанера |
250 |
1 (пачки) |
А5 |
Б4 |
Песок |
1000 |
1 (навалом) |
А5 |
Б4 |
Шифер |
500 |
1 (без упаковки) |
Б4 |
А5 |
паропласт |
500 |
|
Для решения транспортной задачи объемы перевозок приводятся к 1-ому классу груза по следующей формуле:
(1.8)
Где – число ездок, приведенных к 1-ому классу груза;
- объем перевозок указанный в плане;
- номинальная грузоподъемность автомобиля (для осуществления перевозок выбран автомобиль модели МАЗ-4570 грузоподъемностью 10 тонн);
- коэффициент статического использования грузоподъемности.
Подготовка исходных данных для их занесения в матрицу транспортной задачи приводится в табличной форме и представлена в таблице 1.13.
Таблица 1.13 – Подготовка исходных данных к маршрутизации перевозок грузов
Пункт отправления |
Пункт получения |
Перевозки по видам груза | ||||
Вид груза |
, т | |||||
А1 |
Б1 |
Грунт |
500 |
1,0 |
50 | |
А2 |
Б2 |
Песок |
1000 |
1,0 |
100 | |
А3 |
Б2 |
Щебень |
250 |
1,0 |
25 | |
А4 |
Б2 |
Песок |
1000 |
1,0 |
100 | |
А5 |
Б4 |
Песок |
1000 |
1,0 |
100 |
В клетках матрицы транспортной задачи указывается расстояние перевозки и приведенный к 1-ому классу объем грузов в тоннах по отправителям и получателям, затем строится в виде матрицы возможный план перевозок (см. таблицу 1.14 на странице …).
Для отыскания оптимального закрепления потребителей за поставщиками необходимо сделать в полученной таблице первоначальное закрепление, т.е. получить произвольный план закрепления (опорный), удовлетворяющий ограничениям (1.4)-(1.7) при количестве загруженных клеток m+n-1 и отсутствии циклов (контуров). Такой план, содержащий ровноm+n-1 заполненных клеток без циклов, называется базисным.
Контур может быть четырехугольным, шестиугольным, восьмиугольным и т.д. Если число загруженных клеток более m+n-1, то среди них есть цикл.
Существует несколько методов получения опорного плана – метод северо-западного угла (диагональный) и ряд более эффективных, ускоряющих в дальнейшем отыскание оптимального решения, - метод абсолютного двойного предпочтения, метод минимального элемента, метод минимальных разностей и другие.
Распределение груза рекомендуется производить методом минимального элемента, как одним из наиболее простых и эффективных.
В соответствии с этим методом опорный план составляется по следующему правилу: выбирается минимальное расстояние, клетки загружаются объемами перевозок Qij, пока не будут удовлетворены ограничения по вывозу и завозу груза. Объем грузаQij, заносимый в клеткуij, определяется как минимум от объема вывоза по строке и объема завоза по столбцу с учетом ранее назначенных других перевозок. Выбор загрузки именно таким образом обусловлен тем, что, во-первых, необходимо переправить как можно больше груза по маршруту с наименьшим расстоянием, во-вторых, невозможно переправить груза больше, чем имеется у данного грузоотправителя, в-третьих, не должно пересылаться грузополучателю больше груза, чем ему требуется. Выбранное значение и будет представлять собой загрузку данной клетки.
Оставшиеся загрузки проставляются по возможности в клетки с наименьшим расстояниями. При проставлении загрузок необходимо соблюдать условия, оговоренные выше.
Полученный методом наименьшего элемента начальный опорный план транспортной задачи представлен в таблице 1.14.
Таблица 1.14 – начальный опорный план перевозки грузов
грузополучатель |
грузоотправитель |
Объем завоза bi, т | |||||
А1 |
А2 |
А3 |
А4 |
А5 |
| ||
Б1 |
25 24 |
- 17 |
25 12 |
- 25 |
- 19 |
500 | |
Б2 |
25 24 |
- 15 |
- 17 |
100 7 |
100 14 |
2250 | |
Б4 |
- 28 |
100 4 |
0 9 |
- 12 |
- 9 |
1000 | |
Объем вывоза, aj, т |
500 |
1000 |
250 |
1000 |
1000 |
3750 |
Далее полученный план перевозок проверяется на оптимальность с помощью метода потенциалов. В таблицу транспортной задачи вводится вспомогательная строка и столбец, в которые заносятся специальные показатели, называемые потенциалами.
Метод потенциалов основан на том, что если к расстояниям любой строки (столбца) таблицы прибавить или отнять произвольное одно и тоже число, то оценка оптимальности относительно не изменится. Если, например, от расстояний каждой i-ой строки отнимать числоui и от расстояний каждогоj-ого столбца -vj, то тогда относительной оценкой любой клеткиijможет служить параметр Δij вместоlij, рассчитываемый по формуле:
Δij = lij - uij - vij (1.9)
Потенциал для наиболее загруженной строки таблицы принимается равным нулю и по расстояниям загруженных клеток подбираются потенциалы для других строк и столбцов таким образом, чтобы соблюдалось условие (1.9), т.е. расстояние в каждой загруженной клетке должно быть равно сумме потенциалов строки и столбца данной клетки. Затем по вычисленным потенциалам строки столбцов определяются значение оценочного параметра Δij для каждой незагруженной клетки (не вошедшей в базисный план).
Величина параметра Δij характеризует общее увеличение пробега с грузом, достигаемое при включении в план единицы груза по по корреспонденцииijпо сравнению с рассматриваемым планом.
Если значение оценочного параметра свободной клетки будет меньше 0 (Δij < 0), то это значит, что перераспределение корреспонденций по клеткам таблицы с занесением объема перевозок в такую свободную клетку, называемую потенциальной, уменьшит значение целевой функции.
Отсутствие клеток со значением параметра Δij < 0 означает, что проверяемый план закрепления потребителей за поставщиками является оптимальным.
Проверка исходного опрного плана перевозок на оптимальность представлена в таблице 1.15. Суммарный холостой пробег автомобилей составляет 4000 км. План не оптимален, т.к. имеются отрицательные оценки. В связи с этим для клетки с минимальным отрицательным потенциалом (А5Б4) составлен цикл для перехода к следующему (улучшенному) опорному плану. Соответствующие клетки цикла помечаются попеременно «+» и «-», а их значения соответственно увеличиваются или уменьшаются.
Таблица 1.15 – Проверка начального опорного плана на оптимальность и переход к следующему плану перевозок
грузополучатель |
грузоотправитель |
Потенциалы vj | |||||
А1 |
А2 |
А3 |
А4 |
А5 |
| ||
Б1 |
+++++++ 24 |
10 17 |
+++++++ 12 |
18 25 |
5 19 |
0 | |
Б2 |
+++++++ 24 |
8 15 |
5 17 |
100 7 |
+++++++ 14 |
0 | |
Б4 |
7 28 |
100 4 |
+++++++ 9 |
8 12 |
+++++++ -2 9 |
-3 | |
Потенциалы ui |
24 |
7 |
12 |
7 |
14 |
|
Полученный план перевозок, а также его проверка на оптимальность представлены в таблице 1.16. Суммарный холостой пробег автомобилей составляет 4000 км. Полученный опорный план является оптимальным. Данный оптимальный план перевозок единственный.
Таблица 1.15 – Оптимальный план перевозок
грузополучатель |
грузоотправитель |
Потенциалы vj | |||||
А1 |
А2 |
А3 |
А4 |
А5 |
| ||
Б1 |
25 24 |
- 17 17 |
25 12 |
- 25 25 |
- 19 19 |
0 | |
Б2 |
25 24 |
- 6 15 |
- 5 17 |
100 7 |
100 14 |
0 | |
Б4 |
- 9 28 |
100 4 |
- 2 9 |
- 10 12 |
0 9 |
-5 | |
Потенциалы ui |
24 |
9 |
12 |
7 |
14 |
|