Знаходження розв'язку задачі комівояжера методом осереднених коефіцієнтів

Розв'язок задачі комівояжера, за методом осереднених коефіцієнтів, та ксамо, як і за методом редекції рядків і колонок, ділиться на (n-2) етапи (у межах кожного етапу, алгоритм розрахунків однаковий).

Отже, розглянемо класичну задачу комівояжера, і знайдемо її розв'язок методом осереднених коефіцієнтів. Комівояжер повинен обїхати 5 міст, побувати в кожному по одному разу і повернутися у початкове. При цьому витрати на переміщення між містами повинні бути мінімальними. Тарифи містяться в наступній таблиці.

Тарифи на переміщення між містами

Рис. 1. Тарифи на переміщення між містами.

Перший етап: обчислюємо середнє значення довжини шляху для кожного рядка і колонки таблиці.

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

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

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

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

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

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

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

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

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