ї задачі комівояжера
Нехай кожній дузі (i, j) графа (I, U) поставлено в відповідність число зване довжиною дуги.
Розглянемо задачу: визначити найкоротший шлях з безлічі А в безліч В, перетинав кожне безліч розбиття один і тільки один раз. Очевидно, що якщо кожне безліч розбиття складається з одного елемента і, то маємо звичайну задачу комівояжера.
Визначимо функцію: покладемо для довільного шляху. Отже, значеннями функції будуть безлічі номерів підмножин розбиття, які перетинає шлях. Нехай кожне безліч Ф i ,, складається з усіляких підмножин множини {1, 2, ..., p}, a. Застосуємо для вирішення цієї задачі наступний алгоритм.
Достатньою системою функцій в даному випадку будуть функції
Позначимо через число елементів довільного кінцевого безлічі А.
Крок 0. Покладемо. Пометим вершини ознаками. Для помічених вершин збільшимо на 1. Розглянемо одну з позначок і перейдемо до кроку 1.
Крок 1. Нехай - розглянута позначка. Пометим ознаками всі ті вершини, для яких. Для знову помічених вершин збільшимо на 1.
Розглянемо наступну помічену вершину, і будемо повторювати помечіванія до тих пір, поки не пометим деяку вершину так, щоб для ознаки помітки цієї вершини виконувалася умова або поки не можна буде зробити подальших позначок. У першому випадку перейдемо до кроку 2. а в другому до кроку 3.
Крок 2. Будуємо найкоротший допустимий шлях від вершини. Нехай - позначка вершини, для якої. Перейдемо до вершини і розглянемо позначку вершини,
для якої. Далі перейдемо до вершини, з позначкою, для якої. Послідовність і є найкоротшим допустимим шляхом.
Крок 3. Нехай - множина помічених вершин. Розглянемо всі можливі числа при . Визначимо серед цих чисел найменше і візьмемо його за нове наближення до довжині шуканого шляху. Потім перейдемо до кроку 1.
Цей алгоритм можна змінити. Якщо для деякої позначки при всіх j, для яких або, то шлях відповідний цій позначці, вже продовжено у всі суміжні з вершини. Отже, для таких позначок ознаки можна прати.
3.3 Метод гілок і меж (МВГ)
Уявімо, що необхідно обійти всі міста країни. Так як їх багато, то визначити найкоротший шлях скрутно. Тоді можна вибрати якийсь розбиття множини міст, наприклад, розглядати республіки, області або райони, і визначити найкоротший шлях, перетинав кожне з вибраних підмножин розбиття тільки один раз. Потім вже в межах обраних підмножин добудувати отриманий шлях до необхідного. Такий підхід використовується в методі гілок і меж. Цей метод дозволяє пізнати безперспективні часткові рішення, в результаті чого від дерева пошуку на одному кроці відсікається ціла гілка. Тим не менш, задовільних оцінок швидкодії алгоритму Літтла, заснованого на цьому методі, і родинних алгоритмів немає, хоча практика показує, що на сучасних ЕОМ вони іноді дозволяють вирішити задачу комівояжера для графів з кількістю вершин, меншим 100.
Вперше метод гілок і меж був запропонований Лендом і Дойга в 1960 для вирішення загальної задачі цілочисельного лінійного програмування. Інтерес до цього методу і фактично його В«друге народженняВ» пов'язане з роботою Літтла, Мурті, Суїні і Керела, присвяченій задачі комівояжера. Починаючи з цього моменту, з'явилася велика кількість робіт, присвячених методу гілок і меж і різним його модифікаціям. Настільки великий успіх пояснюється тим, що автори першими звернули увагу на широту можливостей методу, відзначили важливість використання специфіки завдання і самі скористалися специфікою задачі комівояжера.
Опис методу гілок і меж
Нехай х 1 - Центр куба Х. Обчислюємо та присвоюємо це значення рекорду. Розбиваємо куб Х 1i зі стороною ВЅ і обчислюємо значення цільової функції в їх центрах:, i = 1, ... 2 n , оновлюючи по ходу обчислень значення рекорду. Перевіряємо виконання умови для i = 1, ..., 2 n і відкидаємо відповідні подкуби. Кожен з решти розбиваємо на 2 n однакових подкубов Х 2 ij зі стороною Вј і поступаємо як раніше. На будь-якому кроці у нас формується безліч До В«кубиківВ» зі сторонами 2 - l , l> = 2, ціле. Правило вибору чергового кубика для розбиття називається правилом розгалуження - можливі варіанти наводяться нижче. Кубики із стороною не більше виключаються з безлічі К - дроблення кубика закінчується. Також виключаються кубики, потрапили в безліч (з індексом k - номером кубика) для поточного значення рекорду, - правило відсікання гілок. Рекорд оновлюється при отриманні меншого значення цільової функції (правило отримання кордонів, тобто оцінок). Значення цільової функції обчислюються в центрі кожного нового подкубіка, що включається до До після розбиття обраного для цього кубика. Алгоритм зупиняється, коли До порожньо.
Рис. 2. Граф-дерево
Зазначена термінологія і назва методу визначаються тим, що візуально дана схема перебору представляється у вигляді графа-дерева, коренева вершина якого відповідає кубу Х, вершини першого ярусу - подкубам X li , вершини другого ярусу - кубикам X 2 li , приєднаним до своїх породжує вершин X li -го ярусу, і т.д. (Див. рис. 2). Якщо кубик виключається з К, його вершина закривається - з неї не будуть йти гілки на наступний ярус. Порядок закриття вершини визначається правилом відсікання (своїм для кожної масової завдання), порядок розкриття - правилом розгалуження (своїм для кожної індивідуальної задачі). Розрізняють два види правил розгалуження за типом побудови дерева рішень (вибору вершин для розкриття): В«в ширину В», коли спочатку розкриваються всі вершини одного ярусу до переходу до наступного, і в В«глибинуВ» - щоразу розкривається лише одна (звичайно з кращим значенням рекорду) вершина на ярусі до кінця гілки. На практиці реалізують деяку суміш, наприклад, перше правило поки вистачає машинної пам'яті (в К не надто багато елементів), потім перемикаються на друге. Перевагу тієї чи іншої стратегії розгалуження оцінюється кожним обчислювачем по-своєму, виходячи з головного завдання методу гілок і меж - швидше отримати кращий рекорд, щоб відсікти більше гілок. Вдалий вибір стратегії розгалуження в МВГ (наприклад, на основі наявної в обчислювача додаткової інформації або евристичних міркувань про об'єкт) дозволяє (хоча і не гарантовано) вирішувати задачі великої розмірності.
Відзначимо, що в гіршому випадку - не вдається відкинути жодної точки х - і приходимо до повного перебору; тобто зазначена експоненціальна оцінка точна на класі всіх ліпшіцевих функцій.
4. Вибір об'єкта управління. аналіз аспектів його роботи
В якості прикладу конкретного застосування методу може бути запропонована прикладна задача, пов'язана з проблемою розміщення та обслуговування обладнання, в якій потрібно визначити оптимальну траєкторію циклічного маршруту руху робота-транспортера по траєкторії цеху з метою періодичного обслуговування обладнання.
Для розгляду можна уявити собі, що робот розвозить по цеху деякий матеріал, необхідний для роботи агрегатів. Припустимо, що вже є деякий зразок робота, тобто немає необхідності купувати новий - капітальні витрати відсутні. Нехай робот має електричний привід і в якості джерела харчування - переносні акумулятори.
5. Постановка і рішення оптимізаційної задачі
5.1 Вибір критерію оптимальності
Основним будемо вважати економічний критерій, тобто будемо прагнути знизити всі статті грошових витрат, пов'язаних з роботою даного робота. Відзначимо, що схема роботи робота повинна відповідати технологічній схемі роботи цеху, тобто поставка необхідного матеріалу повинна здійснюватися в поставлені терміни, визначувані ви...
