Топологическое моделирование на графах

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

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

ТОПОЛОГИЧЕСКОЕ МОДЕЛИРОВАНИЕ

Топологическое моделирование использует примитивы-поверхности, с помощью которых можно формировать как фигуры-тела, так и фигуры-пустоты. Примитив-поверхность моделируется висячей вершиной подграфа, код которой определяет характер (форму) поверхности. Введем следующие коды примитивов-поверхностей для фигур-тел: p - плоскость; d - цилиндрическая поверхность; c - коническая поверхность; s - сферическая поверхность; f - прочие поверхности, описываемые математическими функциями. Для фигур-пустот используются те же коды только со знаком минус. Таким образом положительные коды описывают внешние и выпуклые поверхности, а отрицательные - внутренние и вогнутые. Каждая висячая вершина (поверхность) соединяется единственным ребром с корневой вершиной, которая является либо телом (обозначается символом B), либо пустотой (E). Если сложная фигура содержит и тело и пустоту, то корневая вершина обозначается двумя символами BE. Степень корневых вершин описываемых фигур не может быть меньше двух за исключением сферы, где корневая вершина имеет первую степень. На рис. 1 показаны некоторые фигуры-тела и моделирующие их графы, а на рис. 2 - более сложные сплошные модели, включающие в себя как фигуры-тела, так и фигуры-пустоты.

Таблица 1.
Векторы топологии моделей фигур-тел.

Если все вершины и ребра графа, моделирующего конкретную фигуру, взвесить конкретными значениями измеряемых параметров, то сплошная модель, имеющая единичные размеры, превращается в конструктив. В качестве параметров вершины или ребра конструктива могут быть заданы: ширина, длина, высота, конусность, радиус, координата и т. п.

СИНТЕЗ ПРОЕКТИРУЕМОЙ ДЕТАЛИ

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

В предлагаемой концепции топологического моделирования на графах для описания примитивов-поверхностей, фигур-тел, фигур-пустот, конструктивов и проектируемых деталей используются векторы топологии [3]:

S = (s₁, s₂, ..., s_i, , ..., s_n); (1)

A = (d₁, d₂, ..., d_i, , ..., d_n), (2)

где (1) - вектор закрепленных степеней; (2) - вектор подвижных степеней.

В таблице 1 представлены векторы топологии, описывающие структуру фигур-тел, показанных на рис.1, а в таблице 2 - сплошных моделей, показанных на рис. 2.

Таблица 2.
Векторы топологии сплошных моделей.

В качестве примера рассмотрим процесс синтеза детали, показанной на рис. 3, а, с помощью топологического моделирования на графах. Деталь представляет собой тело вращения - двухступенчатый вал с тремя фасками и шпоночной канавкой. Вертикальными пунктирными линиями показаны сечения вала, разделяющие деталь на отдельные конструктивы. Синтез конструируемой детали выполняется путем последовательного объединения вершин-поверхностей. Основными признаками конформности сопрягаемых поверхностей являются такие, как, например, совпадающие значения кодов, их разнознаковость, совпадение геометрических параметров (конусность, диаметр и т. п.), соосность, эксцентриситет и т. д. Объединенная вершина обозначается кодом поверхности и знаками ±. На рис. 3, б показана графовая модель (дерево) проектируемой детали с расшифровкой ее элементов [4].

Рассмотрим синтез двух фрагментов синтезируемой детали. Первый фрагмент - фигура-тело, моделирующая цилиндр (корневая вершина 2), а второй - это фигура-тело, являющееся цилиндром с вырезанной шпоночной канавкой прямоугольного сечения (корневая вершина 6). Первый фрагмент представлен подграфом, состоящем из четырех вершин (N 2, N 9, N 10, N 2-1), которые соединены между собой тремя ребрами. Вершины N 9 и N 10 моделируют сопрягаемые плоскости, висячая вершина N 2-1 моделирует цилиндрическую поверхность. Первое число составного номера определяет номер фигуры-тела внутри синтезируемой детали, а второе - номер поверхности внутри рассматриваемого фрагмента детали. Второй фрагмент, используемый для иллюстрации, состоит из семи вершин (N 6, N 13, N 14, N 6-1, N 6-2, N 6-3, N 6-4). Четыре висячих вершины, имеющие в составном номере число 6, моделируют четыре различных поверхности. Первые три вершины моделируют три плоскости шпоночной канавки, а последняя - цилиндрическую поверхность, относящуюся ко второй ступени проектируемого вала. Расход памяти на хранение топологичесого "образа" синтезированной детали для вектора (1) составляет 93 байта, для вектора (2) - 67 байтов, для матрицы смежности - 121 байт в упакованном формате. Всего 281 байт.

ФОРМИРОВАНИЕ МОДЕЛИ РАЗМЕРНЫХ ЦЕПЕЙ

