Построение редуцированных матриц и и вычисление оценок снизу

Положим:

Искомая редуцированная матрица получается из с помощью описанной выше процедуры редуцирования. Сумма констант редуцирования равна при этом , а величина

= d(Х¹) +

является оценкой снизу для целевой функции F(x) на множестве .

Рассмотрим теперь множество . Все маршруты из этого множества содержат дугу (r,s). Найдем максимальный связанный путь, который принадлежит всем маршрутам множества Х¹ и содержит дугу (r,s). Пусть этот путь начинается в городе m и заканчивается в городе t (может быть, m = r или t = s, или то и другое одновременно). Чтобы запретить подцикл, начинающийся и заканчивающийся в m, положим (t,m) = +∞. Остальные элементы матрицы полагаем равными соответствующим элементам матрицы , при этом строку, соответствующую городу r и столбец, соответствующий городу s, в матрицу не включаем, поскольку все маршруты из содержат дуги (r,s).

Редуцированная матрица расстояний для вершины получается из матрицы с помощью операции редуцирования. При этом оценка снизу для функции F(x) на множестве вычисляется по формуле

= d(Х¹) + ,

где  – сумма констант редуцирования.

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

После вычисления каждой из оценок (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) с помощью вычисления значений функции (,).

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

Следовательно, (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) +  = 58 + 0 = 58 < Z₀,

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

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

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

Следовательно, (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₁) +  = 58 + 5 = 63 < Z₀.

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

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

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

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

Следовательно, (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₄) +  = 62 + 0 = 62 < Z₀.

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

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

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

Следовательно, (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₅) +  = 62 + 0 = 62 < Z₀.

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

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

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

Рис. 5.2.

Домашнее задание №16

Решите методом ветвей и границ следующую задачу коммивояжера:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.