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

 

Цель работы: получить навыков в решении задачи коммивояжера методом ветвей и границ..

1.Краткие теоретические сведения.

Основным методом решения задачи коммивояжера является метод ветвей и границ (МВиГ). Этот метод является универсальным и может применяться для решения практически всех дискретных экстремальных задач.

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

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

Указанный процесс можно представить в виде так называемого дерева ветвлений.

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

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

,

где ‑минимальное значение целевой функции в задаче или подзадаче, и его нижняя и верхняя оценки соответственно.

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

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

Может оказаться, что задача отыскания нижней и/или верхней оценки сама является сложной. В этом случае соответствующая оценка не используется и можно положить , .

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

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

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

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

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

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

Рассмотрим задачу проведения рекламной кампании в четырех областных центрах Украины

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

 

Город

 

Будем решать задачу методом ветвления вглубь. Вначале построим "приведенную задачу", эквивалентную исходной. Используем процедуру "приведение таблицы", состоящую в вычитании наименьшего числа в каждом столбце (строке), затем наименьшего числа в каждой строке (столбце) и суммировании этих чисел (из каждого города нужно выехать и в каждый город нужно въехать). Получаем . Далее можно работать с приведенной матрицей. Для получения реальной стоимости любого маршрута необходимо добавить к получаемой из приведенной таблицы стоимости величину .

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

 

Город
	0(100)		300(400)	80(180)
	40 (70)	200 (230)	0 (30)

 

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

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

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

В подзадаче дуга не входит в маршрут. Полагаем стоимость этой дуги равной . Какая-то дуга из 1 должна выйти и какая-то дуга должна войти в 2. Можно добавить к нижней оценке сумму наименьших чисел в указанных строке и столбце и вычислить . Аналогично вычисляем , , , , .. Наибольшее значение равно . Следовательно, .

Выбираем дугу (1,2) для дальнейших ветвлений.

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

 

 

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

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

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

Получаем и приведенную таблицу стоимостей для подзадачи . После приведения таблица стоимостей имеет вид:

 

 

Вычисляем .

В матрице стоимости подзадачи имеются следующие дуги нулевой стоимости , , , .

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

, , , .

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

 

 

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

 

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

По дереву ветвлений восстанавливаем построенные частичные маршруты: и . Из таблицы видно, что единственный вариант ‑ полный маршрут стоимости

.

 

 

 

Получили новый рекорд . Из условия отсеивания ветки и можно отсечь.

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

Таким образом решением задачи коммивояжера полный маршрут стоимости