Постановка задачи компоновки

Задача компоновки конструктивных узлов сводится к оптимальному разбиению T₁,…, T _γ множества элементов схемы Х={х₁, х₂,…, х_n} при заданных ограничениях. Ограничения, как правило, налагаются на число элементов k _s и число внешних цепей (выводов) q _s для отдельных узлов разбиения: k _s ≤ k и q _s ≤ q (s=1,…,γ). В качестве критериев оптимальности принимается минимум количества соединений между узлами, минимум суммарного числа внешних выводов и др.

Связность схемы соединений (S) - суммарное число элементарных соединений (цепи с размером 2).

• При описании схемы ГЭК (матрицей Q) для элементного комплекса v_j размером ρ _j дерево соединений содержит ρ _j–1 элементарных соединений, связность схемы равна:

(5.2.1)

m m

S=∑(ρ΄ _j – 1 ) =∑ ρ΄ _j -m,

j =1 j =1

где m– число комплексов (цепей) в схеме.

• При описании схемы ВГС (матрицей R)

(5.2.2)

n n n n

S=½ ∑ ∑ r_ij =∑ ∑ r_ij,

i=1 j=1 i=1 j>i

Когда все цепи имеют размер 2, значение S по этим формулам совпадают.

Результатом разбиения является γ+1 новых схем соединений: γ схем внутриузловых соединений и одна схема межузловых соединений. Схемы внутриузловых соединений задают соединения элементов для узлов T _s (s=1,…,γ).

По аналогии с (2.1) связность схемы межузловых соединений равна

˜

˜

˜

m m γ

(5.2.3)

S=∑(ρ _j – 1 ) =∑ ρ _j –F= ∑ m_s – m,

j =1 j =1 s =1

˜

где F– число межузловых цепей;

ρ _j- размер цепи для схемы межузловых соединений,

m_s- количество цепей, соединенных с элементами узла T_s.

Граф межузловых соединений получается из графа элементных комплексов схемы с помощью следующего преобразования:

- подмножество вершин T_s Ì C заменяется одной вершиной t_s (s=1,…,γ).;

- все ребра, инцидентные вершинам из T_s, считаются инцидентными вершине t_s;

- петли на вершинах t_s (внутренние цепи узлов) устраняются.

Узлы разбиения T₁, T₂, T₃ Удаленные цепи v₁ и v₆

Рис.5. 2.1 Граф элементных комплексов схемы Рис. 5.2.2 Граф межузловых соединений

(граф схемы соединений)

	~

~

Граф межузловых соединений может быть описан матрицей комплексов (Q), строки – узлы t_s, столбцы - межузловые цепи v_j.