Меню
Главная
Авторизация/Регистрация
 
Главная arrow Техника arrow Транспортный процесс и производительность подвижного состава

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

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

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

5

1

7

8

4

2

14

15

315

5

13

8

6

3

1

7

3

108

12

4

14

13

11

4

12

10

108

16

7

15

15

13

5

15

12

99

9

1

13

6

1

1

4

1

189

3

1

5

3

8

10

3

2

81

261

108

126

27

162

27

135

54

900

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

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

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

F(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

u6 + v1 = 3; 5 + u6 = 3; u6 = -2

u6 + v8 = 2; -2 + v8 = 2; v8 = 4

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

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

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

u3 + v3 = 14; 0 + u3 = 14; u3 = 14

u3 + v3 = 14; 14 + v3 = 14; v3 = 0

u4 + v3 = 15; 0 + u4 = 15; u4 = 15

u3 + v7 = 12; 14 + v7 = 12; v7 = -2

u2 + v7 = 7; -2 + u2 = 7; u2 = 9

u2 + 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

max(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

u6 + v1 = 3; 5 + u6 = 3; u6 = -2

u6 + v8 = 2; -2 + v8 = 2; v8 = 4

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

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

u3 + v2 = 4; 4 + u3 = 4; u3 = 0

u3 + v3 = 14; 0 + v3 = 14; v3 = 14

u4 + v3 = 15; 14 + u4 = 15; u4 = 1

u3 + v7 = 12; 0 + v7 = 12; v7 = 12

u2 + v7 = 7; 12 + u2 = 7; u2 = -5

u2 + v4 = 6; -5 + v4 = 6; v4 = 11

u2 + 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

max(3,7,3,4,1,2,2,2,2,5,1,7,6,7) = 7

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

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

Цикл приведен в таблице (1,3 > 1,1 > 6,1 > 6,8 > 5,8 > 5,2 > 3,2 > 3,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

u6 + v1 = 3; 5 + u6 = 3; u6 = -2

u6 + v8 = 2; -2 + v8 = 2; v8 = 4

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

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

u1 + v2 = 1; 0 + v2 = 1; v2 = 1

u3 + v2 = 4; 1 + u3 = 4; u3 = 3

u3 + v3 = 14; 3 + v3 = 14; v3 = 11

u4 + v3 = 15; 11 + u4 = 15; u4 = 4

u3 + v7 = 12; 3 + v7 = 12; v7 = 9

u2 + v7 = 7; 9 + u2 = 7; u2 = -2

u2 + 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

max(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

u6 + v1 = 3; 5 + u6 = 3; u6 = -2

u6 + v8 = 2; -2 + v8 = 2; v8 = 4

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

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

u1 + v2 = 1; 0 + v2 = 1; v2 = 1

u3 + v2 = 4; 1 + u3 = 4; u3 = 3

u3 + v7 = 12; 3 + v7 = 12; v7 = 9

u2 + v7 = 7; 9 + u2 = 7; u2 = -2

u2 + v4 = 6; -2 + v4 = 6; v4 = 8

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

u1 + 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

max(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

u6 + v1 = 3; 5 + u6 = 3; u6 = -2

u6 + v8 = 2; -2 + v8 = 2; v8 = 4

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

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

u1 + v2 = 1; 0 + v2 = 1; v2 = 1

u3 + v2 = 4; 1 + u3 = 4; u3 = 3

u3 + v7 = 12; 3 + v7 = 12; v7 = 9

u2 + v7 = 7; 9 + u2 = 7; u2 = -2

u2 + v4 = 6; -2 + v4 = 6; v4 = 8

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

u4 + 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

max(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

u6 + v1 = 3; 5 + u6 = 3; u6 = -2

u6 + v7 = 3; -2 + v7 = 3; v7 = 5

u2 + v7 = 7; 5 + u2 = 7; u2 = 2

u2 + v4 = 6; 2 + v4 = 6; v4 = 4

u3 + v7 = 12; 5 + u3 = 12; u3 = 7

u3 + v2 = 4; 7 + v2 = 4; v2 = -3

u6 + v8 = 2; -2 + v8 = 2; v8 = 4

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

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

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

u4 + 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

max(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

u6 + v1 = 3; 5 + u6 = 3; u6 = -2

u6 + v7 = 3; -2 + v7 = 3; v7 = 5

u2 + v7 = 7; 5 + u2 = 7; u2 = 2

u2 + v4 = 6; 2 + v4 = 6; v4 = 4

u2 + v5 = 3; 2 + v5 = 3; v5 = 1

u5 + v5 = 1; 1 + u5 = 1; u5 = 0

u5 + v8 = 1; 0 + v8 = 1; v8 = 1

u3 + v7 = 12; 5 + u3 = 12; u3 = 7

u3 + v2 = 4; 7 + v2 = 4; v2 = -3

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

u4 + 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

max(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

u2 + v1 = 5; 5 + u2 = 5; u2 = 0

u2 + v4 = 6; 0 + v4 = 6; v4 = 6

u2 + v5 = 3; 0 + v5 = 3; v5 = 3

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

u5 + v8 = 1; -2 + v8 = 1; v8 = 3

u2 + v7 = 7; 0 + v7 = 7; v7 = 7

u3 + v7 = 12; 7 + u3 = 12; u3 = 5

u3 + v2 = 4; 5 + v2 = 4; v2 = -1

u6 + v7 = 3; 7 + u6 = 3; u6 = -4

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

u4 + 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

u2 + v1 = 5; 5 + u2 = 5; u2 = 0

u2 + v4 = 6; 0 + v4 = 6; v4 = 6

u2 + v5 = 3; 0 + v5 = 3; v5 = 3

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

u5 + v7 = 4; -2 + v7 = 4; v7 = 6

u3 + v7 = 12; 6 + u3 = 12; u3 = 6

u3 + v2 = 4; 6 + v2 = 4; v2 = -2

u6 + v7 = 3; 6 + u6 = 3; u6 = -3

u5 + v8 = 1; -2 + v8 = 1; v8 = 3

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

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

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

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

Значение целевой функции:

F(x) = 5*261 + 7*54 + 6*27 + 3*81 + 4*108 + 15*72 + 5*27 + 1*81 + 4*54 + 1*54 + 3*81 = 4329 т/км

 
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Региональная экономика
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее