Формальная постановка комбинаторно-оптимизационной задачи структурного синтеза на графах. Рассмотреть пример для задачи поиска остовного дерева минимальной длины

Алгоритмизация решения задачи требует её формальной постановки. В общем виде формальная постановка (математическая модель) комбинаторно-оптимизационной задачи имеет вид:

Найти

при

Здесь X – вектор выходных переменных, задающий конечное множество допустимых решений. Для задач структурного синтеза – это множество возможных вариантов структуры;

x – допустимое решение, одно из значений вектора выходных переменных;

x* – оптимальное решение; f – целевая функция задачи оптимизации;

f(x*) – оптимальное значение целевой функции;

- вектор управляемых (варьируемых) параметров, конкретные значения которых определяют один из вариантов структуры объекта, значение целевой функции и показателей, включенных в ограничения;

- вектор неуправляемых переменных;

- граничные значения варьируемого параметра; - ограничение.

Конкретизация общей постановки для различных проектных задач структурного синтеза требует определения состава векторов X, Y, Z и выбора ЦФ или её конструирования.

В приведённой постановке подразумевается, что множество допустимых решений X может быть задано либо получено, следовательно, при формализации задач структурного синтеза в первую очередь необходимо решить задачу определения множества допустимых вариантов структуры.

Для задач структурного синтеза X – это формальное описание допустимого множества вариантов структуры объекта на рассматриваемом уровне детализации.

Основные проблемы при формализации прикладных задач структурного синтеза – это:

1. Получение математической модели объекта и результата проектирования;

2. Конструирование ЦФ и формирование ограничений.

Рассмотрим построение математической модели для электрической цепи, соединяющей штыревые выводы микросхем отрезками проводников. Моделью цепи будет обыкновенный неориентированный граф. Поскольку цепь не должна быть замкнута, то этот граф – дерево (то есть, не имеющий циклов). Ребра этого дерева должны соединять все вершины графа, поэтому дерево является остовным (или покрывающим граф). Таким образом, моделью цепи является взвешенное остновное дерево. Множеству ребер сопоставим множество длин отрезков проводников, а множеству вершин – веса: , M – координаты вершины, K_доп – допустимое количество проводников (зависит от способа монтажа). Так как на n вершинах можно построить остовных дерева, то моделью всех вариантов структуры цепи будет граф , состоящий из t компонент связности, , где - цикломатическое число, равное 0 при отсутствии циклов в графе.

В данном случае критерий – минимальная длина цепи, поэтому ЦФ примет вид:

Итак, формализованная задача поиска остовного дерева минимальной длины примет вид:

Найти при

Решение (поиск) осуществляется перебором.

 

 

Требования, предъявляемые к математическим моделям объектов проектирования для задач структурного синтеза. Информация о схеме, которую необходимо отобразить в модели для решения задач структурного синтеза.

Объектами формализации являются схемы электрические функциональные и принципиальные, а также конструктивные модули или их компоненты (напри­мер, кристаллы матричных БИС или печатные платы многоплатного субблока).

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

• имена (номера) элементов схемы, их логические функции или типы;

• имена (номера) электрических цепей или типы сигналов, которые пе­редаются по ним;

• связанность элементов схемы с точностью до выводов с учетом направле­ния распространения сигнала и фактора неизвестности соединения в пределах
цепи;

• сведения об инвариантности и логических функциях выводов;

• метрические параметры элементов, т.е. их размеры, координаты и размеры полей их контактов;

• топологические характеристики элементов, обусловливающие ограниче­ния на построение соединений (геометрическая форма элементов и выводов, порядок следования выводов, возможность прохода соединений между ними и под элементами, вид линии связи…);

• вид линий связи и метрические параметры (допустимая ширина и длина
печатных и диаметры навесных проводников, размеры областей контактирования печатных линий связи, …);

• топологические свойства соединений (допустимая или рекомендованная
форма мест разветвления линий связи и мест их контактирования, возможные
углы поворота печатных проводников, ограничения на их взаимное рас­положение).

В математической модели монтажного пространства необходимо отразить следующую инфор­мацию:

• метрические параметры (габаритные размеры зоны монтажа, допустимые
расстояния между проводниками, координаты и размеры контактных площадок, …);

• топологические характеристики (форма монтажного пространства, наличие
и форма замкнутых областей, запрещенных для проведения соединений).

Требования, предъявляемые к математической модели, определяются ее наз­начением.

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

• высокая степень формализации отображаемого объекта;

• наличие математического аппарата, позволяющего выполнять формальные
преобразования модели;

• отображение в модели только той информации об объекте, которая является существенной для решения данного класса задач.

• корректность правил перехода - соответствие отношений между компонентами объекта отношениям между элементами математической модели, сопоставленным компонентам объекта.

• однозначность и простота перехода от модели к объекту.

• адекватность и помехоустойчивость модели, т.к. при получении, обработке и хранении данных, представляющих модель, возможны потеря и искажение информации.

При наличии полной информации об объекте эти требования обеспечи­ваются правилами перехода от объекта к модели и обратно и способом представ­ления модели.