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

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

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

Искомый элемент равен 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 т/км