Математическое обеспечение (МО) цифрового (автоматизированного) проектирования

К математическому обеспечению предъявляют требования:
1. Универсальность. МО применяют к широкому классу проектных объектов. При этом под универсальностью не понимается возможность описания одной математической моделью всех свойств объекта. Например функциональные модели, описывающие процессы, происходящие в объекте не отражают его структуру, геометрические свойства и наоборот. Степень универсальности не имеет количественной оценки, а только качественную.
2. Алгоритмическая надежность – свойство математического обеспечения давать правильные результаты при выполнении заданных ограничений на применение моделей или методов. Количественной оценкой алгоритмической надёжности служит вероятность получения правильных результатов при соблюдении оговоренных ограничений на применимость метода. Если вероятность равна единице или близка к ней, то говорят, что метод алгоритмически надёжен.
.

3. Точность – степень совпадения расчетных и истинных результатов. Математические методы могут быть алгоритмически надёжны, но давать различную точность. Если точность ниже предельно допустимой, либо модель вообще не даёт решения, тогда говорят об алгоритмической ненадёжности. Точность оценивается погрешностью:
Решение проектных задач характеризуется:
использованием многих компонент МО (модели, алгоритмы анализа и оптимизации), каждый из которых может вносить погрешности.
векторным характером результатов – вектор выходных параметров, координаты оптимальной точки.
Пусть имеем вектор выходных параметров Y=(y1, …, yi, yn). Тогда погрешность εi расчета параметра уi определяется как:

ɛi=(yim-yiист)/ yiист
yim – расчетное значение результатов
yi ист – истинное значение результатов
ɛ=( ɛ1,…, ɛi,…, ɛn)
Эту погрешность можно свести к скалярной в виде m- нормы:
ɛmax = max| ɛ1,…, ɛi,…, ɛn|
или в виде l- нормы
ɛср = √( ɛ12+,…, ɛi2+,…, ɛn2)
При разработке моделей надо помнить, что стремление к чрезмерной точности может привести к громоскости и трудно реализуемости модели.
4. Адекватность – это способность моделей отображать заданные свойства объекта с погрешностью не выше заданной

5. Экономичность – характеризуется затратами машинного времени и памяти. Затраты памяти определяют длиной программы и объемом исходных данных.
Уменьшить затраты времени и памяти можно рядом методов:
1) при использование разреженных матриц (т.е. матриц, содержащих большое количество нулевых элементов), сэкономить машинную память можно, если каким-то образом хранить в памяти ЭВМ только ненулевые элементы матрицы;
2) исследование сложных систем по частям. Производится расчленение математических моделей на части, которые исследуются самостоятельно;
3) рациональное использование эвристических возможностей человека. В меру своей интуиции и опыта человек может выбрать перспективное продолжение хода вычислений, не вычисляя все возможные варианты..

Математические модели объекта проектирования
В зависимости от отображаемых свойств объекта различают:
- структурные модели
- геометрические модели
- функциональные модели
Структурные модели
Структурные модели отражают взаимное расположение и наличие связей между элементами объекта проектирования. Наибольшее распространение в САПР находят структурные модели в виде графов. Достоинствами – графовых моделей являются простота и наглядность представления структуры объекта в виде графа, возможность постановки большого числа различных формальных задач на графах, простота представления графов в ЭВМ.

Граф – это множество вершин X= {x1, …, xi, …, xn} и множество ребер U= {u1, …, uj, …,um}, соединяющих вершины. Каждое ребро uj есть пара вида (хi,xj). Вершины связанные ребром, называются смежными. Наличие ребра между вершинами xi и xj означает наличие связи между элементами xi и xj (логическую, электрическую, механическую). Кроме связей важно бывает предоставить направление этой связи. Направление моделируется ребром со стрелкой – это ориентированный граф. Если есть несколько связей между вершинами, то это мультиграф.
Часто необходимо задать дополнительную информацию о ребрах или вершинах (например, расстояние). Эта дополнительная информация задается с помощью цифровых меток, которые присваиваются рёбрам или вершинам. Метки называются весами, а граф – называется взвешенним.

