Основна ідея задачі комівояжера полягає у наступному: комівояжер повинен проїхати n міст. Для того, щоб зменшити витрати, він повинен побудувати маршрут таким чином, щоб побувати в кожному місті по одному разу і повернутися у початкове.
Математична постановка задачі коміваяжера має наступний вигляд:
при обмеженнях:
– обмеження на одноразовий виїзд з міста.
– обмеження на одноразовий в’їзд в місто.
де 
– матриця відстаней між усіма містами 
.
Якщо в моделі задачі обмежитися лише умовами (2) і (3), то вона буде еквівалентною задачі про призначення, план якої не обов’язково повинен бути циклічним. Тобто, маршрут комівояжера може розпастися на декілька незв’язних між собою циклів, тоді як насправді він повинен складатися з одного циклу. Щоб забезпечити цю вимогу введемо наступне обмеження:
Покажемо, що в довільному циклі, який починається в першому місті, можна знайти такі 
та 
, які задовідьняють нерівність (4). Нехай на k-му кроці комівояжер переїзджає з міста i в місто j. І припустимо, що 
. Далі, на k+1-му кроці комівояжер буде вирушати з j-го міста в наступному напрямку, тоді 
. Якщо підставити дані величини в (4), отримаємо:
Зауважимо, що дана нерівність виконується для будь-яких значень i та j при 
. Якщо ж 
, то нерівність (4) виконується як строга рівність:
Тобто, якщо комівояжер пересувається з i-го в j-те місто, то нерівність (4) фіксує порядкові номери цих міст.
Отже математична постановка задачі комівояжера полягає у мінімізації функції (1) при обмеженнях (2), (3) і (4).
Перш за все дуже дякую дуже корисна саття, але я не зовсім зрозумів що це за u – іті та u – йоті)
Доброго вечора Vova. В описаній вище математичній моделі задачі комівояжера, ui – це змінна, яка, в якості значення, приймає номер кроку, на якому було відвідано i-те місто. Наприклад, у циклі наступного вигляду 1-5-3-2-4-1, значення ui будуть наступні: u1=1, u5=2, u3=3, u2=4, u4=5.