Разработка системы транспортного обслуживания экономического района грузовыми автомобилями

На  данной  транспортной  сети  нет  никаких  ограничений  по  организации  дорожного  движения,  то  есть  расстояние между  пунктами  02  и 06  равно расстоянию  между пунктами  06  и 02  (ℓ_02-06 = ℓ_06-02).  Таким образом,  матрица кратчайших  расстояний  (см. таблицу 1)  будет симметрична относительно  диагонали.

 

Таблица 1 - Длины звеньев и расстояния между пунктами транспортной сети

 

	02	06	14	15	17	20	22	26	38	41	43	45	47	60	61	63	64	66	68	69	72	75	77	83	84	91	93
02		6	4	5	8	4	3	7	10	6	9	8	11	9	8	12	11	11	14	14	10	13	13	12	13	13	13
06			3	2	2	10	7	4	5	10	10	7	7	13	12	11	10	10	9	9	13	12	11	15	14	16	16
14				1	5	7	4	3	6	7	7	4	7	10	9	8	7	7	10	10	10	9	9	12	11	13	13
15					4	8	5	2	5	8	8	5	7	11	10	9	8	8	9	9	11	10	10	13	12	14	14
17						12	9	2	3	11	8	5	5	13	12	9	8	8	7	7	11	10	10	13	12	14	14
20							3	10	13	3	6	9	12	5	5	9	9	12	16	17	7	11	14	9	10	9	10
22								7	10	3	6	6	9	6	5	9	9	9	13	14	7	11	11	9	10	10	10
26									3	9	6	3	5	11	10	7	6	6	7	7	9	8	8	11	10	12	12
38										11	8	5	2	14	13	9	8	5	4	4	11	7	6	10	9	14	11
41											3	6	9	3	2	6	6	9	13	14	4	8	11	6	7	7	7
43												3	6	5	4	3	3	6	10	11	4	5	8	6	7	7	7
45													3	8	7	6	3	3	7	8	6	5	5	8	7	9	9
47														11	10	7	6	3	6	6	9	5	5	8	7	12	9
60															1	5	6	10	13	14	3	8	11	5	6	4	6
61																4	5	9	12	13	2	7	10	4	5	5	5
63																	1	5	9	10	2	3	7	4	5	5	5
64																		4	8	9	3	2	6	5	4	6	6
66																			4	5	7	2	2	5	4	9	6
68																				1	10	6	2	8	7	12	9
69																					11	7	3	9	8	13	10
72																						5	8	2	3	3	3
75																							4	3	2	7	4
77																								6	5	10	7
83																									1	4	1
84																										5	2
91																											3
93

 

 

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

 

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

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

 

2.1 Постановка транспортной задачи

 

Транспортная задача приведена в таблице 2.1. Условия  транспортной задачи    можно выразить в математической форме, т. е.  построить ее экономико-математическую модель.

Для построения экономико-математической модели введем следующие обозначения:

i – номер поставщика (i =1, 2, 3);

А_i – ресурсы i-го поставщика (i =1, 2, 3), т.е. количество продукции, которое поставщик может отправить потребителям;

j – номер потребителя (j =1, 2, 3, 4, 5, 6);

B_j- потребность j-го потребителя;

L_ij – расстояния между соответствующими пунктами отправлениями и получения;

Q_ij – количество продукции, поставляемое от i-го поставщика j-му потребителю;

Таким образом, экономико-математическую модель оптимального прикрепления потребителей к поставщикам имеет вид:

Объем транспортной работы должен быть минимальным

 

Q_ij ∙ L_ij = min

при условиях

Q_ij = А_i (i =1, 2, 3);

Q_ij = B_j (j =1, 2, 3, 4, 5, 6);

A_i = B_j;   Q_ij  ≥ 0

 

d_ij = L_ij - U_ij - V_ij  ≥ 0

 

 

 

2.2 Решение транспортной задачи методом потенциалов

После построения экономико-математической модели решается задача. Расчеты выполняются в специальной таблице линейного программирования методом потенциалов (таблица 2.1). В этой таблице, кроме ресурсов поставщиков, потребителей и расстояний перевозок, имеются столбец и строка для записи потенциалов U_i и V_j , которые дают определить оптимальность плана закрепления поставщиков за потребителями.

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

 

Таблица 2 – Исходные данные для решения задачи оптимизации  закрепления потребителей за поставщиками

 

Поставщики		Потребители												Объем производства, тыс.т.
		06		63		69		20		84		93
		V06= -2		V63=5		V69=3		V20=3		V84=10		V93=10
22	U22=		7		9		14	**	3		10		10	450
	0		>0		>0		>0	150	0	100	0	200	0
17	U17=	**	2		9	*	7		12		12		14	400
	4		0	50	-1	350	>0		>0		-2		0
15	U15=		2	*	9		9	*	8		12		14	350
	4	150	0	150	0		>0		>0		>0	50	0
Объем потребления, тыс.т.		150		200		350		150		100		250		1200

 

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

