Алгоритм метода ветвей и границ.

1 этап. Ветвлению в первую очередь подвергается подмножество S (S є I ), которому соответствует наименьшее значение нижней оценки целевой функции. I- это множество включающее номера всех подмножеств Di или Di’ , которые находятся на концах ветвления и ветвление которых не прекращено.

2 этап. Если для некоторого подмножества i Σi≥ŋ(D) то ветвление его необходимо прекратить, т. к. потенциальные возможности нахождения лучшего решения в этом подмножестве оказывается хуже, чем значение целевой функции для найденного к данному моменту времени лучшего допустимого решения.

3 этап. Ветвление подмножества Di’ прекращается, если найденное оптимальное решение Є D обосновывается это тем, что значение целевой функции от этого решения равно нижней границе на множестве Di. Следовательно, лучшего допустимого решения на данном множестве не существует. В этом случае рассматривают возможность корректировки верхней оценки целевой функции.

4 этап. Если выполняется соотношение Σ≥ŋ(D), где Σ=min Σi, то выполняется условие i є I оптимальности для найденного допустимого решения.

5 этап. После нахождения хотя-бы одного допустимого решения может быть рассмотрена возможность остановки работы алгоритма с их подсчетом погрешности найденного решения по отношению к оптимальному. ∆= Σ- ŋ(D) разница между нижней и верхней оценкой целевой функции.