Для представления графа в ЭВМ удобно использовать специальные матрицы – смежности и инцидентности (Bn×m)
Матрица смежности А – квадратная размерности n с элементами aij определяемыми по следующему правилу:
aij=1, если вершины xi и xj связаны ребром
aij=0, - в противном случае
Матрица инцидентности В – прямоугольная матрица размерности nxm, элементы вik которой находятся по следующему правилу:
bij=1, если вершины xi и xj связаны ребром
bij=0, - в противном случае
Бинарный характер матриц А и В позволяет экономно записывать матрицы в память ЭВМ, отводя на каждый элемент по одному двоичному разряду машинного слова. Это дает возможность хранить и обрабатывать матрицы очень большой размерности.
Путем или маршрутом в графе называется последовательность смежных ребер вида ....( хi,xj), (хj,xk),( хk,xl).....Цепью называется маршрут, в которой нет повторяющихся ребер. Циклом называется замкнутая цепь. Граф, у которого нет циклов, называется ациклическим (деревом).

Геометрические модели
Это модели, которые с определённой точностью описывают геометрические свойства проектируемого объекта. Геометрические свойства – это пространственное отношение и формы (фигуры). В геометрии понятие пространство и фигуры определяется исходя из понятия множества. Пространство определяется как множество каких-либо элементов (точек), а фигура определяется как произвольное множество точек в данном пространстве.
В САПР используется математическое представление геометрической модели. Наука, которая занимается этим – инженерная (прикладная) геометрия. При геометрическом моделировании объект проектирования предстаёт как геометрический объект (ГО). Для любого геометрического объекта можно определить совокупность независимых условий, однозначно задающих этот объект, то есть позволяющие для любой точки пространства установить, принадлежит эта точка объекту или нет. Такую совокупность независимых условий называют определителем геометрического объекта.

В число условий входят геометрические фигуры (точки, линии, поверхности,) и определённая последовательность действий, посредством которых из этих геометрических фигур можно построить данный геометрический объект. Эта последовательность действий называется алгоритмом воспроизведения данного геометрического объекта.
Количественно геометрический объект характеризуется параметрами. При выделении параметров важно учитывать области их существования, например, для треугольника числа, выражающие длины сторон, всегда больше нуля и сумма двух чисел больше третьего числа.
Для описания геометрической фигуры необходимо выделить параметры двух типов – формы и положения. Параметры формы характеризуют размеры и форму геометрической фигуры, они не изменяются при изменении положения фигуры в пространстве; параметры положения характеризуют положение геометрической фигуры в пространстве. Параметризация формы производится в системе координат, которая связана с самой фигурой и перемещается вместе с ней. Параметризация положения фигуры производится в системе координат независимо от фигуры.

При описании геометрического объекта различают подмножества граничных точек – поверхность геометрического объекта; и подмножество внутренних точек – тело геометрического объекта.
Геометрические объекты бывают сложной формы и сложной структуры. Геометрические объекты сложной формы – это те, у которых поверхность сложного характера (например, корпус судна, автомобиля). Геометрические объекты сложной структуры – состоящие из нескольких ГО.
В автоматизированном проектировании известны два основных подхода к геометрическому модулированию:
Первый подход состоит в том, что выделяется некоторый набор геометрических фигур, которые в данном классе задач считаются элементарными (базовыми). Наряду с геометрическим набором вводится набор действий – геометрических операций над этим набором. Геометрический объект в этом случае называется составным (конструктивным).