Точностные характеристики проектируемой детали во многом зависят от структуры размерной цепи, которая формируется конструктором-оператором в диалоговом режиме с использованием интерфейсной программы САПР [6]. При этом конструктор в достаточно большой степени опирается на свой опыт и интуицию. В соответствии с теоремой Кэли число вариантов размерных цепей (деревьев) равно 2^n-2. При большом числе конструкторских размеров количество диалоговых операций существенно возрастает. Допустим, что пользователя САПР интересует такая структура размерной цепи, которая доставляет минимум суммарному полю допуска размеров. Если значения модулей допуска размеров заданы треугольной матрицей, то эту задачу можно решить, используя известные классические алгоритмы Прима или Краскала. Однако в тех случаях, когда модули допуска размеров равны между собой, то упомянутые выше классические алгоритмы становятся бессильными, так как они вырождаются в перебор. То же самое происходит и с алгоритмом Габова [1], если одна из поверхностей детали является базовой и для нее задана степень вершины.

Таким образом, при наличии одной или нескольких базовых поверхностей, а также в случае, когда все модули допусков размеров одинаковы, классическими методами сформировать модель размерной цепи невозможно. Ключ к решению данной проблемы следует искать в использовании метода замещений [2, 3, 4]. Рассмотрим следующую теорему [3], предварительно введя следующие обозначения: n и m- соответственно, число вершин и число ребер, содержащихся в искомом подграфе; d - компонента вектора подвижных степеней (2).

Теорема. Пусть G (V, E) - неориентированный граф; тогда параметры n, m искомого подграфа и компоненты вектора подвижных степеней (2) связаны между собой системой диофантовых уравнений: (=d)

Графовая модель размерной цепи (без замыкающих звеньев) представляет собой каркас (дерево) [4]. Для пользователя САПР наибольший интерес представляют: а) число вершин второй степени d2, определяющие длину ветвей, отходящих от корня дерева, и б) количество базовых поверхностей детали, относительно которой суммируются модули допусков размеров. Для моделируемой размерной цепи, являющейся деревом, из (3) и (4) имеем следующую систему диофантовых уравнений:

d₁ + 2 d₂ + x d_x = 2 (n - 1); (5)

d₁ + d₂ + d_x = n, (6)

где n - общее число вершин дерева, моделирующего размерную цепь; dx - количество базовых поверхностей, задаваемых пользователем САПР; X - искомая степень вершины дерева, моделирующей базовую поверхность детали.

Решая систему уравнений (5) - (6) относительно X, имеем:

x = (n + d_x - d₂ - 2)/d_x . (7)

Задача формирования оптимальной размерной цепи математически формулируется следующей функцией цели:

и ограничениями

A_max = (A₁, A₂, ..., A_i, ..., A_n); (9)

A_min = (a₁, a₂, ..., a_i, ..., a_n); Q > 0, (10)

где A_max и A_min - соответственно, верхняя и нижняя границы допустимых значений степеней векторов топологии; A_i и a_i - соответственно, максимальное и минимальное значения i-ых компонент векторов топологии A_max и A_min; Q - сумма значений допусков.

ПРИМЕР

Рассмотрим процесс формирования модели размерной цепи на примере детали, показанной на рис. 3, а.

Условие задачи формулируется следующим образом. Пусть поле допусков размеров между всеми поверхностями задано треугольной матрицей (рис. 4, а), а в качестве базовой выбрана поверхность 4 (рис. 4, б). Задана, также, верхняя граница суммы модулей допусков размеров последовательно включенных звеньев размерной цепи, соединяющих две конструкторских поверхности, одна из которых является базовой, Q = 1, 1. Значение Q определяется условиями конструкторского или технологического порядка.

Вопросы задачи, представляющие интерес для пользователя САПР, имеют следующие формулировки:

а) чему равно максимальное количество L последовательно включенных звеньев размерной цепи, соединяющих две конструкторских поверхности, одна из которых является базовой, а сумма составляющих ее модулей допусков размеров не превышает заданной границы Q?

б) каковы структуры (топологии) набора исследуемых размерных цепей с количеством последовательно включенных звеньев от 2 до L?

в) какую структуру размерной цепи из полученного набора выбрать по критерию оптимальности, задаваемого пользователем САПР как при наличии ограничения Q, так и без него ?

В качестве критериев оптимальности используются следующие.

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

где s - вариант структуры размерной цепи (элемент множества N); N - множество структур (подграфов), исследуемых вариантов размерных цепей; b - номер ветви размерной цепи, содержащей более одного звена; Ci - модуль допуска размера l-го звена ветви размерной цепи.

Второй критерий: минимальная сумма поля допусков размеров по всем элементам цепи (8).

Решение поставленной задачи выполняется поэтапно в соответствии с вопросами а), б) и в).

1 этап. Максимальное число L определяется числом элементов исходной матрицы, упорядоченных по возрастанию их абсолютных значений, сумма которых не превышает Q. В нашем случае это определяется суммой минимальных элементов 0,14 + 0,22 + 0,24 + 0,28 = 0,88. Следовательно, L = 4. Отсюда следует, что число вершин второй степени в наборе моделей размерных цепей должно варьироваться от 1 до 3.

