Материал: Транспортный процесс и производительность подвижного состава

Все грузы укладываются партиями на стандартные европаллеты. Европаллет представляет собой специальный поддон, на котором надежно крепится определенный груз. Европаллеты предназначены для максимально быстрой транспортировки и удобства хранения продукции. Они обеспечивают надежную защиту грузов от деформации и прочих повреждений, которые могут возникнуть в процессе их доставки. Стандартные размеры европаллета 800*1200*150 мм.

На каждом паллете обязательно наличие фирменного клейма EUR в овале, выжженного на правых несущих ножках паллета. На остальных ножках также нанесена маркировка, указывающая производителя и цифровая информация (серия, год выпуска).

Таким образом, АО «VEZU» обладает достаточным парком автотранспортных средств. Погрузка автоматизирована с помощью погрузчиков - это существенно ускоряет саму процедуру погрузки-разгрузки.

2. Практический раздел

2.1 Математическая модель задачи

В автотранспортное предприятие поступили заявки на перевозки однородных грузов на следующий день (табл. 5). Требуется:

)        составить оптимальный сменно-суточный план перевозки грузов (маршруты движения автомобилей и сменные задания водителей), обеспечивающий вывоз заданных объемов при минимальном суммарном порожнем пробеге автомобилей;

)        рассчитать выработку автомобиля в тоннах и тонно-километрах при изменении qγ, V_m, t_пв, l_г, T_н;

)        по выполненным расчётам сделать выводы об эффективности перевозок.

Таблица 5

2.2 Алгоритм и метод решения задачи

Имеются отправители грузов A_i , А₂ ...A_i...A_m с имеющимся у каждого отправителя количеством груза a₁, а₂...а_i...а_mтонн.

Имеются получатели груза В₁B₂...B_j...B_n с требуемым каждому количеством груза в₁ в₂...в_j..в_nтонн.

Каждый отправитель может удовлетворить запросы любого получателя.

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

Количество тонн груза для доставки в пункт В_j, из всех пунктов отправления равно

 (1)

Где Х_ij - количество тонн груза предназначенного к отправке из А_i, в В_j, а так как потребность пункта В_j, составляет b_jтонн, то

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

С другой стороны общее количество груза, отправляемого из пункта А_i, во все пункты назначения В_j, составит

По условиям задачи эта сумма равна наличию груза в пункте А_i.

Сказанное справедливо к любому пункту отправления, имеем т аналогичных (1) уравнений:

 (2)

Более компактно уравнения (1) и (2) записываются в форме

Суммарная транспортная работа Р из условий, таким образом, равна

Таким образом, в математической форме транспортная задача требует определения значений переменных Х_ij, минимизирующих линейную формулу

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

Рассмотрим метод потенциалов. Этот метод рекомендуется использовать в курсовом проектировании.

Метод потенциалов реализуется с помощью строго регламентированной процедуры вычислений - алгоритма метода. При этом все вычисления производят в таблице-матрице, составленной по условиям задачи, представленной на рисунке 1.

Задача формулируется так: имеется ряд поставщиков транспортно-однородного груза и ряд потребителей этого груза. Требуется получить такой план закрепления, чтобы при перевозке грузов транспортная работа (ткм) была минимальной. Так как оптимизации подлежит транспортная работа, поэтому в качестве затрат в матрицу вводится расстояние между всеми пунктами.

Для решения задач по составлению оптимальных планов закрепления необходимо провести подготовительную работу, заключающуюся в определении следующих исходных данных:

. Наименование грузоотправителей и объём поставок грузов.

. Наименование грузополучателей и объёмы потребления.

. Расстояние перевозки от каждого грузоотправителя до каждого получателя.

Представим на рис.1 алгоритм метода потенциалов:

Рис. 1. Алгоритм метода

2.3 Решение задачи маршрутизации методом потенциалов

Используем метод минимального километража для построения первого опорного плана (таблица 6):

Таблица 6. Метод минимального километража

Искомый элемент равен c52=1, но т.к. ограничения выполнены, то x52=0.

Опорный план представлен в следующей таблице:

Таблица 7. Первоначальный опорный план

(x) = 5*207 + 1*108 + 6*27 + 1*27 + 7*54 + 14*27 + 12*81 + 15*99 + 1*162 + 1*27 + 3*54 + 2*27 = 4950

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5+ v1 = 3; 5 + u6 = 3; u6 = -2+ v8 = 2; -2 + v8 = 2; v8 = 4+ v8 = 1; 4 + u5 = 1; u5 = -3+ v2 = 1; -3 + v2 = 1; v2 = 4+ v5 = 1; -3 + v5 = 1; v5 = 4+ v3 = 14; 0 + u3 = 14; u3 = 14+ v3 = 14; 14 + v3 = 14; v3 = 0+ v3 = 15; 0 + u4 = 15; u4 = 15+ v7 = 12; 14 + v7 = 12; v7 = -2+ v7 = 7; -2 + u2 = 7; u2 = 9+ v4 = 6; 9 + v4 = 6; v4 = -3

u2 + v6 = 1; 9 + v6 = 1; v6 = -8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;2): 0 + 4 > 1; ∆12 = 0 + 4 - 1 = 3

(2;1): 9 + 5 > 5; ∆21 = 9 + 5 - 5 = 9

(2;3): 9 + 0 > 8; ∆23 = 9 + 0 - 8 = 1

(2;5): 9 + 4 > 3; ∆25 = 9 + 4 - 3 = 10

(2;8): 9 + 4 > 3; ∆28 = 9 + 4 - 3 = 10

(3;1): 14 + 5 > 12; ∆31 = 14 + 5 - 12 = 7

(3;2): 14 + 4 > 4; ∆32 = 14 + 4 - 4 = 14

(3;5): 14 + 4 > 11; ∆35 = 14 + 4 - 11 = 7

(3;6): 14 -8 > 4; ∆36 = 14 -8 - 4 = 2

(3;8): 14 + 4 > 10; ∆38 = 14 + 4 - 10 = 8

(4;1): 15 + 5 > 16; ∆41 = 15 + 5 - 16 = 4

(4;2): 15 + 4 > 7; ∆42 = 15 + 4 - 7 = 12

(4;5): 15 + 4 > 13; ∆45 = 15 + 4 - 13 = 6

(4;6): 15 -8 > 5; ∆46 = 15 -8 - 5 = 2

(4;8): 15 + 4 > 12; ∆48 = 15 + 4 - 12 = 7

(6;2): -2 + 4 > 1; ∆62 = -2 + 4 - 1 = 1(3,9,1,10,10,7,14,7,2,8,4,12,6,2,7,1) = 14

Выбираем максимальную оценку свободной клетки (3;2): 4

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 8. Опорный план №2

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5+ v1 = 3; 5 + u6 = 3; u6 = -2+ v8 = 2; -2 + v8 = 2; v8 = 4+ v8 = 1; 4 + u5 = 1; u5 = -3+ v2 = 1; -3 + v2 = 1; v2 = 4+ v2 = 4; 4 + u3 = 4; u3 = 0+ v3 = 14; 0 + v3 = 14; v3 = 14+ v3 = 15; 14 + u4 = 15; u4 = 1+ v7 = 12; 0 + v7 = 12; v7 = 12+ v7 = 7; 12 + u2 = 7; u2 = -5+ v4 = 6; -5 + v4 = 6; v4 = 11+ v6 = 1; -5 + v6 = 1; v6 = 6

u5 + v5 = 1; -3 + v5 = 1; v5 = 4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;2): 0 + 4 > 1; ∆12 = 0 + 4 - 1 = 3

(1;3): 0 + 14 > 7; ∆13 = 0 + 14 - 7 = 7

(1;4): 0 + 11 > 8; ∆14 = 0 + 11 - 8 = 3

(1;6): 0 + 6 > 2; ∆16 = 0 + 6 - 2 = 4

(2;3): -5 + 14 > 8; ∆23 = -5 + 14 - 8 = 1

(3;6): 0 + 6 > 4; ∆36 = 0 + 6 - 4 = 2

