Условие задачи
Найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов А1, А2, А3, А4, А5 и А6. Расстояния между городами заданы следующей таблицей:
Ответ
Исходная задача коммивояжера задача целочисленная. Пусть хij=1, если путешественник переезжает из i-ого города в j-ый и хij=0, если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь прийти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути: u1=0, un+1=n. Для того чтобы избежать замкнутых путей, выйти из первого города и вернуться...