Page 109 - 6197

2.3.4 Задача комівояжера
Як приклад задачі лінійного цілочисельного
програмування розглянемо задачу комівояжера.
Задача комівояжера має широке прикладне застосування в
транспортних системах, автоматизованому проектуванні,
тестуванні та виготовленні інтегрованих схем, виробництві
друкованих плат, лазерній нарізці пластмас і металів,
рентгенівській кристалографії та інших галузях.
Дамо словесний опис задачі комівояжера. Є n міст
(пунктів), які пронумеровані цифрами від 1 до n . Комівояжер
вирушає із міста під номером i , де i  1 2, , ,n . Кожне
1 1
місто він відвідує тільки один раз і повертається до
початкового пункту (до міста під номером i ). Очевидно, що
1
комівояжер може відвідувати міста в довільному порядку.
Тому i -тий маршрут буде певною комбінацією цифр 1, 2, …,
n , яку позначимо як i ,i , ,i . Отже, i -тий маршрут
1 2 n
визначається як деяка перестановка чисел від 1 до n :
i  i ,i , ,i ,i n 1  , i  i n 1  .
1
2
1
n
На рис. 2.4 показаний маршрут комівояжера, який відвідав

1
6 міст. У даному випадку i  1 3 4 2 6 5 1, , , , , , . Отже, i  ,
1
2
6
5
i  3 , i  , i  , i  , i  , i  i  1 і загальна довжина
4
2 3 4 5 6 1 7
маршруту визначиться як сума віддалей між містами, які
відвідав комівояжер L  c  c  c  c  c  c .
13 34 42 26 65 51
У загальному випадку для довільного маршруту i будемо
мати
nc
L   i   c i k k i , i  i n 1  . (2.14)
1
k 1 1 

109