Задача оптимизации  закрепления потребителей однородного  груза за поставщиками  может  быть решена любым из известных  методов, например, методом  МОДИ. Сущность его состоит в следующем. Вначале строится какой – либо план перевозок, который по специальным правилам проверяется на оптимальность. Если он не оптимален, то строится новый улучшенный план. Таким образом, за конечное число шагов может быть получен искомый оптимальный план.

Первоначальный (опорный) план целесообразно получить методом "двойного предпочтения".  Для этого по каждой строке и по каждому столбцу отмечается знаком * клетка с минимальным расстоянием. Если в таблице 2 клетки имеют одновременно два знака **, то их загружают в первую очередь. Далее проставляем загрузку в клетки, имеющие одну отметку *. Оставшуюся загрузку распределяем по свободным клеткам. Таким образом, в полученном опорном плане от всех поставщиков имеющийся груз вывезен, всем потребителям завезено все, что им требуется. При этом опорный план должен  удовлетворять  двум  условиям:

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

2. Число  загруженных  клеток  должно  быть  равно:

m+n-1,

где m – число поставщиков;

  n – число потребителей.

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

Подсчитаем для опорного плана значение грузооборота  по  формуле (2.1):

Р= 150*3+100*10+200*10+50*9+350*7+150*2+150*9+50*14=6000 ткм.

Р =8700 ткм

Среднее расстояние перевозки  равно:

lп = 8700/1200=7,25 км.

Для проверки на оптимальность по методу МОДИ определим вспомогательные величины U_i (для строк) и V_j (для столбцов), называемые потенциалами. Для этого потенциал одного из поставщиков (22) примем равным 0. Тогда все оставшиеся  потенциалы  определим  по  формуле (2.2)

Учитывая, что  в загруженных клетках d_ij = 0, определим потенциалы строк и столбцов для таблицы 3. В строке 22 загруженных клеток три: 22-20, 22-84 и      22-93.

Отсюда потенциалы столбцов 20, 84 и 93 равны:

U₂₂=0;  V₂₀=ℓ22-20-u₂₂= 3– 0 = 3;

V₈₄=ℓ22-84-u₂₂= 10– 0 = 10;

V₉₃=ℓ22-93-u₂₂= 10– 0 = 10;

 

Далее по загруженной клетке 15-93 определим потенциал строки 15:

U₁₅=ℓ_15-93- v₉₃= 14-10= 4;

по загруженной клетке 15-06 определим потенциал столбца 06:

V₀₆=ℓ_15-06-u₁₅= 2-4= -2;

по загруженной клетке 15-63 определим потенциал столбца 63:

V₆₃=ℓ_15-63-u₁₅= 9-4= 5;

  по загруженной клетке 17-63 определим потенциал строки 17:

U₁₇=ℓ_17-63- v₆₃= 9-5= 4;

       по загруженной клетке 17-69 определим потенциал столбца 69:

V₆₉=ℓ_17-69-u₁₇= 7-4= 3;

Теперь рассчитаем значение параметра d_ij для всех свободных клеток:

 

 

d_22-06 = 7-0-(-2)= 9≥0;

d_22-63=9-0-5= 4≥0;

d_22-69= 14-0-3= 9≥0;

d_17-06= 2-4-(-2)= 0≥0;

d_17-20=12-4-3= 5≥0;

d_17-84= 12-4-10= -2≤0;

d_17-93= 14-4-10= 0≥0;

d_15-69= 9-4-3= 2≥0;

d_15-20= 8-4-3= 1≥0;

d_15-84= 12-4-10= -2≤0;

 

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

Для перемещения загрузки необходимо составить специальный контур, все вершины  которого  лежат в  загруженных клетках, кроме одной, в которой d_ij ‹ 0. В углах контура проставим попеременно знаки "+" и "—", начиная с клетки в которой d_ij ‹ 0. В клетки, где стоят знаки "-" нужно добавить загрузку, а из клеток, где стоят знаки "+" – отнять. Объем перемещаемой по контуру загрузки равен наименьшей цифре, стоящей в углах, откуда загрузку отнимаем. Новый план перевозок после перемещения загрузки по этому контуру представлен в таблице 4. Если среди клеток контура со знаком "+" окажется 2 (или более) с одинаковыми минимальными загрузками, то из плана исключается только одна из них с большим расстоянием, а вместо других оставляют условную нулевую загрузку, чтобы не допустить вырождения плана.

Результаты расчетов свидетельствуют, что величина d_ij принимает значение меньше 0 в клетках 17-63 и 17-84 следовательно, этот план не оптимален.

 

Таблица 3 – Промежуточный план закрепления потребителей за поставщиками

 

Поставщики		Потребители												Объем производства, тыс.т.
		06		63		69		20		84		93
		V06=0		V63=7		V69=5		V20=3		V84=10		V93=10
22	U22=		7		9		14	**	3		10		10	450
	0		>0		>0		>0	150	0	50	0	250	0
17	U17=	**	2		9	*	7		12		12		14	400
	2		0	50	0	350	0		>0		0		>0
15	U15=		2	*	9		9	*	8		12		14	350
	2	150	0	150	0		>0		>0	50	0		>0
Объем потребления, тыс.т.		150		200		350		150		100		250		1200