1 Ветвление

Предполагается, что существует правило , которое сопоставляет любому множествуконечное количество множествтаких, что множество множествявляется разбитием множества(разбитие множества– множество множеств, которые взаимно не пересекаются и в сумме дают). Разбитие множествабудем обозначать так:

.

Относительно правила разбитие множествав идеальном случае предполагается:

а) если мощность множества , тогда;

б) если , тогда множество не может быть разбито на подмножества, то есть в этом случае .

Множества, которые встречаются в процессе ветвления множества , можно упо­рядочить по ветвлениям и эту связь можно изобразить в виде дерева подмножеств решений (– множество вершин,– множество дуг). Корень дерева соответствует множеству , а листья - одноэлементным множествам. Условие а) гарантирует, что любой путь от корня к листу содержит не более ребер.

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

бинарное ветвление;

ветвление по компонентам.

1.1 Бинарное ветвление

Связано с разбитием множества решений по некоторому признаку на два подмножества, которые не пересекаются:ии при этом. Дерево ветвлениядля этого способа имеет вид, показанный на рисунке 1.1 Такие деревья называютсябинарными.

Рисунок 1.1 – Бинарное ветвление

1.2 Ветвление по компонентам

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

Для этого способа ветвления дерево имеет вид, показанный на рисунке 1.2.

Рисунок 1.2 – Ветвление по компонентам

2 Оценка

В методе ветвей и границ для каждого из подмножеств множества допустимых решений определяется оценка (нижняя граница) значений целевой функции. Оценка является функциейи в идеальном случае имеет следующие свойства:

1) (в задаче на максимум имеем знак “”);

2) , если і;

3) , если(в случае задачи на максимум).

Для вычисления оценки может быть решена некоторая оптимизационная задача простой структуры:

(3)

что является оценочной для задачи:

(4)

От оценочной задачи требуется выполнение следующих условий:

1) если оценочная задача (3) не имеет допустимых решений, тогда и задача (4) не имеет допустимых решений;

2) значение целевой функции решения задачи (3) не хуже, чем значение целевой функции решения задачи (4).

3 Рекорд

При решении оценочных задач могут быть найдены допустимые решения задачи (4), а значит и задачи (1)-(2). Наилучшее значение целевой функции задачи (1)-(2), которое достигается на множестве найденных допустимых решений, называется рекордом, а соответственно допустимое решение называется рекордным.

Если к текущему шагу допустимые решения задачи (1)-(2) не найдены, тогда рекорд считается равным . Далее текущее значение рекорда будем обозначать.

4 Тест

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

Тест. Если для некоторого множества справедливо, чтотогда мно­жествоисключается из дальнейшего рассмотрения.

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

Для конкретных задач удается строить и другие эмпирические тесты, которые основываются на необходимых условиях оптимальности или любых других положениях.