Исследование эффективности алгоритма компоновки схем радиоэлектронных средств
Последовательный метод компоновки конструктивных элементов и узлов РЭС. Особенности алгоритмизации и программирования конструктивных элементов на ПЭВМ. Построение математических моделей объектов конструирования, решение задачи компоновки в САПР.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 20.03.2015 |
| Размер файла | 986,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Ульяновский государственный технический университет
Кафедра «Проектирования и технологии электронных средств»
Лабораторная работа
ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА КОМПОНОВКИ СХЕМ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ
Студент гр. Шермонов В.В.
Преподаватель: Мактас М.Я.
Ульяновск 2014
Введение
Цель работы - исследовать эффективность последовательного метода компоновки конструктивных элементов и узлов РЭС в узлы высшего уровня; усвоить особенности алгоритмизации и программирования задачи компоновки конструктивных элементов на ПЭВМ; приобрести навыки построения математических моделей объектов конструирования, реализации и исследования их при решении задачи компоновки в САПР.
1. Общие сведения о задаче компоновки
В настоящее время в радиоэлектронике принят функционально-узловой метод проектирования [1 - 7]. Он предусматривает расчленение радиоэлектронных средств (РЭС) на отдельные конструктивно законченные единицы (модули) различных уровней (рангов). Это могут быть отдельные платы - типовые элементы замены (ТЭЗы), функциональные узлы, субблоки, блоки, панели, пульты, стойки. В связи с этим при разработке конструкций РЭС проектировщик неизбежно сталкивается с задачей распределения элементов схемы низшего уровня по коммутационным пространствам модулей данного уровня иерархии. При ее решении основным критерием оптимальности компоновки модулей является минимизация числа межмодульных связей, что необходимо для повышения надежности схем (за счет уменьшения числа разъемных соединений), уменьшения влияния наводок и времени задержки сигнала в цепях (вследствие минимизации суммарной длины соединений), упрощения конструкции и повышения технологичности разрабатываемого устройства.
Последовательные алгоритмы компоновки
Суть последовательных алгоритмов заключается в том, что вначале по определенному признаку выбирают вершину или группу вершин, к которым затем присоединяют другие вершины графа для образования первого куска. Процесс повторяют до получения заданного разбиения.
Метод максимальной конъюнкции - минимальной дизъюнкции
Основной критерий разбиения графа на куски - минимум числа соединяющих ребер между кусками графа. Если формировать куски графа G так, чтобы каждый из кусков во множестве содержал возможно большее число ребер, то при этом получится локальный минимум суммарного числа K соединяющих ребер.
Рассмотрим метод максимальной конъюнкции - минимальной дизъюнкции [1, 4].
Пусть дана схема с множеством элементов
,
соединенных между собой множеством электрических цепей
.
Ее необходимо скомпоновать в узлы, включающие по t элементов. Число внешних связей узлов не должно превышать z (z - число контактов в разъеме).
Работа начинается с формирования 1го узла. Первым выбирается элемент, подключенный к наибольшему числу цепей. Далее последовательно оцениваются по двум параметрам возможности назначения в формируемый узел оставшихся элементов.
Вначале отбирается множество элементов, назначение каждого из которых в формируемый узел не превышает предельно допустимого числа z внешних связей узла. Затем из полученного множества элементов выбираются такие, которые имеют с назначенными в формируемый узел элементами наибольшее число общих цепей.
При работе алгоритма схема представляется в виде графа Кенига , в котором подмножество вершин E и V интерпретируют соответственно множества элементов E и электрических цепей V. При этом вершина соединяется с вершиной ребром в том случае, когда элемент принадлежит цепи . Для вычисления на ЭВМ граф задается матрицей инцидентности , в которой число строк n определяется количеством элементов схемы, а столбцов m - количеством электрических цепей. Элемент , стоящий на пересечении iй строки и jго столбца, равен 1, если элемент подключен к цепи , и нулю в противном случае.
АЛГОРИТМ
1. Ввод матрицы .
2. По матрице определяем локальные степени вершин :
.
3. Из множества нераспределенных вершин E выбираем вершину с локальной степенью
.
4. Назначаем выбранную вершину во множество , формируемого узла.
5. Строку матрицы , соответствующую назначенной вершине , модифицируем путем поразрядной дизъюнкции со строками матрицы, соответствующими нераспределенным элементам:
; ;…
6. Определяем суммы элементов в модифицированных строках
.
7. Из множества строк выбираем такие, в которых . Объединяем их во множество .
8. Если , то переходим к 17, иначе к 9.
9. Строку матрицы , соответствующую элементу , модифицируем путем поразрядной конъюнкции со строками множества :
;…
10. Определяем суммы элементов в модифицированных строках .
11. Из множества строк выбираем такую, в которой .
12. Вершину , дающую назначаем в формируемый узел .
13. Если , то идти к 17, иначе к 14.
14. Определяем множество нераспределенных элементов . Если , то идти к 19, иначе к 15.
15. Составляем матрицу . Для чего в исходной матрице вместо строк, соответствующих элементам, назначенным в узел , записываем дизъюнкцию всех указанных строк.
16. Идти к 5.
17. Узел считаем сформированным. Поэтому преобразуем матрицу . Исключаем из нее строки, соответствующие элементам, включенным в узел . Получаем матрицу .
18. Идти к 2.
19. Конец.
Рисунок 1. Схема Электрическая Принципиальная.
Рисунок 1.1. Матрица инцидентности.
Практические решения:
Пусть дана схема соединений (рис. 1), которую необходимо скомпоновать в узлы, содержащие не более четырех элементов , и каждый узел имеет не более пяти выводов z?5.
Ручной рассчет
Решение
По матрице исходного графа определяем локальные степени вершин и приписываем их справа к каждой строке матрицы (число цепей, подключенных к каждому элементу схемы):
Q1=
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|||||
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
6 |
1 |
|
|
2 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
7 |
0 |
|
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
2 |
5 |
1 |
|
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
2 |
6 |
0 |
|
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
0 |
||
|
6 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
3 |
6 |
0 |
|
|
7 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
3 |
7 |
0 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
5 |
0 |
|
|
9 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
6 |
0 |
|
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
3 |
6 |
0 |
|
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
6 |
0 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
2 |
6 |
0 |
Максимальную локальную степень, равную четырем, имеет вершина е5,. В качестве исходной выбираем 5ю по порядку е5. Выполним дизъюнкции 5й строки q5, соответствующей е5, с остальными строками:
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
5 v 1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
Сумма элементов в дизъюнкции c(q51)= 6
Находим суммы элементов в дизъюнкциях:
c(q51)= 5, c(q52)= 7 ,c(q53)=5 ,
c(q54)= 6 ,c(q56)= 6, c(q57)= 7, c(q58)= 5 ,c(q59)= 6, c(q510)= 6, c(q511)= 6, с(q512)=6 .
Выбираем вершины, имеющие , и включение которых в формируемый узел не превысит условия z?5. Такими являются вершины е3 и е8. Выполним конъюнкцию 5й строки со строками отобранных элементов е3, е8.
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
5 ? 3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
Сумма элементов в коньюнкции S(b53) = 1
Вычисляем суммы элементов в конъюнкциях S(b58)=0.
Выбираем вершину е3, величина S(b53)=1 у которой максимальна и минимальное число выводов z=4 и включаем ее в узел T1={e5,e3}.
Поскольку по условию в узел необходимо включить четыре элемента, то переходим к подбору следующей вершины.
Для этого модифицируем матрицу .
Вместо 5й и 3й строк в ней запишем дизъюнкцию этих строк.
Получим матрицу Q2:
Q2=
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
||||
|
5 v 3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|||
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
|
|
2 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
0 |
|
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
7 |
0 |
|
|
6 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
7 |
1 |
|
|
7 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
7 |
1 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
|
|
9 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
1 |
|
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
7 |
1 |
|
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
7 |
1 |
Снова вычисляем дизъюнкции строки (5 v 3) со всеми остальными и определяем суммы элементов в них.
|
5 v 3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
(5 v 3)v 1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q(53)k)=6 имеют e2=8,e8,е9=6, e1,е4,e6,e7,e10,e11,e12=7. После выполнения конъюнкции строки (5 v 3) со строками отобранных элементов е8, е9.
|
5 v 3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
(5 v 3) ? 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Справа от матрицы запишем . Максимальное значение =1 имеют вершины e9
Вершину e9 включаем в узел : T1={e3,e5,e9}.
Поскольку по условию в узел необходимо включить четыре элемента, то переходим к подбору следующей вершины.
Для этого модифицируем матрицу .
Вместо 9й , 5й и 3й строк в ней запишем дизъюнкцию этих строк.
Q3=
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
||||
|
(5 v 3)v 9 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|||
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
9 |
0 |
|
|
2 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
10 |
0 |
|
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
9 |
0 |
|
|
6 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
9 |
1 |
|
|
7 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
9 |
1 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
1 |
|
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
9 |
1 |
|
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
8 |
1 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
9 |
0 |
Минимальную c(q(8)k)=7 имеет остальные по 9. e2=10, e11=8. После выполнения конъюнкции строки (5 v 3) v 9 с остальными строками и суммирования элементов в результирующих строках получим:
Максимальное значение S(b(539)k)=1
Ее и включаем в узел : T1={e3,e5,е6,e9}.
Итак, узел сформирован, поскольку в него назначено четыре элемента.
Аналогично формируем второй узел , рассматривая оставшиеся вершины. Ef = E/T1={e1,e2,e4,e7,e8,e10,e11,e12} Для этого из исходной матрицы исключаем строки, соответствующие элементам e3,e5,e6,e9.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|||||
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
4 |
1 |
|
|
2 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
5 |
||
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
2 |
5 |
0 |
|
|
7 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
3 |
6 |
0 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
4 |
0 |
|
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
3 |
5 |
1 |
|
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
5 |
0 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
2 |
5 |
0 |
Получим: Q4 =
Максимальную локальную степень, равную трем, имеют вершины e2, e9, e10. В качестве исходной выбираем 2ю по порядку e2.
Выполним дизъюнкции 2й строки q2, соответствующей e2, с остальными строками:
Находим суммы элементов в дизъюнкциях: c(q21)=4, c(q24)=5, c(q27)=6, c(q28)=4, c(10)=5, c(q11)=5, c(q12)=5.
|
2 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
2 v 1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Выбираем вершины, имеющие , и включение которых в формируемый узел не превысит условия z?4. Такой является вершина e1, e8 у которой c(qjk)?4.
Выполним конъюнкцию 2й строки со строками отобранных элементов e1,e8:
|
2 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
2 ? 1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Вычисляем суммы элементов в конъюнкциях S(b21)=1, S(b28)=0. Выбираем вершину e1, величина S(b21)=1 у которой максимальна, и включаем ее в узел T2={e2,e1}.
Поскольку по условию в узел необходимо включить четыре элемента, то переходим к подбору следующей вершины.
Для этого модифицируем матрицу .
Вместо 1й и 2й строк в ней запишем дизъюнкцию этих строк.
Получим матрицу Q5:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
||||
|
2 v 1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
6 |
0 |
|
|
7 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
6 |
1 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
|
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
6 |
1 |
|
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
6 |
0 |
Снова вычисляем дизъюнкции строки 2 v 1 со всеми остальными и определяем суммы элементов в них.
|
2 v 1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
(2v1)v4 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q(8)k)=5 имеет e8. После выполнения конъюнкции строки 2 v 1 с остальными строками и суммирования элементов в результирующих строках получим:
|
2 ? 1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
(2v1)?4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Справа от матрицы запишем . Максимальное значение S(b(7)k)=1, S(b(10))=1 имеют вершины e7, e10. е7 включаем в узел : T2={е2,e1,e7}.
Поскольку по условию в узел необходимо включить четыре элемента, то переходим к подбору следующей вершины.
Для этого модифицируем матрицу .
Вместо 1й , 2й и 7й строк в ней запишем дизъюнкцию этих строк.
Q6=
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
||||
|
(2v1)v7 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|||
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
8 |
0 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
|
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
8 |
1 |
|
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
8 |
0 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
8 |
0 |
Минимальную c(q(217)k)=7 имеют e8. После выполнения конъюнкции строки (2v1)v7 с остальными строками и суммирования элементов в результирующих строках получим:
Максимальное значение S(b(127)10)=1,
Ее и включаем в узел : T2={e2,e1,e7,e10}.
Итак, узел сформирован, поскольку в него назначено четыре элемента.
Аналогично формируем второй узел , рассматривая оставшиеся вершины. Ef = E/T2={е4,e8,e11,e12} Для этого из исходной матрицы исключаем строки, соответствующие элементам. Получим:
Q7 =
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|||||
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
2 |
|||
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
3 |
0 |
|
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
1 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
2 |
3 |
1 |
Максимальную локальную степень, равную двум, имеют все вершины, кроме e8 . В качестве исходной выбираем 1ю по порядку e4. Выполним дизъюнкции 1й строки q4, соответствующей e4, с остальными строками:
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
4v8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
Находим суммы элементов в дизъюнкциях: c(q48)=3, c(q411)=3, c(q412)=3,
Выбираем вершины, имеющие , и включение которых в формируемый узел не превысит условия z?5. Такими являются вершины e8, e11 и e12 , у которых 3.
Выполним конъюнкцию 1й строки со строками отобранных элементов q8,q11,q12, :
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
4 ?8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Вычисляем суммы элементов в конъюнкциях. S(b48)=0, S(b411)=1, S(b412)=1. Выбираем вершину e11, величина S(b411)=1 у которой максимальна, и включаем ее в узел. T2={e4,e11} .
Поскольку по условию в узел необходимо включить четыре элемента, то переходим к подбору следующей вершины.
Для этого модифицируем матрицу .
Вместо 4й и 11й строк в ней запишем дизъюнкцию этих строк.
Получим матрицу Q8:
Q8=
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
||||
|
4v11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|||
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
|
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
4 |
1 |
Снова вычисляем дизъюнкции строки (4v11) со всеми остальными и определяем суммы элементов в них. Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q(4118)k)=4 имеют e8, e12. После выполнения конъюнкции строки (4v11) с остальными строками и суммирования элементов в результирующих строках получим:
|
4v11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
(4v11)v8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q(4118)k)=4 имеют e8, e12. После выполнения конъюнкции строки (4v11) с остальными строками и суммирования элементов в результирующих строках получим:
Справа от матрицы запишем . Максимальное значение S(b7811)=1 имеет вершина e8, e12. Ее и включаем в узел : T2={e4,e11,e8} .
Поскольку по условию в узел необходимо включить четыре элемента, то переходим к подбору следующей вершины.
Для этого модифицируем матрицу .
Вместо 4й , 8й и 11й строк в ней запишем дизъюнкцию этих строк.
Q9=
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
||||
|
(4v11)v8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|||
|
12 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
6 |
1 |
Справа от матрицыQ9 запишем .
Результаты суммирований запишем справа от каждой строки матрицы Q9. Минимальную c(q(4118k)=6 имеют е12 Максимальное значение S(b4118)=1 имеет вершина е12. Ее и включаем в узел : T3={e4,e8,e11,e12} .
Условия задачи выполнены. Схема скомпонована в узлы по четыре элемента и число внешних соединений каждого не превышает восьми.
Граф схемы, разрезанный на три куска, приведён на рис. 2.1, а схема, скомпонованная в три блока - на рис. 2.2. Качество компоновки оценим по коэффициенту разбиения G схемы.
Общее число цепей между блоками K=, число цепей внутри блоков L=
Тогда коэффициент разбиения схемы
Машинная компоновка
Рисунок 3.1.Результаты машинной компоновки.
программирование алгоритмизация математический рэс
Рисунок 3.2.(Эскиз) Расшифровка результатов машинной компоновки.
Качество компоновки оценим по коэффициенту разбиения G схемы.
Общее число цепей между блоками K=5, число цепей внутри блоков L=10.
Тогда коэффициент разбиения схемы G= 5/10 = 0,5.
Вывод
В ходе лабораторной работы я исследовал эффективность последовательного метода компоновки конструктивных элементов и узлов РЭС в узлы высшего уровня; усвоил особенности алгоритмизации и программирования задачи компоновки конструктивных элементов на ПЭВМ; приобрел навыки построения математических моделей объектов конструирования, реализации и исследования их при решении задачи компоновки в САПР
Достоинствами последовательных алгоритмов компоновки по связанности являются их простота реализации на ЭВМ и высокое быстродействие. Кроме этого, они позволяют легко учитывать дополнительные ограничения на компоновку: несовместимость отдельных элементов в узле, априорно заданное функциональное распределение некоторых элементов схемы и др.
Недостатком этих алгоритмов является локальный пошаговый характер оптимизации.
Поэтому эффективность таких алгоритмов выше при компоновке узлов с небольшим отношением числа элементов к числу выводов также результат будет лучше для схем с относительно невысокой связанностью .Элементы были скомпонованы в 3 узла, по 4 модуля(микросхем) в каждом.
Коэффициент разбиения схемы в ручной компоновке получился равным G= так же как и в машинной G=0,5.
Размещено на Allbest.ru
Подобные документы
Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
курсовая работа [195,5 K], добавлен 08.11.2009Методы решения задачи оптимального резервирования технической системы. Решение задачи методами неопределенных множителей Лагранжа и динамического программирования. Построение оптимальной схемы системы при нагруженном резервировании ее элементов.
лабораторная работа [31,5 K], добавлен 10.06.2009Виды алгоритмов как логико-математических средств, характеристика свойств. Корректный вывод алгоритма при решении вычислительной задачи. Механизм реализации алгоритма, его описание. Решение задачи Майхилла при помощи автоматной модели поведения стрелка.
курсовая работа [53,6 K], добавлен 17.07.2014Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Формулировка, спецификация и математическая постановка задачи. Описание схемы алгоритма. Рассмотрение результата машинного тестирования программы. Получение на занятиях навыков алгоритмизации и программирования задач на языке высокого уровня C#.
курсовая работа [268,2 K], добавлен 22.03.2015Решение задачи на составление компромиссного списка. Построение математической модели. Цена перемещения элементов. Вывод программы. Закреплении элемента а1 на первом месте, а а4 на пятом. Матрица оценок для задачи. Оптимальное решение в виде списка.
курсовая работа [37,5 K], добавлен 30.01.2016Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Разработка простейших линейных алгоритмов (составление логических выражений), программ с ветвлениями, циклических программ и составление их блок-схем. Практическое выполнение обработки массивов на примере вычисления элементов квадратной матрицы.
контрольная работа [173,3 K], добавлен 01.03.2010Генератор для входных параметров логических элементов. Ключевые понятия и принципы конструирования функциональных схем электронных устройств. Схемы некоторых устройств компьютера. Творческая мастерская Excel-графики, вентильные сказки братьев Гейтс.
методичка [2,1 M], добавлен 16.03.2014Проблема разработки математической модели сложной задачи. Построение алгоритма составления расписания занятий. Вероятность обнаружения хорошего варианта за ограниченное время. Множество всех множеств допустимых пар, поиск элементов, прогноз тупика.
реферат [42,1 K], добавлен 29.01.2010
