Задача коммивояжера и метод ветвей и границ

Предположим, что фирма должна провести рекламную кампанию во всех областных го- родах Беларуси, в каждом городе ровно по одному разу. Известно, сколько стоит переезд между двумя любыми городами. Фирма желает снизить свои дорожные расходы. Математическая модель такой ситуации называется задачей коммивояжера, которая со- стоит в следующем. Задан полный орграф. Орграф называется полным, если каждая пара вершин i и j соединена дугами (i, j) и (j, i). Известна стоимость cij каждой дуги (i, j). Тре- буется построить гамильтонов цикл (т.е. цикл, проходящий через каждую вершину ровно по одному разу) такой, что суммарная стоимость всех его дуг была минимальной. Отметим, что есть взаимно однозначное соответствие между гамильтоновыми циклами (т.е. маршрутами коммивояжера) в полном графе с n вершинами и перестановками n элементов. Перестановка σ = (i 1 ,..., in) соответствует маршруту коммивояжера, прохо- дящему через вершины i 1 ,..., in и включающему дуги (i 1, i 2), (i 2, i 3) ,..., (in− 1, in), (in, i 1). Основным методом решения задачи коммивояжера является метод ветвей и границ (МВиГ). Этот метод является универсальным и может применяться для решения практи- чески всех задач оптимизации.

Основные принципы МВиГ для решения задачи минимизации состоят в следующем.

1) Ветвление. Исходная задача разбивается (ветвится) на две или более подзадачи та- ким образом, что решение исходной задачи является решением хотя бы одной из подзадач. Каждая из подзадач, в свою очередь, ветвится на более мелкие подзадачи. Процесс мо- жет повторяться до тех пор, пока получаемая подзадача не становится тривиальной и ее решение легко отыскивается.

Этот процесс можно представить в виде так называемого дерева ветвлений. Вершины дерева ветвлений соответствуют подзадачам и разбиты на уровни. Исходная задача яв- ляется вершиной нулевого уровня. Подзадачи, полученные из исходной задачи, являются вершинами первого уровня. Подзадачи, полученные из вершин первого уровня, являются вершинами второго уровня, и т.д. Дуги направлены из вершин уровня i в вершины уровня i + 1. В каждую вершину входит ровно одна дуга.

2) Построение нижних и верхних оценок минимального значения целевой функции. Для исходной задачи, а также для любой ее подзадачи могут быть найдены

числа LB и U B такие, что

LB ≤ F∗ ≤ UB,

где F ∗ – минимальное значение целевой функции в задаче или подзадаче, LB и U B – его нижняя и верхняя оценки соответственно.

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

Верхняя оценка может быть получена в результате отыскания любого допустимого реше- ния рассматриваемой задачи и вычисления соответствующего значения целевой функции. Для задачи коммивояжера достаточно найти суммарную стоимость дуг какого-нибудь до-

пустимого маршрута. Наилучшая, т.е. наименьшая из всех имеющихся в наличии верхних оценок, называется (текущим) рекордом.

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

4) Оптимальное решение. Процесс вычислений прекращается, когда нет ни одной под- задачи, которая может продолжать ветвиться. В этом случае оптимальное решение соот- ветствует текущему рекорду.

В приведенном методе остается неопределенным способ выбора подзадачи для ветвления. Наиболее употребимым является способ, при котором ветвят ту подзадачу, которой со- ответствует наименьшее значение нижней оценки либо ту, которая быстрее приведет к тривиальной подзадаче.

Различают методы ветвления в глубину и в ширину.

При ветвлении в глубину всегда ветвят одну из подзадач наибольшего уровня. Это быстрее приводит к построению полного допустимого решения.

При ветвлении в ширину ветвят подзадачи одного уровня до тех пор, пока все они не будут рассмотрены. Такое ветвление позволяет получать больше нижних и верхних оценок и может привести к большему количеству отсеянных вариантов. Однако требуется больше памяти для хранения промежуточных результатов.

Пример. Пусть матрица (таблица) стоимостей переезда между городами выглядит сле-

дующим образом:

город(i, j)	Минск(1)	Брест(2)	Витебск(3)	Гомель(4)	Гродно(5)	Могилев(6)
	∞
		∞
			∞
				∞
					∞
						∞

Будем решать задачу методом ветвления вглубь. Вначале построим ”приведенную задачу”, эквивалентную исходной. Используем процедуру ”приведение таблицы”, состоящую в вы- читании наименьшего числа в каждом столбце (строке), затем наименьшего числа в каж- дой строке (столбце). Суммируя эти числа (из каждого города нужно выехать и в каждый город нужно въехать), получаем ∆0= (220 + 100 + 170 + 210 + 100 + 150) + (30 + 50) = 1030. Далее можно работать с приведенной матрицей. Для получения реальной стоимости лю- бого маршрута необходимо добавить к получаемой из приведенной таблицы стоимости величину ∆0.

Приведенная таблица:

(i, j)
	∞	200(250)	30(80)	90(140)	170(220)	0(50)
		∞
			∞
	120(150)	450(480)	80(110)	∞	580(610)	0(30)
					∞
						∞

Для элементов приведенной таблицы оставим обозначения cij.

