Иванов, А.А. Автоматизация технологических процессов и производств

100 Глава 4 . Оптимизация параметров инте грированной системы полную аналогию с задачей составления оптимального расписания обработки N заготовок. Существо метода ветвей и границ состоит в следующем. Имеется начальное множество вариантов решения задачи U { 1,2, N}. Пусть < 7 , —значение некоторого параметра, характеризующего качество ре­ шения задачи в г'-м варианте. Оптимальному решению соответствует условие < 7 * = min qt i e U где q *—точная нижняя граница для множества {qt, #2, •••, %}• Для множества U вводится понятие «оценка снизу» q, которая удовлетворяет условию я < ?*■ Затем проводится последовательное улучшение оценки снизу с це­ лью приближения ее к точной нижней границе q -э q ' . Начальное множество U разбивают на подмножества с точными нижними грани­ цами критерия качества, например на два подмножества. Это позволя­ ет уменьшить число элементов. Для более детального исследования подмножества его, в свою очередь, разбивают еще на подмножества. Процедуру разбиения представляют в виде дерева разбиений (рис. 4.6). Рис. 4.6. Дерево разбиений к задаче оптимизации методом ветвей и границ Пусть множество U разбивается на подмножества А и В с точны­ ми нижними границами qA и qB, связанными с q соотношением q = min (q*A, q*B).