Дискретная оптимизация - 3 стр.

                                       3
                     МЕТОД ВЕТВЕЙ И ГРАНИЦ

                         §1. Общая схема метода

Рассмотрим задачу дискретной оптимизации вида
                          ϕ( x) → min ,                                     (1)
                                    x∈Ω
где Ω - некоторое конечное множество из R n .
Для решения данного класса задач часто используется метод ветвей и границ,
в основе которого лежат следующие основные модули:
1) построение дерева допустимых вариантов;
2) составление оценочных задач;
3) определение правила обхода дерева вариантов;
4) отбрасывание “неперспективных” множеств вариантов;
5) проверка критерия останова.
Рассмотрим подробно каждый из указанных модулей.
1) Построение дерева вариантов осуществляется на основе разбиения множеств
   на конечное число непересекающихся подмножеств. Факт разбиения множе-
   ства называется ветвлением и производится на очередном шаге метода в со-
   ответствии со сформулированным заранее правилом. Это правило связано со
   спецификой конкретного допустимого множества исследуемой задачи. Од-
   нако если исходная задача среди прочих               имеет ограничения вида
    x j ∈{1,0}, j =1, n (т.е. является задачей с булевыми переменными), то можно
   воспользоваться универсальным правилом ветвления: Ω =Ω 1 ∪ Ω 2 , где
    Ω 1 ={x ∈Ω : xi =1}; Ω 2 ={x ∈Ω : xi =0}; i - зафиксированный номер коор-
   динаты 1 ≤i ≤n . Порядок фиксирования координат оговаривается в правиле
   ветвления. Отметим, что правило разбиения множества на подмножества в
   конкретной задаче может быть не единственным.
2) Оценкой функции ϕ (x) задачи (1) на множестве Ω называется такое число
    ξ =ξ (Ω) , что ϕ ( x) ≥ξ , ∀x ∈Ω . Для получения оценок составляется оценоч-
   ная задача, решение которой используется для вычисления соответствующей
   оценки. К оценочным задачам предъявляются следующие требования: с од-
   ной стороны, их решение не должно занимать много времени. Но вместе с
   тем оценки, полученные с их помощью должны быть как можно точнее (т.е.
   разность ξ (Ω) −min ϕ( x) не должна быть слишком большой). Такие требо-
                     Ω
  вания объясняются тем, что именно оценки используются при отбрасывании
  неперспективных множеств (следовательно, при сокращении перебора). При
  составлении оценочных задач можно воспользоваться универсальным пра-
  вилом: отбросить в исходной задаче наиболее “тяжелые” (трудновыполни-
  мые) ограничения (например, требование целочисленности). Получаемые
  оценки должны обладать монотонностью в том смысле, что оценки под-
  множеств не должны быть меньше оценки разветвленного множества (то
  есть если Ω =Υ Ω k , то должно быть выполнено условие ξ (Ω) ≤ξ (Ω k )∀k .
                 k