3.3.1 Описание метода ветвей и границ

Пусть х¹ – центр куба Х. Вычисляем   и присваиваем это значение рекорду  . Разбиваем куб Х ¹ⁱ со стороной ½ и вычисляем значения целевой функции в их центрах:  , i= 1,… 2ⁿ, обновляя по ходу вычислений значение рекорда  . Проверяем выполнение условия  для i=1,…, 2ⁿ и отбрасываем соответствующие подкубы. Каждый из оставшихся разбиваем на 2ⁿ одинаковых подкубов Х^2ij со стороной ¼ и поступаем как прежде. На любом шаге у нас формируется множество К «кубиков» со сторонами 2^-l, l>=2, целое. Правило выбора очередного кубика для разбиения называется правилом ветвления – возможные варианты приводятся ниже. Кубики со стороной не больше   исключаются из множества К – дробление кубика заканчивается. Также исключаются кубики, попавшие в множество   (с индексом k – номером кубика) для текущего значения рекорда, – правило отсечения ветвей. Рекорд обновляется при получении меньшего значения целевой функции (правило получения границ, т.е. оценок). Значения целевой функции вычисляются в центре каждого нового подкубика, включаемого в К после разбиения выбранного для этого кубика. Алгоритм останавливается, когда К пусто.

Рис. 2. Граф-дерево

Указанная терминология и название метода определяются тем, что визуально данная схема перебора представляется в виде графа-дерева, корневая вершина которого соответствует кубу Х, вершины первого яруса – подкубам X^li, вершины второго яруса – кубикам X^2li, подсоединенным к своим порождающим вершинам X^li-го яруса, и т.д. (см. рис. 2). Если кубик исключается из К, его вершина закрывается – из нее не будут идти ветви на следующий ярус. Порядок закрытия вершины определяется правилом отсечения (своим для каждой массовой задачи), порядок раскрытия – правилом ветвления (своим для каждой индивидуальной задачи). Различают два вида правил ветвления по типу построения дерева решений (выбора вершин для раскрытия): «в ширину», когда сначала раскрываются все вершины одного яруса до перехода к следующему, и в «глубину» – всякий раз раскрывается лишь одна (обычно с лучшим значением рекорда) вершина на ярусе до конца ветви. На практике реализуют некоторую смесь, например, первое правило пока хватает машинной памяти (в К не слишком много элементов), затем переключаются на второе. Предпочтительность той или иной стратегии ветвления оценивается каждым вычислителем по-своему, исходя из главной задачи метода ветвей и границ – быстрее получить лучший рекорд, чтобы отсечь больше ветвей. Удачный выбор стратегии ветвления в МВГ (например, на основе имеющейся у вычислителя дополнительной информации или эвристических соображений об объекте) позволяет (хотя и не гарантированно) решать задачи большой размерности.

Отметим, что в худшем случае   – не удается отбросить ни одной точки х – и приходим к полному перебору; т.е. указанная экспоненциальная оценка точна на классе всех липшицевых функций.

4. Выбор объекта управления. Анализ аспектов его работы

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

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