Page 96 - 6197

Умови (2.13) означають, що початкова множина
  1
  0
допустимих розв’язків G розбивається на дві множини G
1
  1
  1
і G . Для задачі з множиною G до обмежень (2.3) і (2.4).
2 1
додаємо лінійне обмеження x  x  *  , а для задачі з
0 j  0 j 
  1
  1
множиною G - лінійне обмеження G . Таке розбиття
2 2
множини на дві згідно умови (2.13) називають дихотомічним.
  k
Stk. Нехай на k -тому кроці розгалуження отримана G
s
задача. Розв’язуємо отриману задачу лінійного програмування
  k
без врахування цілочисельності змінних x , j  1,n . Якщо
j
G   k задача не має розв’язку, то вона вилучається із списку
s
задач-претендентів. Допускаємо, що G   k задача має розв’язок
s
і x   k *   1   k * ,x   k * , ,x n   k *  - її оптимальний план, а
x
2
  k

R x
      k *  . При цьому можливі такі випадки.
G
s
  k *   k
і. Всі змінні x , j  1,n - цілі числа. Якщо x - рекорд і
j

  k
R x

R x   k *    , то x k  1  x   k * - новий рекорд і G   k задача
s
вилучається із списку задач-претендентів.
  k
G
іі. Якщо       k *  , то G s   k задача вилучається за
R x

s
правилом відсіву і в подальшому не розглядається.
  k *
ііі. Серед змінних x , j  1,n є хоча би одна з
j
нецілочисельним значенням з номером j . У такому випадку
0
G   k задача розбивається на дві задачі G   k і G   k за правилом,
s s, 1 s, 2
що сформульоване в St1.
Процес обчислень продовжується за наведеною схемою на
кроці Stk до тих пір поки список задач-претендентів не
вичерпається.
96