Метод гілок меж (вг)
Цей метод представляє, по суті, схему методів і містить одну процедуру, яка змінюється від завдання до завдання. Знайти її для нового завдання – це ПРОБЛЕМА. При вирішенні деякої задачі в методі гілок кордонів ми повинні розташовувати крім основної задачі деякою «ослабленою» задачею, яка відрізняється від основного зняттям певної умови, що ускладнює основне рішення. При цьому ми повинні мати ефективний метод вирішення ослаблених завдань, оформленим у вигляді деякої процедури. Назвемо їїдопоміжною процедурою.
Для задачі про комівояжер (ЗК) таким ослабленим завданням є завдання про призначення (ДТ). Тут ми знімаємо умову, що рішення має бути циклом. Сказане означає, що для реалізації методу гілок та кордонів для задачі про комівояжер необхідно мати ефективний метод вирішення задачі про призначення. Будемо вважати, щодопоміжноюпроцедуроюдля задачі про комівояжер є угорський метод вирішення задачі про призначення.
Для звичайної цілісної задачі ослабленим завданням є відповідна безперервна ЗЛП, що виходить зняттям умови цілісності, адопоміжноюпроцедурою– симплекс-метод.
Другою важливою процедурою методу гілок та кордонів єпроцедура розгалуження.
Встановимо попередньо наступний факт.
Нехай у певній задачі оптимізації (для визначеності задачі мінімізації) ми додаємо деякі додаткові умови на варіанти вибору. Що станеться з оптимальним значенням цільової функції? Зрозуміло, що оскільки стара оптимальна альтернатива (ОА) може не задовольняти нову умову, то в новій ОА значення цільової функції може виявитися гіршим. Таким чином, оптимальне значення цільової функції при додаванні додатковогоумови або залишиться незмінним, або погіршитися, тобто не покращає.
Навпаки, при знятті певної умови оптимальне значення цільової функції не погіршується, але може покращити.
Процедура розгалуженняздійснює розбиття деякої задачі на ряд підзавдань. Це розбиття досягається запровадженням додаткових умов.
Умови правильного розбиття під час розгалуження
НехайP- деяке завдання лінійного програмування,S- безліч допустимих розв'язків цього завдання. Не змінюючи цільової функції та вихідних обмежувальних умов, накладемо на вирішення вихідної задачі послідовно за однією додатковою обмежувальною умовою із сукупності умови
Зі сказаного вище випливає, що якщо
Розгалуження наочно можна уявити так:
У методі ВГ розгалуженню піддається «ослаблена» задача та його результаті виходять також «ослаблені» завдання.
Сенс розгалуження полягає в тому, що для деяких розгалужень оптимальні рішення можуть задовольняти відкинутій умові і, отже, серед них можна знайти оптимальне рішення вихідного завдання
Потрібно мати на увазі, що розгалуження можуть піддаватися не тільки завданняP, але і розгалуження
