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

Математическая модель задачи коммивояжера. Задача коммивояжера может быть сформулирована как целочисленная введением булевых переменных, если маршрут включает переезд из города i непосредственно в город j и в противном случае.

Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений 1 Условия 2 4 в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения 2, 3 выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв ограничение 2, и один раз из него выехав ограничение 3. Однако этих ограничений не достаточно для постановки задачи коммивояжера, так как они не исключают решения, где вместо простого цикла, проходящего через n вершин, отыскиваются 2 и более отдельных цикла подцикла, проходящего через меньшее число вершин.

Поэтому задача, описанная уравнениями 2 4 должна быть дополнена ограничениями, обеспечивающими связность искомого цикла. Для того, чтобы исключить при постановке задачи все возможные подциклы в систему ограничений задачи включают следующее ограничение, где, и . 4.