6 Составление рациональных маршрутов перевозок грузов

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

Z_п=Z_г=Q_г/Д_рq_нy_с, (6.1)

где Z_п,Z_г - число порожних и груженых ездок;

y_с =1.

Таблица 6.1 - Заданный план перевозок грузов, ездки

Пункт прибытия груженых автомобилей i	Пункт отправления груженых автомобилей j																b1
	Г15			Г15					Г17		Г18				Г6
Г15			0		0					5,25			12,25			9	2
									2
Г18			12,25		12,25					7			0			20,5	1
				1
Г20			13,25			13,25				15			8			22,75	1
											1
Г21			9					9		13,5			12,75			9,5	1
				1
Г19			7,25					7,25		12,5			6			16,25	1
											1
Г1			20,25					20,25		24,75			31,75			11,25	1
															1
Г2		26,5					26,5			31			38			17,5	1
															1
Г3		27					27			32,5			38,5			18	1
															1
Г16		7,5					7,5			6,25			12,75			15,75	2
									2
Г11		4,25					4,25			8,75				15,75		4,75	2
	2
Г7		11					11			15,5				14,75		11,5	2
	2
a1	4			2					4		2				3		15

Построим первоначальный допустимый план Х₁ с базисом S₁. Для этого таблицу 6.1, преобразуем в таблицу 6.2, учитывая, что Г₁₅, Г₁₇, Г₁₈, Г₆ являются потребителями, а Г₁₅,Г₁₈,Г_20,Г₂₁,Г₁₉,Г₁,Г₂,Г₃,Г₁₆,Г₁₁ и Г₇ - поставщиками порожних автомобилей. Построение первоначального плана X₁ произведем методом минимального элемента. В табл. 6.1 находим клетку с наименьшим расстоянием.

Таблица 6.2 - Исходный план движения порожняка, ездки

Пункт прибытия груженых автомобилей i	Пункт отправления груженых автомобилей j																a1
	Г15			Г15					Г17		Г18				Г6
Г15			0		0					5,25			12,25			9	2
Г18			12,25		12,25					7			0			20,5	1
Г20			13,25			13,25				15			8			22,75	1
Г21			9					9		13,5			12,75			9,5	1
Г19			7,25					7,25		12,5			6			16,25	1
Г1			20,25					20,25		24,75			31,75			11,25	1
Г2		26,5					26,5			31			38			17,5	1
Г3		27					27			32,5			38,5			18	1
Г16		7,5					7,5			6,25			12,75			15,75	2
Г11		4,25					4,25			8,75				15,75		4,75	2
Г7		11					11			15,5				14,75		11,5	2
b1	4			2					4		2				3		15

Такой будет клетка (1,1} (С_1,1 = 0). В качестве первой базисной поставки выберем наименьшее из значений четвертой строки и третьего столбца:

х_1,1 = min (а_1, ь₁) = min (2, 4) = 2, (6.2)

Занесем х_1,1 = 2 в клетку (1,1) .Скорректируем значение величины а₄ и b₃ после определения базисной переменной х_1,1 = 2:

а'₁ = а₁ – х_1,1 = 2 – 2 = 0, (6.3)

b’₁ = ь₁ – х_1,1 = 4 – 2 = 2, (6.4)

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

х_1,2 = min (а₁ b₂) = min (2, 2) = 2, (6.5)

Заносим х_1,2 = 2 в клетку (1.1).

Скорректируем значения а и б:

a'₁ = а₁- х_1,2 = 2 – 2 = 0, (6.6)

b'₂ = b₂ – х_1,2 = 2 –– 2 = 33, (6.7)

Рассуждая аналогичным образом, заканчиваем построение первого допустимого плана возврата порожняка (табл. 6.2)

Затем проверяем на оптимальность, для этого используем потенциал, для загруженных клеток.

П_i+П_j=l_ij

Загруженной считается клетка, в которой записана поставка от поставщика к получателю. Расчетов потенциалов заключается в том, что мы анализируем строчки или столбцы с известным потенциалом и через загруженные клетки рассчитываем потенциал строки или столбца. Для потенциальной клетки строим контур таблица 6.3.

Таблица 6.3 – Расчет потенциалов

Пункт разгрузки		Пункт погрузки			Потребность в грузе
		П7	П8	П10
		35	40	26
Г1	0	20 ^35	^30	^36	20
Г2	12	5 ^47	5 ^52	^56	10
Г3	21	^32	20 ^41	5 ^47	25
Г9	-13	^38	^19	15 ^13	15
Наличие груза		25	25	20	70

Продолжение таблицы 6.3

Пункт разгрузки		Пункт погрузки			Потребность в грузе
		П7	П8	П10
		35	40	26
Г1	0	20 ^35	^30	^36	20
Г2	8	^47	10 ^52	^56	10
Г3	-3	5 ^32	15 ^41	5 ^47	25
Г9	-37	^38	^19	15 ^13	15
Наличие груза		25	25	20	70

Окончание таблицы 6.3

Пункт разгрузки		Пункт погрузки			Потребность в грузе
		П7	П8	П10
		35	40	26
Г1	0	5 ^35	15 ^30	^36	20
Г2	22	^47	10 ^52	^56	10
Г3	-3	20 ^32	^41	5 ^47	25
Г9	-37	^38	^19	15 ^13	15
Наличие груза		25	25	20	70

Таблицы 6.4 – Оптимальный план перевозок

Пункт разгрузки		Пункт погрузки			Потребность в грузе
		П7	П8	П10
		35	40	26
Г1	0	^35	20 ^30	^36	20
Г2	22	^47	5 ^52	5 ^56	10
Г3	11	25 ^32	^41	^47	25
Г9	-21	^38	^19	15 ^13	15
Наличие груза		25	25	20	70