Метод оптимизации для решения поставленной задачи

Наиболее часто встречающийся, распространенный метод для решения такого типа задач - метод ветвей и границ.

.3.1 Общее описание метода ветвей и границ

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

, , - дискретно

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

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

Примеры деревьев:

Начальной вершине 0 соответствует исходное допустимое множество или исходная задача (1), а любой другой вершине - подмножество , полученное в результате ветвления, или подзадача :

, .

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

Процесс ветвления из данной вершины не производится, если выполнено одно из условий:

. Граница найдена точно: , т.е. получено решение подзадачи . Будем говорить, что в этом случае вместо оценки решения в вершине найдено полное решение , соответствующее этой вершине.

. Множество является пустым.

. Из полученных до этого полных решений найдется такое , что граница удовлетворяет неравенству

.

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