№18. Решение задачи коммивояжера с использованием метода ветвей и границ

Цель: научить использовать метод ветвей и границ для решения задачи коммивояжера.

Оборудование: практикум, тетрадь для лабораторных и практических работ.

Литература:

1. Плотников А. Д. Математическое программирование: экспресс-курс. - Мн.: Новое знание, 2007. С. 147-156.
2. Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 446-465.

Время выполнения: 2 часа.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Сформулируйте постановку задачи коммивояжера.
2. Опишите математическую модель задачи коммивояжера.
3. Опишите процесс редукции матрицы.
4. Опишите процесс решения задачи коммивояжера методом ветвей и границ.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:

Постановка задачи коммивояжера

Имеется n городов. Расстояния между любой парой городов известны и оставлют a_ij (i,j = 1,n, i!=j). Если прямого маршрута между городами i и j не существует, то a_ij = ∞. Растояния между городами удобно записывать в виде матрицы A = (a_ij), где a_ii = ∞.

Коммивояжер, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них один, и только один раз, и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы наименьшей.

Если городам поставить в соответствие вершины графа, а соединяющим их дорогам — дуги, то в терминах теории графов задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром (по имени английского математика Гамильтона) называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Здесь под длиной контура понимают не количество дуг, входящих в контур, а сумму их длин.

Для записи постановки задачи в терминах целочисленной линейной оптимизации определим булевы переменные следующим образом:

1. x_ij = 1, если коммивояжер переезжает из города i в город j;
2. x_ij = 0, в противном случае.

Тогда задача заключается в отыскании значений переменных x_ij, минимизирующих

при ограничениях

Методы решения задачи коммивояжера

• метод ветвей и границ;
• венгерский метод..

Алгоритм метода ветвей и границ

• Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d_min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d_min.
• Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d_min, и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d_min.
• Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
• Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
• Выбирают дугу (i,j), для которой степень нулевого элемента достигает максимального значения.
• Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*). Для получения матрицы контуров, включающих дугу (i,j), вычеркивают в матрице строку i и столбец j. Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
• Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*).
• Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*). Если H(i,j)<H(i*,j*), то дальнейшему ветвлению в первую очередь подлежит множество (i,j), иначе - разбиению подлежит множество (i*,j*).
• Если в результате ветвлений получается матрица (2x2), то определяют полученный ветвлением гамильтонов контур и его длину.
• Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

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

Решение.

СОДЕРЖАНИЕ РАБОТЫ:

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Сформулируйте постановку задачи коммивояжера.
2. Опишите математическую модель задачи коммивояжера.
3. Опишите процесс редукции матрицы.
4. Опишите процесс решения задачи коммивояжера методом ветвей и границ.

ДОМАШНЕЕ ЗАДАНИЕ:

Выучить алгоритм решения задачи коммивояжера методом ветвей и границ.