Графоаналитический метод ветвей и границ

Этот метод относится к методу инженерной оптимизации. Он рассчитан по получение квазиоптимального решения. После нахождения всех квазиоптимальных, выбираем оптимальный. Метод основан на применении дихотомичного дерева.

На каждом шаге построения алгоритма рассматриваются все возможные пустые (конечные) вершины дерева.

При использовании метода ветвей и границ идёт последовательное построение дерева, шаг за шагом. На каждом шаге продолжение получаем из одной из вершин, но для того, чтобы определить из какой продолжать построение, рассматриваются все конечные вершины.

Будем полагать, что на некотором шаге к у нас образовались висячие вершины. Каждой вершине соответствует своя сложность – S_i(r_i,n_i) – количество проверок, имеющих характеристический признак = 1, и лежащих в пути от вершины 0 к вершине Х_i. Сложность определяет количество проверок.

Модифицированная таблица покрытий – B_i(D_i,V_i). Она строится для каждой висячей вершины. Каждая таблица строится на основе исходной таблицы путём вычёркивания строк, которым соответствуют проверки в пути от корневой вершины к рассматриваемой. В том случаем, если в пути лежит проверка с характеристическим признаком = 1, то вычёркиваются все столбцы, которые накрываются этой проверкой.! Так как мы работаем с дихотомичным деревом, то на каждом шаге может образовываться только 2 новых вершины. Для этих вершин и надо рассчитать сложность и построить модифицированную матрицу. Параметры можно использовать с предыдущего шага.

Нижняя граница ожидаемых проверок для получения полного решения Inf β_i. Если предварительно проверки упорядочить по возрастанию модуля характеристических чисел… Для продолжения дихотоничного дерева, выбирается та вершина, для которой имеется минимальное значение суммы единиц проверок. В качестве проверки, которая будет исходить из вершины, выбирается первая проверка, соответствующая модифицированной таблицы. На каждом шаге контролируется построение полного алгоритма. Получаемое решение является квазиоптимальным. Как правило, этот метод не используют, если идёт речь о построении алгоритма по минимальному числу проверок. Алгоритм построения оптимального решения с учётом количества проверок и ресурсной обеспеченности. Если надо построить алгоритм, который обладает минимальным количеством проверок и наилучшим обеспечением используют метод ветвей и границ, в качестве решающего правила выбирают функцию ψ(.