Теоретичний матеріал для виконання завдання №4

6. Постановка задачі комівояжера

7. Представлення задачі комівояжера у вигляді графа

8. Метод гілок і границь

9. Застосування методу гілок і границь до розв’язання задачі комівояжера

10. Приклад розв’язання задачі про обробку деталей

1. Постановка задачі комівояжера

Розглянемо один з варіантів задачі про визначення оптимальної послідовності обробки деталей. Припустимо, що n різних деталей, занумерованих від 1 до n, треба обробити на одному верстаті. При переході від обробки деталі i до деталі k потрібен час d_ik на переналагодження верстата, різне при різних i і k. Значення d_ik задані в табл. 4.4. Потрібно визначити такий порядок обробки деталей, при якому загальний час на обробку буде мінімальним. Оскільки можливо n варіантів обробки першої деталі, n-1 – другий і т.д., то загальне число варіантів обробки буде дорівнює n!. Отже, ця задача відноситься до задач комбінаторного типу.

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

Таблиця 4.4

i	k
	1	2	. . .	n
1 2 . . . n	– d21 . . . dn1	d12 – . . . dn2	. . . . . . . . . . . .	d1n d2n . . . –

У математиці задача подібного виду одержала назву задачі комівояжера. Комівояжер (агент, що рекламує товар своєї фірми) повинний відвідати n–1 інших міст і повернутися до вихідного пункту. Відомі відстані між містами d_ik, задані у виді уже розглянутої табл. 4.4. Потрібно установити, у якому порядку комівояжер повинний відвідувати міста, щоб загальна пройдена відстань була мінімальною.

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

Представлення задачі комівояжера у виді графа

Дуже наглядно задачу комівояжера можна представити у виді графа G = (X, U), вершини якого відповідають містам, а дуги – дорогам, що з'єднують міста між собою. Кожній дузі, що з'єднує міста і, k, приписуємо число d_ik, назване довжиною дуги і рівне відстані між містами i і k. Якщо з кожного міста є безпосередній шлях у будь-яке інше місто без заходу в проміжні міста, то кожні дві вершини графа будуть з'єднані дугами в обох напрямках. Граф, що виходить при цьому, називається повним.

На практиці повні графи зустрічаються рідко. Якщо граф не повний, то його можна вважати повним, думкою відновивши відсутні дуги і приписавши їм довжину d=∞. У таблиці відстаней відповідні клітки зручно залишати незаповненими.

Елементарний шлях у графові, що проходить через усі вершини, називають гамільтоновим шляхом.

Замкнутий елементарний шлях, тобто елементарний контур, що проходить через усі вершини графа, називають гамільтоновим контуром.

Ці назви зв'язані з задачею Гамільтона. Як бачимо, задача комівояжера зводиться до знаходження найкоротшого гамільтонова контуру чи найкоротшого гамільтонова шляху.

Надалі основним видом задачі комівояжера будемо вважати замкнутий варіант, коли задана вершина, у якій починається і закінчується маршрут комівояжера. Однак незамкнуті варіанти легко приводяться до замкнутого.

Нехай задано граф G =(X,U) і задано початкову крапку х₀Х, але не зазначена кінцева крапка. Замінимо довжини всіх дуг, що закінчуються в х₀, нулями. Тоді будь-який гамільтонів контур буде містити дугу нульової довжини, що закінчується в х₀. Якщо знайти найкоротший контур і виключити з нього дугу нульової довжини, що закінчується в х₀, то одержимо найкоротший гамільтонів шлях.

Якщо не зазначені ні початкова, ні кінцева вершини графа, то уводимо фіктивну вершину z, що з'єднується з усіма вершинами графа в обох напрямках. Цю вершину приймаємо за початкову і знаходимо найкоротший гамільтонів контур. Виключивши з нього дугу нульової довжини, що виходить з z, і дугу нульової довжини, що заходить у z, одержимо найкоротший гамільтонів шлях.