Метод ветвей и границ	Описание метода

Метод ветвей и границ. Описание

На каждом шаге имеется:

рекорд x ;

просмотренная часть P D, для которой f(x) > f(x ); 8x 2 P ;

разбиение множества DnP на подмножества di1 ; : : : ; dik .

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 4.

9.03.2016

6 / 8

Метод ветвей и границ	Описание метода

Метод ветвей и границ. Описание

Шаг состоит в следующем

Выбрать элемент разбиения, например, dik .

Вычислить UB(dik ). Åñëè f(x ) > UB(dik ), то сменить рекорд x .

Вычислить LB(dik ).

Åñëè LB(dik ) > f(x ), то добавить dik ê P и перейти к следующему шагу.

Åñëè LB(dik ) 6 f(x ), но во множестве dik удалось найти

наилучший элемент x~ : f(~x) 6 f(x) 8x 2 dik , то добавить dik ê P . Åñëè f(x ) > f(~x), положить x := x~.

Åñëè LB(dik ) 6 f(x ) и элемент x~ найти не удалось, то разбиваем dik на подмножества dik = dik+1 [ [ dik+m . Переходим к следующему шагу, имея новое разбиение для DnP .

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 4.

9.03.2016

7 / 8