Метод ветвей и границ

Сущность метода заключается в направленном ветвлении области возможных решений оптимизационной задачи с целью локализации оптимального решения в одной из подобластей. При решении каждой задачи этим методом к ней должны быть применены следующие 2 процедуры:

1.Ветвление множества допустимых решений.

2.Определение нижних и верхних границ целевой функции.

Формирование нижних и верхних оценок целевой функции

Общепринятым считается применение данного метода для задачи в которой направление оптимизации приведено к виду минимизации целевой функции.

Поэтому рассмотрим задачу следующего вида:

Min f(x)

x є D

В этой формуле х-вектор допустимых оптимизационных переменных , среди которых часть переменных действительные числа и часть - целочисленные переменные.

Нижней оценки целевой функции в зависимости от выбранного способа ветвления могут определятся либо для подобластей Di є D либо для подобластей Di є Dٰ , где Di и Dٰ получены из соответствующих множеств Di и D путем снятия условия целочисленности на переменные.

Нижней оценкой целевой функции f(x) на некотором множестве Di или Diٰ будем называть величину Σi=min Σij , где Σij – значение целевой функции f(x) на множестве Di для решений подзадачи j .

Если при решении подзадачи установлено , Di – пустое множество , то нижнюю оценку принимают равной бесконечности.

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

Для большинства задач вычисляют только одно значение верхней оценки на множестве Di. ŋ (Di).

Ее определяют как значение целевой функции для найденного допустимого_лучшего решения исходной задачи.

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

На начальном этапе решения задачи значение верхней оценки обычно принимают равной бесконечности ŋ (Di) = ∞ .

При нахождении первого допустимого решения , которое пренадлежит множеству D, xдоп є D, рассчитывают верхнюю оценку на множестве D , как значение целевой функции от найденного допустимого решения - ŋ (D) = f(xдоп).

Затем при определении лучшего допустимого решения x ٰдоп (f(x ٰдоп )< f(xдоп)) ,

ŋ (D)= f(x ٰдоп ).

Значение верхней оценки в процессе решения задачи может только уменьшаться.