Метод ветвей и границ. Общая схема

 

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

Пусть существует некоторая функция f(X), экстремум которой (например, максимум) необходимо найти при некоторой системе ограничений.

Этой системой определяется ОДП задачи - обозначим ее G. Пусть некоторым способом мы можем определить верхнюю границу функции на этой области ₀, т.е. ₀ f(X), X G.

Затем проверяют, не существует ли какой-нибудь очевидный способ нахождения точки X⁰, для которой f(X⁰)= ₀. Если он есть, то искомый максимум найден.

Если такого способа нет, то множество G разбивают на подмножества G₁ и G₂ и для каждого из них находят верхнюю границу ₁ и ₂ (при этом _{0 1} и _{0 2}). Далее оптимальный план ищут в наиболее перспективном множестве, т.е. в том, которому соответствует наибольшая оценка.

 

 

Этот процесс может быть изображен в виде дерева (рис.18). На каждом шаге процесса делается попытка найти точку Х в соответствующем подмножестве, на которой реализуется его верхняя граница. Если попытка не удается, то ветвление продолжают, рассматривая каждый раз наиболее перспективное подмножество (для его выбора сравнивают оценки вершин дерева, из которых нет выходов).

Если попытка найти Х: f(X) = _k удалась, то это будет оптимальный план для всего исходного множества G (поскольку для остальных подмножеств верхние границы заведомо меньше).

При решении задачи на минимум схема та же, но рассматриваются вершины с наименьшей оценкой.

Этот метод всегда сходится, если мы имеем дело с ограниченной дискретной областью.

Чтобы конкретизировать метод ветвей и границ, необходимо установить:

1) алгоритм поиска границ ;

2) алгоритм разбиения множества на части;

3) алгоритм поиска Х, реализующего границу ;

4) сходимость метода.