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

Решить задачу 4.2 методом Ленд и Дойг, исходные данные по вариантам взять в лабораторной работе № 10.

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

Пусть имеется (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 и вычисление оценки _0,1.

Множество X_0,1есть множество всех возможных маршрутов коммивояжера. Оценку_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и нижняя оценка функционала_r,tна нем. Этому подмножеству соответствует приведенная матрицаC"_r,t. Подмножество разбиваем на два:X_r+1,m+1, X_r+1,m+2, каждому из которых будут соответствовать свои оценки_r+1,m+1, _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процедурой приведения. Для получения_r+1,m+2 складываем_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процедурой приведения. Для получения_r+1,m+2складываем_r,tс полученными коэффициентами приведения.

Пример.

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

C0,1		j
		0	1	2	3	4	5	hi
i	0	M	4	10	13	4	8	4
	1	2	M	9	7	6	7	2
	2	8	5	M	5	5	9	5
	3	5	8	5	M	7	10	5
	4	6	4	4	9	M	4	4
	5	5	1	4	8	3	M	1
		0	0	0	0	0	0
		Hj

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

Решение.

Шаг 0. Приводим матрицуC_0,1.Находимh_iи вычитаем изc_i,j. Получим матрицу

C'0,1		j
		0	1	2	3	4	5	hi
i	0	M	0	6	9	0	4	4
	1	0	M	7	5	4	5	2
	2	3	0	M	0	0	4	5
	3	0	3	0	M	2	5	5
	4	2	0	0	5	M	0	4
	5	4	0	3	7	2	M	1
		0	0	0	0	0	0
		Hj

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

C"0,1		j
		0	1	2	3	4	5	hi
i	0	M	0	6	9	0	4
	1	0	M	7	5	4	5
	2	3	0	M	0	0	4
	3	0	3	0	M	2	5
	4	2	0	0	5	M	0
	5	4	0	3	7	2	M
								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.Матрица расстояний будет иметь вид:

C11		j
		0	1	2	4	5	hi
i	0	M	0	6	0	4
	1	0	M	7	4	5
	3	0	3	0	2	5
	4	2	0	0	M	0
	5	4	0	3	2	M
		Hj

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

C11		j
		0	1	2	4	5	hi
i	0	M	0	6	0	4
	1	0	M	7	4	5
	3	0	3	M	2	5
	4	2	0	0	M	0
	5	4	0	3	2	M
		Hj

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

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

C1,2		j
		0	1	2	3	4	5	hi
i	0	M	0	6	9	0	4	0
	1	0	M	7	5	4	5	0
	2	3	0	M	M	0	4	0
	3	0	3	0	M	2	5	0
	4	2	0	0	5	M	0	0
	5	4	0	3	7	2	M	0
		0	0	0	5	0	0
		Hj

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

C1,2		j
		0	1	2	3	4	5	hi
i	0	M	0	6	4	0	4
	1	0	M	7	0	4	5
	2	3	2	M	M	0	4
	3	0	3	0	M	2	5
	4	2	0	0	0	M	0
	5	4	0	3	2	2	M
		Hj						1,2=26

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

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

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

C21		j
		0	1	2	4	hi
i	0	M	0	6	0
	1	0	M	7	4
	3	0	3	M	2
	5	4	0	3	M
				3
		Hj				2,1=24

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

		j
C"2,1		0	1	2	4	hi
i	0	M	0	3	0
	1	0	M	4	4
	3	0	3	M	2
	5	4	0	0	M
		Hj

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

		j
C22		0	1	2	4	5	hi
i	0	M	0	6	0	4
	1	0	M	7	4	5
	3	0	3	M	2	5
	4	2	0	0	M	M
	5	4	0	3	2	M
						4
		Hj

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

		j
C22		0	1	2	4	5	hi
i	0	M	0	6	0	0
	1	0	M	7	4	1
	3	0	3	M	2	1
	4	2	0	0	M	M
	5	4	0	3	2	M
		Hj					2,2=25

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

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

_3,4=28

X_3,4

_3,3=25

X_3,3

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

C51		4	5	hi
i	0	0	М
	3	M	0
		Hj		 5,1=26

т.е. остаются переходы из 0 в 4, из 3 в 5. Эти переходы и переходы, выбранные при движении по дереву от вершины для подмножества X_5,1до вершины подмножестваX_0,1, получаем цикл 0423510 , длина которогоl=26.Так как все_r,tдля концевых вершин дерева не меньше 26, то этот цикл оптимальный.

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