Задача комівояжера. Математична постановка задачі

Основна ідея задачі комівояжера полягає у наступному: комівояжер повинен проїхати n міст. Для того, щоб зменшити витрати, він повинен побудувати маршрут таким чином, щоб побувати в кожному місті по одному разу і повернутися у початкове.

Математична постановка задачі коміваяжера має наступний вигляд:

Задача комівояжерапри обмеженнях:

Задача комівояжера — обмеження на одноразовий виїзд з міста.

Задача комівояжера — обмеження на одноразовий в'їзд в місто.

де Задача комівояжера — матриця відстаней між усіма містами Задача комівояжера.

Якщо в моделі задачі обмежитися лише умовами (2) і (3), то вона буде еквівалентною задачі про призначення, план якої не обов'язково повинен бути циклічним. Тобто, маршрут комівояжера може розпастися на декілька незв'язних між собою циклів, тоді як насправді він повинен складатися з одного циклу. Щоб забезпечити цю вимогу введемо наступне обмеження:

Задача комівояжера

Покажемо, що в довільному циклі, який починається в першому місті, можна знайти такі zadacha_komivojagera8 та Задача комівояжера, які задовідьняють нерівність (4). Нехай на k-му кроці комівояжер переїзджає з міста i в місто j. І припустимо, що Задача комівояжера. Далі, на k+1-му кроці комівояжер буде вирушати з j-го міста в наступному напрямку, тоді  zadacha_komivojagera11. Якщо підставити дані величини в (4), отримаємо:

Задача комівояжера

Зауважимо, що дана нерівність виконується для будь-яких значень i та j при Задача комівояжера. Якщо ж Задача комівояжера, то нерівність (4) виконується як строга рівність:

Задача комівояжера

Тобто, якщо комівояжер  пересувається  з i-го в j-те місто, то нерівність (4) фіксує порядкові номери цих міст.

Отже математична постановка задачі комівояжера полягає у мінімізації функції (1) при обмеженнях (2), (3) і (4).

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар