Математические методы в организации транспортного процесса
Для столбца, соответствующего индексу V 8, ими будут L 5, 8 = 17, L
6, 8 = 13, L 7, 8 = 19. Значения индексов U 5, U 6, U 7 известны: U 5 = 26,
U 6 = 15, U 7 = 12. Следовательно,
V 8 = min(U 5 + L 5, 8 = 26 + 17 = 43; U 6 + L 6, 8 = 15 + 13
= 28;
U 7 + L 7, 8 = 12 + 19 = 31) = 28.
Запишем их в строку V i (смотрите таблицу ниже).
4. Все индексы найдены. Проверим полученное решение на
оптимальность, т. е. выполнение условия L ij >= V j – U i для каждой
заполненной клетки матрицы.
[pic]
Для всех заполненных клеток условие L ij >= V j – U i соблюдается.
Полученное решение является оптимальным. Следовательно, минимальными
расстояниями от вершины 1 до всех остальных будут:
V 2 = 8, V 3 = 10, V 4 = 10, V 5 = 26, V 6 = 15, V 7 = 12, V 8 = 28.
Определим кратчайший путь от вершины 1 до вершины 5. Для этого в
столбце 5 найдём элемент, значение которого равно разности индексов столбца
и строки L ij = V j – U i :
L 4, 5 = V 5 – U 4 = 26 – 10.
L 4, 5 – последнее звено пути и, соответственно,
вершина 4 – предпоследняя.
И далее, в столбце 4 определим:
L 1, 4 = V 4 – U 1 = 10 – 0 = 10.
L 1, 4 – первое звено пути, так как вершина 1 является начальной
фиксированной.
Таким образом, имеем минимальный путь от вершины 1 до вершины 5,
проходящий через вершины 1, 4, 5, длина которого равна 26.
| |  скачать работу |
Математические методы в организации транспортного процесса |
