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

(4;4): 8 + 8 > 15; ∆44 = 8 + 8 - 15 = 1

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

(4;7): 8 + 9 > 15; ∆47 = 8 + 9 - 15 = 2

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

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

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

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

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

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

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

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

Таблица 14. Опорный план №5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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+ v3 = 7; 0 + v3 = 7; v3 = 7+ v3 = 15; 7 + u4 = 15; u4 = 8

u4 + v6 = 5; 8 + v6 = 5; v6 = -3

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

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

(4;4): 8 + 8 > 15; ∆44 = 8 + 8 - 15 = 1

(4;7): 8 + 9 > 15; ∆47 = 8 + 9 - 15 = 2

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

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

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

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

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

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

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

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

Таблица 16. Опорный план №6

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

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

u4 + v6 = 5; 8 + v6 = 5; v6 = -3

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

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

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

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

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

(3;8): 7 + 4 > 10; ∆38 = 7 + 4 - 10 = 1(2,1,3,3,1) = 3

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

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

Цикл приведен в таблице (2,5 → 2,7 → 6,7 → 6,8 → 5,8 → 5,5).

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

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

Таблица 18. Опорный план №7

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

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

u4 + v6 = 5; 8 + v6 = 5; v6 = -3

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

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

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

(5;7): 0 + 5 > 4; ∆57 = 0 + 5 - 4 = 1(2,1,1) = 2

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

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

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

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

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

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

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

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

u4 + v6 = 5; 8 + v6 = 5; v6 = -3

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

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

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

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

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

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

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

Таблица 22. Опорный план №9

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

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

u4 + v6 = 5; 8 + v6 = 5; v6 = -3

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

Значение целевой функции:(x) = 5*261 + 7*54 + 6*27 + 3*81 + 4*108 + 15*72 + 5*27 + 1*81 + 4*54 + 1*54 + 3*81 = 4329 т/км

2.4 Определение маршрутов методом совмещенных планов

Составляем оптимальный план возврата порожняка под погрузку:

Таблица 23. Оптимальный план возврата порожняка

Составляем матрицу совмещенных планов. Выделим отдельным цветом добавленные в матрицу совмещенные планы:

Таблица 24. Матрица совмещенных планов

Строим маршруты движения автомобилей непосредственно на матрице совмещенных планов. Вначале выбираем маятниковые маршруты, после кольцевые.

Маятниковые маршруты определяются клетками с двойной нагрузкой, при этом выбираем наименьшее из значений (в тоннах). В нашем случае клеток с двойной нагрузкой две:

Таблица 25. Выбор маятниковых маршрутов

Итак, маятниковые маршруты:

) А1-Б1-А1, на котором необходимо развезти 126 тонн;

) А4-Б3-А4, на котором необходимо развезти 72 тонны.

Удаляем из матрицы клетки с двойной загрузкой и составляем кольцевые маршруты:

Кольцевые маршруты составляем по следующему принципу: все нечетные вершины должны лежать в «груженых» клетках, а четные - в клетках с порожняком. Для удобства будем отмечать каждый четырехзвенный маршрут отдельным цветом.

) Кольцевой маршрут А2-Б2-А3-Б5-А2 на 81 тонну. Исключаем данный маршрут и ищем новые маршруты.

Таблица 26. Четырехзвенный кольцевой маршрут

) Кольцевой маршрут А5-Б3-А1-Б8-А5 на 54 тонны. Исключаем данный четырехзвенный маршрут и ищем новые маршруты.

Таблица 27. Четырехзвенный кольцевой маршрут

) Кольцевой маршрут А5-Б1-А1-Б7-А5 на 54 тонны. Удаляем его из рассмотрения.

Таблица 28. Четырехзвенный кольцевой маршрут

Поиск четырехзвенных маршрутов завершен. Осуществляем поиск шестизвенных маршрутов:

) Маршрут А5-Б1-А1-Б7-А6-Б5-А5 на 54 тонны. Исключаем его из рассмотрения:

Таблица 29. Шестизвенный кольцевой маршрут

Имеем следующую матрицу.

Таблица 30. Заключительный поиск кольцевых маршрутов

Осталось развести 6 точек по 27 тонн в каждую, а также осталось 6 клеток с 27 тоннами порожняка. В данном случае остался единственный замкнутый маршрут из 12 звеньев, который полностью удовлетворит запросы всех потребителей в грузах.

Маршрут выглядит следующим образом:

Таблица 31. 12-звенный кольцевой маршрут

А5-Б1-А1-Б7-А6-Б6-А4-Б4-А2-Б2-А3-Б5-А5 на 27 тонн.

Проверяем, весь ли груз таким образом будет доставлен потребителям. Имеем: 126+72+(81+54+54)*2+54*3+27*6=900, таким образом, маршруты полностью удовлетворят запросы потребителей.

2.5 Технологический расчет маршрутов

На каждый маршрут распределим количество автомобилей. Для этого найдем реальную грузоподъемность: