1.2. Задача коммивояжера (КМ)

Коммивояжер должен посетить каждый из городов множества N={1,…,N} ровно один раз и вернуться в начальный город. Расстояние от города I до города J Известно и равно CIj.

Требуется найти порядок обхода городов (гамильтонов маршрут) минимальной длины.

Пусть XIj = 1, Если коммивояжер сразу после города I идет в город J, и XIj = 0, иначе.

Коммивояжер должен из каждого города один раз выйти и один раз в него войти. Эти условия записываются равенствами

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

Или

Целевая функция в данных обозначениях записывается однозначно

Комбинаторная постановка задачи коммивояжера может быть сформулирована достаточно лаконично. Задан ориентированный граф G=(V,E), M=|V|, каждой дуге (I,J)ÎE которого приписана длина Cij. Найти такую перестановку вершин (P(1),P(2),…,P(M)), что выражение

CP(i),P(i+1) +cP(m),P(1)

Принимает минимальное значение.

< Предыдущая		Следующая >