Геометрический алгоритм оптимизации профиля матрицы жесткости для решения задач по методу конечных элементов
При решении задач по методу конечных элементов результирующая матрица жесткости имеет симметричную и квазидиагональную структуру. Чтобы минимизировать ширину ленты ненулевых чисел, сосредоточенных вдоль главной диагонали матрицы жесткости, и тем самым уменьшить расход оперативной памяти и время счета, необходимо нумеровать конструкцию так, чтобы разность номеров узлов смежных конечных элементов была минимальной. Современные программные комплексы, как правило, оснащены графическими препроцессорами, в которых формируется геометрия конструкции. На выходе они генерируют структуры, хранящие координаты узлов и топологию конструкции, но делают это хаотично, не учитывая влияния порядка расположения узлов на ширину ленты матрицы жесткости. Автоматическая перенумерация узлов чаще всего выполняется в основном расчетном блоке программы. Существует множество алгоритмов оптимизации профиля матрицы жесткости (наиболее полное их описание приведено в книге «Технология разреженных матриц» C.Писсанецки). Все они, как правило, используют математический аппарат теории графов и работают с топологическими структурами геометрической модели конструкции.
Оптимизацию профиля матрицы жесткости можно выполнить на уровне препроцессора, до формирования топологии конструкции. Прибегнуть к этому алгоритму целесообразно, когда ранее разработанное программное обеспечение, не оснащенное блоком перенумерации узлов, интегрируется в графический редактор (например, в AutoCAD) и дополняется новым графическим интерфейсом. Коллектив авторов столкнулся с этой проблемой во время программной реконструкции прочностного комплекса «МУССОН», разработанного для расчетов подземных сооружений. Этот программный комплекс был создан в 90-е годы для операционной системы DOS с препроцессором, функционирующим в среде графического редактора AutoCAD 10-12. Программа хорошо себя зарекомендовала в проектных организациях России и СНГ. Конечно-элементное ядро «МУССОНа» не было оснащено блоком перенумерации узлов, поэтому при интегрировании «МУССОНа» в новые версии AutoCAD, функционирующие в ОС Windows, разработали модуль, выполняющий оптимизацию профиля матрицы жесткости непосредственно в среде графического редактора AutoCAD. Программа реализована на языке AutoLISP и использует для своей работы графические примитивы и базу данных AutoCAD.
Принцип оптимальной нумерации достаточно прост. Чтобы обеспечить минимальную разность номеров узлов на смежных конечных элементах, необходимо нумеровать узлы примерно по спирали, охватывающей наиболее узкие части конструкции (рис. 1).
Рис. 1. Нумерация узлов
Большинство алгоритмов перенумерации прямо или косвенно реализуют этот принцип на уровне топологических структур данных.
Программа «МУССОН» в качестве исходной информации использует чертеж расчетной схемы, сохраненный программой AutoCAD в формате DXF. Разработанный нами блок оптимизации профиля матрицы жесткости формирует самостоятельно DXF-файл, изменяя в нем порядок следования примитивов AutoCADa по оптимальному направлению. Отличительной особенностью разработанной программы является то, что перенумерации подвергаются не узлы, а номера конечных элементов.
Рассмотрим более подробно основные шаги этого алгоритма. Сначала формируется базовая структура данных LIST_PTC — список координат центров тяжести графических примитивов, описывающих несущие элементы конструкции. Структура этого списка выглядит следующим образом:
(
(x1 y1 Hand1)
(x2 y2 Hand2)
. . . . . . .
)
где x1, y1 — координаты центра тяжести примитива, Hand1 — метка графического примитива в базе данных AutoCAD.
По информации из этого списка определяются габариты конструкции, и на нее виртуально накладывается сетка хеширования (рис. 2).
Рис. 2. Формирование структурированных списков
На следующем этапе выполняется распределение элементов списка LIST_PTC по локальным полосам сетки хеширования (см. рис. 2). На выходе формируются две информационные структуры: LIST_I и LIST_J — структурированные списки, хранящие элементы списка LIST_PTC, но распределенные по координатным полосам сетки хеширования:
- LIST_I — элементы, находящиеся в зоне полос, параллельных оси X;
- LIST_J — элементы, находящиеся в зоне полос, параллельных оси Y.
Структура этих списков выглядит следующим образом (см. рис. 2): ( i_1 i_2 i_3 i_4 … i_n ), где i_1 i_2 … i_n — локальные списки, состоящие из элементов списка LIST_PTC, находящиеся в зоне i-й (j-й) полосы. Далее сравнивается размерность списков LIST_I и LIST_J. Список с наибольшей размерностью становится базовым для формирования фронта перенумерации. Например, для конструкции на рис. 2 размерность списка LIST_I равна 6, а размерность списка LIST_J — 25, поэтому список LIST_J становится базовым для формирования фронта перенумерации. После выбора базового списка начинается работа основного цикла алгоритма перенумерации. В ходе работы цикла последовательно перебираются элементы списка LIST_I (LIST_J). Элементы подсписка, соответствующего текущей полосе хеширования, сортируются в направлении возрастания (убывания) координаты X (для LIST_I) или Y (для LIST_J). Возрастание или убывание сортировки чередуется через полосу — таким образом достигается спиралевидный порядок обхода элементов. На выходе формируется последовательный набор графических примитивов AutoCAD, который записывается средствами языка AutoLISP в DXF-файл. Полученный DXF-файл является исходным для прочностного комплекса «МУССОН». На рис. 3 показан порядок нумерации стержней тестового примера, полученный в результате работы алгоритма геометрической перенумерации.
Рис. 3. Результат работы алгоритма геометрической перенумерации стержней
Рис. 4. Нумерация узлов конструкции подземной автостоянки
На рис. 4 приведена нумерация узлов конструкции многоярусной подземной автостоянки, сформированная программой «МУССОН» по результатам геометрической перенумерации стержней в препроцессорном блоке AutoCAD.
Предлагаемый подход к решению задачи оптимизации профиля матрицы жесткости достаточно универсален и может быть адаптирован к входным форматам практически любой системы прочностного анализа.
