ТЕМА 9. МЕТОД ГІЛОК І ГРАНИЦЬ

9.1. На практиці більш ефективними в порівнянні з методами перерізу є алгоритми, що реалізують метод гілок і границь. Останній відноситься до групи комбінаторних методів розв’язання ЗЦЛП і, так само, як і методи перерізу, спирається на розв’язання задачі з послабленими обмеженнями (ЗПО).

Нехай xr - цілочисельна змінна, значення xr* якої в оптимальному розв’язку ЗПО є дробовим. Очевидно, що в оптимальному розв’язку вихідної задачі значення xr  буде задовольняти одній із двох нерівностей:  або  .

Введення цих умов у ЗПО породжує дві не зв'язані між собою задачі, тобто задача розгалужується. Кожна така підзадача розв’язується як задача лінійного програмування.

9.2. Алгоритм методу гілок і границь

Крок 1. Розв’язується задача з послабленими обмеженнями. Якщо отриманий розв’язок задовольняє вимогам цілочисельності, то обчислення припиняють. Інакше слід перейти до кроку 2.

Крок 2. Серед цілочисельних змінних, що набули в оптимальному розв’язку ЗПО дробових значень, вибирають (довільним чином) змінну xr, що ініціює процес розгалужень. Вихідна задача розбивається на дві підзадачі. Одну з них одержують із ЗПО шляхом введення обмеження типу  , другу - обмеження типу  .

Крок 3. Розв’язують підзадачі (1) і (2) за допомогою двоїстого симплекс-методу. Якщо підзадача не має допустимих розв’язків, вона виключається з розгляду. В отриманих розв’язках xr приймає цілі значення. Якщо до інших змінних вихідної задачі не пред'являються вимоги цілочисельності, то процес обчислень припиняють. Оптимальному розв’язку вихідної задачі буде відповідати той із розв’язків підзадач (1) і (2), що забезпечить краще значення цільової функції.

Крок 4. У протилежному випадку, якщо вимоги цілочисельності не виконуються, кожна з поточних підзадач розбивається на дві нові підзадачі. Для кожної з породжених підзадач повторюються кроки 2 і 3 доти, поки не буде отриманий деякий цілочисельний розв’язок.

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

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

Крок 7. Для підзадач з нецілочисельними розв’язками і значеннями цільової функції, кращими поточної границі, повторюють кроки 2, 3, 4, 5, 6 доти, доки всі підзадачи не будуть прозондовані або поки для них не будуть отримані цілочисельні розв’язки.

Крок 8. В якості оптимального розв’язку вихідної задачі приймається розв’язок тієї підзадачі, яка відповідає останній зафіксованій границі.

Розглянемо наступний приклад:

Z=2x1+3x2®max

Сукупність породжених підзадач представлена у вигляді дерева на рис.6.2.

Рис. 6.2. Схема пошуку оптимального розв’язку задачі лінійного цілочисельного програмування методом гілок і границь

Очевидно, що на кількість кроків алгоритму, необхідних для знаходження оптимального розв’язку, також може вплинути вибір змінної, ініціюючої процес розгалуження. Якщо вибрати в якості такої змінної не x1, а x2,, то схема пошуку розв’язку зміниться.