|
|
|
содержание .. 25 26 27 28 ..
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
перповерхность
ограничений
и
т
.
д
.
Другими
сло
-
вами
,
поиск
заключается
в
выполнении
пар
ша
-
гов
,
каждая
пара
включает
спуск
на
гиперповерх
-
ность
ограничений
и
движение
вдоль
гиперпо
-
верхности
ограничений
.
Идею
метода
легко
пояснить
для
случая
по
-
иска
в
двумерном
пространстве
при
одном
огра
-
ничении
ψ
(
X
) = 0.
На
рис
. 4.
11
это
ограничение
представлено
жирной
линией
,
а
целевая
функция
—
совокупностью
более
тонких
линий
равного
уровня
.
Спуск
обычно
осуществляют
по
нормали
к
гиперповерхности
ограничений
(
в
данном
слу
-
чае
к
линии
ограничения
).
Условие
окончания
поиска
основано
на
сопоставлении
значений
це
-
левой
функции
в
двух
последовательных
точках
,
получаемых
после
спуска
на
гиперповерхность
ограничений
.
Рассмотрим
вопрос
,
касающийся
получения
аналитических
выражений
для
направлений
спуска
и
движения
вдоль
гиперповерхности
ограничений
.
:07+%
.
Необходимо
из
текущей
точки
поиска
(
попасть
в
точку
C
,
являющуюся
ближайшей
к
(
точкой
на
гиперповерхности
ограничений
,
т
.
е
.
решить
задачу
min |
B-A
|
при
условии
ψ
(
X
)=0,
которое
после
линеаризации
в
окрестностях
точки
(
имеет
вид
ψ
(
B
) + (
grad
ψ
(
B
))
T
(
A-B
) = 0.
Используя
метод
множителей
Лагранжа
,
обозначая
C
-
(
=U
и
учитывая
,
что
минимизация
рассто
-
яния
равнозначна
минимизации
скалярного
произведения
U
на
U
,
запишем
Ф
(
C
) =
U
T
U
+
λ
(
ψ
(
B
)+(
grad
ψ
(
B
))
T
U
);
∂
Ф
/
∂
C
= 2
U
+
λ
(
grad
ψ
(
B
)) = 0;
(4.2
1
)
∂
Ф
/
∂λ
=
ψ
(
B
) + (
grad
ψ
(
B
))
T
U
= 0.
(4.22)
Тогда
из
(4.2
1
)
получаем
выражение
U
= - 0,5
λ
(
grad
ψ
(
B
)),
подставляя
его
в
(4.22),
имеем
ψ
(
B
) - 0,5
λ
(
grad
ψ
(
B
))
T
grad
ψ
(
B
)= 0;
откуда
λ
= (0,5(
grad
ψ
(
B
))
T
grad
ψ
(
B
))
-
1
ψ
(
B
).
и
окончательно
,
подставляя
λ
в
(4.2
1
),
находим
U
= -
grad
ψ
(
B
)(
grad
ψ
(
B
))
T
grad
ψ
(
B
))
-
1
ψ
(
B
).
N(’@$*’$
(-#45
8’0$"0#($",*#+&’
#8")*’1$*’;
.
Шаг
в
гиперплоскости
D
,
касательной
к
гипер
-
поверхности
ограничений
,
следует
сделать
в
направлении
вектора
S
,
на
котором
целевая
функция
уменьшается
в
наибольшей
мере
при
заданном
шаге
h
.
Уменьшение
целевой
функции
при
переходе
из
точки
C
в
новую
точку
*
подсчитывают
,
используя
формулу
линеаризации
F
(
X
)
в
окрестностях
точки
C
:
F
(
C
) -
F
(
A
) =
h
(
grad
F
(
A
))
T
S
,
где
grad
F
(
A
)
T
S
—
приращение
F
(
X
),
которое
нужно
минимизировать
,
варьируя
направления
S
min
F
(
C
) =
min
((
grad
F
(
A
))
T
S
),
(4.23)
где
вариация
S
осуществляется
в
пределах
гиперплоскости
D
;
grad
ψ
(
A
)
и
S
—
ортогональные
векто
-
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
107
%+,
. 4.
))
.
Траектория
поиска
в
соответствии
с
методом
проекции
градиента
:
Q
-
условный
экстремум
;
0,
)
, 2, 3
-
точки
на
траектории
поиска
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
ры
.
Следовательно
,
минимизацию
(4.23)
необходимо
выполнять
при
ограничениях
(
grad
ψ
(
A
))
T
S
= 0,
S
T
S
=
1
.
Последнее
ограничение
говорит
о
том
,
что
при
поиске
направления
движения
,
вектор
S
должен
лишь
указывать
это
направление
,
т
.
е
.
его
длина
несущественна
(
пусть
S
—
единичный
вектор
).
Для
решения
(4.23)
используем
метод
множителей
Лагранжа
Ф
(
S
,
λ
,
q
) = (
grad
F
(
A
))
T
S
+
λ
(
grad
ψ
(
A
))
T
S
+
q
(
S
T
S
-
1
),
где
λ
и
q —
множители
Лагранжа
;
∂
Ф
/
∂
S
=
grad
F
(
A
) +
λ
grad
ψ
(
A
) +
q
S
= 0;
(4.24)
∂
Ф
/
∂λ
= (
grad
ψ
(
A
))
T
S
= 0;
(4.25)
∂
Ф
/
∂
q
=
S
T
S
-
1
= 0.
(4.26)
Из
(4.24)
следует
,
что
S
= -(
grad
F
(
A
) +
λ
grad
ψ
(
A
) )/
q
;
подставляя
S
в
(4.25),
получаем
(
grad
ψ
(
A
))
T
grad
F
(
A
) +
λ
(
grad
ψ
(
A
))
T
grad
ψ
(
A
) = 0,
откуда
λ
= - [(
grad
ψ
(
A
))
T
grad
ψ
(
A
)]
-
1
(
grad
ψ
(
A
))
T
grad
F
(
A
),
S
=
= - {
grad
F
(
A
)-
grad
ψ
(
A
)[(
grad
ψ
(
A
))
T
grad
ψ
(
A
)]
-
1
(
grad
ψ
(
A
))
T
grad
F
(
A
)} /
q
=
= - {
E - grad
ψ
(
A
)[(
grad
ψ
(
A
))
T
grad
ψ
(
A
)]
-
1
(
grad
ψ
(
A
))
T
}
grad
F
(
A
) /
q
.
(4.27)
Таким
образом
,
матрица
%
=
E - grad
ψ
(
A
)[(
grad
ψ
(
A
))
T
grad
ψ
(
A
)]
-
1
grad
ψ
(
A
))
T
представляет
собой
проектирующую
матрицу
,
а
вектор
S
,
рассчитанный
по
(4.27), —
проекцию
гра
-
диента
grad
F
(
A
)
на
гиперповерхность
ограничений
.
Частным
случаем
применения
метода
проекции
градиента
являются
задачи
оптимизации
с
мак
-
симинным
критерием
.
Действительно
,
для
поиска
экстремума
функции
минимума
max min
Z
j
(
X
),
X
j
где
Z
j —
нормированная
величина
j-
го
выходного
параметра
y
j
,
удобно
применять
метод
проекции
гради
-
ента
.
В
качестве
ограничений
задачи
в
исходной
постановке
фигурируют
только
прямые
ограничения
,
max
i
>
x
i
>
x
min
i
.
Здесь
,
max
i
и
x
min
i
—
граничные
значения
допустимого
диапазона
варьирования
параметра
,
i
.
В
процес
-
се
поиска
,
если
минимальной
является
функция
Z
q
(
X
)
и
траектория
поиска
пересекает
гребень
Z
q
(
X
) -
Z
k
(
X
) = 0,
(4.28)
то
поиск
продолжается
в
направлении
проекции
градиента
функции
Z
q
(
X
)
на
гиперповерхность
греб
-
ня
(4.28).
4.3.
"4,-:0497:
?:5:A
,-8<7-<804@4
,+0-.?:
"84=.
5<81
,+0-.?:
384.7-016
8.I.0+2
.
Принятие
проектных
решений
охватывает
широкий
круг
задач
и
процедур
—
от
выбора
вариантов
в
конечных
и
обозримых
множествах
до
задач
творче
-
ского
характера
,
не
имеющих
формальных
способов
решения
.
Соответственно
в
САПР
применяют
как
средства
формального
синтеза
проектных
решений
,
вы
-
полняемого
в
автоматическом
режиме
,
так
и
вспомогательные
средства
,
способствующие
выполне
-
нию
синтеза
проектных
решений
в
интерактивном
режиме
.
К
вспомогательным
средствам
относятся
базы
типовых
проектных
решений
,
системы
обучения
проектированию
,
программно
-
методические
комплексы
верификации
проектных
решений
,
унифицированные
языки
описания
ТЗ
и
результатов
проектирования
.
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
108
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
Задачи
синтеза
структур
проектируемых
объектов
относятся
к
наиболее
трудно
формализуемым
.
Существует
ряд
общих
подходов
к
постановке
этих
задач
,
однако
практическая
реализация
большин
-
ства
из
них
неочевидна
.
Поэтому
имеются
лишь
“
островки
”
автоматического
выполнения
процедур
синтеза
среди
“
моря
”
проблем
,
ждущих
автоматизации
.
Именно
по
этой
причине
структурный
синтез
,
как
правило
,
выполняют
в
интерактивном
режиме
при
решающей
роли
инженера
-
разработчика
,
а
ЭВМ
играет
вспомогательную
роль
:
предоставление
необходимых
справочных
данных
,
фиксация
и
оценка
промежуточных
и
окончательных
результатов
.
Однако
в
ряде
приложений
имеются
и
примеры
успешной
автоматизации
структурного
синтеза
в
ряде
приложений
;
среди
них
заслуживают
упоминания
в
первую
очередь
задачи
конструкторского
проектирования
печатных
плат
и
кристаллов
БИС
,
логического
синтеза
комбинационных
схем
циф
-
ровой
автоматики
и
вычислительной
техники
,
синтеза
технологических
процессов
и
управляющих
программ
для
механообработки
в
машиностроении
и
некоторые
другие
.
Структурный
синтез
заключается
в
преобразовании
описаний
проектируемого
объекта
:
исход
-
ное
описание
содержит
информацию
о
требованиях
к
свойствам
объекта
,
об
условиях
его
функцио
-
нирования
,
ограничениях
на
элементный
состав
и
т
.
п
.,
а
результирующее
описание
должно
содержать
сведения
о
+&"7%&7"$
,
т
.
е
.
о
составе
элементов
и
способах
их
соединения
и
взаимодействия
.
Постановки
и
методы
решения
задач
структурного
синтеза
в
связи
с
трудностями
формализации
не
достигли
степени
обобщения
и
детализации
,
свойственной
математическому
обеспечению
проце
-
дур
анализа
.
Достигнутая
степень
обобщения
выражается
в
установлении
типичной
последователь
-
ности
действий
и
используемых
видов
описаний
при
их
преобразованиях
в
САПР
.
Исходное
описа
-
ние
,
как
правило
,
представляет
собой
ТЗ
на
проектирование
,
по
нему
составляют
описание
на
неко
-
тором
|