Page 94 - 6197

Алгоритм методу гілок і меж включає в себе таку
послідовність перацій:
G
Обчислення оцінки. Нехай G  G і    min :R   x .

x G

G

Тоді   називається нижньою оцінкою, якщо для будь-
якого x  G виконується умова
G
    R   x .
Розгалуження. На початку роботи алгоритму G   0  G .
  0
Множину G розіб’ємо на r множин, що не пересікаються
1
1 r
j
G   0   G , G  G  , i  .
i i j
i 1 
Тепер розглянемо k -тий крок роботи алгоритму. Нехай
G   k , i  1,r множини, до яких ще не застосовувалась
i k
операція розбиття. Із сукупності G   k , i  1,r вибираємо
i k
множину G   k і розіб’ємо її на множини, що не перетинаються
s
2 r
  k   k
G   G .
s s,t
t 1 
Таким чином, у процесі розбиття отримуємо сукупність
множин, які ще не були піддані операції розбиття. Це
k  1 k  1
вершини G , i  1,r . Множини G , i  1,r
i k 1 i k 1
утворюють список задач для подальшого розгалуження.
Обчислення планів. Якщо на k -ому кроці розгалуження
  k   k k  1 k  1
відомий план x  G , а на k  кроці план x  G і
1
i i

  k
  k

R x
якщо R x k  1    , то план x   k  G відкидається.
i
  k
Найменше із допустимих розв’язків x і буде рекордом.
Правило відсіву. Нехай у процесі розгалуження отримали
  k
множину G , а також відомий рекорд x . Тоді при
r
94