(4;6): 1 + 6 > 5; ∆46 = 1 + 6 - 5 = 2

(5;4): -3 + 11 > 6; ∆54 = -3 + 11 - 6 = 2

(5;6): -3 + 6 > 1; ∆56 = -3 + 6 - 1 = 2

(5;7): -3 + 12 > 4; ∆57 = -3 + 12 - 4 = 5

(6;2): -2 + 4 > 1; ∆62 = -2 + 4 - 1 = 1

(6;3): -2 + 14 > 5; ∆63 = -2 + 14 - 5 = 7

(6;4): -2 + 11 > 3; ∆64 = -2 + 11 - 3 = 6

(6;7): -2 + 12 > 3; ∆67 = -2 + 12 - 3 = 7(3,7,3,4,1,2,2,2,2,5,1,7,6,7) = 7

Выбираем максимальную оценку свободной клетки (1;3): 7

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 9. Перераспределение по циклу.

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 2) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 10. Опорный план №3

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5+ v1 = 3; 5 + u6 = 3; u6 = -2+ v8 = 2; -2 + v8 = 2; v8 = 4+ v8 = 1; 4 + u5 = 1; u5 = -3+ v5 = 1; -3 + v5 = 1; v5 = 4+ v2 = 1; 0 + v2 = 1; v2 = 1+ v2 = 4; 1 + u3 = 4; u3 = 3+ v3 = 14; 3 + v3 = 14; v3 = 11+ v3 = 15; 11 + u4 = 15; u4 = 4+ v7 = 12; 3 + v7 = 12; v7 = 9+ v7 = 7; 9 + u2 = 7; u2 = -2+ v4 = 6; -2 + v4 = 6; v4 = 8

u2 + v6 = 1; -2 + v6 = 1; v6 = 3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;3): 0 + 11 > 7; ∆13 = 0 + 11 - 7 = 4

(1;6): 0 + 3 > 2; ∆16 = 0 + 3 - 2 = 1

(2;3): -2 + 11 > 8; ∆23 = -2 + 11 - 8 = 1

(3;6): 3 + 3 > 4; ∆36 = 3 + 3 - 4 = 2

(4;6): 4 + 3 > 5; ∆46 = 4 + 3 - 5 = 2

(5;7): -3 + 9 > 4; ∆57 = -3 + 9 - 4 = 2

(6;3): -2 + 11 > 5; ∆63 = -2 + 11 - 5 = 4

(6;4): -2 + 8 > 3; ∆64 = -2 + 8 - 3 = 3

(6;7): -2 + 9 > 3; ∆67 = -2 + 9 - 3 = 4(4,1,1,2,2,2,4,3,4) = 4

Выбираем максимальную оценку свободной клетки (1;3): 7

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 11. Перераспределение по циклу.

Цикл приведен в таблице (1,3 → 1,2 → 3,2 → 3,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 27. Прибавляем 27 к объемам грузов, стоящих в плюсовых клетках и вычитаем 27 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 12. Опорный план №4

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5+ v1 = 3; 5 + u6 = 3; u6 = -2+ v8 = 2; -2 + v8 = 2; v8 = 4+ v8 = 1; 4 + u5 = 1; u5 = -3+ v5 = 1; -3 + v5 = 1; v5 = 4+ v2 = 1; 0 + v2 = 1; v2 = 1+ v2 = 4; 1 + u3 = 4; u3 = 3+ v7 = 12; 3 + v7 = 12; v7 = 9+ v7 = 7; 9 + u2 = 7; u2 = -2+ v4 = 6; -2 + v4 = 6; v4 = 8+ v6 = 1; -2 + v6 = 1; v6 = 3+ v3 = 7; 0 + v3 = 7; v3 = 7

u4 + v3 = 15; 7 + u4 = 15; u4 = 8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;6): 0 + 3 > 2; ∆16 = 0 + 3 - 2 = 1

(3;6): 3 + 3 > 4; ∆36 = 3 + 3 - 4 = 2

(4;2): 8 + 1 > 7; ∆42 = 8 + 1 - 7 = 2