Рішення задачі про комівояжера методом гілок і границь

II варіант рішення

I варіант

Given

Формування оптимального плану вихідної ЗДЛП

Формування цільової функції ЗДЛП

Формування початкових умов

Формування блоку обмежень ЗДЛП

Given

Формування умов невід’ємності, що накладають на змінні

Формування процесу пошуку экстремума

Формування розв’язку задачі

Визначення оптимального вектора Х

Визначення оптимального значення функції цілі

Постановка задачі

Є n міст (А ₁, А ₂, А ₃,... А_n), задана матриця відстаней між містами . Необхідно відшукати такий найкоротший замкнутий маршрут (цикл), що проходить один і тільки один раз через кожне місто, при якому мінімізується сумарна довжина шляху .

Математична модель задачі

У загальному випадку нехай розглядаються n пунктів, тоді вводиться n ² альтернативних змінних x_ij. Причому відповідна змінна буде дорівнювати 0, якщо перехід з i в j пункт не входить у розглянутий маршрут. І, мабуть, що така змінна буде дорівнювати 1, якщо зазначений перехід можливий. Тоді умова прибуття в кожен пункт і виходу з кожного пункту тільки по одному разу виражається співвідношенням виду:

(4.1)

(4.2)

Для забезпечення безперервності маршруту вводять додатково n змінних і при цьому формують n ² додаткових обмежень:

;

. (4.3)

У такому випадку сумарна довжина маршруту, який необхідно мінімізувати, буде записуватися в наступному вигляді:

. (4.4)

Для розв’язування задачі (4.1)–(4.4) існує багато різних методів. Однак, одним з найбільш, простих і зручних є метод гілок і границь.

Дата добавления: 2014-11-25