Методическое пособие для выполнения контрольной работы по дисциплине
жүктеу/скачать 0.49 Mb.
|
| x1x4 (0+18=18),x1x6 (0+19=19),x2x5 (5+4=9),x3x2 (4+0=4),x4x2 (18+0=18),x5x3 (15+0=15), x6x1 (0+42=42),x6x3 (0+0=0). Максимальная сумма из всех сумм постоянных приведения равна 42, что соответствует дуге x6x1. Таким образом, множество делится на два подмножества и 10(x6x1).
Нижняя граница подмножества равна нижней границе множества плюс 42 (139), что больше 102, и, следовательно, множество 9 не является оптимальным. Чтобы получить матрицу расстояний 10, нужно из матрицы 1 вычеркнуть строку А6 и столбец А1 и элемент с16 заменить прочерком “”.
После приведения данной матрицы нижняя граница для 10 будет равна 97+9=106, что больше, чем 102. Следовательно, найденный маршрут x4→x1→x6→x3→x2→x5→x4 является кратчайшим с длиной пути l=102. Окончательно вся схема ветвления представлена ниже. Задание 5. Найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов А1, А2, А3, А4, А5 и А6. Расстояния между городами заданы следующей таблицей:
жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|