Автоматизированное проектирование. Норенков И.П. - 114 стр.

 5@!"! 4                            %!#*%!#&F*:,$*    $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

     Задача ДМП определяется следующим образом:
         extr F(N),
         X∈D                                                                             (4.30)
         D = { X | W(X) > 0, Z(X) = 0 },
где F(X) — целевая функция; W(X), Z (X) — вектор-функции, связанные с представленными в ТЗ тре-
бованиями и ограничениями; D — дискретное множество. В полученной модели, во-первых, каждый
элемент множества рассматриваемых законченных структур должен иметь уникальное сочетание зна-
чений некоторого множества числовых параметров, вектор которых обозначим X. Во-вторых, необхо-
димо существование одной или нескольких функций J(X), значения которых могут служить исчер-
пывающей оценкой соответствия структуры предъявляемым требованиям. В-третьих, функции J(X)
должны отражать внутренне присущие данному классу объектов свойства, что обеспечит возмож-
ность использования J(X) в качестве не только средств оценки достигнутого при поиске успеха, но и
средств указания перспективных направлений продолжения поиска. Эти условия выполнимы далеко
не всегда, что и обусловливает трудности формализации задач структурного синтеза.
      Однако наличие формулировки (4.30) еще не означает, что удастся подобрать метод (алгоритм)
решения задачи (4.30) с приемлемыми затратами вычислительных ресурсов. Другими словами, при-
менение точных методов математического программирования вызывает непреодолимые трудности в
большинстве случаев практических задач типичного размера из-за их принадлежности к классу NP-
трудных задач. Поэтому лидирующее положение среди методов решения задачи (4.30) занимают при-
ближенные методы, в частности, декомпозиционные методы, отражающие принципы блочно-иерар-
хического проектирования сложных объектов. Декомпозиционные методы основаны на выделении
ряда иерархических уровней, на каждом из которых решаются задачи приемлемого размера.
      Основу большой группы математических методов, выражающих стремление к сокращению пе-
ребора, составляют операции разделения множества вариантов на подмножества и отсечения непер-
спективных подмножеств. Эти методы объединяются под названием /$&#-) ($&($; ' 8")*'=. Основ-
ная разновидность метода ветвей и границ относится к точным методам решения комбинаторных за-
дач. Рассмотрим эту разновидность.
      Пусть имеется множество решений M, в котором нужно выбрать оптимальный по критерию
F(Xj) вариант, где Xj — вектор параметров варианта mj ∈ M; пусть также имеется алгоритм для вы-
числения нижней границы L(Mk) критерия F(Xj) в любом подмножестве Mk множества M, т.е. такого
значения L(Mk), что F(Xj) ≥ L(Mk) при любом j (подразумевается минимизация F(X)). Тогда основная
схема решения задач в соответствии с методом ветвей и границ содержит следующие процедуры: 1)
в качестве Mk принимаем все множество M; 2) ветвление: разбиение Mk на несколько подмножеств
Mq; 3) вычисление нижних границ L(Mq) в подмножествах Mq; 4) выбор в качестве Mk подмножества
Mp с минимальным значением нижней границы критерия (среди всех подмножеств, имеющихся на
данном этапе вычислений), сведения об остальных подмножествах Mq и их нижних границах сохра-
няются в отдельном списке; 5) если | Mk| > 1, то переход к процедуре 2, иначе одноэлементное множе-
ство Mk есть решение.
      Метод ветвей и границ в случае точного вычисления нижних границ относится к точным мето-
дам решения задач выбора и потому в неблагоприятных ситуациях может приводить к экспоненциаль-
ной временной сложности. Однако метод часто используют как приближенный, поскольку можно
применять приближенные алгоритмы вычисления нижних границ.
      Среди других приближенных методов решения задачи ДМП отметим /$&#- 4#%)45*#; #0&'/'-
6)=''. Так как пространство D метризовано, то можно использовать понятие )-окрестности Sa(Xk) те-
кущей точки поиска Xk. Вместо перебора точек во всем пространстве D осуществляется перебор то-
чек только в Sa(Xk). Если F(Xj) ≥ F(Xk) для всех Nj ∈ Sa(Xk), то считается, что найден локальный ми-
нимум целевой функции в точке Xk. В противном случае точку Xq, в которой достигается минимум
F(X) в Sa(Xk), принимают в качестве новой текущей точки поиска.


 &.+.)$(*),$" . !"#$%!#&'&($"!))$*         +($*,#&($"!)&*                                   114