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

1. На множині припустимих планів G ₀ знаходять оптимальне значення функції цілі (2.1), відкинувши умови цілочисельності (2.4). При цьому знаходять оцінку функції якості

.

Цю оцінку вважають верхньою оцінкою функції якості G ₀. Якщо план задовольняє умовам цілочисельності, то він вважається оптимальним для ЦЗЛП (2.1)–(2.4).

Якщо ж умови цілочисельності для задачі (2.1)-(2.4) не виконуються, то переходять до пункту два цього алгоритму.

2. Починають розвивати процес розгалуження. Для цього вибирають деяку нецілочисельну компоненту x_j = x_{j 0}, 1 £ j £ n. При цьому множину G ₀ розбивають на дві непересічні підмножини .

Операцію реалізують у такий спосіб

Для наочності отриманого результату зображують дерево розв’язків.

		G0
0 крок
1 крок

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

Якщо ж, допустимо, на множині одержують цілочисельний план, а на множині – нецілочисельний, причому , то надалі розвивається процедура розгалуження на множині .

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

Дата добавления: 2014-11-25