Page 92 - 6197

2.3.2 Метод гілок і меж
В основі методу гілок і меж лежить ідея послідовного
розбиття множини допустимих рішень. На кожному кроці
методу елементи розбиття підлягають аналізу – чи вміщує
дана підмножина оптимальний розв’язок. Якщо розглядається
задача на мінімум, то перевірка здійснюється шляхом
порівняння значення цільової функції на даній підмножині з її
верхньою оцінкою. Як оцінка зверху береться значення
цільової функції на деякому допустимому розв’язку.
Допустимий розв’язок, який визначає найменшу верхню
оцінку, називають рекордом. Якщо значення цільової функції
на даній підмножині не менше оцінки зверху, то поточний
розв’язок задачі не вміщує рішення, яке краще за рекорд, і
його можна відкинути. Якщо значення цільової функції на
черговому етапі розв’язування задачі менше рекордного, то
відбувається зміна рекорду. Множина розв’язків переглянута,
якщо виявлено, що вона не вміщує розв’язку кращого за
рекорд.
Якщо переглянуті всі елементи розбиття, алгоритм
закінчує роботу, а поточний рекорд є оптимальним
розв’язком. У протилежному випадку серед не переглянутих
елементів розбиття вибирається підмножина, яка у певному
сенсі є перспективною. Вона підлягає розбиттю
(розгалуженню). Нові підмножини аналізуються згідно
наведеної вище схеми. Процес продовжується до моменту
перегляду всіх елементів розбиття.
Розбиття множини розв’язків зручно подати у вигляді
дерева рішень. На рисунук 2.2 наведені приклади одночасної
(рис. 2.2, а) і односторонньої (рис. 2.2, б) схем розгалуження.
Кожна вершина дерева відповідає деякій підмножині
розв’язків. Дуги, що виходять із верши, означають, що на
деякому кроці цю підмножину не вдалося відсікти і вона була
розбита на підмножини. Вершини, у які входять такі дуги,

92