САПР в задачах конструкторского проектирования. Тюрин И.В. - 15 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Как составить матрицу цепей?
2.
Что представляет собой каждый элемент матрицы цепей?
3.
Как заполняется вспомогательная матрица?
4.
Как выполняются операции дизъюнкции и инверсии?
Лабораторная работа 6
Решение задачи размещения последовательно-итерационным алгоритмом
Цель работы. Ознакомиться с последовательно-итерационным алгоритмом и решить задачу размещения радиоэлек-
тронных элементов в монтажном пространстве с минимальной суммарной длиной соединений.
Исходные данные. Схема электрическая принципиальная, представленная мультиграфом G (V, R) с числом вершин n.
Требуется изучить постановку задачи размещения элементов схемы и последовательно-итерационный алгоритм реше-
ния задачи; получить вариант задания, решить задачу размещения элементов схемы в монтажном пространстве
Т коммута-
ционной платы с числом посадочных мест
m = n последовательно-итерационным алгоритмом по минимуму суммарной дли-
ны соединений.
Методические указания по выполнению работы
В качестве исходных данных для решения задачи размещения рассматривается схема соединения элементов, заданная в
виде графа
G (V, R), где V = {v
1
, …, v
n
} – множество конструкционных элементов, R = {r
1
, …, r
p
} – множество связей между
ними и множество установочных (посадочных) мест на коммутационной плате
T = {t
1
, …, t
m
}, причем T ≥ V.
Требуется так разместить вершины
V в посадочных местах T, чтобы минимизировать выбранный критерий оптимально-
сти. Критерием может служить, в частности, минимум суммарной длины соединений, минимум внутрисхемных линий, ми-
нимум соединений, длина которых превышает заданную величину и др. Наиболее часто в задачах размещения минимизиру-
ется суммарная длина соединений
∑
=
=
=
m
j
i
ijij
SlQ
1
,1
2
1
, (1)
где
l
ij
– расстояние между i-м и j-м установочными местами, в которых расположены соответствующие конструктивные эле-
менты;
S
ij
– число кратных связей между элементами.
При размещении элементов на плоскости коммутационной платы расстояние приближенно определяется в виде
jijiij
yyxxl −+−= , (2)
или более точно, с использованием формулы
(
)
(
)
22
jijiij
yyxxl −+−=
. (3)
Последовательно-итерационный алгоритм размещения состоит из двух этапов. На первом этапе (последовательная
часть) последовательно заполняются установочные места элементами с учетом числа связей между ними. Этап заканчивает-
ся, когда все элементы размещены. На втором этапе (итерационная часть) производится перестановка элементов с целью
минимизации выбранного критерия оптимальности.
Множества конструктивных элементов
V и множества связей между ними R графа G (V, R) задаются матрицей смежности
nn
ij
sS
×
= , где n = V. Монтажное пространство задается множеством установочных мест T в виде матрицы длин L или спи-
ска координат позиций. Расстояния между установочными местами определяются по формуле (2) или (3). Некоторые эле-
менты могут быть закреплены за отдельными позициями.
На последовательном этапе размещение производится с использованием коэффициента связности
K (v
i
) элемента v
i
с
ранее размещенными элементами, определяемого по формуле
(
)
(
)
(
)
(
)
()
(
)
i
Jj
ijiiiii
vSvVvVvVvvK ρ2ρρ2 ρρ
разм
размостразм
∑
∈
−=−⊂=⊂−⊂=
, (4)
где
()
∑
∈
=⊂ρ
разм
разм
Jj
iji
SVv – число связей элемента
i
v с подмножеством размещенных вершин V
разм
; ρ (v
i
⊂ V
ост
) – число свя-
зей элемента
i
v с подмножеством оставшихся вершин V
ост
; J
разм
– множество номеров размещенных элементов; ρ (v
i
) – сте-
пень вершины
v
i
.
Целью этапа является получение первоначального размещения элементов в поле монтажного пространства, которое
рассматривается как первое приближение итерационной части алгоритма. Заполнение монтажного пространства осуществ-
ляется в следующем порядке. Вначале размещаются закрепленные за соответствующими установочными местами элементы,
затем в свободную позицию размещается один (первый) конструктивный элемент, а далее производится размещение элемен-
тов с максимальными значениями коэффициента связности в очередных свободных позициях монтажного пространства. В
результате такого последовательного размещения элементов формируется массив пар
},1 ,,1 ),,{(
_______
mknitv
ki
==
, для которого
рассчитывают значение критерия по формуле (1).

Страницы