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

Задача коммивояжера

Имеется n городов, пронумерованных числами 1, 2,..., n. Для любой пары городов (i, j) задано расстояние (время, путевые расходы) C(i,j) ³ 0 между ними. Поэтому в общем случае C(i, j) ¹ C(j, i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной.

Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь C(i, j) – время переналадки при переходе от обработки детали i к обработке детали j. Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.

Для записи постановки задачи в терминах целочисленного линейного программирования определим переменные следующим образом: = 1, если коммивояжер переезжает из i -го города в j -й; – в противном случае. Тогда задача заключается в отыскании значений переменных , удовлетворяющих следующим соотношениям:

(5.1)

при условиях

(въезд в город j); (5.2)

(выезд из города i); (5.3)

(i ¹ j); (5.4)

x_ij = {0,1}, , целые, i = 1,..., m, j = 1,..., n. (5.5)

Ограничения (5.4) требуют, чтобы маршрут образовывал контур.

Допустимый маршрут х представим как множество упорядоченных пар городов:

х = .

Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (i, j) является дугой маршрута. Длина F (х) маршрута х равна сумме соответствующих элементов C (i, j). Заметим, что множество всех допустимых маршрутов X содержит (n-1)! элементов.

Обозначим через матрицу расстояний. Чтобы запретить переезды вида (i,i), положим C (i, i) = +∞ (i = 1,…, n).

Пусть

.

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

Пусть d (X) = – сумма констант редуцирования.

Тогда для любого маршрута

F (х) = =

= + d (X) ≥ d (X) (5.6)

Неравенство (5.6) показывает, что d (X) является оценкой снизу для множества Х. Кроме того, после редукции длины всех маршрутов уменьшаются на одну и ту же величину d (X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.

Ветвление

Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, являющемуся подмножеством множества Х. При этом начальная вершина соответствует множеству всех маршрутов Х (рис. 5.6).

Рис. 5.6. Ветвление

На каждом шаге из числа кандидатов на ветвление выбирается множество Х ¹ с наименьшей оценкой. Оно разветвляется на два подмножества и . Подмножество состоит из всех маршрутов множества Х ¹, содержащих некоторую выбранную на данном шаге дугу (r, s), подмножество – из всех маршрутов множества Х ¹, не содержащих дуги (r,s).

Ребро дерева, соединяющее вершины Х ¹ и , помечается (r, s), а ребро дерева, соединяющее Х ¹ и , помечается .

Пусть – редуцированная матрица, соответствующая вершине Х ¹. Опишем способ выбора дуги (r, s). Он основан на стремлении сделать оценку поменьше, а оценку – больше, для того чтобы увеличить вероятность выбора для дальнейшего ветвления множества . Стремление к уменьшению приводит к выбору такой дуги (m,n), для которой

(m,n) = 0, (5.7)

поскольку все маршруты множества содержат дугу (m,n). Стремление же увеличить приводит к выбору среди дуг, удовлетворяющих условию (5.7), той дуги, для которой значение функции

максимально, т.е.

Смысл введения функции состоит в том, что величина является оценкой снизу для длины любого маршрута из Х ¹, не содержащего дуги (m,n), так как величина выражает дополнительное расстояние, которое коммивояжер проезжает в случае, когда в маршрут не включена дуга (m,n).

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

Положим:

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

= d (Х ¹) +

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

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

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

= d (Х ¹) + t,

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

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

После вычисления каждой из оценок (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) = Q(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.7).

Рис. 5.7.

Контрольные вопросы

1. Запишите задачу целочисленного линейного программирования.

2. Сформулируйте алгоритм метода ветвей и границ.

3. Перечислите область применения ЗЦЛП.

4. С какими трудностями приходится сталкиваться при алгоритмизации методов решения ЗЦЛП?

5. Приведите классификацию методов решения ЗЦЛП.

6. Какая задача называется задачей с ослабленными ограничениями?

7. Сформулируйте принцип ветвления в методе ветвей и границ.

8. Какую задачу решает понятие границы в методе ветвей и границ?

9. Сформулируйте постановку задачи коммивояжера.

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

Задание №14

Решите ЗЦЛП методом ветвей и границ.

1. max(3 x₁ + 4 x₂) 2. max(3 x₁ + 4 x₂)

4 x₁ + 5 x₂ £ 20 x₁ + 7 x₂ £ 21

x₁ + 6 x₂ £ 12 x₁ + x₂ £ 4

0£ x₁ £ 5 0 £ x₁ £ 4

0£ x₂ £ 4 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. ` x₁, x₂ – целые.

3. max(x₁ + x₂) 4. max(4 x₁ + x₂)

3 x₁ + 4 x₂ £ 12 2 x₁ - 3 x₂ £ 6

3 x₁ + 2 x₂ £ 9 4 x₁ + 9 x₂ £ 18

0£ x₁ £ 4 0 £ x₁ £ 2

0£ x₂ £ 2 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

5. max(3 x₁ + x₂) 6. max(x₁ + 2 x₂)

4 x₁ + 3 x₂ £ 18 x₁ + x₂ £ 5

x₁ + 2 x₂ £ 6 3 x₁ + 8 x₂ £ 24

0£ x₁ £ 5 0 £ x₁ £ 5

0£ x₂ £ 3 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

7. max(2 x₁ + x₂) 8. max(3 x₁ - 2 x₂)

5 x₁ + 2 x₂ £ 30 2 x₁ + 3 x₂ £ 6

3 x₁ + 8 x₂ £ 48 x₁ - x₂ £ 2

0£ x₁ £ 6 0 £ x₁ £ 3

0£ x₂ £ 6 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

9. max(3 x₁ + 2 x₂) 10. max(x₁ + 2 x₂)

2 x₁ + x₂ £ 7 5 x₁ + 9 x₂ £ 45

4 x₁ + 3 x₂ £ 18 x₁ + 3 x₂ £ 12

0£ x₁ £ 3 0 £ x₁ £ 9

0£ x₂ £ 4 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

11. max(2 x₁ + 5 x₂) 12. max(4 x₁ + 6 x₂)

4 x₁ + 5 x₂ £ 20 3 x₁ + 7 x₂ £ 21

x₁ + 6 x₂ £ 12 x₁ + x₂ £ 4

0£ x₁ £ 6 0 £ x₁ £ 5

0£ x₂ £ 5 0 £ x₂ £ 4

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

13. max(2 x₁ + 3 x₂) 14. max(5 x₁ + 2 x₂)

3 x₁ + 4 x₂ £ 12 2 x₁ - 3 x₂ £ 6

3 x₁ + 2 x₂ £ 9 4 x₁ + 9 x₂ £ 18

0£ x₁ £ 6 0 £ x₁ £ 3

0£ x₂ £ 3 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

15. max(4 x₁ + 2 x₂) 16. max(2 x₁ + 5 x₂)

4 x₁ + 3 x₂ £ 18 x₁ + x₂ £ 5

x₁ + 2 x₂ £ 6 3 x₁ + 8 x₂ £ 24

0£ x₁ £ 6 0 £ x₁ £ 4

0£ x₂ £ 4 0 £ x₂ £ 4

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

17. max(3 x₁ + 2 x₂) 18. max(5 x₁ - 3 x₂)

5 x₁ + 2 x₂ £ 30 2 x₁ + 3 x₂ £ 6

3 x₁ + 8 x₂ £ 48 x₁ - x₂ £ 2

0£ x₁ £ 7 0 £ x₁ £ 3

0£ x₂ £ 6 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

19. max(4 x₁ + 3 x₂) 20. max(x₁ + 3 x₂)

2 x₁ + x₂ £ 7 5 x₁ + 9 x₂ £ 45

4 x₁ + 3 x₂ £ 18 x₁ + 3 x₂ £ 12

0£ x₁ £ 4 0 £ x₁ £ 8

0£ x₂ £ 4 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

21. max(4 x₁ + 4 x₂) 22. max(3 x₁ + 3 x₂)

4 x₁ + 5 x₂ £ 20 3 x₁ + 7 x₂ £ 21

x₁ + 6 x₂ £ 12 x₁ + x₂ £ 4

0£ x₁ £ 6 0 £ x₁ £ 4

0£ x₂ £ 5 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

23. max(2 x₁ + 3 x₂) 24. max(5 x₁ + x₂)

3 x₁ + 4 x₂ £ 12 2 x₁ - 3 x₂ £ 6

3 x₁ + 2 x₂ £ 9 4 x₁ + 9 x₂ £ 18

0£ x₁ £ 4 0 £ x₁ £ 2

0£ x₂ £ 2 0 £ x₂ £ 3

x₁, x₂ ³ 0 x₁, x₂ ³ 0

x₁, x₂ – целые. x₁, x₂ – целые.

25. max(4 x₁ + x₂)

4 x₁ + 3 x₂ £ 18

x₁ + 2 x₂ £ 6

0£ x₁ £ 5

0£ x₂ £ 3

x₁, x₂ ³ 0

x₁, x₂ – целые.

Задание №15

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

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.

ТЕМА 6.

Дата добавления: 2014-12-29