Формирование списка кандидатов на ветвление

После вычисления каждой из оценок (i = 1,2) следует проверить, не состоит ли множество из единственного маршрута. Если в каждой строке и в каждом столбце матрицы оказалось лишь по одному элементу, отличному от + ¥, то множество содержит единственный маршрут, длина которого равна . В этом случае верхняя граница (наименьшее из уже вычисленных значений F (x) полагается равной минимуму из предыдущего значения Z ₀ и , т.е.

Z ₀ = min { Z ₀, }.

Если содержит более одного маршрута и меньше текущего значения Z ₀, то множество включается в число кандидатов на ветвление. Остановка производится, если наименьшая из оценок снизу кандидатов на ветвление не меньше текущего значения Z ₀.

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

Возьмем в качестве произвольного допустимого маршрута:

x ₀ = {(1,2), (2,3), (3,4), (4,5), (5,1)}.

Тогда F(x ₀) = 10 + 10 + 20 + 15 + 10 = 65 – текущее значение Z ₀ – (верхняя граница длин всех маршрутов).

Получим редуцированную матрицу .

0 0 9 12 0

Нижняя граница d (x) = 10 + 1 + 8 + 10 + 8 + 9 + 12 = 58. Данное значение является нижней границей длин всех маршрутов. Заметим, что в идеальном случае поиск решения заключался бы в выборе ровно одного нулевого элемента в каждой строке и каждом столбце. Другими словами, если бы такой маршрут нулевой длины бы быть найден, то длина оптимального маршрута равнялась бы 58. Исходя из верхней и нижней границ, можно заключить, что 58 ≤ F (x ^*) ≤ 65.

Выберем дугу (r,s) с помощью вычисления значений функции Q(m,n).

Q(1,2) = 0, Q(2,1) = 0, Q(3,1) = 0, Q(4,2) = 4, Q(1,5) = 1, Q(2,3) = 5, Q(3,4) = 2, Q(5,2) = 2.

Следовательно, Q(r,s) = (2,3). Осуществим разбиение (ветвление). Правое подмножество X ₂ будет содержать все маршруты, которые исключают дугу (2,3). Поэтому C ₂ (2,3) = +∞.

~ ~ =

Оценка снизу для правого подмножества X ₂ определяется следующим образом:

d (X ₂) = d (X) + Θ(2,3) = 58 + 5 = 63 < Z ₀.

Левое подмножество X ₁ будет содержать маршруты, которые всегда включают дугу (2,3), и поэтому вторая строка и третий столбец в матрицу C ₁ не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C ₁ (3,2) = +∞, чтобы запретить подцикл {(2,3),(3,2)}. В результате получим матрицу

C ₁ = = .

Оценка снизу для левого подмножества:

d (X ₁) = d (X) + t = 58 + 0 = 58 < Z ₀,

где t – константа приведения матрицы С₁

В списке кандидатов на ветвление множества X ₁ и X ₂. Так как d (X ₁) < d (X ₂), будем производить ветвление множества X ₁. Выберем дугу (r,s) с помощью значений функции Q(m,n) для матрицы.

Q(1,2) = 0, Q(1,5) = 2, Q(3,1) = 2, Q(3,4) = 3, Q(4,2) = 4, Q(5,2) = 2.

Следовательно, Q(r,s) = 4, (r,s) = (4,2).

Правая подматрица:

C ₄ = ~ = .

Оценка снизу для правого подмножества:

d (X ₄) = d (X ₁) + Θ(4,2) = 58 + 4 = 62 < Z ₀.

Левая подматрица. Левое подмножество X ₃ будет содержать маршруты, которые всегда включают дугу (4,2), и поэтому четвертая строка и второй столбец в матрицу C ₃ не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C ₃ (3,4) = +∞, чтобы запретить подцикл {(4,2),(2,3),(3,4)}. В результате получим матрицу

C ₃ = ~ ~ = .

d (X ₃) = d (X ₁) + t = 58 + 5 = 63 < Z ₀.

В списке кандидатов на ветвление множества X ₃, X ₄, X ₂.

Минимальная нижняя оценка оказалась у множества X ₄, следовательно, для дальнейшего разбиения выбираем множество X ₄.

Определим дугу (r,s) с помощью значений функции Q(m,n) для матрицы .

Q(1,2) = 0, Q(1,5) = 1, Q(3,1) = 0, Q(3,4) = 3, Q(4,1) = 1, Q(5,2) = 2.

Следовательно, Q(r,s) = 3, (r,s) = (3,4).

Правая подматрица.

C ₆ = ~ = .

Оценка снизу для правого подмножества:

d (X ₆) = d (X ₄) + Θ(3,4) = 62 + 3 = 65 = Z ₀.

Следовательно, множество X ₆ исключаем из списка.

Левая подматрица. Левое подмножество X ₅ будет содержать маршруты, которые всегда включают дугу (3,4), и поэтому третья строка и четвертый столбец в матрицу C ₅ не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C ₅ (4,2) = +∞, чтобы запретить подцикл {(2,3), (3,4), (4,2)}, однако это условие оказалось уже выполненным. В результате получим матрицу:

C ₅ = = .

Оценка снизу для левого подмножества:

d (X ₅) = d (X ₄) + t = 62 + 0 = 62 < Z ₀.

В списке кандидатов на ветвление множества X ₃, X ₅, X ₂.

Минимальная нижняя оценка оказалась у множества X ₅, следовательно, для дальнейшего разбиения выбираем множество X ₅. Определим дугу (r,s) с помощью значений функции Q(m,n) для матрицы .

Q(1,2) = 0, Q(1,5) = 1, Q(4,1) = 3, Q(5,2) = 2.

Следовательно, Q(r,s) = 3, (r,s) = (4,1).

Правая подматрица:

C ₈ = ~ ~ = .

Оценка снизу для правого подмножества:

d (X ₈) = d (X ₅) + Θ(4,1) = 62 + 3 = 65 = Z ₀.

Следовательно, множество X ₈ исключаем из списка.

Левая подматрица. Левое подмножество X ₇ будет содержать маршруты, которые всегда включают дугу (4,1), и поэтому четвертая строка и первый столбец в матрицу C ₇ не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C ₇ (1,2) = +∞, чтобы запретить подцикл {(2,3), (3,4), (4,1), (1,2)}.

C ₇ = = .

Оценка снизу для левого подмножества:

d (X ₇) = d (X ₅) + t = 62 + 0 = 62 < Z ₀.

В списке кандидатов на ветвление множества X ₃, X ₇, X ₂. Множество X ₇ содержит единственный маршрут с минимальной нижней оценкой, поэтому задача решена.
X ₁ = = X ^*;

Z ₀= F (x ^*) = 10 + 8 + 10 + 20 + 14 = 62.

Представим процесс решения в виде дерева (см. рис. 5.2.).

Рис. 5.2.