Имеется n городов, условно пронумерованных от 1 до n. Коммивояжер, выезжая из города 1, должен посетить каждый город один раз и вернуться в исходный пункт. Пусть известны расстояния (или транспортные затраты) cij между городами (). Требуется найти самый короткий маршрут (или маршрут, обеспечивающий минимальные транспортные затраты).
Введем переменные:
(6.30)
где .
Требование однократного посещения каждого города можно представить в виде следующей системы уравнений:
(6.31)
Однако ограничения (6.31) полностью не определяют допустимые маршруты, так как не исключают возможности разрыва пути, т.е. появления нескольких не связанных между собой подмаршрутов для части городов. Поэтому следует ввести n-1 дополнительных переменных , принимающих только целые неотрицательные значения, и записать следующие ограничений, исключающие возможность существования подмаршрутов:
. (6.32)
Таким образом, задача о коммивояжере состоит в минимизации целевой функции:
(6.33)
при условиях (6.30) – (6.32).
|
|
Пример 6.8. Коммивояжеру, находящемуся в Париже, необходимо посетить три города и вернуться обратно. Имеется информация о стоимости перелета из одного города в другой (таблица 6.6). Необходимо составить маршрут посещения городов, чтобы затраты на дорогу были минимальными и каждый пункт посещался только один раз.
Таблица 6.6