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

Коммивояжер - это бродячий торговец, который должен обойти несколько городов, побывав в каждом ровно 1 раз, причем суммарное пройденное расстояние должно быть min.

Имеется n пунктов, cij- стоимость или время или расстояние для перехода из i пункта в j. Требуется обойти все пункты по 1 разу, и вернутся в исходную точку, иными словами нужно отыскать цикл минимального веса (стоимостью).

Математическая модель:

Напишем целевую функцию:

Нужно 1 раз зайти и выйти: х_ij –входим из i пункта в j

сумма всех городов, из которых можем выйти

Например, у нас 5 городов. Но тех условий недостаточно. Это не цикл, поэтому нужно добавить ещё 1 условие:

(*), причём i, j =2…n

Пояснение к условию: предположим мы отыскали цикл длиной k<n, тогда просуммируем все неравенства (*) вдоль цикла:

; =1, т. к идем вдоль цикла.

Получили противоречивое неравенство, т.к предположили, что в решение оказался цикл длиной меньше, чем n. Условие (*) гарантирует отсутствие такого цикла.