Методи розв'язування задач дискретної оптимізації

Задачі дискретної оптимізації - це задачі знаходження екстремуму функції, заданої на дискретному (найчастіше - кінцевому) множині точок. Якщо область визначення функції складається з кінцевого числа точок, то задачу дискретної оптимізації завжди, в принципі, можна вирішити перебором усього цього множини. Однак на практиці це множина хоч і звичайно, але може бути дуже велике, так що методи перебору не ефективні.

До методів належать:

1. Метод гілок і меж
2. Методи відсікаючих площин вирішення завдань цілочисельного програмування
3. Алгоритм гілок і меж для вирішення завдань цілочисельного програмування c булевими змінними
4. Алгоритми рішення задачі календарного планування
5. Алгоритм гілок і меж для вирішення задач календарного планування
6. Алгоритм розв'язання задачі комівояжера
7. Метод динамічного програмування

Метод гілок та границь. Переваги та недоліки.

Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж.

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

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

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

Алгоритм методу

Результатом роботи алгоритма є знаходження максимуму функції на допустимій множині. При чому множина можу бути як дискретною, так і раціональною. В ході роботи алгоритму виконується дві операції: розбиття вихідної множини на підмножини(гілки), та знаходження оцінок(меж). Існує оцінка множини згори та оцінка знизу. Оцінка згори - точка що гарантовано не менша за максимум на заданії підмножин. Оцінка знизу - точка що гарантовано не більша за максимум на заданії підмножині. Множина що має найбільшу оцінку зверху зветься рекордною. На початку вся множина вважається рекордною.

1. Рекордна множина розбивається на підмножини;
2. Знайти оцінки згори та знизу для нових підмножин;
3. Визначити максимальну оцінку знизу серед усіх підмножин;
4. Видалити ті множини у яких оцінка зверху менша за максимальну оцінку знизу;
5. Знайти максимальну оцінку згори серед усіх підмножин ту вважати її рекордною;
6. Якщо не досягнуто дискрентості, або необхідної точності перейти по пункту 1;

Результатом роботи є значення між оцінкою згори та знизу для рекордної множини. Точністю є різниця між верхнею та нижньою оцінками, тобто для дискретних множин алгоритм завершений тоді, коли ці оцінки співпадають. Метод використовується для вирішення деяких NP-повних задач. Швидкість алгоритму залежить від вигляду функції та способу визнацення оцінок, але гарантовано не більша за повний перебір.

Основні недоліки:

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

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

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

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