Инструменты пользователя

Инструменты сайта


examination:mo:question12

Вопрос 12. Методы ветвей и границ. Общая характеристика. Разбиение на подмножества, стратегии ветвления, «оценивание» и правила отбраковки подмножеств.

Суть метода ветвей и границ - в направленном частичном переборе допустимых решений.

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

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

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

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

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

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

Перенесен в следующий вопрос

examination/mo/question12.txt · Последние изменения: 2014/01/15 08:19 (внешнее изменение)