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

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

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

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

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

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

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

Читати повністю

Двоїста задача лінійного програмування

Кожній задачі лінійного програмування певним чином можна поставити у відповідність деяку іншу задачу, яка називається двоїстою задачею лінійного програмування. Запишемо пряму (вихідну) задачу лінійного програмування, яка полягає у визначенні максимуму цільової функції:

120

при обмеженнях:

216

39

Читати повністю