РІШЕННЯ ЗАДАЧІ ПРО КОМІВОЯЖЕРА МЕТОДОМ гілок І ГРАНИЦЬ
II варіант рішення
I варіант
Given
Формування оптимального плану вихідної ЗДЛП
Формування цільової функції ЗДЛП
Формування початкових умов
Формування блоку обмежень ЗДЛП
Given
Формування умов невід’ємності, що накладають на змінні
Формування процесу пошуку экстремума
Формування розв’язку задачі
Визначення оптимального вектора Х
Визначення оптимального значення функції цілі
Постановка задачі
Є n міст (А1, А2, А3,... Аn), задана матриця відстаней між містами . Необхідно відшукати такий найкоротший замкнутий маршрут (цикл), що проходить один і тільки один раз через кожне місто, при якому мінімізується сумарна довжина шляху .
Математична модель задачі
У загальному випадку нехай розглядаються n пунктів, тоді вводиться n2 альтернативних змінних xij. Причому відповідна змінна буде дорівнювати 0, якщо перехід з i в j пункт не входить у розглянутий маршрут. І, мабуть, що така змінна буде дорівнювати 1, якщо зазначений перехід можливий. Тоді умова прибуття в кожен пункт і виходу з кожного пункту тільки по одному разу виражається співвідношенням виду:
(4.1)
(4.2)
Для забезпечення безперервності маршруту вводять додатково n змінних і при цьому формують n2 додаткових обмежень:
;
. (4.3)
У такому випадку сумарна довжина маршруту, який необхідно мінімізувати, буде записуватися в наступному вигляді:
. (4.4)
Для розв’язування задачі (4.1)–(4.4) існує багато різних методів. Однак, одним з найбільш, простих і зручних є метод гілок і границь.