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

Сформулированная задача — задача целочисленная. Пусть хij = 1 , если путешественник переезжает из i -ого города в j-ый и хij = 0, если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u1 = 0, un+1 = n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные xij и переменные ui. ( ui целые неотрицательные числа).


ui-uj+nxij ≤ n-1, j = 2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤ ui ≤ n, xin+1 = xi1, i=2..n


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *