МОДЕЛИРОВАНИЕ ТРАНСПОРТНЫХ ПРОЦЕССОВ
Содержание
1. Построение агрегатированной модели транспортной сети (МТС) 3
2. Формирование системы оптимальных грузопотоков с помощью модели транспортной задачи линейного программирования 10
3. Решение задачи развоза груза в MS Еxcel 17
Список литературы 21
1. Построение агрегатированной модели транспортной сети (МТС)
На практике используют агрегатированные и детализированные модели транспортных сетей. Агрегатированные модели строятся на основе микрорайонирования.
Границы микрорайонов наносятся по следующим правилам:
1) естественные и искусственные преграды выступают в качестве границы и не препятствуют проезду транспорта в любую часть микрорайона без выезда с его территории;
2) по улицам микрорайона имеется возможность беспрепятственного проезда;
3) конфигурация микрорайонов произвольная;
4) площадь микрорайонов выбирается в зависимости от предполагаемого размера модели транспортной сети.
Центр микрорайона определяется:
1) месторасположением единственного поставщика или потребителя в микрорайоне;
2) географическим центром при наличии нескольких поставщиков или (и) потребителей.
Построим агрегатированную модель транспортной сети (МТС) по приведенной план-схеме района перевозок (приложение 1).
Нанесем на план-схему границы и центры микрорайонов (рис. 1).
Нанесем центры микрорайонов на лист МТС в виде вершин. Микрорайону ставится в соответствие вершина, расположенная в его центре. Вершины сети нумеруются и для смежных микрорайонов соединяются дугами (звеньями). Длина звена определяется наименьшим значением расстояния, полученного из результатов промеров всех возможных комбинаций проезда с учетом масштаба и организации дорожного движения. На дугах модели сети проставим их протяженности и дорожно-транспортные ограничения на организацию движения, а именно наличие одностороннего движения. Протяженность дуги определили как наименьшее и возможных расстояний проезда между смежными районами. Расстояния проезда измерили курвиметром по карте с учетом масштаба (рис. 2).
Рис. 2. Расстояния проезда между центрами микрорайонов, км
Кодирование модели приведем в табл. 1, где в скобках записаны длины однозвенных связей. Например, первая строка таблицы показывает, что с вершиной 1 связаны вершины 2, 6, 11 и 12 длины соответствующих однозвенных связей равны 0,25, 0,11, 033, 0,35 км соответственно.
По полученной агрегатированной МТС рассчитаем матрицу кратчайших расстояний и путей проезда методом Дейкстры.
Определим кратчайшие расстояния и кратчайшие пути проезда от вершины 1 до всех остальных.
Этап 1.
Вершине, от которой требуется определить кратчайшее расстояние, присваивается потенциал, равный нулю, т.е. v1 = 0.
Этап 2.
1. Определим потенциалы вершин, являющихся конечными по отношению к вершине 1. Значения потенциалов конечных вершин vj определяются по формуле:
vj = vi + cij,
где cij – длина звена (i,j).
v2 = v1 + c12 = 0 + 0,25= 0,25,
v6 = v1 + c16 = 0 + 0,11 = 0,11,
v11 = v1 + c1 11 = 0 + 0,33= 0,33,
v12 = v1 + c1 12 = 0 + 0,35= 0,35.
2. Выбор наименьшего значения из не присвоенных потенциалов:
min (v2 v6 v11 v12) = v6 = 0,11
3. Звено (1,6) отмечается стрелкой (рис. 3). Вершине 6 присваивается значение кратчайшего расстояния, равное 0,11 (присвоенные значения записываются на модели транспортной сети у соответствующих вершин).
Этап 3.
За начальную принимается вершина 6. Рассчитываются потенциалы смежных вершин:
v2 = 0,11 + 0,28 =0,39
v3 = 0,11 + 0,31 =0,42
v12 = 0,11 + 0,22 =0,33
Потенциал вершин 2, 12 определен дважды, в расчетах оставляют наименьший: v2 = 0,25, v12 = 0,33.
Выбор наименьшего значения из не присвоенных потенциалов:
min (v2 v3 v11 v12) = v2 = 0,25
Звено (1,2) отмечается стрелкой (рис. 3). Вершине 2 присваивается значение кратчайшего расстояния, равное 0,25
Этап 4.
За начальную принимается вершина 2. Рассчитываются потенциалы смежных вершин:
v6 = 0,25= + 0,28= 0,53,
v3 = 0,25 + 0,3=0,55,
v4 = 0,25 + 0,38 =0,63
Потенциал вершин 3 и 6 определены дважды, в расчетах оставляют наименьший: v3= 0,42, v6 =0,11
Выбор наименьшего значения из не присвоенных потенциалов:
min (v3 v4 v11 v12) = v11 = 0,33
Вершине 11 присваивается потенциал 0,33.
Этап 5.
За начальную принимается вершина 11. Рассчитываются потенциалы смежных вершин:
v12 = 0,33= + 0,2= 0,53,
v19 = 0,33 + 0,58=0,91,
Потенциал вершины 12 определен дважды, в расчетах оставляют наименьший: v12= 0,33.
Выбор наименьшего значения из не присвоенных потенциалов:
min (v3 v4 v12 v19) = v12 = 0,33
Вершине 12 присваивается потенциал 0,33.
Аналогично рассчитаем потенциалы других вершин, расчет приведен в таблице 2.
2. Формирование системы оптимальных грузопотоков с помощью модели транспортной задачи линейного программирования
Сформируем систему оптимальных (по критерию минимума транспортной работы) грузопотоков при заданных объемах производства и потребления грузов для рассмотренной ранее модели транспортной сети.
Составим математическую модель задачи линейного программирования.
Пусть xij − количество единиц груза, запланированного к перевозке от i-го поставщика к j-му потребителю, cij – расстояние перевозки груза от i-го поставщика к j-му потребителю. Найти значение целевой функции:
xij ≥ 0; i = 1,2…m, j = 1,2…n,
(условие транспортной задачи закрытого типа)
где m – кол-во поставщиков груза, n – кол-во потребителей груза, ai –объем производства i-го поставщика, bj – потребность j-го потребителя.
Исходную информацию для решения задачи сведем в табл. 5, где в клетках запишем расстояния перевозки от i-го поставщика к j-му потребителю (т.е. расстояния между центрами микрорайонов, ранее вычисленные методом Дейстры на основе агрегатированной модели транспортной сети).
Решим задачу методом МОДИ.
1 этап
В табл. 6 определим необходимое число загруженных клеток:
m + n – 1 = 4+6 – 1 = 9.
В нашем опорном плане 8 загруженных клеток, поэтому при невозможности расчета потенциалов клетку с одним известным потенциалом и наименьшей стоимостной оценкой необходимо будет загрузить нулевым объемом перевозок.
2 этап
Расстановка потенциалов. Первой строке матрицы присваивают нулевой потенциал (α1 = 0). Для определения потенциалов всех строк и столбцов используют условие для загруженных клеток: αi + βj = cij, где αi – потенциал i-й строки; βj – потенциал j-го столбца; cij – стоимостная оценка в загруженной клетке. Расчет потенциалов для опорного плана представлен в табл. 7.
Так как, при текущем числе загруженных клеток расчет всех потенциалов невозможен (т.е условие m + n – 1 не выполняется), то загружаем клетку (1,2) нулевым объемом перевозок.
3 этап
Проверка решения на оптимальность. Если в незагруженной клетке матрицы выполняется условие cij < αi + βj, то решение не является оптимальным.
Проверим опорный план (табл. 7) на соответствие данному условию:
α1+ β3=0 + 2,66 = 2,66 ≤ 2,66 (условие выполняется);
α1+ β4=0−1,88 = −1,88 ≤ 2,95 (условие выполняется);
α1+ β5=0+2,19= 2,19 > 2,05 (условие не выполняется);
α2+ β1=−1,09+0 = −1,09 ≤ 1,09 (условие выполняется);
α2+ β4=−1,09−1,88 = − 2,97 ≤ 2 (условие выполняется);
α2+ β6=−1,09+1,01 = −0,08 ≤ 1,47 (условие выполняется);
α3+ β1= 1,88+0 = 1,88 ≤ 2,96 (условие выполняется);
α3+ β2= 1,88+1,09= 2,97 > 2,35(условие не выполняется);
α3+ β5= 1,88+2,19= 4,07 > 0,9 (условие не выполняется);
α3+ β6= 1,88+1,01 = 2,89 > 1,94 (условие не выполняется);
α4+ β1= 0,31+0 = 0,31 ≤ 1,21 (условие выполняется);
α4+ β2= 0,31+1,09 = 1,40 ≤ 2,3 (условие выполняется);
α4+ β3= 0,31+2,66 = 2,97 ≤ 2,97 (условие выполняется);
α4+ β4= 0,31-1,88 = -1,57≤ 4,16 (условие выполняется);
α4+ β5= 0,31+2,19 = 2,5 ≤ 3,2 (условие выполняется).
Для клеток (1,5), (3,2), (7,5), (3,6) условие не выполняется, эти клетки называются потенциальными. Для них отыщем величину [(αi + βj) – cij]:
α1+ β5 –с15=0+2,19- 2,05 =0,14,
α3+ β2–с42= 1,88+1,09- 2,35=0,62,
α3+ β5–с45= 1,88+2,19- 0,9=3,17,
α3+ β6–с46= 1,88+1,01 -1,94=0,95,
данное значение максимальное для клетки (4,5), с нее начнется выполнение этапа 4.
4 этап
Построение контуров перераспределения. С выбранной потенциальной клеткой (3,5) строится контур, все вершины которого расположены в загруженных клетках, а только одна в потенциальной.
Для выбранной потенциальной клетки возможно построение лишь одного контура, в котором вершина с потенциальной клеткой обозначается знаком плюс, и, проходя по контуру, знак чередуется (табл.7).
В вершинах со знаком минус определяется наименьший объем перевозки (в нашем случае это 20 тонн, клетка 4,3),), который прибавляется к объемам в клетках со знаком плюс и вычитается из объемов со знаком минус.
В результате перераспределения объема перевозок формируется новый план, далее повторяются шаги, начиная со 2.
Расчет потенциалов для нового плана приведен в табл. 8. По незагруженным клеткам новый план аналогично проверяется на оптимальность.
В результате расчета в новом плане выявлены следующие потенциальные клетки:
α1+ β5=0+2,19= 2,19 > 2,05 => α1+ β5 –с15=0+2,19- 2,05 =0,14;
α3+ β3= -1,29+2,66= 1,37 > 0,78 => α4+ β3–с43 = 1,37 — 0,78 = 0,59
Из них выбирается клетка (4,3), с нее начинается построение нового контура (табл. 8).
В вершине контура со знаком минус определяется наименьший объем перевозки (20 тонн, клетка 4,5), который прибавляется к объемам в клетках со знаком плюс и вычитается из объемов со знаком минус. В результате получаем новый план развоза (новый план № 2).
Для нового плана развоза повторяем расчет потенциалов и проверку оптимальности (табл. 9).
В результате расчета в новом плане выявлена одна потенциальная клетка:
α1+ β5=0+2,19= 2,19 > 2,05 => α1+ β5 –с15=0+2,19- 2,05 =0,14,
В вершине контура со знаком минус определяется наименьший объем перевозки (0 тонн, клетка 1,2). В результате план не меняется, меняется лишь место положения загруженной клетки с (1,2) на (1,5). В результате изменения места положения загруженной клетки меняется и значения потенциалов (табл. 10).
Для нового плана развоза повторяем проверку оптимальности (табл. 10).
В новом плане № 3 потенциальных клеток не найдено. Следовательно, данный план развоза признаем оптимальным. Значение целевой функции (величина транспортной работы) для данного план примет значение:
F = 80*0+80*1,01+20*0+40*1,57+40*1,1+20*0,78+100*0+80*1,32 = 308,8 ткм
3. Решение задачи развоза груза в MS Еxcel
Для решения транспортной задачи воспользуемся функцией «Поиск решения» MS Excel.
Выполним подготовительные действия.
1. В таблицу Excel заносятся исходные данные: матрица данных о расстоянии перевозки грузов (значения сij); данные об объемах производства и потребностях (значения ai и bj).
2. Формируется пустая матрица вывода результатов решения транспортной задачи
3. В матрице вывода результатов вносятся формулы расчета суммарного объема перевозок из каждого ГОП и в каждый ГПП.
4. Задается ячейка, в которую вноситься формула расчета значения целевой функции: . В Excel целевую функцию задаем формулой =СУММПРОИЗВ(Массив1;Массив2) (рис. 4).
Рис. 4. Выполнение подготовительных действий в Excel
После оформления исходных данных вызываем функцию «Поиск решения». В появившееся окно вносим данные о целевой функции, изменяемых ячейках, ограничениях.
Изменяемыми ячейками является массив пустой матрицы, в нашем случае — массив B4:G7. Целевой ячейкой будет ячейка B20, зададим ее равенство минимальному значению.
Ограничением является равенство суммарных объемов перевозок из каждого ГОП объемам производства и равенство объемов перевозок каждому ГПП потребностям.
Помимо этого вносят ограничения неотрицательности искомых переменных (рис. 5), после чего дается команда «Выполнить» и «ОК».
Рис. 5 Ввод данных для функции «Поиск решения» MS Excel
После выполнения ряда итераций программа выводит искомый план перевозок (ячейки B4:G7), минимальное значение целевой функции (ячейка B20).
Полученный в MS Excel план идентичен плану, рассчитанному распределительным методом (рис. 6).
Рис. 6. Результат решения транспортной задачи в MS Excel
Список литературы
1. Просов, С.Н. Модель кольцевой маршрутизации перевозок грузов помашинными отправками: лабораторный практикум и методические указания для практических занятий по курсу «Моделирование транспортных процессов» / С.Н. Просов. – М.: МАДИ, 2016. – 48 с.
2. Просов, С.Н. Лабораторный практикум по курсу «Теоретические основы организации и функционирования систем» / С.Н. Просов. – М.: ООО «Техполиграфцентр», 2002. – 45 с.
3. Модели и методы теории логистики: учеб. пособие для вузов / под ред. проф. В.С. Лукинского. – СПб.: Изд-во Питер, 2003. – 176 с. 5.
4. Просветов, Г.И. Математические методы в логистике: учебнометодическое пособие / Г.И. Просветов. – М.: Изд-во РДЛ, 2006. – 272 с.