ЛАБОРАТОРНАЯ РАБОТА №2
ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА КОМПОНОВКИ
СХЕМ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ
Цель работы – исследовать эффективность последовательного метода компоновки конструктивных элементов и узлов РЭС в узлы высшего уровня; усвоить особенности алгоритмизации и программирования задачи компоновки конструктивных элементов на ПЭВМ; приобрести навыки построения математических моделей объектов конструирования, реализации и исследования их при решении задачи компоновки в САПР.
ОБЩИЕ СВЕДЕНИЯ О ЗАДАЧЕ КОМПОНОВКИ
В настоящее время в радиоэлектронике принят функционально-узловой метод проектирования [1 – 7]. Он предусматривает расчленение радиоэлек-тронных средств (РЭС) на отдельные конструктивно законченные единицы (модули) различных уровней (рангов). Это могут быть отдельные платы – ти-повые элементы замены (ТЭЗы), функциональные узлы, субблоки, блоки, па-нели, пульты, стойки. В связи с этим при разработке конструкций РЭС проек-тировщик неизбежно сталкивается с задачей распределения элементов схемы низшего уровня по коммутационным пространствам модулей данного уровня иерархии. При ее решении основным критерием оптимальности компоновки модулей является минимизация числа межмодульных связей, что необходимо для повышения надежности схем (за счет уменьшения числа разъемных соеди-нений), уменьшения влияния наводок и времени задержки сигнала в цепях (вследствие минимизации суммарной длины соединений), упрощения кон-струкции и повышения технологичности разрабатываемого устройства.
Математическая формулировка задачи
Для алгоритмизации и формального решения задачи компоновки РЭС производится переход от электрической схемы соединений РЭС к мультиграфу. При этом каждому конструктивному элементу (модулю) ставят в соответствии вершину мультиграфа, а электрическим связям схемы – его ребра. В этом случае задача компоновки формулируется следующим образом [2 – 5].
Дан мультиграф 
. Требуется разбить («разрезать») его на отдельные куски 
, 
,…, 
так, чтобы число ребер, соединяющих эти куски, было минимальным. Это значит надо минимизировать функцию:
, где 
(2.1)
При разбиении графа на куски 
, 
задаются следующие ограничения:
, (2.2)
, (2.3)
, (2.4)
; 
, (2.5)
где Uij – множество ребер, соединяющих куски 
и 
.
Другими словами, совокупность кусков разбиения графа 
является разбиением графа G, если любой кусок из этой совокупности не пустой
, (2.6)
и для любых двух кусков 
пересечение множества вершин – пустое множе-ство (2.3), а пересечение множества ребер (2.4) может быть не пустым. Кроме этого объединение всех кусков (2.5) должно в точности равняться графу G.
В выражении (2.4) множество 
определяет подмножество ребер 
, попадающих в разрез (сечение) между кусками 
и 
графа G.
Конструктивными ограничениями в задачах компоновки являются:
а) максимально допустимое количество вершин t в куске
; (2.7)
б) число кусков разрезания графа
, (2.8)
где l – количество вершин в исходном графе;
в) максимальное число внешних связей каждого отдельного куска графа
. (2.9)
Физический смысл ограничений (2.2) – (2.9) следующий.
Условия (2.2) – (2.4) означают, что не может быть двух узлов, содержащих один и тот же элемент, вместе с тем электрические цепи, соединяющие отдельные узлы существуют.
Условие (2.5) – суммарное число элементов, входящих в отдельные узлы, равно количеству элементов, входящих в электрическую схему всего устройства.
Условие (2.6) – не может быть узла, в котором не содержится ни одного элемента.
Условие (2.7) – соответствует числу конструктивных элементов, которые необходимо разместить в коммутационном пространстве, (2.8) – требуемое число узлов, в которые требуется скомпоновать конструктивные элементы устройства, (2.9) – определяет количество контактов используемого разъема.
Для оценки качества компоновки схемы в узлы, что соответствует оценке качества разбиения на куски, введем понятие коэффициента разбиения 
. Для этого допустим, что граф G разбит на k кусков: 
. Тогда множество ребер U графа G можно представить в виде
. (2.10)
Каждое подмножество 
запишем следующим образом:
,
(2.11)
……………………………
,
где – подмножество всех ребер, инцидентных вершинам 
куска ; 
– подмножество ребер, соединяющих подмножество вершин куска между собой; (или 
) – подмножество ребер, соединяющих куски и .
Тогда отношение суммарного числа внутренних ребер (ребер подмножеств ) к суммарному числу соединительных ребер (ребер подмножеств ) назовем коэффициентом разбиения графа G:
. (2.12)
Коэффициент разбиения позволяет оценивать качество разбиения графа на куски, а также сравнивать различные алгоритмы разбиения графов. Очевидно, что лучшим разбиениям для одного и того же графа соответствуют наибольшие значения .
Существует значительное количество алгоритмов компоновки, которые мо-жно условно разбить на пять групп: 1) последовательные алгоритмы; 2) итера-ционные алгоритмы; 3) алгоритмы, использующие методы целочисленного программирования; 4) алгоритмы, основанные на решении задачи о назначе-нии; 5) смешанные алгоритмы.
