Этапы МВГ

1. Строятся вершины первого уровня. Для каждой вершины вычисляется оценка . Ветвится вершина, которой соответствует максимальная оценка.

2. Для вершин уровня k (k=2,3,…) вычисляется оценка . Ветвится та из висячих вершин уровня k, k-1,…,1, которой соответствует максимальная оценка.

3. Действия этапа 2 повторяются до тех пор, пока не будет получено точное решение на последнем уровне n. Итоговая вершина отвечает решению Х^*=(х₁^*, х₂^*, …,х_n^*). Для него вычисляют значение целевой функции z(X^*).

4. Если значение z(X^*) не хуже оценок оставшихся висячих вершин, т.е. z(X^*)≥, то найдено оптимальное решение, причем если:

- z(X^*)>, то оптимальное решение единственно;

- для висячих вершин, в которых z(X^*)=, производится ветвление и осуществляется поиск других оптимальных решений задачи в соответствии с этапами 2 и 3.

Если значение z(X^*) для вершин последнего уровня не лучше значения оценок оставшихся висячих вершин, т.е. z(X^*)<, то переходят к этапу 2.

Для задачи на нахождение минимума вместо верхней границы нужно рассматривать нижнюю (z(X)≥) и отсекать ветви при z(X^*)≤.

Дата добавления: 2014-01-15