Пример. Решить методом внешней точки следующую задачу.
min F(x , x |
2 |
) x2 |
2x2 |
при |
x |
x |
2 |
1 0 |
||||
|
1 |
|
1 |
2 |
|
|
|
1 |
|
|
||
В качестве метода безусловной оптимизации |
||||||||||||
будем |
|
|
|
|
|
|
|
|
|
|
|
|
использовать классический метод. |
|
1)2 |
|
|
||||||||
H (x |
, x |
,r) |
x2 2x2 r(x |
x |
|
|
|
|||||
1 |
2 |
|
|
1 |
2 |
1 |
2 |
|
|
|
|
|
H
x
1H
x2
2x1 2r(x1 x2 1) 0
4x2 2r(x1 x2 1) 0
x1=2x2
x2 2 r3r
lim |
x2 |
1 |
x1=2/3 |
r |
|
3 |
|
Лекция 21. Формальное описание коммутационных схем. Методы и алгоритмы решения задачи компоновки.
Математическая модель монтажно-коммутационного пространства.
Электрическую схему интерпретируют ненаправленным мультиграфом, в котором каждому i-му конструктивному элементу (модулю) ставят в соответствие вершину мультиграфа хi, а электрическим связям схемы — его ребра uij
Требуется «разрезать» граф G(X, U) на отдельные куски Gi(Xi, Ui) так, чтобы число ребер, соединяющих эти куски,
было минимальным
k |
k |
|
|
k |
min Uij ; |
i j |
при |
Gi (X i ,Ui ) G(X ,U ) |
|
i 1 |
j 1 |
|
|
i 1 |
Последовательный алгоритм распределения конструктивных элементов
Пример. Произвести разрезание графа на части по 3 вершины в каждой части с помощью последовательного
алгоритма компоновки (используя критерий относительного веса min bij(xi)= (хi)- aij.
Строим матрицу связности.
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
0 |
3 |
2 |
1 |
0 |
6 |
2 |
0 |
0 |
0 |
1 |
4 |
0 |
5 |
3 |
3 |
0 |
0 |
0 |
1 |
0 |
4 |
4 |
2 |
1 |
0 |
0 |
0 |
1 |
4 |
5 |
1 |
4 |
1 |
0 |
0 |
2 |
8 |
6 |
0 |
0 |
0 |
1 |
2 |
0 |
3 |
Вычисляем вершину с самой большой максимальной
степенью. Это вершина 5.
Подбор кандидатов на присоединение в единый кусок производим по формуле: bij(xi)= (хi)- aij, где aij -число связей i-той вершины с j-ой
b51=8 -1=7; b52=8 -4=4; b53=8 -1=7; b56=8 -2=6
Следовательно, объединяем 5 и 2 в один кусок
|
1 |
3 |
4 |
52 |
6 |
1 |
0 |
3 |
2 |
1 |
0 |
3 |
3 |
0 |
0 |
1 |
0 |
4 |
2 |
0 |
0 |
1 |
1 |
52 |
1 |
1 |
1 |
0 |
2 |
6 |
0 |
0 |
1 |
2 |
0 |
b521=5 -1= 4; b523=5 -1=4; b524=5 -1=4; b526=5 -2=3.
В один кусок с 5 и 2 объединяем вершину 6
Лекция 22. Постановка задачи размещения
конструктивных модулей на плате. Классификация алгоритмов размещения.
Параметры коммутационного поля
0 |
|
X |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Y |
|
х х х х х х |
х х х х х х |
|
|
||||
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
х х х х х х |
х х х х х х |
|
|
|
|
||
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
х х х х х х |
х х х х х х |
|
х х х х х |
х |
х х х х х х |
. . . . . . . . . . .
х х х х х х х х
Размещение элементов
Расстояние между соединяемыми элементами (выводами i и j) можно определить одним из следующих способов:
dij(1) (xi x j )2 |
(yi y j )2 |
, |
dij(2) | xi x j | | yi y j | , |
|
|
dij(3) | xi x j |S |
| yi y j |S . |
|
Задано множество конструктивных элементов R={r1,r2,…,rn} и множество связей между этими элементами V={v1,v2,…,vp},
а также множество установочных мест (позиций) на коммутационной плате T={t1,t2,…,tk}. Найти такое
отображение множества R на множестве T, которое обеспечивает экстремум целевой функции
n |
n |
N |
min F cij dij |
cij fij(k ) / sk |
|
i 1 |
j 1 |
k 1 |
f (k )
где ij – вес k-ой цепи, связывающей элементы i и j; sk – число контактов, объединенных цепью;
N – число цепей схемы между i и j элементами.
Если необходимо, то можно учесть рассредоточение элементов с точки зрения тепловой или электромагнитной совместимости следующим образом
cij |
|
c|ij |
|
|
|
|
Ei E j |
|
|
1 |
|
|
||
|
Eдоп |
|
||
|
|
|
|
|
Здесь с/ij – весовой коэффициент, рассчитанный по
предыдущему выражению, - коэффициент теплоотдачи в реальной конструкции или коэффициент, учитывающий электромагнитную совместимость, Ei и Ej – мощности,
рассеиваемые в компонентах i и j либо уровни напряженности электромагнитного поля, Eдоп –
допустимый уровень мощности или напряженности двух рядом размещенных элементов.