Математична модель задачі [1]
Метод гілок і границь – це один з методів
повного перебору. Його застосування
можливе не завжди, а лише тоді, коли
виконуються додаткові умови на множині
і мінімізованою на ній функцією
,
Нехай,
–
скінченних лінійно впорядкованих множин
і
- сукупність умов, що ставлять у
відповідність векторам виду
(
булеве
значення
(вираз, який для кожної множини аргументів
ставить у відповідність значення
«істина», або «хибність»). Вектори
, для яких
,
звуться частковими розв’язками.
Оптимальність можливих розв’язків
визначає деяка функція
,
а усі можливі розв’язки складають
множину
.
Потрібно знайти мінімум цієї функції
та елемент, на якому цей мінімум
досягається, або встановити його
відсутність.
В основі методу гілок і границь лежить ідея послідовного розбиття множини допустимих рішень на підмножини ("розділяй і володарюй"). На кожному кроці методу елементи розбиття піддаються перевірці для з'ясування, містить дана підмножина оптимальне рішення чи ні. Перевірка здійснюється за допомогою обчислення оцінки знизу для функції цієї підмножини. Якщо оцінка знизу не менше рекорду - найкращого з знайдених розв’язків, то підмножина може бути відкинуто. Підмножина, що перевіряється, може бути відкинута ще й у тому випадку, коли в ньому вдається знайти найкращий розв’язок. Якщо значення цільової функції на знайденому на знайденому розв’язку менше рекорду, то відбувається зміна рекорду. По закінченню роботи рекорд є шуканим розв’язком.
Вхідні дані
Для задач, що розв’язуються алгоритмом гілок і границь чи решета умову можна сформулювати за допомогою:
скінченні набори значень
,
з елементів яких буде формуватися
шуканий розв’язок задачі;
умови, при виконанні яких, знайдений розв’язок у вигляді набору
буде являти собою шуканий розв’язок.
Вихідні дані
На виході роботи алгоритму, в залежності від поставленої задачі ми можемо отримати:
сукупність всіх векторів
, що є оптимальними розв’язками даної
задачі;один, або сукупність з всіх знайдених оптимальних розв’язків задачі , для якого виконується спеціальна умова, що вказана в формулюванні задачі;
відсутність розв’язку.
Опис методів розв’язання задачі Метод гілок та границь
Розглянемо задачу дискретного
програмування в загальній формі
мінімізувати
,
за умов
,
де
- скінченна множина.
В основу методу гілок і границь покладено такі побудови, що дозволяють в ряді випадків істотно зменшити обсяг перебору варіантів .
Обчислення нижньої границі (оцінки)
.
Часто вдається, не розв'язуючи задачу,
знайти нижню границю (оцінку) цільової
функції на множині розв'язків
(або на її деякій підмножині)
.
Розбиття на підмножини. Реалізація методу пов'язана з постійним розбиванням множини G на дерево підмножин. Розбиття відбувається за такою схемою:
.......
Рис.1 Схема роботи алгоритму методу гілок та границь