Курсовая работа (т): Транспортный процесс и производительность подвижного состава

С другой стороны общее количество груза, отправляемого из пункта А_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

(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. Оптимальный план возврата порожняка