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

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

Введем переменные:

(6.30)

где .

Требование однократного посещения каждого города можно представить в виде следующей системы уравнений:

(6.31)

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

. (6.32)

Таким образом, задача о коммивояжере состоит в минимизации целевой функции:

(6.33)

при условиях (6.30) – (6.32).

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

Таблица 6.6