МЕТОД ГІЛОК І ГРАНИЦЬ ДЛЯ розв’язування ЦЗЛП

КОМБІНАТОРНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ ЦЗЛП

Комбінаторні методи – це велика група методів дискретного програмування. Ідея цих методів полягає в тому, що процедуру повного перебору всіх планів задачі заміняють частковим перебором. Цей процес реалізується шляхом відкидання деякої підмножини варіантів, які свідомо не містять шуканого оптимуму. Далі перебір ведеться серед варіантів, що залишилися, які є в певному змісті перспективними.

Необхідно підкреслити, що комбінаторним методам не властиві помилки округлення (такі помилки грають досить істотну роль при використанні методів відсікання). Більше того, відзначимо, що для комбінаторних методів характерна більше проста алгебра, але трохи складніше логіка рішення. Досвід чисельної реалізації комбінаторних методів показує, що при такому підході істотно знижується ступінь непередбачуваності результату.

У теоретичному плані необхідно відзначити, що більшість комбінаторних методів не вимагають доказу збіжності алгоритму.

До комбінаторних методів відносять наступні методи розв’язування ЦЗЛП:

- адитивний алгоритм Балаша;

- алгоритм Літла, Муті, Суіні і Керела для розв’язування задачі комівояжера;

- метод неявного перебору (метод Джеферсона)

- метод Фора й Мальгаранжа.

Уперше метод гілок і границь стосовно до ЗЦЛП був запропонований в 1960 р. у роботі Ленда й Дойга. Однак, запропонований підхід не зробив істотного впливу на розвиток методів розв’язування задач дискретного програмування.

Фактично друге народження методу гілок і границь пов'язане з роботою Літла, Муті, Суіні й Керела (1963 р.). Ця робота присвячена розв’язуванню задачі комівояжера. Друге народження методу пояснюється тим, що автори відзначили надзвичайну широту методу, вони показали важливість використання специфіки задачі при застосуванні цього методу.

У загальному випадку ЦЗЛП формулюється в такий спосіб: знайти оптимум функції:

; (2.1)

при обмеженнях

(2.2)

(2.3)

(2.4)