close

Вход

Забыли?

вход по аккаунту

?

Отчёт 3 [kto](1)

код для вставкиСкачать
Федеральное агентство по образованию
Государственное Образовательное Учреждение Высшего Профессионального Образования
Тверской Государственный Технический Университет
Кафедра Электронных Вычислительных Машин
Лабораторная работа №3
по дисциплине: Конструкторско-Технологическое Обеспечение
Размещения элементов схемы в монтажной области последовательным алгоритмом
Выполнил: Селянкин В.О., ВМКСС - 0603
Проверил: Лебедев В.В.
Тверь, 2009
Задание
Изучить размещение элементов схемы в монтажном пространстве последовательным алгоритмом.
Схема
Результаты
Размещение в монтажном пространстве
Графическое представление лесом
Ответы на контрольные вопросы
Постановка задачи размещения. Критерии оптимизации
Задача размещения заключается в определении оптимального (в соответствии с некоторым критерием) положения элементов и связей между ними в монтажном пространстве типовой конструкции.
При этом общая постановка задачи разбивается на две подзадачи:
Размещение конструктивных элементов
Трассировка связей между ними.
Исходные данные для задачи размещения: схема соединений элементов (элементы и цепи по задействованным выводам), метрические и топологические параметры монтажного пространства.
Задачу размещения можно сформулировать следующим образом: Имеется множество конструктивных элементов E={ei / i=1, N} и множество соединяющих их цепей Q={qk / k=1, K}. Монтажное пространство определено множеством фиксированных позиций для установки элементов T={tj / j=1, M}, причем M≥N. Необходимо найти такое отображение множества Е на множество Т, при котором достигается экстремум некоторой целевой функции F.
Главная цель размещения - создание наилучших условий для трассировки. На практике используются следующие критерии оптимизации размещения: минимум суммарной длины всех соединений;
минимум длины самой длинной связи; минимум числа пересечений связей; максимум числа цепей с возможно более простой конфигурацией;
максимально близкое расположение модулей, имеющих наибольшее количество связей между собой. Перечислите группы алгоритмов размещения
Все алгоритмы размещения можно свести в следующие основные группы: Алгоритмы решения задач математического программирования, сходные по постановке задач задаче размещения.
Последовательные алгоритмы.
Итерационные алгоритмы.
Алгоритмы, использующие непрерывно-дискретные методы оптимизации.
Приведите и объясните формулу для нахождения суммарной взвешенной длины соединений
Для некоторого размещения суммарная взвешенная длина соединений
,
где di,j - элемент матрицы Dr, определяет расстояние между позициями установки конструктивных элементов ei и ej;
d_(i,j)= √(|S_i- S_j |^2+|t_i-t_j |^2 ) или d_(i,j)= |S_i- S_j |+|t_i-t_j |,
где Si, ti, Sj, tj - координаты i, j - вершин графа;
,
где - число цепей, в которые входят одновременно элементы ei и ej. - вес q-й связи; - количество элементов, соединяемых q-й цепью;
mi - номер вертикального ряда, в котором расположен элемент ei.
Внешним выводам сопоставим элемент е0. Соединения с ним элементов из множества Е учтем вектором столбцом взвешенных связей H={hi / I=1, N}. Монтажная область внешних выводов обычно фиксирована на периферии типовой конструкции, т.е. расположение контактных площадок задано. Контактные площадки, кроме выводов питания и земли, - инвариантны. Поэтому расстояние от элемента еi до внешних выводов можно приближенно определять как расстояние от вертикального (горизонтального) ряда, в котором установлен этот элемент, до контактной группы.
Далее задача сводится в минимизации L(a) на множестве размещений А. Это один из вариантов задачи квадратичного назначения, Алгоритмы, реализующие решение этой задачи, можно использовать на практике при N = 15÷20.
Документ
Категория
Рефераты
Просмотров
63
Размер файла
104 Кб
Теги
kto, отчет
1/--страниц
Пожаловаться на содержимое документа