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

курсовая работа

Математична модель задачі комівояжера

Завдання комівояжера може бути сформульована як цілочисельна введенням булевих змінних , якщо маршрут включає переїзд з міста i безпосередньо в місто j і в іншому випадку. Тоді можна задати математичну модель задачі, тобто записати цільову функцію і систему обмежень:

(1)

Умови (2) - (4) в сукупності забезпечують, що кожна змінна дорівнює або нулю, або одиниці. При цьому обмеження (2), (3) висловлюють умови, що комівояжер побуває в кожному місті один раз на нього прибувши (обмеження (2)), і один раз з нього виїхавши (обмеження (3)).

Проте цих обмежень не достатньо для постановки задачі комівояжера, так як вони не виключають рішення, де замість простого циклу, що проходить через n вершин, відшукуються 2 і більше окремих циклу (підциклу), що проходить через менше число вершин. Тому завдання, описана рівняннями (2) - (4) повинна бути доповнена обмеженнями, що забезпечують звязність шуканого циклу.

Для того, щоб виключити при постановці завдання всі можливі підцикли в систему обмежень задачі включають такі обмеження:

, Де , і .

Делись добром ;)