3.4 Пример

Решить задачу коммивояжера с матрицей расстояний

.

1. Вычисление оценки . Выполним операцию приведения матрицы .

Отсюда

.

2. Выбор дуги для ветвления. Для всех нулей приведенной матрицы вычислим :

Максимальное значение равно 6 и достигается на дугах и . Выберем для ветвления, например, дугу , потому что .

3. Ветвление. Множество разбиваем на два подмножества и . Верхний индекс указывает на номер итерации, а нижний - на наличие выбранной дуги в маршрутах данных множеств. Множество состоит из всех маршрутов коммивояжера, не содержащих дугу . Весь процесс решения данной задачи изображен на рис. 6. Рядом с каждой вершиной указано значение оценки целевой функции для соответствующего множества маршрутов.

Рис. 6

4. Вычисление оценки . Выполним операцию приведения матрицы, соответствующей . Она получается из приведенной матрицы заменой элемента на .

Получаем

Замечаем, что . Значит оценку для можно вычислить проще, а именно .

5. Вычисление оценки . Матрица, соотсетствующая , получается из приведенной матрицы вычеркиванием 1-й строки, 2-го столбца и запрещением элемента .

Итак, .

6. Выбор множества для ветвления. Так как , то ветвим множество .

7. Выбор дуги ветвления. Для приведенной матрицы из п. 5 вычислим

.

Максимальное значние достигается на дугах и . Выберем для ветвления дугу .

8. Ветвление. Множество разбиваем на два подмножества и . Множество состоит из всех маршрутов множества , не содержащих дугу , а - из всех маршрутов множества , содержащих дугу (см. рис. 6).

9. Вычисление оценки .

.

9. Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 5, вычеркиванием 3-й строки, 4-го столбца и запрещением элемента .

.

Значит .

9. Допустимое решение задачи. В п. 10 получена матрица размером с двумя незапрещенными элементами и . Это означает, что множество состоит из единственного маршрута, который содержит дуги . Его длина равна 23, т.е. .

10. Отсев неперспективных множеств. Так как , то множество не содержит оптимального решения и выбывает из числа кандидатов на ветвление.

11. Выбор множества для ветвления. Кандидатом на ветвление является только множество .

12. Выбор дуги ветвления. Для приведенной матрицы из п. 4 вычислим . Выберем для ветвления дугу .

13. Ветвление. Множество разбиваем на два подмножества и .

14. Вычисление оценки . . Так как , то объявляется неперспективным.

15. Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 4, вычеркиванием 2-й строки, 1-го столбца и запрещением элемента .

.

Итак, .

9. Выбор множества для ветвления. Единственным кандидатом на вевление является .

10. Выбор дуги ветвления. Для приведенной матрицы из п. 18 вычислим . Выберем для ветвления дугу .

11. Ветвление. Множество разбивается на и .

12. Вычисление оценки . .

13. Вычисление оценки . Матрица, соответсвующая , получается из приведенной матрицы, найденной в п. 18, вычеркиванием 1-й строки, 3-го столбца и запрещением элемента (исключаем подцикл ).

Значит .

9. Выбор множества для ветвления. Кандидатами на ветвление являются и . Так как для обоих множеств нижняя оценка больше рекорда целевой функции, то они являются неперспективными. Других кандидатов на ветвление нет. Следовательно, процесс решения задачи окончен. Оптимальным решением является маршрут , его длина равна 23.