9.2. Числовий приклад. Розглянемо наступну лінійну оптимізаційну задачу:

z=2x1+3x2®max

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

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

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

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

Основними недоліками розглянутого методу гілок і границь є:

1. Відсутність правил для вибору змвнної, яка ініціює процес розгалужень.

2. Відсутність правил для вибору послідовності розв’язання породжених задач.

3. Необхідність повністю розв’язувати задачу лінійного програмування. Цей недолік є найбільш серйозний, особливо при розв’язанні задач великої розмірності. Разом з тим, існують модифікації методу гілок і границь, які замість розв’язання ЗЛП застосовують процедуру “оцінки” верхньої границі цільової функції (в задачах максимізації) або нижньої (в задачах мінімізації). Така оцінка потребує порівняно невеликого обсягу обчислень. Дійсно, для кожного неоптимального розв’язку нам досить знати величину цільової функції, яку воно забезпечує. Основна ідея полягає в оцінюванні штрафів, тобто величин зміни цільової функції, пов’язаної із введенням обмежень типу xk£ [bk], xk³ [bk] до оптимальної симплекс-таблиці підзадачі, що є точкою розгалуження.

Незважаючи на вказані недоліки, метод гілок і границь на сьогоднішній день є найбільш надійним засобом розв’язання ЗЦЛП, що зустрічаються на практиці. Однак це не означає, що він може бути застосований до будь-якої задачі цілочисельного лінійного програмування. Розв’язання задач методом галузей і границь на ЕОМ припускає активну участь людини в процесі пошуку оптимуму.