Разработка транспортного процесса на основе математических методов линейного программирования и построения эпюр грузопотоков

 

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

Основан метод потенциалов на том, что  если к расстояниям любой строки (столбца) таблицы прибавить или  отнять произвольное одно и то же число, то оценка оптимальности относительно не изменится. Если, например, от расстояний каждой i-ой строки отнимать число u_i и от расстояний каждого j-ого столбца – u_j, то тогда относительной оценкой любой клетки ij может служить параметр u_ij вместо l_ij, рассчитываемый по формуле:

     (1.9)

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

Величина  параметра u_ij характеризует общее увеличение пробега с грузом, достигаемое при включении в план единицы груза по корреспонденции ij по сравнению с рассматриваемым планом.

Если  значение оценочного параметра свободной  клетки будет меньше нуля u_ij <0, то это значит, что перераспределение корреспонденций по клеткам таблицы с занесением объема перевозок в такую свободную клетку, называемую потенциальной, уменьшит значение целевой функции.

Отсутствие  клеток со значением параметра u_ij <0, означает, что проверяемый план закрепления потребителей за постановщиками является оптимальным.

 

Таблица 1.15 -  Проверка начального опорного плана на оптимальность  и переход к следующему плану  перевозок

 

Грузополучатель	Грузоотправитель					Объем завоза bi	Потенциалы  vj
	А1	А2	А3	А4	А5
Б1	7            31	9           23	0 3           20	1           16	500 6	500	24
Б2	2            17	500 5	500 9	8         14	15        12	1000	15
Б3	250 - 31	3        24	-5       20	+                -13       9	500 13	750	31
Б4	0     + 16	8        14	500 10	-   750 7	14        12	1250	16
Б5	1000 5	12        7	7           6	22      18	33       20	1000	5
Объем вывоза ai	1250	500	1000	750	1000	4500
Потенциалы ui	0	-10	-6	-9	-18

 

 

План не оптимален, так как имеет  отрицательные оценки. Поэтому для  клетки с минимальным отрицательным  потенциалом (А₄,Б₃) составляется цикл для перехода к улучшенному плану.

 

 

 

 

 

 

 

 

 

 

 

Таблица 1.16 – Проверка улучшенного опорного плана на оптимальность и переход к следующему плану перевозок

 

Грузополучатель	Грузоотправитель					Объем завоза bi	Потенциалы  vj
	А1	А2	А3	А4	А5
Б1	31	23	0             20	16	500 6	500	-5
Б2	17	500 5	500 9	14	12	1000	-1
Б3	0 31	24	20	250 9	500 13	750	2
Б4	250 16	14	500 10	500 7	12	1250	0
Б5	1000 5	7	6	0            18	20	1000	-11
Объем вывоза ai	1250	500	1000	750	1000	4500
Потенциалы ui	16	6	10	7	11

 

Полученное  решение является оптимальным, так  как все оценки пустых (небазисных) клеток имеют неотрицательное значение.

 

 

 

 

 

 

 

 

 

 

 

 

2 РАЗРАБОТКА  МАРШРУТОВ ПЕРЕВОЗОК ГРУЗОВ

2.1 Разработка  рациональных маршрутов перевозок

 

По оптимальному сводному плану ездок автомобилей  с грузами и оптимальному плану  возврата порожних таких же автомобилей (ездок без груза) составляются рациональные маршруты движения подвижного состава при перевозке грузов. Составление рациональных маршрутов возможно двумя способами: методом "таблиц связей" и методом “совмещенных планов”. Наиболее широкое применение получил последний из них.

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

В тех  клетках полученной таблицы совмещенных  планов, где имеются две цифры (выделенная и невыделенная), получаются маятниковые маршруты, количество ездок  на которых равно минимуму {X_ij, X_ji}, где X_ij - количество ездок с грузом и X_ji – количество ездок без груза. Включенное в маршрут количество ездок с грузом или без груза из дальнейшего рассмотрения исключается.

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

Применим  метод совмещенных планов для  данных из таблицы 2.1.

 

Таблица 2.1 - Совмещенный план гружёных и  порожних ездок.

Грузополучатель	Грузоотправитель
	А1	А2	А3	А4	А5
Б1		500			500
Б2		500	1000 500
Б3				750 250	500
Б4	1250 250		500	500
Б5	1000				1000

 

Как видно  из табл. 2.1, для данных планов перевозок  имеются три маятниковых маршрута с обратным порожним пробегом:

М1: А3Б2−Б2А3=500т;

М2: А4Б3−Б3А4=250т;

М3: А1Б4−Б4А1=250т.

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

Таблица 2.2. – Рациональные кольцевые маршруты 

Грузополучатель	Грузоотправитель
	А1	А2	А3	А4	А5
Б1		500			500
Б2		500	500
Б3				500	500
Б4	1000		500	500
Б5	1000				1000

Таблица 2.3. – Рациональные кольцевые маршруты

Грузополучатель	Грузоотправитель
	А1	А2	А3	А4	А5
Б1
Б2
Б3				500	500
Б4	500			500
Б5	500				500

 

Как видно  из табл. 2.2, 2.3, для данных планов перевозок имеются два рациональных кольцевых маршрута:

М4: А2Б1-Б1А5-А5Б5-Б5А1-А1Б4-Б4А3-А3Б2-Б2А2=500т

М5:А4Б3-Б3А5-А5Б5-Б5А1-А1Б4-Б4А4=500т.

 После  того, как получены маршруты движения  при перевозке груза условными  десятитонными автомобилями, разрабатываются  схемы маршрутов перевозки грузов  с указанием конкретных видов  грузов и объемом их перевозки,  порожних пробегов от пунктов  разгрузки в пункты погрузки. При этом фактическое количество k-го груза Q_ijk, перевозимого между двумя пунктами, определяется по формуле:

      (2.1)

где X_ijk – количество ездок автомобилей с k-м грузом между этими пунктами.

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

      (2.2)

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

Составленные  маршруты приведены в таблицах 2.4 и 2.5.

 

Таблица 2.4. - Маршруты перевозки заданных грузов.

 

№ маршрута	Наименование маршрута	∑nоб	ze	∑ne	lгр	lx	lобщ	βм
М1	А4Б3–Б3А4	25	1	25	9	9	18	0,52
М2	А1Б4–Б4А1	25	1	25	16	16	32	0,54
М3	А3Б2–Б2А3	50	1	50	9	9	18	0,5
Р1	А2Б1–Б1А5–А5Б5–Б5А1–А1Б4–Б4А3- А3Б2-Б2А2	50	4	200	53	26	79	0,83
Р2	А4Б3-Б3А5- А5Б5-Б5А1- А1Б4-Б4А4	50	3	150	45	25	70	0,65

 

 

 

 

 

 

 

 

 

Таблица 2.5. – Мощность грузопотока на маршруте.