Лекция: Метод ветвей и границ, решение линейных целочисленных задач.(Метод Ленд и Дойг)

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

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

Формализуем задачу.

Пусть известна матрица расстояний между пунктами i и j. В качестве неизвестной величины введем переменную

Модель задачи о коммивояжере будет иметь вид

(4.9)

при ограничениях:

; (4.10)

; (4.11)

. (4.12)

Еще одно ограничение сформулируем следующим образом: искомые переменные должны образовывать полный контур, включающий все пункты.

Ограничение (4.10) говорит о том, что коммивояжер должен в каждый пункт заехать только один раз, а ограничение (4.11) — из каждого пункта выехать только один раз. Ограничения (4.10)—(4.12) и дополнительное ограничение на маршруте коммивояжера создают так называемый гамильтоновый контур (по имени ирландского математика У. Гамильтона).

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

Если сформулированное достаточное условие не выполняется для всех вершин, то это еще не означает, что в графе нет гамильтонова контура. Условие (необходимое) обязательного присутствия данного контура в графе пока не найдено.

Предложено достаточно большое количество методов поиска на графе гамильтоновых контуров минимальной длины, в основе которых заложен подход организованного, отличного от полного, просмотра «перспективных» маршрутов.