Page 93 - 6197

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

а) б)
Рисунок 2.2 – Дерево рішень

У схемі одностороннього розгалуження вибирається
перша (ліва) вершина на нижньому рівні, а для схеми
одночасного розгалуження такою вершиною може бути будь-
яка. Алгоритм закінчує роботу, якщо перекреслені всі кінцеві
вершини.
Дамо формалізований опис задачі лінійного
цілочисельного програмування (2.2) – (2.5). Всі цілочисельні
розв’язки задачі (2.2) – (2.5), які задовольняють умовам (2.3) і
(2.4) утворюють випуклу множину, яку позначимо як G .
Тепер задачу цілочисельного програмування запишемо у
такому вигляді:
R   min :x *  R   x ,

x  G , G  N ,
n
де G - число елементів множини G ; N  2 .

93