Дипломная работа: Моделирование конкурентоспособности товара на современном рынке

Начальной вершине 0 соответствует исходное допустимое множество или исходная задача (1), а любой другой вершине – подмножество , полученное в результате ветвления, или подзадача :

, .

Если при ветвлении из каждой вершины происходит разбиение соответствующего ей множества на две части, то схема метода изображается бинарным деревом.

Процесс ветвления из данной вершины не производится, если выполнено одно из условий:

. Граница найдена точно: , т.е. получено решение подзадачи . Будем говорить, что в этом случае вместо оценки решения в вершине найдено полное решение , соответствующее этой вершине.

. Множество является пустым.

. Из полученных до этого полных решений найдется такое , что граница удовлетворяет неравенству

.

В данном случае дальнейший поиск решения исходной задачи на подмножестве не имеет смысла, и говорят, что вершина «убита» вершиной . В самом деле, из