Минимизация холостых пробегов автотранспортного предприятия (стр. 2 из 5)

N>m+n-1 N<m+n-1

Ликвидация лишних занятых клеток

N=m+n-1

Создание недостающих занятых клеток

Расчёт индексов

Проверка незанятых клеток на потенциальность

Построение цепочки возможных перемещений загрузок

Расчёт знаков “+” и “-“ по вершинам цепочки

Поиск наименьшей среди загрузок, отмеченных знаком “-“

Изменение загрузки на вершинах цепочки

Решение закончено: оптимальный план составлен

Потенциальных клеток нет

Рис. 1. Блок-схема алгоритма метода потенциалов.

§ 4. РАСЧЁТ ПО МЕТОДУ СОВМЕЩЁННЫХ ПЛАНОВ.

п.4.1.Расчёт оптимального плана возврата порожняка. Решение транспортной задачи начинается с разработки допустимого исходного плана, который разрабатывается в табличной форме. В матрицу условий (таблица 4) вводится дополнительный столбец и строка.

ТАБЛИЦА 4. Матрица условий.

Пункт назначения (образов. порожняка)
Пункт назначения	Вспом. Индек.		Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8		Потребность в перевозках
Ui / Vi
А1	5	1	7	8	4	2	14		15
А2	5	13	8	6	3	1	7		3
А3	12	4	14	13	11	4	12		10
А4	16	7	15	15	13	5	15		12
А5	9	1	13	6	1	1	4		1
А6	3	1	5	3	8	10	3		2
Наличие порожняка

В строке записываются значения индексов V_j, а в столбце – значения индексов U_i .

Для дальнейших расчётов необходимо определить количество автомобиле-ездок, их находим по формуле :

Z_e= Q/ q_* g,

где Q – объём перевозок;

q – грузоподъёмность автомобиля (т);

g -- коэффициент использования грузоподъёмности.

Значения q и g возьмём из таблицы 3. Результаты вычисления занесём в таблицу 5.

ТАБЛИЦА 5. Расчёт ездок от объёма перевозки грузов (в тоннах).

Пунктотправления	А1	А1	А1	А2	А3	А4	А4	А5	А5	А6	А6
Пунктназначения	Б1	Б7	Б8	Б2	Б5	Б3	Б4	Б1	Б3	Б5	Б6
Объём перевозок	189	81	81	81	81	36	54	108	54	54	54
Количество автомобиле- ездок	42	18	18	18	18	8	12	24	12	12	12

В правом верхнем углу клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами; условие Sb_j= Sа_i= 194 (ездки) выполняется.

ТАБЛИЦА 6. Допустимый исходный план.

Пункт назначения (образов. порожняка)
Пункт назначения	Вспом. Индек.		Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8		Потребность в перевозках
Ui \ Vi
А1	425	1	7	8	4	2	1814		1815		78
А2	5	1813	8	6	3	1	7		3		18
А3	12	4	14	13	1811	4	12		10		18
А4	16	7	815	1215	13	5	15		12		20
А5	249	01	1213	6	01	1	4		1		36
А6	3	1	5	3	128	1210	3		2		24
Наличие порожняка	66	18	20	12	30	12	18	18		194/194

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

Планируем перевозки ближайшим из неудовлетворённых ещё потребителей, записывая соответствующие загрузки в клетки с наименьшими расстояниями. При соблюдении условий, описанных выше, удовлетворяя спрос и предложения пунктов отправления и потребления, происходит заполнение необходимых клеток; остаток по столбцу или строке сносится в клетку остатков, который впоследствии заносится в свободные не вычеркнутые клетки. При этом необходимо соблюдать условие, что количество заполненных клеток должно соответствовать числу m + n -1, где m — число пунктов отправления или погрузки; n – число пунктов погрузки.

В таблице 6 количество занятых клеток равно числу m + n -1=13; а в таблице 6 количество занятых клеток не равно этому числу 13 . Поэтому необходимо создать недостающие клетки, поставив нулевые загрузки в клетки А₅-Б₂ и А₅-Б₅.

Допустимый исходный план составлен, проверим его на оптимальность.

п.4.2.Расчёт индексов для занятых клеток.

п.4.2.1.Расчёт суммарного холостого пробега. Рассчитываем суммарный холостой пробег для допустимого исходного плана (таблица 6) с помощью формулы:

_nm

S_Lx = S S X_{ij *} l_ij , { 6 }

^{j=1 i=1}

где S_Lx -- суммарный холостой пробег (км); X_ij – количество порожняка, подаваемого между i-ым пунктом назначения, ездки; l_ij – расстояние от i-ого пункта отправления до j-ого пункта назначения (км).

п.4.2.2. Расчёт индексов. Следующим пунктом вычислений находим индексы для загруженных клеток :

U_i + V_j =l_ij X_ij, { 7 }

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

U_i + V_j =l_ij, для X_ij>0 { 8 } и U_i + V_j =l_ij , для X_ij=0 . { 9 }

Для определения индексов используются следующие правила:

а) индексы U_iзаписываются во вспомогательный столбец ;

б) индексы V_j записываются во вспомогательную строку;

в) индексы правой клетки вспомогательного столбца принимаются за нуль: U₁=0.

Тогда из уравнения {6} можно выразить U_iи V_j .

Далее, рассчитаем индексы для таблицы 7 допустимого исходного плана по этим правилам.

ТАБЛИЦА 7. Допустимый исходный план ( предварительный вариант).

Пункт назначения (образов. порожняка)
Пункт назначения	Вспом. Индек.		Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8		Потребность в перевозках
Ui \ Vi		5	-3	9	9	-3	-1	14	15
А1	0		425	1	72	81	4	2	1814		1815		78
А2	16		516	1813	817	619	310	114	723		+ 328		18
А3	14		127	47	149	1310	1811	49	1216		1019		18
А4	6		16	7	815	1215	13	5	155		129		20
А5	4		249	01	1213	67	01	12	419		18		36
А6	11		313	17	515	313	128	1210	322		224		24
Наличие порожняка	66	18	20	12	30	12	18	18		194/194

V₁= A₁Б₁ – U₁ = 5-0= 5; V₇ = A₁Б₇ – U₁ = 14-0=14; V₈ = A₁Б₈ – U₁= 15-0 =15