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

Пусть имеется (n+ 1)городов A ₀, A ₁, A ₂, A ₃, ..., A_n. Между всеми парами городов известно расстояние c_{i , j} ³0. Коммивояжер, который находится в городе A ₀, должен обойти все города, побывав в каждом ровно один раз и вернуться в город A ₀ так, чтобы длина пройденного пути была наименьшей. Путь коммивояжера i ₀, i ₁, i ₂, ..., i_n, i ₀ образует замкнутый маршрут. Его длина

l (i ₀, i ₁, i ₂, ..., i_n, i ₀)=

Так как это задача на перестановках, то число таких маршрутов равно n!. Для поиска минимального (оптимального) маршрута применим метод ветвей и границ. Общая схема этого метода приведена в разделе «Комбинаторные методы решения задач целочисленного линейного программирования». Дадим описание этого метода для задачи о коммивояжере.

Алгоритм.

Шаг 1. Задание множества X _0,1 и вычисление оценки x _0,1.

Множество X _0,1 есть множество всех возможных маршрутов коммивояжера. Оценку x _0,1 получаем, используя процедуру приведе н ия матрицы C _0,1= C =(c_{i , j} ), i =1,2,3,…, n, j =1,2,3,…, n, следующим образом.

Для всех i =1,2,3,…, n, h_i:=min{ c_{i , j} | j =1,2,3,…, n },

c'_{i , j} := c_{i , j} – h_i, i =1,2,3,…, n, j =1,2,3,…, n.

Для всех j =1,2,3,…, n, H_j:=min{ c'_{i , j} | i =1,2,3,…, n },

c" _{i , j} := c' _{i , j} – H_j, i =1,2,3,…, n, j =1,2,3,…, n.

Переменные h_i, H_j называют коэффициентами приведения. Матрицу C" _0,1=(c"_{i , j}), i =1,2,3,…, n, j =1,2,3,…, n, называют приведенной матрицей.

Полагаем

Шаг 2 .Разбиение множества X_r,t на подмножества.

Пусть построено подмножество X_{r , t} и нижняя оценка функционала x_{r , t} на нем. Этому подмножеству соответствует приведенная матрица C"_{r , t} . Подмножество разбиваем на два: X_{r+ 1, m+ 1}, X_{r+ 1, m+ 2}, каждому из которых будут соответствовать свои оценки x_{r+ 1, m+ 1}, x_{r+ 1, m+ 2} и приведенные матрицы С"_{r+ 1, m+ 1}, С"_{r+ 1, m+ 2}. Подмножество X_{r+ 1, m+ 1}получается из X_{r , t} добавлением условия: из пункта p непосредственно идти в пункт q. Подмножество X_{r+ 1, m+ 2} получается добавлением условия: из пункта p непосредственно в пункт q идти запрещается. Пару (p, q) выбирают таким образом, чтобы с наибольшей вероятностью подмножество X_{r+ 1, m+ 1}содержало оптимальный цикл, а X_{r+ 1, m+ 2} не содержало его. Для этого пару (p, q) выбирают таким образом, чтобы c_{p , q} =0, при этом, чтобы величина min{ c_{p , j} | j¹q } + min{ c_{i , q} | i¹p } была максимальной, где c_{p , j} , c_{i , q} берутся из матрицы C"_{r , t}

Шаг 3. Преобразование матриц расстояний, пересчет оценок.

Матрицу C"_{r+ 1, m+ 2}строим следующим образом. Полагаем C_{r+ 1, m+ 2}= C_{r , t} , в ней с_{p , q} := M, где M – достаточно большое число, принимаемое за бесконечность. Матрица C"_{r+ 1, m+ 2} получается из C_{r+ 1, m+ 2} процедурой приведения. Для получения x_{r+ 1, m+ 2}складываем x_{r , t} с полученными коэффициентами приведения. Матрицу C"_{r+ 1, m+ 1} строим следующим образом. Полагаем C_{r+ 1, m+ 1}= C_{r , t} , и в ней вычеркиваем строку p и столбец q. Налагаем условие, иключающее образование малых циклов. Для этого восстанавливаем части маршрута, образованные непосредственными переходами в X_{r+ 1, m+ 1}. Если добавление любой пары (i, j) к этим маршрутам образует малый цикл, то в матрице C_{r+ 1, m+ 1} c_{i , j} := –M. Матрица C"_{r+ 1, m+ 1} получается из C_{r+ 1, m+ 1} процедурой приведения. Для получения x_{r+ 1, m+ 2} складываем x_{r , t} с полученными коэффициентами приведения.

 

Пример.

Рассмотрим задачу, в которой матрица расстояний имеет вид:

C 0,1	j
						hi