2 этап. Используя формулу (7), формируем таблицу 3 вариантов степеней базовой поверхности проектируемой детали. На основе полученной таблицы формируем следующие векторы допустимых степеней:

A_max = (2, 2, 2, 5, 2, 2, 2), A_min = (1, 1, 1, 5, 1, 1, 1); (12)

A_max = (2, 2, 2, 4, 2, 2, 2), A_min = (1, 1, 1, 4, 1, 1, 1); (13)

A_max = (2, 2, 2, 3, 2, 2, 2), A_min = (1, 1, 1, 3, 1, 1, 1). (14)

3 этап. Используя метод замещений [3,4] , получаем три варианта решения, показанные на рис. 5. Каждый вариант решения является подграфом, моделирующим размерную цепь при ограничении на топологию, соответственно (12), (13) и (14). Из полученных вариантов пользователь САПР выбирает наилучший по двум упомянутым выше критериям оптимальности. Лучшие варианты размерных цепей, сгенерированные экспериментальной программной системой AVENIR, показаны на рис. 4, б: над осевой линией расположена размерная цепь, оптимизированная по первому критерию, а под осевой линией - по второму критерию. Формирование размерных цепей с помощью данной программной системы существенно сокращает число диалоговых итераций в системе "человек-машина" и экономит время проектировщика. Пользователю САПР требуется выбрать критерий оптимальности и пометить базовые поверхности, а размерная цепь на экране дисплея формируется автоматически. При необходимости проектировщик может дополнить ее замыкающими звеньями.

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

Вычислительный эксперимент, выполненный в Институте конструкторско-технологической информатики РАН на IBM PC/AT, при решении задач (8)-(10) по моделированию размерных цепей с использованием программной системы AVENIR [4], на 10 вершинных полных исходных графах, показал, что для однопроцессорных вычислительных машин при равных затратах машинного времени более предпочтительным с точки зрения погрешности решения является прием релаксации по сравнению с установкой лимита времени. При этом исходные матрицы весов заполнялись генератором случайных чисел с равномерным законом распределения. Результаты эксперимента представлены на рис. 6. Кривые получены путем аппроксимации экспериментальных точек методом наименьших квадратов. По горизонтальной оси отмечаются показатели деформации начального подграфа без релаксации - e и в скобках D0, по вертикальной - десятичный логарифм от числа узлов, полученных в дереве замещений (ДЗ) [3]. Пунктирной линией показаны трудоемкости точного решения; штрих-пунктирной - при установке лимита времени, эквивалентного 1000 узлам ДЗ; сплошной линией представлены трудоемкости решения после предварительной релаксации. На каждой кривой показаны диапазоны погрешностей e в %. На штрих-пунктирной линии кружочками показаны те значения деформации, на которых наблюдались отдельные случаи, когда время отыскания первого нуль-узла было больше отпущенного лимита времени на последующее решение. Эксперимент показал, также, что при решении задачи (3)-(10) с увеличением разности между всеми компонентами Ai и ai = 1, трудоемкость решения снижается как с релаксацией так и без нее. При всех компонентах векторов (9) Ai = 9 и ai = 1 с приемом релаксации трудоемкость в среднем не превышает трудоемкости лучших классических алгоритмов отыскания каркаса с минимальным весом. Это объясняется тем, что решение, как правило, появляется в корневом узле ДЗ без дальнейшего ветвления. В процессе вычислительного эксперимента максимальное время формирования оптимальной размерной цепи не превышало двух секунд.

Рассмотренные два примера топологического моделирования на графах (сплошная модель детали и модель размерной цепи) показывают широкие возможности метода замещений при использовании последнего в конструкторских и технологических САПР. Использование программной системы AVENIR в режиме "черного ящика" дает дополнительные сервисные возможности пользователю САПР.

ЛИТЕРАТУРА

1. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. ВО "Наука", Новосибирск, 1994, 365 с.

2. Горшков А.Ф., Соломенцев Ю.М. Применимость вершинных замещений в классе задач о К-вершинных подграфах. - Доклады Академии Наук, т. 336, # 2, 1994. с. 157-160.

3. Горшков А.Ф., Соломенцев Ю.М. Применимость реберных замещений в классе комбинаторных задач на графах. - Доклады Академии Наук, т. 337, # 2, 1994. с. 151-152.

4. Горшков А.Ф., Соломенцев Ю.М. Отыскание экстремальных каркасов с предписанными степенями вершин методом замещений. - Доклады Академии Наук, т. 347, # 4, 1996. с. 443-445.

5. Ильинский Д.Я. САПР в ГПС. - Под ред. Б.И. Черпакова. М.: Высшая школа, 1990. 96 с.

6. Митрофанов В.Г., Калачев О.Н., Схиртладзе А.Г. и др. САПР в технологии машиностроения. - Ярославль, 1995. 298 с.