Второй подход непосредственное описание и воспроизведение геометрических свойств объекта без использования вспомогательных, заранее заготовленных фиксированных фигур. В этом случае непосредственно описывается закон образования геометрического объекта как множество точек, обладающих соответствующими свойствами.
Подход, основанный на «прямом» моделировании геометрического объекта, в зависимости от способа формирования можно разделить на кусочно-аналитические и алгебро-логические модели объекта.
В кусочно-аналитических моделях поверхность объекта представляется отдельными кусками гладких поверхностей, называемыми гранями. Каждая грань задаётся своим уравнением поверхности и границами грани. Рёбра геометрического объекта или границы грани есть линии пересечения поверхностей, ограничивающие геометрический объект. Точки пересечения рёбер называются вершинами.
Существует три вида моделей: стержневая, оболочная и объемная.

Стержневая модель геометрического объекта позволяет весьма просто дать форму изображения проектируемого объекта путём построения проволочно-каркасной модели геометрического объекта. В такой модели описываются только рёбра и вершины геометрического объекта, грани не описываются (рис.1а).Ребра представлены в виде стержней, соединенных в узлах (вершинах 1,2,3....). Основными уравнениями для описания такой модели являются уравнения прямой линии в трехмерном пространстве. Такая модель является подмоделью, но она позволяет оперативно осуществлять вывод изображения геометрического объекта, а также выполнять такие операции, как построение аксонометрических и перспективных проекций.
Математическое описание моделей такого рода сравнительно простое, что обуславливает высокое быстродействие программного обеспечение. К недостаткам таких моделей следует отнести сложность или невозможность представления внутреннего облика объекта, построения произвольных его разрезов и сечений.

Рис. 1. Геометрические модели объекта
а – стержневая; б - оболочечная

Оболочечная модель объекта (рис.1б), основана на представлении внешнего облика объекта в виде совокупности поверхностей, являющихся гранями модели (А, Б, В...). Линии пересечения поверхностей образуют ребра модели.
Такая модель описывается системой уравнений поверхностей и может быть использована для моделирования внешнего облика объектов любой формы. Основной ее недостаток невозможность представления внутреннего облика объекта, построение его разрезов и сечений.
Наиболее современной моделью, нашедшее широкое применение в САПР, является объемная (твердотелая модель). Общепринятым порядком моделирования твердого тела является последовательность выполнения булевых операций (объединение, вычитание и пересечение) над объемными элементами (сферы, призмы, цилиндры, конусы, пирамиды и т.д.). Эти элементы описываются теми же уравнениями, что и поверхности оболочечной модели, однако объемные элементы считаются заполненными. Пример выполнения операций с объемными элементами показан на рис.2.

Рис.2. Операции с объемными элементами

Функциональное описание объектов проектирования
Функциональная модель объекта или его составляющих элементов представляет собой зависимость, связывающую выходные характеристики объекта с входными, управляющими и внешними параметрами. В общем случае функциональные модели записываются в виде соотношения:
Y= F (X, U, V, t, S) (1)
S= (x, y, z)
Y – выходная характеристика (вектор-функция);
X – вектор-функция входных (внутренних) параметров;
U – вектор-функция управляющих параметров;
V – вектор-функция воздействия среды на элемент;
F – вектор-функция преобразования определяющих векторов в выходные характеристики объекта.
В общем случае функции Y, X, U, V зависят от времени t и пространственной координаты S=(x,y,z).
Состав X зависит от способа задания режима функционирования объекта и от того, какие элементы влияют на эти свойства.
Вектор U содержит совокупность параметров и характеристик, которые проектировщик назначает, исходя из цели проектирования с учётом соответствующих ограничений.

Вектор V определяется свойствами среды, в которой будет функционировать объект.
Вектор F – результат формализации общего представления об объекте, его составных частей и иных факторов, взаимодействующих с внешней средой и между собой.
Вид и состав всех функций формулы (1) существенно меняются при переходе от одного элемента к другому и существенно зависят от текущего этапа проектирования, становясь всё более точными и исчерпывающими ближе к завершению проекта.
Построение функциональной математической модели возможно, если выполнено морфологическое описание объекта проектирования, т.е. описан состав его элементов и их взаимосвязь.

