Общая схема метода ветвей и границ
Рассматривается задача дискретного программирования j(x) ® max, xÎ X, X - конечное множество. (4. 6)
Для ее решения методом ветвей и границ достаточно:
1. Уметь разбивать множество X (переобозначим его через X(0, 1)) на некоторые подмножества X(1, 1), X(1, 2), X(1, 3),.... Каждое из полученных подмножеств, в свою очередь, может быть разбито на подмножества X(2, 1), X(2, 2), X(2, 3),..., и так далее, вплоть до получения одноэлементных подмножеств. Индексы (i, j) у подмножеств X (i, j) означают следующее: i - номер уровня разбиения, j - порядковый номер в уровне.
В результате такого разбиения получается дерево подмножеств:
X(0, 1)
X(1, 1) X(1, 2) X(1, 3) X(1, 4)
2. На каждом из таких подмножеств X(i, j) уметь строить верхние оценки максимального значения функционала, т.е. определять значение x(i, j) такое, что x(i, j)³ max{ j (x) | xÎ X(i, j)}. (4. 7.)
|
X(2, 1) X(2, 2)... X(2, k) X(0, k+1)...