i		M
		M
			M
				M
					M
						M
		Hj

 

Требуется решить поставленную задачу методом ветвей и границ.

Решение.

Шаг 0. Приводим матрицу C _0,1. Находим h_i и вычитаем из c_{i , j} . Получим матрицу

C' 0,1	j
						hi
i		M
		M
			M
				M
					M
						M
		Hj

 

Величины H_j записаны в последней строке этой таблицы, вычитаем их из c'_{i , j} ,получим следующую таблицу

 

C" 0,1	j
						hi
i		M
		M
			M
				M
					M
						M
							x 0,1=21
		Hj

 

Строим дерево разбиения

Шаг 1 .

Разбиваем множество X _0,1 на подмножества X _1,1, X _1,2. В качестве пары (p, q) берем (2,3). Для нее c" _2,3=0 и (min{ c _{2, j} ) |j¹ 3} + min{ c_{i ,3} | i¹ 2})максимально. Для подмножества X _1,1 из пункта 2 идти в пункт 3. Матрица расстояний будет иметь вид:

C 11	j
					hi
i		M
		M
				M
					M
		Hj

Для запрета малых циклов запрещаем переход из пункта 3 в пункт 2, получаем

 

C 11	j
					hi
i		M
		M
			M
				M
					M
		Hj

Все коэффициенты приведения равны 0, поэтому С" _1,1= С _1,1, x _1,1= x _0,1=21.

Подмножество X _1,2 получаем их подмножества X _1,1 запретом перехода из пункта 2 непосредственно в пункт 3. Матрица расстояний будет иметь вид

C 1,2	j
						hi
i		M
		M
			M	M
				M
					M
						M
		Hj

После приведения получим матрицу C¢ _1,2.

C¢ 1,2	j
						hi
i		M
		M
			M	M
				M
					M
						M
		Hj	x 1,2=26

При этом оценка получит значение: x _1,2=21 + 5=26.

Достраиваем дерево разбиения

Шаг 2. Минимальная оценка x _1,1, поэтому разбиваем подмножество X _1,1. В качестве пары (p, q), относительно которой проводим ветвление, используем пару (4,5). Для подмножества X _2,1

C 21	j
				hi
i		M
		M
			M
				M
		Hj	x 2,1=24

В этой матрице с целью запрета малых циклов запрещен перeход из 5 в 4. H ₂=3,поэтому x _2,1=21 + 3=24. Приведенная матрица будет иметь вид

	j
C" 2,1					hi
i		M
		M
			M
				M
		Hj

 

Для подмножества X _2,2

		j
C 22						hi
i		M
		M
			M
				M	M
					M
		Hj

 

После приведения получим

		j
C¢¢ 22						hi
i		M
		M
			M
				M	M
					M
		Hj	x 2,2=25

Оценка принимает вид: x _2,2=21 + 4=25. Достраиваем дерево разбиения

На последующих шагах получим

x 3,4=28

x 3,3=25

Для подмножества X _5,1будем иметь:

C¢¢ 51			hi
i			М
	M
		Hj	x 5,1=26

т.е. остаются переходы из 0 в 4, из 3 в 5. Эти переходы и переходы, выбранные при движении по дереву от вершины для подмножества X _5,1 до вершины подмножества X _0,1, получаем цикл 0 ® 4 ® 2 ® 3 ® 5 ® 1 ® 0, длина которого l =26. Так как все x_{r , t} для концевых вершин дерева не меньше 26, то этот цикл оптимальный.

Если требуется найти все оптимальные решения, то работу алгоритма необходимо продолжить, т.к. на подмножестве X _3,1 оценка x _3,1=26 и на этом подмножестве могут быть оптимальные решения.

Самостоятельная работа № 12.

Задание. Решить задачу коммивояжера для данных, приведенных в таблице (по вариантам)

Вариант 1

j

i

Вариант 2

j

i

Вариант 3

j

i

Вариант 4

j

i

Вариант 5

j

i

Вариант 6

j

i

Вариант 7

j

i

Вариант 8

j

i

Вариант 9

j

i

Вариант 10

j

i

Вариант 11

j

i

Вариант 12

j

i

Вариант 13

j

i

Вариант 14

j

i

Вариант 15

j

i

Вариант 16

j

i

Вариант 17

j

i

Вариант 18

j

i

 

		Вариант 19
		j
i
		Вариант 20
		j
i
		Вариант 21
		j
i
		Вариант 22
		j
i
		Вариант 23
		j
i
		Вариант 24
		j
i
		Вариант 25
		j
i

 

		Вариант 26
		j
i
		Вариант 27
		j
i
		Вариант 28
		j
i
		Вариант 29
		j
i
		Вариант 30
		j
i

 

.