Классификация функциональных моделей
В зависимости от способа построения функциональные модели бывают теоретическими и экспериментальными. Если физическая сторона процесса не изучена, то модель строится на основе опыта – это экспериментальная модель. Рассматриваются только входные и выходные параметры моделируемого объекта, рассматриваемого в виде кибернетического «черного ящика».
Функциональные математические модели, исходя из связей между параметрами моделей, разделяют на аналитические и алгоритмические. Аналитические модели имеют форму явных функциональных зависимостей искомых параметров от других параметров моделей. В алгоритмической модели такая зависимость выражена неявно, она описана в виде некоторого алгоритма.

Если при получении математической модели учитываются случайные факторы реального процесса и параметры модели носят случайный характер, такие модели называются стохастическими. В противном случае модели являются детерминированными.
Переменные входящие в модель, могут принимать отдельные изолированные значения или любые значения в пределах определённого непрерывного интервала. В первом случаи модель называется дискретной, во втором случаи модель называется непрерывной.
Особенности входящих в математические модели уравнений позволяют выделить линейные и нелинейные модели.
В зависимости от того, учитываются ли динамические процессы (то есть процессы, изменяющиеся во времени) или нет, различают динамические и статические модели.

Основные виды функциональных моделей
При проектировании сложных объектов используются функциональные модели следующих видов: 1. Математические модели в форме дифференциальных уравнений в частных производных (распределённые модели). Такие модели отражают процессы, протекающие непрерывно в трёхмерном пространстве и во времени. В общем виде записываются как:
Ф (S, x, U, V, Y, ∂y/∂S, ∂2y/∂S2 , , …, t)=0
Ф – оператор связи между переменными и их производными.
Примером распределённой модели могут быть уравнение теплопроводности при моделировании радиоэлектронных устройств. Это уравнение связывает изменение температуры в пространстве и во времени со свойствами среды.

2. Математические модели в форме обыкновенных дифференциальных уравнений (сосредоточенные модели), которая записывается в виде:
dY/dt = F(X,Y,U,V,t)
Сосредоточенные модели используются в основном при проектировании различных подсистем проектируемого сложного объекта. Здесь решаются задачи, связанные с динамическими процессами.
3. Если динамические процессы не учитываются, то учитываются только статические состояния объекта. В этом случае
F (X, Y, U, V)= 0
В частном случае математическая модель может быть в виде алгебраического уравнения
Y=F(V)

4.Математическая модель в форме логических уравнений. Используется аппарат алгебры логики, изучающий отношения между дискретными двухзначными величинами. Логические модели широко используют при проектировании схем ЭВМ, контактно-релейных схем и т.д.
5. Математические модели (ММ) стохастических процессов (случайный характер).
При проектировании многих сложных систем, удобнее их рассматривать как системы массового обслуживания. Основными составными частями ММ системы массового обслуживания являются модель входного потока заявок, модель совокупности обслуживающих каналов и их информационных связей, модель дисциплины обслуживания.
В качестве моделей применяют тот или иной алгоритм. Примерами такого типа моделируемых объектов являются телефонные станции, сеть торговых баз, комплекс заправочных станций и т.д.

Методы построения функциональных моделей
Основной принцип получения теоретических распределённых моделей заключается в использовании фундаментальных физических законов.
К ним относятся законы сохранения массы, энергии, количества движения. Указанные законы в общем случае записываются в виде:
∂φ/∂t=-divJ+G
, где
φ – некоторая фазовая переменная (плотность, энергия, импульс)
J = (Jx, Jy, Jz) – вектор потока фазовой переменной;
G – скорость генерации (массы, энергии, количества движения);
t – время.
divJ=∂Jx/∂x+∂Jy/∂y++∂Jz/∂z - ивергенция вектора потока J (расхождение), которая характеризует сумму притока – стока через поверхность элементарного объёма.