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

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

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

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 ^ٰдоп).

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

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

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

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

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

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

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

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

Этот метод применяется для решения задач коммивояжера и по назначению.

Задача коммивояжера:

Пусть задана матрица С=|| C_ij || расстояний между городами. Если от некоторой строки i или некоторого столбца j вычесть минимальный из них, то получим матрицу, у которой в каждой строке и в каждом столбце будет хотя бы один нулевой элемент. Такая матрица называется приведенной, а процесс получения нулей – приведением. Сумма вычитаемых в процессе приведения элементов называется приводящей const обозначается h^k, где к – порядковый номер приведения.

Для описания процедуры ветвления используем геометрическую интерпретацию метода. Разбиение множества всех циклов на не пересекаемые подмножества будет изображать дерево с вершинами, состоящими из пар допустимых(i,j) и запрещенных (i,j) городов.

Пара (i,j) содержит все маршруты, которые позволяют переход из города i в j(i,j) – все маршруты, запрещающие переход

из города i в j. Пара (к,l) – содержит все маршруты, в которых разрешен переход не только с к в l, но из i в j.

Обозначим вершину, из которой осуществляется ветвление, k,l k,lчерез х. Вершину, которая наиболее вероятно принадлежит

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

границу w(x). Процесс ветвления опишем следующим образом: процесс выбора пары городов для ветвления как игру 2-х лиц.

Игрок y имеет преимущество: он может выбирать любую еще не выбранную пару городов для ветвления. Стремясь построить цикл минимальной длины, он должен из исходной матрицы выбрать те пары городов, которым соответствуют минимальные элементы(в приведенной матрице это нулевые элементы).

Поскольку каждая строка и столбец приведенной матрицы содержат хотя бы один нулевой элемент, то претендентов на ветвление на 1-м шаге для множества y будет не меньше, чем n.

Неоднозначность выбора пары затрудняет процесс игрока y. Поэтому для выбора однозначной стратегии он накладывает ограничивающие факторы для игрока y: если y для объезда выбирает пару городов (i,j), то y должен выехать из любого города, но не в j и въехать в любой город, но не из i. Y ÷ (i,j).

Игрок y будет стремиться выбрать такой допустимый переезд, чтобы суммарный путь был минимальным. Поэтому в строке i приведенной матрицы он выбирает тот город (исключая j), которому соответствует минимальное расстояние. А в столбце j – город (исключая i), которому соответствует минимальный элемент.

Зная о стратегии y, игрок y выбирает из всех допустимых пар городов ту пару, у которой будет наибольшее расстояние.