Очевидно, что нижняя оценка для приведенной задачи равна LB (0) = 0. Для отыскания верхней оценки построим какой-нибудь маршрут коммивояжера. Например, разумным бу- дет включить в этот маршрут дугу минимальной стоимости, скажем, (2,5). Далее выбрать

дугу минимальной стоимости вида (5, j), j / = 2. Это (5,1). Далее, выбрать дугу минималь-

ной стоимости вида (1 ,j) ,j / = 2, 5. Поступая аналогично, (1,6), (6,3), (3,4), и, без вариантов,

(4,2). Получаем верхнюю оценку U B (0) = 740. Она является рекордом R.

Далее разветвим исходную задачу. Ветвление будем осуществлять по вхождению или невхождению некоторой дуги в маршрут. Будем выбирать дугу нулевой стоимости, ко- торая дает наибольшее значение нижней оценки для подзадачи при ее невхождении в маршрут. Дуги нулевой стоимости: (1,6), (2,5), (3,6), (4,6), (5,2), (6,1), (6,3), (6,4).

В подзадаче P (1, 6) (P (1, 6)) дуга (1,6) не входит (входит) в маршрут.

Рассмотрим подзадачу P (1, 6). Полагаем стоимость дуги (1,6) равной ∞. Какая-то дуга из

1 должна выйти и какая-то дуга должна войти в 6. Можно добавить к нижней оценке сум-

му наименьших чисел в указанных строке и столбце, обозначаемую ∆16 = 30. Аналогично вычисляем ∆2, 5, ∆3, 6, ∆4, 6, ∆5, 2, ∆6, 1, ∆6, 3, ∆6, 4. Наибольшее значение равно ∆5, 2 = 380. Выбираем дугу (5,2) для дальнейших ветвлений. Вычисляем LB (5, 2) = LB (0)+∆5, 2 = 380. Нарисуем начальное дерево ветвлений, состоящее из 3 вершин - начальной 0 и вершин, обозначенных (5, 2) (соответствующая дуга не входит в маршрут коммивояжера) и (5,2) (входит), см. рис.

Припишем вершинам соответствующие значения LB.

Рассмотрим подзадачу P (5, 2). Поскольку дуга (5,2) входит в маршрут, другие дуги не могут выйти из 5 и войти в 2. Вычеркиваем строку 5 и столбец 2. Кроме того, дуга

(2,5) войти в маршрут не может. Полагаем стоимость этой дуги равной ∞. Вычисляем

∆5, 2 = 350. После приведения таблица имеет вид:

(i, j)
	∞
				∞
		∞
			∞
					∞

Вычисляем LB (5, 2) = LB (0) + c 5, 2 + ∆5, 2 = 350.

Будем ветвить подзадачу P (5, 2), так как размерность соответствующей матрицы мень- ше и быстрее можно получить тривиальную подзадачу. В приведенной таблице для этой подзадачи находим дуги нулевой стоимости: (1,5), (1,6), (2,1), (3,6), (4,6), (6,1), (6,3), (6,4).

R 0 = U B = c (2, 5, 1, 6, 3, 4) = 740

R 1 = c (1, 5, 2, 4, 3, 6) = 540

✤ LB =✜460

24

✤ LB =✜540= R 1

36

✒

✣✢

✒ ❅

✤ LB =✜460

✣✢❅

✤ LB =✜540

15

✒ ❅

❅❘ 36

✤ LB =✜350

✣✢❅

✤ LB =✜650 ✣✢

52

✒ ❅

❅❅❘ 24

✤ LB =✜0

✣✢❅

✤ LB =✜480 ✣✢

0 ❅❘

15 ❳❳

✤ LB =?✜?

❅

✣✢❅

✤ LB =✜380

❆

✣✢❆

❳❳③??

❅❘ 52 ❳❳ LB ✤=58✜0❆ ✣✢

❆

✣✢❆

❳❳③ 12

❆

❆

❆ ✤ LB =?✜?

❆

❆ ✣✢❆❯??

❆

❯

❆❆✤ LB =✜630 ✣✢

12

✣✢

Ответ: c∗ = c (1, 5, 2, 4, 3, 6) = 540 + ∆0= 540 + 1030 = 1570

Наибольшее значение ∆ i,j при записи в указанные клетки ∞ равно ∆1, 5 = 130. Выбира- ем дугу (1,5) для дальнейших ветвлений. В дерево ветвлений добавляем вершины (1,5) и (1, 5), следующие за вершиной (5,2).

В подзадаче P (1, 5) дуга (1,5) не входит в маршрут. Полагаем стоимость этой дуги равной

∞. Вычисляем ∆1, 5 = 130 и LB (1, 5) = LB (5, 2) + ∆1, 5 = 480.

Рассмотрим подзадачу P (1, 5). Вычеркиваем строку 1 и столбец 5 из матрицы для под-

задачи P (5, 2). Дуга (1,5) образует путь с уже введенной в маршрут дугой: (1,5),(5,2). Поэтому можно положить c 2, 1 = ∞. Вычисляем ∆2, 1.

Процесс останавливается для матриц 2 × 2. В этом случае можно найти решение либо

определить, что оно не существует. Получив новый рекорд, можно отсечь некоторые вет-

ви.

Дата добавления: 2015-07-08