Реферат: Минимизация холостых пробегов автотранспортного предприятия
Проверка незанятых клеток на потенциальность
Построение цепочки возможных перемещений загрузок
Расчёт знаков “+” и “-“ по вершинам цепочки
Поиск наименьшей среди загрузок, отмеченных знаком “-“
Изменение загрузки на вершинах цепочки
Решение закончено: оптимальный план составлен
Потенциальных клеток нет
Рис. 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 | |||||
| Наличие порожняка | |||||||||||||
В строке записываются значения индексов Vj , а в столбце – значения индексов Ui .
Для дальнейших расчётов необходимо определить количество автомобиле-ездок, их находим по формуле :
Ze = 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 |
В правом верхнем углу клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами; условие Sbj = 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 . Поэтому необходимо создать недостающие клетки, поставив нулевые загрузки в клетки А5 -Б2 и А5 -Б5 .
Допустимый исходный план составлен, проверим его на оптимальность.
п.4.2. Расчёт индексов для занятых клеток.
п.4.2.1. Расчёт суммарного холостого пробега. Рассчитываем суммарный холостой пробег для допустимого исходного плана (таблица 6) с помощью формулы: