Лекция: Общая схема
В методе на каждой итерации строится список из перспективных подмножеств, одно из которых, по крайне мере содержит оптимальный план. На нулевой итерации. Вычисляем оценку итерации, рекорд итерации .
Вычисляем разность. Возможны случаи:
1.. В этом случае рекордный план будет оптимальным планом задачи, так как на нём достигалась нижняя граница.
2., где — малое положительное число, заданная точность вычисления. В этом случае рекордный план можно взять в качестве — оптимального, то есть приближённого решения задачи (1).
3.. Тогда заданная точность не достигнута. Переходим к первой итерации. Для этого в соответствие с первым предположением ветвим на более мелкие. Для каждого вычисляем границу по второму предположению, и бесперспективные подмножества отбрасываем, а перспективные включаем в список для первой итерации.
Определение. Пусть на некоторой итерации есть подмножество и вычислен рекорд. Тогда множество будет перспективным, если. Если, то, очевидно, на нём нет планов, лучших, чем рекордный и, ветвь можно отсечь, это подмножество будет бесперспективным.
Пусть – список перспективных подмножеств -ой итерации. Вычисляем оценку итерации. Вычисляем рекорд итерации .
Вычисляем разность .
Совершаем анализ:
1. если, то построен оптимальный план. Записываем ответ.
2. если, то построен -оптимальный план. Записываем ответ.
3. если, то переходим к ой итерации. Для этого выбираем из наиболее перспективное подмножество ( с наименьшей нижней границей) и дробим его по первому предположению. В включаем перспективные подмножества из вновь полученных дроблением и остальных подмножеств множества .
И так далее.
Ясно, что на итерациях уменьшаются, а увеличиваются (чем мельче подмножество, тем точнее можно для неё построить границу). Следовательно, числа будут уменьшаться и, в конце концов, метод ветвей и границ позволит, решить задачу (1).
Замечание 2. Слово «эффективная» во втором предположении означает, что нижняя граница не сильно отличается от точной нижней. Чем точнее строится оценка, тем быстрее сходится метод ветвей и границ.