Лабораторная работа 11. Применение метода ветвей и границ к решению задачи о коммивояжере

 

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

C(0, 1)=

 

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

Решение.

Шаг 0. Приводим матрицу C(0, 1). Находим h(i) и вычитаем из c(i, j). Получим матрицу

 

C'(0, 1) =

 

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

 

C" (0, 1)=

 

Оценка x(0, 1)=21.

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

x(0, 1)=21

Шаг 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(1, 1)=

 

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

 

C(1, 1)=

 

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

Для подмножества X(1, 2) из пункта 2 непосредственно идти в пункт 3 запрещается. Матрица расстояний будет иметь вид

C(1, 2)=

 

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

 

 

C(1, 2) =

При этом оценка иметь вид: x(1, 2)=21+5=26.

 

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

x (0, 1)=21

2 идти 3 2 не идти 3

x(1, 1)=21 x(1, 2)=26

 

 

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

 

C(2, 1=)

 

 

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

C" (2, 1)=

 

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

 

C(2, 2)=

 

 

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

 

C”(2, 2)=

 

Оценка принимает вид: x(2, 2)=21+4=25.

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

 

x (0, 1)=21

2 идти 3 2 не идти 3

x (1, 1)=21 x (1, 2)=26

4 идти 5 4 не идти 5

x (2, 1)=24 x (2, 2)=25

 

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

Подмножество X(3, 1):

 

C" (3, 1)=

При этом оценка равна x(3, 1)=26.

Подмножество X(3, 2):

C”(3, 2)=

Вычислим оценку x(3, 2)=28.

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

x (0, 1)=21

2 идти 3 не идти 3

x (1, 1)=21 x (1, 2)=26

4 идти 5 4 не идти 5

x (2, 1)=24 x (2, 2)=25

1 идти 0 1 не идти 0

x (3, 1)=26 x (3, 2)=28

 

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

 

 

x (0, 1)=21

2 идти 3 не идти 3

x (1, 1)=21 x (1, 2)=26

4 идти 5 4 не идти 5

x (2, 1)=24 x (2, 2)=25

1 идти 0 1 не идти 0 4 идти 2 4 не идти 2

x (3, 1)=26 x (3, 2)=28 x (3, 3)=25 x (3, 4)=28

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

x (0, 1)=21

2 идти 3 2 не идти 3

x (1, 1)=21 x (1, 2)=26

4 идти 5 не идти 5

x (2, 1)=24 x (2, 2)=25

1 идти 0 1 не идти 0 4 идти 2 4 не идти 2

x (3, 1)=26 x (3, 2)=28 x (3, 3)=25 x (3, 4)=28

5 идти 1 5 не идти 1

x (4, 1)=25 x (4, 2)=27

1 идти 0 1 не идти 0

x (5, 1)=26 x (5, 2)=29

 

 

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

 

C”(3, 2)

j i	4	5	h(i)
0	0	М
3	M	0
H(j)

 

 

т.е. остаются переходы из 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 и на этом подмножестве могут быть оптимальные решения.