Помощь студентам в учебе
Алгоритм линеаризации механических структур сложных технических систем по отношению эквивалентности
|
ВВЕДЕНИЕ 8
1. Моделирование механической структуры изделия 10
1.1. Проблемы автоматизации сборки 10
1.2. Обзор существующих подходов к описанию механических структур 12
1.2. Графовая модель структуры изделия 15
1.3. Гиперграфовая модель структуры изделия 18
2. Устранение избыточности в гиперграфных моделях 19
2.1. Собираемость в терминах гиперграфа 19
2.1. Избыточность и неопределенность механической структуры 22
2.2. Линеаризация гиперграфовой модели изделия 24
2.3. Постановка задачи линеаризации по соотношениям эквивалентности ....31
3. Алгоритм линеаризации по критерию эквивалентных вершин 33
3.1. Проектирование алгоритма 33
3.2. Параметры конфигурации 35
3.2. Определение параметров алгоритма для реализации 47
4. Программная реализация алгоритма линеаризации 48
4.1. Программные средства разработки 48
4.2. Описание структур данных и функций 49
5. Тестирование программного комплекса 58
5.1. Подготовка тестовых данных 58
5.2. Анализ полученных результатов и перспективы развития 60
ЗАКЛЮЧЕНИЕ 63
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 65
ПРИЛОЖЕНИЕ А 68
ПРИЛОЖЕНИЕ Б 69
ПРИЛОЖЕНИЕ В 70
ПРИЛОЖЕНИЕ Г 71
ПРИЛОЖЕНИЕ Д 72
1. Моделирование механической структуры изделия 10
1.1. Проблемы автоматизации сборки 10
1.2. Обзор существующих подходов к описанию механических структур 12
1.2. Графовая модель структуры изделия 15
1.3. Гиперграфовая модель структуры изделия 18
2. Устранение избыточности в гиперграфных моделях 19
2.1. Собираемость в терминах гиперграфа 19
2.1. Избыточность и неопределенность механической структуры 22
2.2. Линеаризация гиперграфовой модели изделия 24
2.3. Постановка задачи линеаризации по соотношениям эквивалентности ....31
3. Алгоритм линеаризации по критерию эквивалентных вершин 33
3.1. Проектирование алгоритма 33
3.2. Параметры конфигурации 35
3.2. Определение параметров алгоритма для реализации 47
4. Программная реализация алгоритма линеаризации 48
4.1. Программные средства разработки 48
4.2. Описание структур данных и функций 49
5. Тестирование программного комплекса 58
5.1. Подготовка тестовых данных 58
5.2. Анализ полученных результатов и перспективы развития 60
ЗАКЛЮЧЕНИЕ 63
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 65
ПРИЛОЖЕНИЕ А 68
ПРИЛОЖЕНИЕ Б 69
ПРИЛОЖЕНИЕ В 70
ПРИЛОЖЕНИЕ Г 71
ПРИЛОЖЕНИЕ Д 72
Сборка является важнейшим этапом жизненного цикла изделия. Результирующие характеристики напрямую зависят от качества сборки. На этом этапе выявляются конструкторские недочеты и уточняются требования к обработке деталей и свойствам отдельных компонентов изделия. Сборка обладает высокой трудоемкостью и, зачастую самой высокой длительностью среди всех этапов жизненного цикла объекта производства.
В наши дни, производственные процессы постепенно автоматизируются. Открываются и исследуются новые направления автоматизации. Одним из таких является CAAP (Computer-Aided Assembly Planning) - автоматизированное планирование сборочного процесса. В область исследования этого направления входят проблемы создания, организации и управления процессом сборки. К основным задачам исследования в этом направлении можно отнести поиск адекватной модели структуры изделия, декомпозицию изделия на сборочные единицы и моделирование процесса сборки.
Существуют различные модели механической структуры изделия. Наиболее популярной среди них является графовая модель (в англоязычной литературе - Liaison Graph). В ней, механический контакт представляется ребрами, а каждой уникальной детали ставится в соответствие вершина. В общем случае, базирование деталей рассматривается как отношение переменой местности, а не бинарной, как представлено в графовой модели. Минимальной геометрически определенной группе деталей соответствуют полные подграфы (клики) графа связей, представленные в виде гиперрёбер в гиперграфной модели изделия. Эта модель позволяет проводить анализ механической структуры на избыточность и формировать последовательность сборки в виде последовательности стягиваний гиперрёбер.
Задача о ликвидации избыточности в гиперграфе обладает высокой сложностью. Вводится понятие линеаризации - удаление вершин, которые не позволяют сформировать последовательность стягиваний только из гиперрёбер кратности 2. Формализация критериев, на основе которых следует удалить то или иное гиперребро, представляет из себя нетривиальную задачу и является объектом исследования по сей день. Одним из таких критериев является эквивалентность вершин. В работе предлагается формализация данного критерия в виде математического описания в терминах гиперграфа. Две вершины называются эквивалентными, если при сборке они должны войти в одну сборочную единицу. Путь между этими вершинами в гиперграфе следует защитить от удаления в процессе линеаризации. В рамках диссертации был разработан обобщенный алгоритм линеаризации по критерию эквивалентности вершин на основе поиска в ширину. Были найдены и исследованы дополнительные параметры конфигурации этого алгоритма, для управления принятием решения на каждом шаге его работы. Алгоритм был спроектирован таким образом, чтобы в последствии, дополнять его любым набором входных данных, позволяющим скорректировать его работу. В работе приводится реализация алгоритма с фиксированными пара-метрами его конфигурации.
В наши дни, производственные процессы постепенно автоматизируются. Открываются и исследуются новые направления автоматизации. Одним из таких является CAAP (Computer-Aided Assembly Planning) - автоматизированное планирование сборочного процесса. В область исследования этого направления входят проблемы создания, организации и управления процессом сборки. К основным задачам исследования в этом направлении можно отнести поиск адекватной модели структуры изделия, декомпозицию изделия на сборочные единицы и моделирование процесса сборки.
Существуют различные модели механической структуры изделия. Наиболее популярной среди них является графовая модель (в англоязычной литературе - Liaison Graph). В ней, механический контакт представляется ребрами, а каждой уникальной детали ставится в соответствие вершина. В общем случае, базирование деталей рассматривается как отношение переменой местности, а не бинарной, как представлено в графовой модели. Минимальной геометрически определенной группе деталей соответствуют полные подграфы (клики) графа связей, представленные в виде гиперрёбер в гиперграфной модели изделия. Эта модель позволяет проводить анализ механической структуры на избыточность и формировать последовательность сборки в виде последовательности стягиваний гиперрёбер.
Задача о ликвидации избыточности в гиперграфе обладает высокой сложностью. Вводится понятие линеаризации - удаление вершин, которые не позволяют сформировать последовательность стягиваний только из гиперрёбер кратности 2. Формализация критериев, на основе которых следует удалить то или иное гиперребро, представляет из себя нетривиальную задачу и является объектом исследования по сей день. Одним из таких критериев является эквивалентность вершин. В работе предлагается формализация данного критерия в виде математического описания в терминах гиперграфа. Две вершины называются эквивалентными, если при сборке они должны войти в одну сборочную единицу. Путь между этими вершинами в гиперграфе следует защитить от удаления в процессе линеаризации. В рамках диссертации был разработан обобщенный алгоритм линеаризации по критерию эквивалентности вершин на основе поиска в ширину. Были найдены и исследованы дополнительные параметры конфигурации этого алгоритма, для управления принятием решения на каждом шаге его работы. Алгоритм был спроектирован таким образом, чтобы в последствии, дополнять его любым набором входных данных, позволяющим скорректировать его работу. В работе приводится реализация алгоритма с фиксированными пара-метрами его конфигурации.
Диссертационное исследование посвящено моделированию механических структур сложных изделий в CAD-системах. Рассмотрена задача устранения избыточности механических структур. Эта задача решалась на основании эксперт-ной информации о парах деталей, которые должны войти в одну сборочную единицу. Условие вхождения деталей по любым конструкторским, технологическим или производственным основаниям формализованы в виде совокупности отношений эквивалентности. Эти отношения записываются в форме условных равенств. В терминах множеств описаны основные понятия, необходимые для математической формулировки задачи. Введены определение терминов: эквивалентная вершина, класс эквивалентных вершин, защищенные гиперрёбра. Поставлена задача линеаризации гиперграфовой модели структуры изделия на основе соотношения эквивалентности.
В рамках дипломной работы найден и описан алгоритм линеаризации гиперграфных моделей по критерию эквивалентности вершин, базирующийся на поиске в ширину для защиты гиперрёбер от удаления. Приведены и рассмотрены параметры конфигурации алгоритма, на основе которого можно изменить поведение операторов алгоритма и изменить структуру и объем выходных данных. Рассмотрены подробно каждые значения этих параметров. Составлены эвристики для фиксирования этих параметров для разработки конкретной реализации алгоритма. Разработан и протестирован алгоритм линеаризации по критерию избыточных вершин.
Проведен вычислительный эксперимент и выполнено тестирование алгоритма. В зависимости от ряда параметров: число вершин и ребер графовой модели, количество классов эквивалентности и количества вершин в каждом классе, - сделан вывод об эффективности работы алгоритма, определены основанные технические недостатки реализации.
Несмотря на исследовательских характер работы, были выявлены вполне практические закономерности. Алгоритм и его программная реализация могут быть использованы для интеграции в систему экспертного анализа механических структур любой CAD-системы, позволяющий установку пользовательских расширений функциональности. Связные подмножества гиперрёбер разной кратности позволяют описывать геометрически разрешимые и неразрешимые ситуации установки некоторых типовых группировок деталей. Процесс линеаризации служит для подготовки модели к виду, позволяющему генерировать на основе нее последовательности сборки. Уточнение требований к этому процессу, формализация критериев позволяет установить ограничения, сохраняемые в модели, увеличивая долю участия ЛПР в процессе изменения модели.
В рамках дипломной работы найден и описан алгоритм линеаризации гиперграфных моделей по критерию эквивалентности вершин, базирующийся на поиске в ширину для защиты гиперрёбер от удаления. Приведены и рассмотрены параметры конфигурации алгоритма, на основе которого можно изменить поведение операторов алгоритма и изменить структуру и объем выходных данных. Рассмотрены подробно каждые значения этих параметров. Составлены эвристики для фиксирования этих параметров для разработки конкретной реализации алгоритма. Разработан и протестирован алгоритм линеаризации по критерию избыточных вершин.
Проведен вычислительный эксперимент и выполнено тестирование алгоритма. В зависимости от ряда параметров: число вершин и ребер графовой модели, количество классов эквивалентности и количества вершин в каждом классе, - сделан вывод об эффективности работы алгоритма, определены основанные технические недостатки реализации.
Несмотря на исследовательских характер работы, были выявлены вполне практические закономерности. Алгоритм и его программная реализация могут быть использованы для интеграции в систему экспертного анализа механических структур любой CAD-системы, позволяющий установку пользовательских расширений функциональности. Связные подмножества гиперрёбер разной кратности позволяют описывать геометрически разрешимые и неразрешимые ситуации установки некоторых типовых группировок деталей. Процесс линеаризации служит для подготовки модели к виду, позволяющему генерировать на основе нее последовательности сборки. Уточнение требований к этому процессу, формализация критериев позволяет установить ограничения, сохраняемые в модели, увеличивая долю участия ЛПР в процессе изменения модели.