Реферат: Минимизация холостых пробегов автотранспортного предприятия

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	7 2	8 1	4	2	1814		1815		78
А2	16		5 16	1813	8 17	6 19	3 10	1 14	7 23		+ 3 28		18
А3	14		12 7	4 7	14 9	13 10	1811	4 9	12 16		10 19		18
А4	6		16	7	815	1215	13	5	15 5		12 9		20
А5	4		249	01	1213	6 7	01	1 2	4 19		1 8		36
А6	11		3 13	1 7	5 15	3 13	128	1210	3 22		2 24		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

……………………….. ………………………….. …………………………

U₅ = A₅ Б₁ – V₁ = 9-5= 4; V₃ = A₅ Б₃ – U₅ = 13-4= 9; U₄ = A₄ Б₃ – V₃ = 15-9 =6;

После расчёта индексов проверяем незанятые клетки на потенциальность.

п.4.2.3. Определение потенциальных клеток. Незанятые клетки, для которых получилось, что U_i + V_j >l_ij – называются потенциальными. Проверяем незанятые клетки на потенциальность. Проверка сводится к сравнению расстояний каждой незанятой клетки с суммой соответствующих ей индексов.

А₁ Б₂ = u₁ + v₂ = 0-3 = -3 < ( l_1-2 =1) ;

А₁ Б₃ = u₁ + v₃ = 0+9 = 9 > ( l­_1-3­ =7) -- 2 ;

....................................................................;

А₂ Б₈ = u₂ + v₈ = 16+15= 31> ( l_2-8 =3) -- 28 ;

.....................................................................;

А₆ Б₈ = u₆ + v₈ = 11+15= 26> ( l_6-8 =2) -- 24 .

По данным вычислений построим таблицу 7.

4.1.5. Оптимизация плана. Проверка допустимого плана на оптимальность заключается в соблюдении условий: {8} и {9}. Если данные условия не соблюдаются для клеток X_ij =0, то значение потенциала отрицательно, что и определяет потенциальную клетку. Следует скорректировать допустимый план. Корректировка плана состоит в перемещении в потенциальную клетку с наименьшим по модулю потенциалом какую-нибудь загрузку. Перемещение производится при условии сохранения количества “+” и “-“ по строке и столбцу. Производя перемещение, следует повторить процесс определения потенциала до тех пор, пока условия {8} и {9} не будут соблюдены. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.

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

Цепочку возможных перемещений определяют: для потенциальной клетки с наибольшим значением потенциала строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы одна из её вершин находилась в данной клетке, а все остальные вершины в занятых клетках. Знаком “+” отмечают в цепочке её нечётные вершины, считая вершину в клетке с наибольшим потенциалом, а знаком “-“ – чётные вершины. Наименьшая загрузка в вершинах 18 ездок, уменьшая загрузку в вершинах со знаком “-“ и увеличивая её в вершинах со знаком “+” получают улучшенный план. Дальнейшие расчёты по его оптимизации производятся аналогично. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.