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

Даны множество вершин и множество дуг. Здесь вершины представляют города, а дуги ‑ упорядоченные пары и городов, между которыми возможна непосредственная поездка, время которой. Цель ‑ нахождение маршрута, начиная с города 1, с минимальным временем, и проходящего через каждый город только один раз.

Введем бинарную решающую переменную :

Задача коммивояжера может быть сформулирована в виде следующей задачи ДО:

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

(в каждый город въезжают только один раз),

(из каждого города выезжают только один раз),