автореферат диссертации по строительству, 05.23.17, диссертация на тему:Экстремальные комбинаторные задачи в строительной механике и методы их решения

РГВ ОД

На правах рукописи

о "3 »■ ■

/ ( ;

СЕРГЕЕВ Николай Давидович

ЭКСТРЕМАЛЬНЫЕ КОМБИНАТОРНЫЕ ЗАДАЧИ В СТРОИТЕЛЬНОЙ МЕХАНИКЕ И МЕТОДЫ ИХ РЕШЕНИЯ

05.23.17 - строительная механика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Санкт-Петербург 1996 г.

Работа выполнена в Санкт-Петербургском государственном архитектурно-строительном университете

Официальные оппоненты:

доктор технических наук, ведущий научный сотрудник Вовкушевский A.B.

доктор технических наук, профессор, член-корреспондент Жилищно-коммунальной академии Сливкер В.И.

доктор технических наук, профессор Темнов В.Г.

I

Ведущая организация ЛЕННИИПРОЕКТ

Защита состоится _ 1996 г. в /^час ¿»ЛАшп

на заседании диссертационного совета Д 063.31.04 при Санкт-Петербургском государственном архитектурно-строительном университете по адресу:. 19К005, Санкт-Петербург, 2-я Красноармейская ул., 4.

С диссертацией можно ознакомиться в фундаментальной библиотеке университета.

Автореферат разослан "//-" ¿¿-¿¿Л . 1996 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

Дерябин И.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальное и» проблем!,!. Проектируемая конструкция должна бьпь надежной н экономичной. Удачное сочетание этих противоречивых I ребоианий II проекшых решениях составляет предмет инженерного искусана с давних времен.

CipeMjieiine разрешить что противоречие научной постановкой попроси приняло » настоящее время форму теории ошималыют проектирования конарукций, находящейся еще в процессе становления. Основная задача здесь екппнея iик: минимизировать значение целевой функции, i.e.. и «Гнием случае, величину за i par, связанных с реализацией конструкции, при выполнении неравенс|в-01 раничеини: условий прочности, жесткости, устойчивости и конструктивных ограничений.

- При проецировании мпогоэлсментпых многократно сгашчески неопред'тимых стержневых или коиечноэлементных конструкций решение этой задачи сопряжено с двумя основными трудностями: I) множеству допустимых решений, как правило, сооыетствует невыпуклая область проетранепш переменных, и, как следствие эюго, задача оказывается многоэкстремальной - требуется найти глобальный минимум целевой функции в обход или среди локальных; 2) решение задачи связано со значительными вычислительными затратами и с достаточно большими запросами к обьему памяти вычислительной системы.

- Предпринимаемые упрощения задачи в большинстве случаев лишают се реально! о смысла

- Получение решения за счет подробного исследования основных зависимостей воможно лишь при небольшом числе переменных и, следовшсльио, к названным задачам прямого оiношения не имеет.

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

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

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

использоваться как рабочий при разработке типовых конструкций^ повторяемых в сотнях-тысячах стереотипов и при проектировании отдельных дорогостоящих конструкций или тех конструкций, для которых экономия массы имеет первостепенное значение.

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

Цели и задачи диссертации.

- Преодолеть первую трудность (связанную с многоэкстремальностью задачи) за счет постановки и решения оптимизационной задачи как экстремальной комбинаторной,.

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

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

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

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

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

, вопросу, касающемуся основ. строительной механики в ее современном развитии. .

Автор защищает!

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

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

- .Методы. сокращения вычислительных затрат и объема перерабатываемого числового материала при многократном повторении расчета сложных стержневых и конечноэлементных систем, связанном с изменением жеспсостп их элементов. • .

- Методы экономного перерасчета сложных стержневых и конечно-элементных систем при их последовательной многоэтапной модификаций.

Научная новнзна результатов работы.

- Дана постановка экстремальных задач строительной механики, использующих "дискретные"" переменные, ~ как задач экстремальных комбинаторных.

- Разработаны перечисленные выше новые методы их решения.

Достоверность основных положений работы, предлагаемых здесь

методов и алгоритмов устанавливалась:

- критическим анализом существующих методов в сопоставлении с предлагаемыми.

- строгим доказательством теорем, опенок и формул,

- решением примеров и серий примеров, в том числе с применением ЭВМ. .

Практическое значение выполненной работы определяется экономией стоимости конструкций, проектируемых по предлагаемой методике,, и экономией затрат па само проектирование.

Внедрение результатов работы.

1) Достоверность п надежность разработанных методов компоновки ■ конструкций практически проверена (поблочно) в вычислительном центре' Ленинградского Промстройпроекта. Там же с применением этих методов проведен анализ работы и выполнены контроль и настройка программного комплекса АВРОРА-75М. проектирующего поперечники стальных каркасов прокатных и трубопрокатных цехов.

2) ЛенНИIIПроекту передана составленная и отлаженная автором программа LEDA (Ленточную матрицу декомпозирующий алгоритм),

'обеспечивающая экономию машинного времени и одновременно исполь-пемото оОьсма памяти ЭВМ л 1.5-2 раза против ленточного алгоритма метода перемещений при расчете стержневых решеток; программа включена в программный комплекс по проектированию жилых и гражданских зданий.

3) ЛснПромсгроппроекту перетаны рекомендации по сокращению машинного времени и объема исполыуемон памяти ЭВМ пр:: расчете аержневых систем на основе существующих стандартных программ.

4) На основании метода главы 12 диссертации в Киевском отделении ЦН1 ШПроектсгальконсгрукини разработан эффективный алгоритм корректировки результатов факторизации матрицы.

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

Апробация. Основные результаты работы доложены на конференции по применению ЭВМ в строительной механике, Ленинград, 1972 г.; на VI .международном кошрессе по применению математики в технических науках, i. Веймар. ГДР. 1972 i.: па Всесоюзной конференции "Проблемы опти-мтыаним в механике ¡иердото деформируемого тела", Вильнюс, 1974 г.; на

координационных совещаниях в Центральном научно-исследовательском институте строительных конструкций Госстроя СССР по теме "Расчет и оптимизация конструкций" в 1974-77 гг.; на ХХУ1-ХХУШ, XXXI, XXXIII, XXXIV, XXXVII научных конференциях Ленинградского инженерно-строительного института в 1968-70, 1973, 1975-77, 1979 гг. и на конференциях СПбГАСУ в 1980-95 гг.; на научных семинарах кафедры строительной механики Ленинградского института инженеров железнодорожного транс-• порта в 1975 г.; на заседаниях секции оптимизации Научно-исследовательского института на общественных началах при ГПИ Ленинградский Промстройпроект в 1969-78 гг.; на научных семинарах Центрального научно-исследовательского института строительных конструкций (1977 г.), Киевского ► отделения ЦНИИПроектстальконструкция (1976 г.), кафедры исследования операций Ленинградского государственного университета (1977 г.); на заседании секции строительной механики Л О НТО "Стройиндустрия" (1978 г.); на научных семинарах кафедры строительной механики Санкт-Петербургского государственного кораблестроительного университета в 1988 и 1993 гг.

Публикации. По теме диссертации опубликованы монография, доклад на международном конгрессе по применению математики в технических науках, 5 статей в центральных журналах и 16 статей в сборниках трудов ЛИСИ, ЛИИЖТа, ЛенПромстройпроекта и СПбГАСУ.

Объем диссертации, состоящей из введения, 15-ти глав и заключения, составляет 286 страниц, включая 67 рисунков, 23 таблицы и список литературы из 140 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Введение

Во введении дается общая характеристика работы, поясняется последовательность изложения.ее частей и их взаимосвязь. Рассматриваемые в работе экстремальные комбинаторные задачи строительной механики ориентированы на усовершенствование проектирования и расчета многоэлементных многократно статически или кинематически неопределимых . конструкций, рассчитываемых по стержневой или конечноэлементной модели. Основу работы составляют постановка задач и разработка методов их решения. При этом за счет сужения и конкретизации условий задач из общих проблем строительной механики и проектирования выделяется, взаимосвязанный комплекс вполне определенных вопросов и выясняются пути их решения, что переводит соответствующие запросы техники из широкой .и не вполне четко определенной технико-теоретической области в круг задач реального проектирования или в непосредственную близость к этому кругу.

Так. вылеление из общей проблемы оптимального проектирования экстремальных комбинаторных задач оптимальной компоновки конструкций при заданных' наборах унифицированных элементов устраняет трудность

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

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

Остается еще одна обьекгивпая трудность. Глубина оптимизации прямо ' мвпеит от трудоемкости алгоритма проверочного расчета конструкции. Чем более трудоемок этот алгоритм. тем раньше будет остановлен оптимизационный поиск и тем менее совершенное решение будет получено. Ра ¡рабо 1 анш.п! меюд не накладывает никаких ограничений на расчетную схему конструкции при условии, что алгоритм проверочного расчета извеаеи. Обьектнвно возникает вопрос (комплекс, вопросов) о совершенствовании таких алгоритмов. И) этого объемного сложного комплекса мы опять-таки выделяем конкретный вопрос, требующий, по нашему мнению, первоочередного решения: сокращение трудоемкости алгоритмов строительной механики, ориентированных на решение линейных упругих задач. Причины такого вы деления следующие. В' настоящее время в подавляющем большинстве проектных разработок используются именно эти расчетные схемы конструкций, это положение сохранится, по нашему мнению, и в ближайшем будущем. При решении нелинейных задач строительной механики методами последовательных приближении основным аппаратом движения в рассматриваемых функциональных пространствах является решение линейных алгебраических уравнений. В области решения, линейных алгебраических задач с разреженными симметричными

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

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

Часть I. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ СТРОИТЕЛЬНОЙ МЕХАНИКИ. КРИТИЧЕСКИЙ ОЧЕРК СОВРЕМЕ1ЩОГО СОСТОЯНИЯ ВОПРОСА

Глава 1. Обзор литературы по теории оптимального проектирования конструкций и по вопросам усовершенствования расчета сложных статически неопределимых систем

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

Эти задачи в нашей работе основные. Они выделяются в главе 1 из. более широкого круга экстремальных задач строительной механики. Сюда относятся прежде всего задачи оптимального проектирования конструкций, рассчитываемых по стержневой, конечноэлементной или континуальной : модели. Ввиду обширности литературы по этой тематике в главе 1 даны ссылки лишь на отдельные работы, наиболее характерные для основных направлении теории. Упоминаются ранние для этой области работы Лагранжа, Максвелла, Л.ви. Мичелла; работы, характерные своим инженерным подходом ( Пихтарников Я.М.): статьи и книги, посвященные та* называемым

обратным задачам строительной механики (Pippard A., Heimann H., Рабинович И.M., Виноградов А.И., Радциг Ю.А., Комаров В.А., Хуберян K.M., Филин А.П. и Гуревич Я.И., Шелли Ф.); работы по применению — методов математического программирования (Богатырев А.И., Виноградов А.И., Даииелов Э.Р., Лазарев И.Б;, Мацюлявичус Д А., Рейтман М.И., Родионов A.A.. Хог Э. и Apopa Я., Чирас A.A., Brown D., Ang A., Hupfer P., Mosses F.. Prager W.); по применению статистических методов поиска (Почгман Ю.М., Лазарев П.Б. и Валуйских В.П.), по применению алгоритмического подхода к решению задач (Абрамов Н.И., Goble G., DcSantis Ph.. Rudolf F.): специфические работы, примыкающие к этой тематике (Гольдшгейи Ю.Б. и Соломеш М.А., Уайлд Д.Дж.) и другие. В обзоре современною состояния теории охарактеризованы ее основные направления, постановки задач и методы их решения. Итоги обзора в нужном для наших целей критическом аспекте изложены в разделе "Актуальность 1емы диссертации".

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

Отмечается, что для уменьшения трудоемкости прямого расчета статически или кинематически неопределимой системы существенно используется разреженность симметричных матриц, характерных для строительной механики (работы Аргироса Дж., Филина А.П., Тананайко О.Д.. Шварца М.А.. Феивееа С.Д. и Браннна Ф.Г., Клемперта Ю.З., Тыоарсопа Р.. обзор Фа.тдеева Д.К. и Фаддеевой В.Н.). положительная определенность пп\ матриц обеспечивает стабильность вычислений '(ФореаГп Дж. и Молер К.). Оптимальные и субоптнмальные методы упорядочивания строк и столбцов разреженной симметричной матрицы с целью сохранения ее разреженности в процессе вычислений связаны с "lono.ioi ической интерпретацией структуры матрицы и с использованием теории графов (Trent H.M.. Papter S.. Гольдштейн Ю.Б., Перельмутер A.B., Джордж А. и Лю Дж.. Tinney W.F.. Walker J.W., Spillers W.R.. Hickerson N. и др.). Для минимизации чнелл арифметических операций используется метод динамического программирования (Spillers W.R., Hickerson N.), более )ффекшвное решение полу чено за счет применения метода ветвей и границ при постановке соответствующей задачи как экстремальной комбинаторной.

Эффективные методы перерасчета системы при ее однократной модификации (работы Аргироса Дж. и Келен С., Бренлунда O.E., Роя Дж.Р., Шарпфа Д.В.. Роева В.И., Тананайко О.Д.) используют данные, полученные

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

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

Часть II. ЭКСТРЕМАЛЬНАЯ КОМБИНАТОРНАЯ ЗАДАЧА ОПТИМАЛЬНОЙ КОМПОНОВКИ КОНСТРУКЦИИ ПРИ ЗАДАННЫХ НАБОРАХ УНИФИЦИРОВАННЫХ ЭЛЕМЕНТОВ

Глава 2. Постановка задачи. Понижение верхней оценки оптимума.

Распределение вариантов конструкции по диапазонам стоимости

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

' Члены наборов катаны идесь унмфнциропам/шчи элементами, так как они яыбнрльмгл >п гмпегтпукчиих горсменто» и клилопш. на мог у г быть и специально запроектирован!! р виде иршедешии к единообразию обра.'цог.. что соответствует поштю "хнификзиия".

Конечное множество комбинаций, на котором задана целевая функция (стоимость конструкции), в этой экстремальной комбинаторной задаче может быть представлена точечным множеством в многомерном пространстве. Отмечая на каждой in t координатных осей (Г- число групп элементов конструкции) точки с последовательными порядковыми номерами от 1 до Sj

(.s, - количество наборов унифицированных элементов, заданных для ;-й

группы) и проводя соответствующие этому гиперплоскости, параллельные координатным, получаем в их пересечении множество точек, расположенное в пределах /-мерши о параллелепипеда, имеющее порядок (общее число

I

точек), равный ЛГ0 = ]~[ .у,, при л,— const Л'0 = л .

/=1

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

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

Глава 3. Ранжировка вариантов

В этой главе множество возможных вариантов конструкции рассматривается в виде компоновочной схемы вариантов, т.е. графа-дерева, на котором реализуется алгоритм динамического программирования.

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

Глава 4, Оптимальный вариант конструкции

Если второй этап ранжировки провести до конца, последовательно выполняя расчет всех вариантов, то оптимальный вариант конструкции определился бы как ближайший к концу ранжированной ленты среди вариантов, отвечающих всем ограничениям, задачи. Однако, затраты на вычисления могли бы при этом не только ослабить эффект оптимизации, но и перекрыть получаемый выигрыш, что привело бы вместо выигрыша к потерям. Для исключения подобных ситуаций формируется специальный критерий остановки поиска на основании полученного ранее распределения количества вариантов по заданным диапазонам их стоимости. Число-вариантов, -подлежащих дальнейшему рассмотрению, устанавливается поэтапно решением уравнения условного баланса, . сопоставляющего возможный выигрыш и затраты на его получение; учитываются вероятность реального выигрыша н его доля, расходуемая на вычисления. Поиск прекращается, если дальнейшие затраты оказываются неоправданными. Таким образом, объективно оптимальным оказывается вариант конструкции, коIорыи ^РРгпстствует остановке поиска.

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

Глава 5. Критическая оценка локальных методов поиска экстремума в связи с характерными особенностями задач оптимального проектировании статически неопределимых конструкции. Примеры

В этой ьтапе на примерах покатана невыпуклость области допустимых решений и многозкстремальность в задачах оптимизации статически неопределимых систем. Методы локалыюй оптимизации (градиентные при континуальных переменны»;, покоординатного и косого спуска, шагового перепроектирования - при дискретных переменных) позволяют прийти лишь к одному из локальных минимумов целевой функции и часто вероятность его получения значительно выше, чем вероятность нахождения глобального минимума при движении из случайно назначаемых стартовых точек, а значение локального минимума существенно больше, чем глобального. Показано, что при использовании метода шагового перепроектирования ' возможно зацикливание (колебание между двумя вариантами решения вместо остановки) и остановка на решении, не имеющем экстремального смысла. В то же время методом, предлагаемым в главах 2-4, во всех этих примерах определяе1ся глобальный минимум. В конце главы с применением ЭВМ дается анализ работы программной системы АВРОРА-75М, использующей метод шагового перепроектирования, и приводятся рекомендации по надежной работе этой системы.

Часть III. СОКРАЩЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЗАТРАТ И ОБЪЕМА ПЕРЕРАБАТЫВАЕМОГО ЧИСЛОВОГО МАТЕРИАЛА ПРИ МНОГОКРАТНОМ ПОВТОРЕНИИ РАСЧЕТА КОНСТРУКЦИИ, СВЯЗАННОМ С ИЗМЕНЕНИЕМ ЖЕСТКОСТИ ЕЕ ЭЛЕМЕНТОВ

Глава 6. Экст ремальные комбинаторные задачи усовершенствования алгоритмов расчета статически (кинематически) неопределимых систем

Глава 6 является вводной к последующим главам III части работы, она ггосвяпгена изложению основных установок, принятых при разработке методов, рассматриваемых в главах 7-10, эти установки в равной мере относятся и к главам 11-15, составляющим IV часть нашего исследования.

При реализации поисковых методов оптимального проектирования конструкций основной объем машинного времени расходуется на многократное повторение циклов расчета конструкции и конструирования

несущих элементов. Причем на конструирование обычно приходятся в несколько раз большие затрать! времени, чем на расчет.

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

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

Заметим, что одна и та же элементная или блочная структура матрицы (картина взаимного расположения нулевых и ненулевых элементов или блоков) может отвечать различным стержневым и конечноэлементным системам. Структура матрицы, как известно, связана не с типом и конкретным видом системы, а с топологической схемой конструкции. Топологическая схема представляет собой граф, пояснения о соответствии которого матрице уравнений даны в главах 7-10.

В главах 7, 8 излагаются методы, позволяющие определять оптимальный план решения вычислительной задачи, т.е. ту последовательность ведущих элементов главной диагонали матрицы или ведущих блоков главной квазидиагонали, которой соответствует минимум арифметических операций при решении системы уравнений с разреженной матрицей. Алгоритм, предлагаемый в главе 8, позволяет также эффективно сократить используемый объем памяти ЭВМ. Методы, развитые в главах 9, 10, служат для подготовки к решению тех же задач в условиях применения метода сил. Полученный для одной из стержневых или конечноэлементных систем оптимальный план решения уравнений мэжет быть затем использован для любой другой системы, имеющей ту „же топологическую схему. Таким образом, применение методов, разработанных в главах 7-10. дает основу для постепенною накопления библиотеки оптимальных планов, т.е. для самосовершенствования автоматизированной системы оптимального проектирования в процессе ее эксплуатации.

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

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

Глава 7. Минимизация числа арифметических операций в задачах с разреженными симметричными положительно определенными матрицами

Сформулированы три экстремальные комбинаторные задачи о мпкимн-!ании числа арифметических операций при обращении, факторизации матрицы и при решении уравнений с этой матрицей. Рассматриваются симметричные (структурно и численно) разреженные (со значительным количеством пулевых элементов) положительно определенные * хорошо обусловленные матрицы нерегулярной структуры, характерные для строительной механики стержневых и конечноэле.ментных систем и наиболее экономные по трудоемкости их преобразования (схема единственного деления метода Гаусса или схема Холецкото с выбором ведущих элементов только на главной диагонали). Последовательность решения вычислительных задач интерпретирована модификацией (изменением структуры) матрицы инциденций (получаемой заменой ненулевых элементов рассматриваемой числовой матрицы единицами) и соответствующей этому модификацией неориентированного графа, матрицей смежности вершин которого является матрица инциденций. При использовании очередной строки числовой матрицы как ведущей соответствующая ец строка матрицы инциденций логически суммируется с каждой из тех ее строк, в ведущем столбце которых стоят единицы; ведущие строка и столбец устраняются (вычеркиваются) при факторизации, при обращении матрицы они остаются на своих местах. Аналогично этому ведущей строке

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

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

Теорема 1. Любой план на графе мажорирует тот же план на его суграфе по значению функции трудоемкости.

(Множества вершин графа и суграфа совпадают, но часть ребер графа отсутствует в суграфе.)

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

(В полном графе каждая вершина соединена ребрами, т.е. смежна, со всеми остальными. Свободная вершина полного подграфа имеет совпадающие степени смежности в подграфе и в графе.)

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

Однако, н после это го дополнения алгоритм непосредственною построения плана (простой и легко реализуемый) в общем случае не позволяет получить оптимальный ri tun. Он целесообразен при малой пов1 оряемос 1 и вычислительной задачи. При большой повторяемости (серийности) решения задачи с матрицей заданной структуры, как это имеет мест при решении задач, рассмотрении* п главах 2-5, целесообразно минимизирован, функции трудоемкости с использованием методов

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

Разработаны все необходимые элементы решения экстремальных комбинаторных задач о поиске оптимальных планов решения вычислительных задач с применением метода ветвей и границ:

1. Указано правило ветвления исходного множества планов на непересекающиеся подмножества.

2. Для определения планов в исходном множестве и в его подмножествах используется алгоритм минимальной степени с указанными выше дополнениями.

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

4. Доказана неухудшаемость этих оценок в процессе ветвления (теорема 4).

С использованием неориентированного графа, соответствующего. симметричной разреженной матрице 22-го порядка, проиллюстрированы все детали реализации методов, разработанных в настоящей главе, применительно к решению системы уравнений по схеме единственного деления алгоритма Гаусса. Результаты примера показывают существенный выигрыш в трудоемкости решения вычисли 1ельной задачи при использовании предлагаемых меюдов определения плана задачи по сравнению как с прои¡вольным планом решения, так и с планом, построенным по алгоритму ' минимальной степени.

Глава 8. Сокращение времени счета и используемого объема

памяти ЭВМ при расчете кинематически неопределимых систем, имеющих топологическую схему в виде I рафа-реше тки

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

Рассматриваются линейно деформируемые плоские и пространственные стержневые системы, осевая схема которых топологически эквивалентна

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

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

Структуру разреженной матрицы уравнений метода перемещений (матрицы реакций) определяет матрица инциденций, получаемая из первой заменой ненулевых блоков единицами, нулевых - нулями. Ленточная структура матрицы инцидецций с минимальной шириной ленты, очевидно, реализуется при последовательной сплошной нумерации узлов решетки вдоль узкой ее стороны (в пространственном случае первой нумеруется плоская решетка с наименьшими размерами сторон, затем, последовательно, плоские решетки, параллельные первой).

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

Так как матрица реакций симметрична, то формируется только, например, нижняя часть ленты (включая главную диагональ), после прямого хода метода Гаусса сохраняется лишь левый треугольный сомножитель, т.е. ленточная часть нижней треугольной матрицы (на месте исходной полуленты). Пусть N - число вершин в каждом ярусе плоской решетки, М - число ярусов (./V < М), тогда для матрицы инциденций ширина ленты Н — N+1, порядок матрицы п~ N М, число хранимых элементов V] = N М(Ы +1). Общее число блочных операций прямого хода равно

/! = +ЗЛ0(ЛГ М-Л0+А(//3 +ЗЯ2 -4/0.

2 .6 Приведенная формула не учитывает операции' внутри блоков ведущего квазистолбца, что не сказывается на результатах дальнейшего сопоставления, алгоритмов..

Пусть в пространственной решетке Ь - число . плоских решегок (Лт < А/ 5 тогда Н = N М +1, п = N МЬ и показатели можно

опреде/ить по тем же формулам, заменив Аг на N М, Л/ на Ь.

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

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

Число взаимно несмежных узлов решетки, нумеруемых на первом этапе, как нетрудно- проверить, определяется следующей формулой: К = 0,5(л + т), где для плоских решеток п = N М, для пространственных п = N М L\ т = 1, если А7 и А! (и L) нечетные, в противном случае т - 0.

Матрицы, соответствующие такой нумерации, имеют следующие особенности:

1. Первые К столбцов и строк Матрицы ннциденций оказываются HsatiMHo несмежными, т.е. ríe' содержат ненулевых побочных элементов в подматрице, образованной этими столбцами и строками. Поэтому на прямом ходе метода Гаусса структура первых É блочных столбцов матрицы реакций не изменяется и после преобразования (пересчета элементов), выполняемого только внутри ненулевых блоков этих столбцов, определяются первые К блочных столбцов левой треугольной матрицы разложения.

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

3. Регулярность двухэтапнон нумерации определяет регулярную структуру матриц пнннденцнй. что обеспечивает простую систему адресации при программировании метода Гаусса с учетом плотного хранения ненулевых элементов (блоков).

Общее число хранимых блочных элементов матрицы реакций равно Vi = Ka + (п - К)b. для плоских решеток а = 5; b — N + 1, для пространственных - й = 7, b-N Л/т i. Учитывая формулы для Vj и К и принятые обозначения, имеем при N или М (или L) четных для плоских решеток

когда N, М (или L) нечетны, приведенные формулы дают результат незначительно меньше действительного.

-N +1

v = — = 2----, для пространственных v =

vs /V + 6

Таким образом, при достаточно больших N (и М) используемый объем оперативной и внешней памяти ЭВМ для ленточного алгоритма примерно в 2' раза больше, чем для рассматриваемого.

Общее число блочных арифметических операций для матрицы реакций

составит /2 =—/N М+ЪИ)(}-Ы М-Я)+ ЗЫ2 -4Ы). 2 2 2 6

Эта формула так же, как й формула для /у, не учитывает операции внутри

блоков ведущего квазистолбца.

По приведенной формуле можно определить показатель также и для

пространственной решетки, заменив N на N М, М на Ь, причем для плоской решетки /= 14, для пространственной / = 27. Для случая нечетных N и М (и Ь) этг формула дает результат несколько больше действительного. .

В нижеследующей таблице приведены значения отношений (р = f■¡L

для плоских ((рп ^ и пространственных ((рпр) решеток при N — М — Ь.

' N 3 4 t. 10 20 30 40 100 1000

<Рпл 0,73 1,00 1,73 1,94 1,99 2,00 2,00 2,00

<Рпр 1,47 1,98 2,14 2,07 2,05 2,03 2,01 2,00

. Программа LEDA (ленточную матрицу декомпозирующий алгоритм), составленная автором на языке PL-1 и реализованная в операционной системе OS-IBM-360 на машине ЕС-1022 в вычислительном центре Промстройпроекта подтвердила достоверность и надежность рассмотренного алгоритма. Время работы определялось с помощью встроенной функции TIME. Отношения затрат машинного времени и теоретические значения показателя (р весьма близки.

Преимущества алгоритма, LEDA перед ленточным очевидны и для обратного ходя метода Гаусса, для метода Холецкого й для вычисления определителей матриц.

Алгоритм LEDA может найти преимущественное применение при расчете континуальных систем по стержневой аналогии, а также при расчете электрических сетей и других физических объектов, основным элементом -расчетной схемы которых является граф-решетка. Кроме того, при разбиении пластины на треугольные конечные .элементы и трехмерного массива на тетраэдры нумерация вершин получаемых графов по системе LEDA приводит- к аналогичному рассмотренным случаям сокращению трудоемкости и объема хранимого и перерабатываемого числового м.перихча. т.е. машинного времени, оперативной и долговременной памяти, а также числа и длительности обменов между ними.

Глава 9. Экстремальные комбинаторные задачи локализации

базисных циклов графа в связи с формализацией метода сил

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

Степень разреженности матрицы уравнений метода сил определяется особенностями топологической структуры статически неопределимой стержневой системы и конкретными приемами их учета при составлении уравнений. Замкнутый жесткий контур системы (включающий, возможно, опорное основание) может быть использован для построения координатных функции метода сил: трех - при плоском деформировании контура, шести -при пространственном. Контуру системы соответствует простой цикл ее графа. (В простом цикле не повторяются вершины, а следовательно, и ребра графа.) Если соединения всех элементов жесткие, то, назначив базисные циклы графа и используя соответствующие им стержневые контуры, можем получить полный набор координатных функций. При этом структура матрицы смежности базисных циклов (расположение нулей и единиц в этой матрице) совпадает с блочной структурой матрицы уравнений метода с^л. Если отдельные соединения системы допускают свободные взаимные перемещения элементов (без нарушения геометрической неизменяемости), то приравнивание пулю соответствующих усилий, выраженных через лишние неизвестные базовой системы, все соединения которой жесткие, определит 'однородные уравнения, позволяющие выделить нужное подпространство в базовом пространстве усилий и перейти от координатных функций базовой системы к координатным функциям исходной. Для конечноэлементных систем те же вопросы решаются совершенно аналогично.

Формирование базиса циклов графа может быть выполнено алгоритмически. Таким образом, при указанном подходе применение метода сил не связано с какими-либо неформальными операциями, предшествующими расчету, и в этом отношении подобно использованию метода перемещений (задача рациональной нумерации неизвестных при разреженной матрице уравнений характерна для обоих методов). Однако, для координатных функции метода сил не специфична локальность, что так характерно для метода перемещений. Возникает задача локализации базисных циклов графа для получения разреженной матрицы метода сил.

Циклы базисов В и /? графа С можно поставить во взаимно • однозначное соответствие так, что циклу С; из В будет соответствовать цикл

ц ] из р. в разложение которого по базису В входит цикл С,- (¿,_/ = 1, 2,..., /»,.

где т - циклический ранг графа С ); при этом совпадающие циклы будут

соответствовать друг другу. Доказательство этой леммы основывается на возможности выявления последовательно вложенных один в другой (с уменьшением порядка на единицу) ненулевых дополнительных миноров к единичным элементам невырожденной квадратной матрицы из единиц и нулей, строки которой соответствуют разложению циклов базиса Р по базису В, столбцы - циклам базиса В.

Обозначим: я,- - степень смежности /-го базисного цикла, т.е. число

базисных циклов графа (? (включая и сам цикл г), с которыми смежен (имеет

т

общие ребра) /-й базисный цикл; £ = 2 -У; - показатель взаимной смежности

базисных циклов ( т = т(С) - циклический ранг графа Сг ). s¡ равно числу

единиц в г-й строке (г-ом столбце) матрицы смежности базисных циклов, Л' равно числу единиц во всей этой матрице. ■ Базис В0 графа С? назовем

оптимальным, если Б (Во) < 5(В), где В - произвольный базис того же графа. Циклический ранг графа равен' т = д — р + г, где д - число ребер, р - число вершин, г- количество независимых связных компонент графа; для связного графа г= 1.

Если из связного графа (7, имеющего д ребер и р вершин, устранить все П£ ребер простого цикла С (вершины не устраняются), то циклический ранг

полученного графа Н определит число независимых циклов, которые можно построить в графе (7, не используя ребер цикла С,

т(Н)-(д-пс)-р + Г/у = т(Сг)~(пс ~ тн + \) - т(Ц) - ас,

здесь г /у - число компонент графа Н.

Следовательно, если цикл С - базисный в графе С, то при любом выборе других базисных циклов этого графа по меньшей мере сгс базисных

циклов с необходимостью будут включать ребра цикла С и

яс>ас =пс-тн+1 .

Таким образом, (7^ — это минимально возможная степень смежности

базисного цикла С с циклами базиса графа С.

После этого предварительного рассмотрения в главе 9 доказывается следующая теорема, определяющая достаточные условия оптимальности

базиса циклов графа. Базис В0 графа <7 оптимален, если для его циклов С'(-'

(/= I. 2,.... /•), С^ (] = г + \, г +2,..., т) выполняются следующие достаточные } еловая:

1. s(C-) = er (С,0) < а (С,) , ¡=1,2!..., г < m, гф 0;

2. при г < т

а) л(Су) = cr(Cj) + 1 < а(Су), Cj*C®. j~ г J-\, г +2.....т:

• О) ff (С?) < сх(Си)-,1и- <т(С,°) + 1 < а(С,)-»,.; С,*С)\

где н„, л,. - число неравенств л(Су)> cr(Cj), превращающихся в равенства после замены в базисе только одного цикла CÜ (или С^) на цикл С;/ (соответственно, - С,.), £ = 1, 2,..., г; /= г +1, г +2,..., /;г.

В условиях 1. 2 в соответствии с леммой С,. Су, С„, С, - простые циклы графа G, в разложение каждого из которых по оазису 50 входит соответственно цикл С/*. Cj, Cj!, Cf. Приведем здесь лишь часть доказательства этой теорелдл по условию 1 при г = т. Действительно, в этом

т т Iii

случае имеем 5(S0) = £ cr(Cf) < £ ст(С,) < 2 j(C,) =S(B) и базис Б0

Ы /=! ;=)

оптимальный. Здесь С, (/ - !. 2..... т) - циклы произвольного базиса В

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

Граф напивают плоским, или планарным, если его можно уложить на плоскости (ила па сфере) oei самопересечения ребер.

Так как циклический ранг плоского грифа G равен числу его граней (дли кргикости будем наьмзать гранями только внутренние грани, внешнюю грань назовем контуром графа), то показатель сгс для произвольного простого цикла в плоском графе определяется так:

т(]1) =■ m(G) - (ьге + gc )+Гс = "'(б) - 0-е - °С = Sc + Sc ~ Г с >

здесь g^, g^ - число граней графа G, смежных с циклом С и расположенных соответственно внутри и вне этого простого цикла; у с - число

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

g^—VC' TilK кпк ГР:1НЬ графа G, смежная с циклом С и

расположенная вне (или внутри) этого цикла, не может быть слагаемым

более, чем одной новой грани графа Н, а новая грань может иметь своими слагаемыми и несколько тех (или других). Отсюда следует:

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

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

у £

граней не возникает, у с ~ ® и> следовательно, а £ — g(-■ + ; для циклов

С? базиса Вц, определяемых границами граней, с £ — 1 + ££(С0), /=1,2,..., т.

Грань с циклом С® и все грани, с ней смежные, смежны с циклом С,-, в разложение которого по базису В0 входит С/, так как грань с циклом С? расположена внутри цикла С; (как одно из его слагаемых) и в случае, если грань, с ней смежная, расположена вне С,-, то цикл С; проходит по ребру смежности этой грани и грани с циклом С?. Здесь имеется ввиду, что циклы С,- ( / = 1, 2, ..., т ) принадлежат произвольному базису рассматриваемого графа и в соответствии с леммой могут быть поставлены во взаимно однозначное-соответствие с циклами Cf ( / = I, 2, ..., ш ) базиса В0. Следовательно, граней, смежных с каждым циклом С,-, не меньше, чем

Г*о

смежных с соответствующим ему циклом С,-, т.е. ¿(С¡) = 1 + ст(С?) < + ЕЕ{С1) = £7(С,), /=1,2,..., т .

Таким образом, выполняется условие 1 теоремы при г = т.

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

показателей ас вместо степеней смежности базисных циклов и на учете

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

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

Глава 10. Формирование системы локализованных базисных циклов непланарного графа

В главе 10 с использованием понятий прикладной топологии излагается содержание и прорабатываются детали приближенного метода локализации базисных циклов непланарных2 графов.- Цели и установки, связанные с формализацией метода сил, здесь те же, что и в главе 9.

Если род г графа и алгоритм его укладки известны, то граф-блок, имеющий р вершин и д ребер, можно уложить на замкнутой ориентируемой поверхности класса к - г с образованием полиэдра (многогранника), каждая грань которого гомеоморфна кругу (может быть превращена в круг деформацией). Число граней полиэдра Г = /»1 + 1 — 2г определяется формулой Эйлера р-д + Г = % = 2-2к, здесь % - эйлерова характеристика, т = д — р+! - циклический ранг связного графа, т.е. блока3.

Будем называть грань полиэдра тривиальной, или /-гранью, если на ее границе не повторяются ни вершины, ни ребра, в противном случае грань будет нетривиальной, или п-гранью. Границы /-граней (/-циклы), гомологичные нулю (стягивающиеся в точку), независимы друг от друга как циклы внутренних гранен плоского графа. Кроме того, могут быть указаны независимые друг от друга и от /-циклов 2 г циклов-образующих группы одномерных гомологий полиэдра (С-циклы). В главе 10 эта классификация поясняется на примере укладки на торе полного графа .

- Нснланармый граф нелыя уложить . на плоскость (или на сферу) без самопересечении его ребер.

3 Для сферы К-0, для тора к - I, для "кренделя" к — 2 и т.д.

~2-г

Назовем предбазиеом предварительно формируемую систему циклов, из которой п дальнейшем будет получен базис.

Если все грани полиэдра окажутся тривиальными, то в предбазис могут быть включены т+1 циклов: I) все /-циклы (это гомологичные'нулю циклы, их число Г = ш + 1 — 2 г); 2) циклы-образующие группы одномерных гомологии полиэдра (С-циклы, число этих циклов при любом варианте их выбора равно 2/', они независимы друг от друга и от гомологичных нулю циклов), /-циклы предбазиса связаны единственной зависимостью - их сумма нулевая; для получения базиса следует исключить тог Г-цикл, степень смежности которого в предбазисе наибольшая. Результаты локализации зависят от принятой укладки графа и от конкретного выбора С-циклов.

В главе 10 приведены укладки полного графа К-; и полного

двудольного графа з при наличии в укладках только тривиальных граней.

Здесь же указаны развертки полиэдров, назначенные С-циклы. исключаемый /-цикл и числовые данные; дана также укладка полного графа К5, при

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

Если в полиэдре имеются нетривиальные грани («-грани), то в предбазис могут быть введены циклы-границы не только тривиальных (/-циклы), но и нетривиальных граней («-циклы). Если на границе и-грани повторяются лишь вершины, но не ребра, то «-цикл - эйлеров граф. т.е. замкнутая цепь, содержащая все вершины и ребра /¡-цикла. Если на границе «-грани имеются повторяющиеся ребра (каждое из них - участок границы «-грани самой с собой и поэтому повторяется ровно два раза), то /¡-циклом, соответствующим такой «-грани, назовем граф, определяемый вершинами и ребрами ее границы после устранения пз нее всех повторяющихся ребер. В общем случае он будет представлен несколькими компонентами, каждая ш которых - эйлеров граф.

Как известно, множество ребер эйлерова графа можно подразделить на простые циклы, не имеющие общих ребер, «-цикл, представляющий собой в общем случае несколько компонент с такими группами -.простых циклов (циклический вектор), можем принять за 'базисный вектор (цикл) в пространстве циклов (циклических векторов) исходного графа.

Полная сумма всех /- и «-циклов полиэдра нулевая и никакая частичная их сумма не может быть нулевой,- так как каждое ребро полиэдра принадлежит ровно двум циклам, включенным в предбазис. Следовательно, все и и /¡-циклы (их число равно V — т + \ — 2г) связаны единственной зависимостью: каждый из них есть сумма всех остальных. Исключая из

предбазиса один (любой никл), получаем т — 2г независимых циклоп, каждый из которых гомологичен нулю: любая I- или /(-грань (в том числе и и-грань с устраненными повторяющимися ребрами ее границы) отделяется от остальной части поверхности при разрезе по циклу-границе" грани. Дополнение такой системы циклов 2г циклами-образующими группы одномерных гомологии полиэдра (С-цикламн), независимыми друг от друга и от гомологичны\ нулю циклов предбазиса, позволило бы получить базис пространства циклов графа.

Далее в главе 10 используется иной путь получения базиса, при котором все оазисные циклы становятся простыми.

Случай, когда в полиэдре имеются нетривиальные грани, проиллюстрирован примерами; приведены схемы и укладки графов; указаны: /■-никлы, С-циклы. разбиения /г-циклов на несмежные простые циклы, набор простых циклов предбазиса, зависимость между ними (равенство нулю суммы соответствующих циклов), цикл, исключаемый из этой зависимой группы, числовые результаты.

Часть IV. .МЕТОДЫ ПЕРЕРАСЧЕТА МНОГОКРАТНО СТАТИЧЕСКИ ИЛИ КИНЕМАТИЧЕСКИ НЕОПРЕДЕЛИМЫХ СИСТЕМ ПРИ ИХ МОДИФИКАЦИИ

Глава 11. Постановка вопроса. Перерасчет системы при однократной модификации

В данной главе и в следующих двух главах рассматривается локальная жесткостпая модификация многоэлементной многократно статически (кинематически) неопределимой системы, т.е. изменение жесткости относительно небольшого количества ее элементов, но произвольное по величине: возможно увеличение жесткости до бесконечности и уменьшение ее до нуля с выпадением элементов из системы. Имеется ввиду, что результаты расчета исходной системы сохранены. В этих условиях вместо нового полного расчета модифицированной системы может быть выполнен экономный компактный перерасчет. В данной главе имеется ввиду однократный перерасчет , в г лавах 12, 13 рассматривается многоэтапный последовательный процесс перерасчета.

Запишем матричное уравнение метода сил или перемещений в общем

виде МУ + К = 0, где М = а'(ра~, У-столбец неизвестных; а - матрица координатных лекторов: <р - матрица податливости или жесткости. При узловой на/рузке для метода сил Р = и'<рЬ, для метода перемещений Р--Я \ Ъ - столбец усилий в основной системе метода сил; Л - столбец узловых шнруэок. (В I ,;нс 1! кроме узловой нагрузки учитывается внеузловая. температурные и начальные деформации, заданные перемещение.)

Устраняя из уравнения, записанного для модифицированной системы,

(М + ДМ)(У + А У) + (Е+ А/) = О

нулевую левую часть исходного уравнения, получаем V

(М + АМ)ДУ + ДЛ/7 + А^ = 0,

ДМ = а А(ра = а,ь

для метода сил Д/"" = а'АсрЬ — а^ А<р¡, ; для метода перемещений ДF = 0.

Индексом И здесь обозначены матрицы со строками и столбцами, относящиеся только к модифицированным элементам системы. Имеем

(М + а), А<р,, а,,) А У + а), А<рь / = 0, для метода сил / = «Л У + Ь/,; для метода перемещений / = а/( У.

ДУ= -(М+ А«»а «/,)"'«;, Др„/= -М^Я^А^А/-' здесь Е„ - единичная матрица, порядок которой п равен степени

неопределимости системы.

Справедливо следующее тождество:

(Еп + аР)~1а = (.Е„ + арГха{Ек +ра){Е,, +/?«)"' = = (£„ + а р)~х (а + а р а)(Еь + р а)~] = = (Еп+ар)-\Еп+аР)а{Е,1+ра)->=а(Е,1+рау-\ Здесь Е), - единичная матрица порядка И (/? < и), размеры матриц а - п х И, Р - Их /г, все матрицы - двучлены невырожденные. Используя это тождество при а = ; /?= АЯ/, Л/-1, получаем

АУ= -М~ха\ {Еь+АрМ^а'^Ар,,/. Вынося Д(р)х за скобку, имеем окончательно

ДУ = -М-'а), ( Д^л'+яа Л/-1«;,)-1/.

V

Символ обращения матрицы М означает здесь операцию прогонки (выполняемую один раз) квазистолбца а'^ через треугольное разложение матрицы М, сохраненное после расчета исходной системы. Матрицы адА известны. При локальной- модификации многоэлементной многократно неопределимой системы Л « п, матрица, записанная в скобках, имеет малый порядок, матрица М + АМ не формируется и очевидно, что применение

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

Формульц подобные приведенной, впервые получены Аргиросом и Келен (Англия) в 1956 г. с использованием при 1шводе механической интерпретации. Здесь приведен чисто алгебраически/! вывод этой формулы, яанный автором настоящей работы в 1968 г.

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

Глава 12. Перерасчет статически (кинематически) неопределимой системы при се многоэтапной последовательной модификации

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

А по'формуле

Ат=А+ХЗУ

( в обозначениях главы 11 Ат = Мт - М + ДМ = М +а' &<Р/, Я/, ). где

X, У-прямоугольные. 51-квадратная матрицы.

Учитывая, что порядок £ много меньше порядка А и что на первом этапе система уравнений решается методом Гаусса или Холецкого с разложением исходной матрицы на треугольные сомножители, на каждом из этапов перерасчета целесообразно заменить формирование и полую факторизацию модифицированной матрицы корректировкой (пересчетом) результатов факторизации, использованных на предыдущем этапе.

Преобразование треугольных сомножителей при модификации матрицы определяет следующая теорема. Пусть известна факторизованная квадратная матрица А = Р() порядка п, где Р - левая, £) - правая треугольные матрицы, по главной диагонали расположены единицы. Тогда факторизация того же типа невырожденной матрицы А,„ = А+Х£ У =

= Рт <2Ш, где матрица X имеет размеры п х И , У - размеры И х п 5 -

квадратная невырожденная матрица порядка /г, /? < и, определяется следующими выражениями:

е„, = 0+(;>- Х)и ([]„ + 2)-' ' - £)(у<о,

Здесь [5"*']„ - квазнднагональная матрица с п одинаковыми квадратными

блоками 5 й - левая квазитреугольная матрица, все ненулевые блоки которой - единичные матрицы порядка А. Так, при п = 4, /г = 1

I 0 1 0 0 0

1 1 1 -1 1 _ _ 1 1

, вГ' = , Е-со ' = 0 I

1 1 1 0 -1 1

1 1 1 1 0' 0 -1 1 0 0 1 0

со =

Индекс означает последовательное разбиение соответствующей матрицы на блоки и формирование их них квазидиагональной матрицы. При этом размерам матриц п х 1г ,Нхп,И х к п соответствуют размеры блоков 1х А , А х1, А х/?.

При доказательстве этой' теоремы вначале устанавливается, что Рт, Qnl - треугольные матрицы- того же типа, что и Р, <2. Для невырожденной матрицы Ат такое разложение единственно. Затем при использоватт»

свойств введенных матриц &>, Е — со~1 с помощью матричных преобразований доказывается, что' Р»^,,, =Ат. Теорема остается в силе и для матриц с комплексными элементами.

Операции Р~ХХ и означают решение систем уравнений С

треугольными матрицами Р или <2' и квазпст<5лбшшн свободных членов X или У'. Учитывая строение матриц (Р~]Хсо: со'-Е,

нетрудно убедиться, что левая квазитреугольная матрица Р(Р~1 X) .¡со (и

правая квазитреугольная матрица с нулевой главной квазидиагональю

{со' — Е)(У()~1)С10_ ) формируется в процессе решения указанных систем

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

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

Если А значительно меньше п, то анализ указанных формул показывает, что при их использовании значительно сокращается трудоемкость по сравнению с формированием и полной факторизацией модифицированной-

матрицы Ат. Указанный эффект определяется решением уравнений с известными треугольными матрицами и с квазидиагональной матрицей и тем, что сама матрица ~ЛШ"при'этом''не формируется.- - ------- -------

В главе 12 рассматриваются обобщения и частные случаи корректировки результатов факторизации матриц, анализируется эффективность вычислительной схемы корректировки. Для случая, когда £ - вырожденная матрица (что характерно для одной из форм метода конечных элементов), развивается схема корректировки для специальной формы факторизации матрицы, названной субспектральной.

Далее этот математический аппарат применяется к процессу последовательной многоэтапной модификации дискретных систем, включая случаи введения в систему новых элементов и устранения части существующих.

Глава 13. Критический анализ алгоритмов многоэтапного перерасчета статически (кинематически) неопределимых систем

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

Так, весьма характерно мнение, что алгоритм Аргироса-Келси непригоден для многоэтапного перерасчета (Собесчанский Дж. Матричный алгоритм для модификации конструкций, основанный на понятии параллельного элемента. Ракетная техника и космонавтика, 1969, N II), против чего не возражает и Аргирос (Аргирос Дж., Бренлунд О., Рой Дж., , Шарпф Д. Прямая процедура модификации для метода перемещений. Ракетная техника и космонавтика, 1971, N9). Это мнение повторяется в работах других авторов. Полагают, что если на различных этапах модифицируются не одни и те же, а разные элементы, то порядок основной

матрицы . алгоритма Аргироса-Келси + (см. выше),

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

матрицы, но лишь дофакторизация ее дополнительно возникающего окаймления. Конечно, все результаты предшествующих перерасчетов придется сохранять, так как они частично участвуют в перерасчете на очередном этапе. В главе 13 все здесь сказанное пояснено подробно. Таким образом, при многоэтапном перерасчете алгоритм Аргироса-Келси, преобразованный в главе 13, весьма эффективен по вычислительным затратам по сравнению с прямыми расчетами системы, но требует увеличения используемого объема памяти. Заметим, что алгоритм, рассмотренный в главе 12, не имеет этого недостатка, так как сохранять результаты предшествующих этапов перерасчета здесь не требуется.

Схема последовательного перерасчета дискретной системы при ее многоэтапной модификации впервые была предложена в упомянутой выше статье Собесчанского (США) в форме алгоритма параллельных элементов. Во второй отмеченной выше работе (Аргирос и др.) этот алгоритм оценивался как значительно более экономный по числу требуемых арифметических операций, чем полный новый расчет системы, выполняемый на каждом этапе модификации. Возможность противопоставления этого алгоритма как более эффективного алгоритму Аргироса-Келси. при не слишком малом количестве последовательных модификаций рассматривалась как прямое следствие модели параллельных элементов, использованной при выводе матричных формул последовательного перерасчета. В главе 13 показано, что оба эти положения не верны, хотя, исходя из выводов статьи Собесчанского, они в той или иной форме были повторены в последующих работах других авторов. Показано, что матричные формулы алгоритма параллельных элементов могут быть выведены чисто алгебраически без привлечения механической модели (как в главе 12 и формулы алгоритма Аргироса-Келси - без механической интерпретации, использующей понятия дополнительно задаваемых напряжений или деформаций). Кроме того, показано, что оба эти алгоритма взанмопревращаемы один в другой матричными преобразованиями. В алгоритме Собесчанского имеется целый ряд излишних операций, и есди их устранить, то он превратился бы в алгоритм Аргироса-Келси в той преобразованной редакции, которая ему придана в данной главе:

На характерном содержательном примере, заимствованном из статьи Собесчанского, продемонстрированы те положения, которые предварительно обоснованы в общем виде: алгоритм Собесчанского существенно менее эффективен, чем прямой расчет системы на каждом этапе модификации: преобразованный нами алгоритм Аргироса-Келси и тот алгоритм, который рассмотрен в главе 12, вполне конкурентоспособны: при относительно небольшом (10-20) количестве этапов модификации экономнее первый, при большем их числе -. второй. Оба эти алгоритма весьма экономны по трудоемкости при локально^ поэтапной модификации системы по сравнению с прямым расчетом на каждом этапе.

Глава 14. Итерационные процессы перерасчета стержневых и 0 конечиоэлемет пых систем при их модификации

Если изменяется жесткость многих или всех элементов системы, но не слишком резко, то вместо прямого решения уравнений Мт Ут + Ет =0, отвечающих модифицированной системе (принадлежность матриц этой системе отмечена индексом т), удобно использовать алгоритм обобщенного метода простой итерации

С+1> = Г^~С(М„, Г™ +Рт), к = о, 1, 2,...

В указанных условиях можно реализовать спектральную оптимизацию этого итерационного процесса. Полагая С - аМ ', имеем

У^Л) = М-1Г„, + ТУЬк), Т = Е-аМ~{Мт, У,(и0) = У.

Здесь У- столбец неизвестных метода перемещений или сил, полученный при решении уравнений, соответствующих исходной системе МУ + Е = 0.

Операция Л/-1/ соответствует прогонке столбца / через треугольное разложение матрицы М, известное из расчета исходной системы.

Так как матрицы М и М т симметричные положительно

определенные, то М-1 Мт - матрица простой структуры (имеет полную систему собственных векторов, приводится к диагональной форме) и все ее собственные значения //положительны. При этом Т - также матрица простой структуры с той же системой собственных векторов и все ее собственные значения Лвещественны: А,- = 1 — а (1=1, 2, ..., п );

п - порядок матриц М, М 1п, Т.

Необходимые и достаточные условия сходимости рассматриваемого итерационного процесса — 1 < 1 — а< 1, или 2 —«/¿,>0; аг//(->0

( / = I, 2...../?) означают, что процесс сходится тогда и только тогда, когда

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

Е + Т-2Е-аАГ1Мт=аМ~1(2а~1М-Ми1) и Е-Т=аМ~1Мт.

Учитывая, что а>0 н вновь используя утверждение, только что

примененное к произведению Д/ ' Мт. устанавливаем, чю для выполнения

\ка!анното требования необходимо и достаючно. чюпы симморнччая м прчна

Л' -- Л/ - Д1,, - </(2//"'с' -(,",„)</ - п'ч/а

была положительно определенной. (Здесь а - матрица координатных векторов метода премещений или сил, <р - матрица жесткости или податливости.) Для соблюдения последнего условия достаточно, чтобы была положительно

•> -1

определенной симметричная матрица Ц/=1а (р~(рт , так как тогда-ее

можно разложить по схеме Холецкого: у/ = С'С и, учитывая, что столбцы матрицы а линейно независимы (исходная и модифицированная системы геометрически неизменяемы), (7 - невырожденная квадратная матрица.

получить матрицу N = (Са)' (во) как положительно определенную матрицу Грама для системы линейно независимых векторов - столбцов матрицы С а.

Каждый г-й диагональный блок квазидиагональной матрицы <р представлен произведением числа сг; на квадратную симметричную положительно определенную матрицу А,-. (Здесь имеется ввиду невырожденная матрица

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

модулей Юнга, моментов инерции и площадей поперечных сечений стержней, деформации сдвига которых несущественны, или модулей Юнга конечных элементов и толщин элементов, рассчитываемых по двухмерной модели), то

каждый диагональный блок квазидиагональной матрицы у/— 2а~1(р — (рт будет представлен произведением числа 2а~[а, -а1т на матрицу А,- и матрица у/ будет положительно определенной при выполнении условия 2а~'сг1- — <т/,„> 0 для всех ее диагональных блоков (в главе 14 рассмотрен и общий случаи).

При использовании метода перемещений О",- = с, у, ат = с,- у ¡т, при использовании метода сил О"; -(С/Х/) ^ <т;/), = (с, у ,/м)~', где у, > 0. ут > 0 - упомянутые выше параметры жесткости стержня или конечного элемента, с,- - положительные константы. Следовательно, для сходимости

рассматриваемого итерационного процесса достаточно выполнение следующих неравенств:

при расчете методом перемещений

а<2гтп{у ¡¡у ¡п$ = 21т&х(у ¡т1у ¡) = 2Ц ;

I I

при расчете методом сил

а < 2min (у ¡т /у ¡)~2г ,

/= 1,2, ...,ni; т — число диагональных блоков матрицы у/.

В главе 14 далее доказано, что за норму матрицы Т можно принять

максимальный из модулей ее собственных значений тах|Л,-1 =

/ 1 '

= max|l — «//,•) (аналогично нормамн матриц М-|М,(1 и (Af'M,,,)-1

i

будут соответственно // ( = max М ¡ >Q и f.1^1 =(niin и ,•)"' > 0 ). Гак как

i i ' .

ошимальное значение а о параметра а соответствует минимуму нормы

] 1

матрицы Т, то из решения задачи о минимаксе min шах 1 — а/л А при

а i

ограничениях -1 < Я,= 1 -a ßj < 1 или 0 < а ßj <2 ( i = 1,2, ..., п ) следует 2

а0=--. Указанные ограничения определяют необходимое и

Mi +Мп

о 2

достаточное условие сходимости итерационного процесса U < а < —.

М |

Если исходную и модифицированную системы поменять местами, го T~E-ß(M 1М ,„) > 0, необходимое и достаточное условие

сходимости процесса определится неравенствами 0</?<2ß п\ достаточные условия сходимости запишутся так: при расчете методом перемещений

ß < 2min (/;,„/7;) =■ 2г, при расчете методом сил

/

ß < 2 min (у ( / ^ ¡т) = 21 q. Учитывая, что достаточные условия сходимос ти

i

сильнее (точнее, не слабее) необходимых и достаточных условий, получаем для метода перемещений а <2!q<2!ß\, ß <2r <2 ß „. Отсюда получаем границы отрезка вещественной положительной полуоси, который содержит спектр матрицы М_1М/м, q> ß „>г>0 и приближенное решение задачи спектральной оптимизации итерационного алгоритма ■

2 2 2

а{) =а0(?, /■)=-<-<— .

4 + г /у,

Аналогично для метода сил

->//,>//„>-->0, а0 = «о(?- = —-<2г<— . г (] <7 + г //,

Зная границы отрезка, содержащего спектр матрицы М можно

оценить с погрешностью в сторону увеличения число обусловленности этой матрицы цх! ц п<д! г.

Но обобщенный метод простои итерации эквивалентен обычному методу простой итерации (когда принимается С = аЕ)., примененному к

уравнению с матрицей М '.Мш:

М-'(М„, ¥,„ +Ет) = М~%Мт Гт + ЛГ Ч, =0.

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

При этом условии малость нормы вектора погрешностей определяется малостью нормы вектора невязок

& = М-\{М + Ш) +/•„,] = У,<*> + АГ'(ЛЛ/ Г™ +Ет),

который вычисляется на каждом шаге алгоритма.

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

Глава 15. Интерполяция векторов состоянии в пространстве вариантов линейной дискретной системы

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

Если к - число конструктивных групп и набор жесткостных параметров г'-й группы может быть реализован в ш,- вариантах, то все

возможные варианты проектируемой системы составят точечное множество к

из п0 = ]~[ точек, расположенных в пределах ^-мерного параллелепипеда.

( = 1

Даже при относительно небольших значениях к и что характерно для технических систем, Пц велико и анализ всех вариантов при проектировании трудно реализуем или невозможен, если расчет каждого варианта системы требует значительных затрат.

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

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

Пусть вектор X состояния дискретной системы определяется решением уравнений

Дх+/ = 0)

где А - симметричная положительно определенная матрица порядка Л^; У ' - столбец свободных членов, и пусть определены неизвестные двух , опорных вариантов

х',--^1/, , х2=>-АЪ1/2.

Представляя приближенное решение уравнений А,^х1П 4- / ,„ =0 для промежуточного варианта ш в виде суммы д:т=Х|+Дх = Х|+Д}!, имеем

Ч = АтАУ + {А,пх\ + /т) = Ат Ьу + И ,

г = Л_)'-Дл- , (Ах = -А~],

<р-и'х- = Ау'Ат А у + 2 А у'к + Ах' Ат Ах , Ау~Ке, 1де и - вектор" не:.язок; у - вектор погрешностей: (р - функция ошибки ( ? - знак транспонирования), К - специальная интерполяционная матрица,

0,5

= Вc + g = Q .

формируемая на основании вектора разности Дг = — ■х'1 • с ~ »1-мерный

столбец аппроксимационных коэффициентов (т < ¡V).

Таким образом,

р=с'(К'А„1К)с+2с'К'к+Ах'АтАх = с'Вс+2с^ + б.

Необходимые условия экстремума этой функции: с\<р

Представляя матрицу А„, в разложении по схеме Холецкого

Ат = (/'(7 , имеем матрицу Грама В =(СК)'СК для системы векторов-столбцов матрицы С А", при линейной независимости которых (иначе -столбцов матрицы К, так как (7 - невырожденная) матрица В будет положительно определенной.

Но матрица 2 В - это матрица вторых производных функции <р по всем элементам столбца с. следовательно, при линейно независимых столбцах, матрицы К функция <р - выпуклая, се единственный экстремум - минимум определяется столбцом

. с0 = -ВЛ.

В главе 15 подробно разбирается вопрос о формировании матрицы К с обеспечением линейной независимости ее столбцов. Рассматриваются три алгоритма интерполяции с использованием вариантов квазидиагональных матриц К, определяющих ступенчатую аппроксимацию вектора Ах. Сопоставляются затраты на вычисления при непосредственном решении уравнений и при интерполяции векторов неизвестных с использованием каждого из трех интерполяционных алгоритмов (с уточняющим итерационным процессом) для уравнений с ленточными матрицами при наличии окаймления. Данные, приведенные в таблицах главы 15, позволяют оценить область эффективного применения алгоритмов интерполяции при порядках матриц от 6 до 105, при тех же диапазонах ширины полуленты Н (Н равна порядковому номеру последнего ненулевого элемента в первой строке матрицы, для ленточных матриц с окаймлением шириной IV вместо Н в таблицах принимается № + Н ). Кроме того, в таблицах варьируется число столбцов свободных членов уравнений и количество числовых элементов на одном участке вектора Ах, принимаемое при его ступенчатой аппроксимации.

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

и относящиеся к ним собственные векторы удовлетворяющие уравнению

И-Л(г) Е)Л(Г) = 0, °

где А - симметричная положительно определенная матрица порядка /V; Е-единичная матрица; О, Г = 1,2,..., Л/.

Для промежуточного варианта, которому соответствуег матрица Дт, принимаем приближенное выражение собственного вектора по формуле:

где с - »1-мерный столбец (т < М); К - интерполяционная матрица, формируемая с обеспечением линейной независимости ее столбцов на основании вектора

/7 - Ь[г) + * О или при (>\г) = -Ь(р Ь ~.Ь\Г) ~ Ф 0 .

С учетом предыдущих уравнений имеем вектор невязок, вектор погрешностей

и = (Ат-А$Е)кс, У-Кс-Й«

и функцию ошибки

<р = и'г=(КсУ(Ат-АУЕ)Кс-(КсУ(лт-Л%Е)и£ = = с'(к'АтК-АУк'ку = с'Вс.

Для того, чтобы столбец С соответствовал нулевому значению згой функции, достаточно, чтобы он удовлетворял однородным уравнениям

Вс-0,

последние определяют ненулевой столбец решений лишь при условии вырожденности матрицы В.

Так как матрица Ат положительно определена и столбцы матрицы К

линейно независимы, то матрицы К*АтК и К* К положительно определены как невырожденные матрицы Грама для систем векторов-столбцов матриц в К (см. выше) и К. Отсюда следует положительность чисел //,■ ( / - 1,2.....m<N), определяемых из уравнения

с£е1 В(м) = скЛ (К'АтК-цк'к}= 0 .

При ступенчатой аппроксимации вектора матрице К придается

кпазиднагональиая форма с диагональными блоками из одного или двух

столонов. следовательно, в этом случае квадратная симметричная мЗ трипа

К(К - квазидщпопальная с диагональными блоками не выше второго порчдкп и лет ко приводится к лиги опальному пилу

ьу

к

'{к'^я

причем г'/ > 0 ( /' =1.2..... /77 ) ввиду положительной определенности

матрицы К Я - ортогональная квазидиагональная матрица той же простейшей структуры, что и К 'К.

Положительные числа /// определяются из условия

с!еЦР- //£) = О

как собственные числа положительно определенной матрицы

р = £>;°'5 я' (А:' л,„ А:) Л £>;05

порядка т< N.

После этого из уравнения 5 г = 0, записанного в форме

определяются векторы Су ^ 0 ( / = 1, 2, .... /77), образующие яолную систему вещественных собственных векторов ввиду положительной определенности симметричных матриц К*АтК, К*К. включая и тот случай, когда //,-будет кратным собственным числом.

При этом значение функции ошибки с учетом последнего уравнения будет равно

' <р-^с\{а- 'Л„, К - [//; -.(,</- х^А 'А'} г, = с\[В(ц ,)]г, +

+(//,. -^)г,' А"А'с, = {и¡-

и после нормирования вектора К С,- по условию с/) =' равно

Следовательно, функция ошибки (р / получит значение, наименее отклоняющееся от нуля, если при определении вектора су использовать то и: чисел //у (/ = 1, 2,..., /77), которое окажется ближайшим по величине к Я^

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

аппроксимационных переменных, т.е. числа элементов столбца с, при - указанном выборе числа //¿ можно ориентироваться на приближенное

значение собственного числа Л ^ , определяемое из 01 ношения Релея:

• * л)"'- '

При ГП - N матрица К - квадратная невырожденная порядка А/, |)( однородная система

к'{а,п-ле)кс=о

имеет ненулевое решение только при условии — ЛЕ^ = 0, и5 которого

следует собственное значение матрицы Ат При л = л ^ решение С0 тщь

уравнения определяет точный собственный вектор так как

предыдущее уравнение эквивалентно следующему:

.(г'(ат-л^е)кс\ = [а„, -= 0 .

' При определении частот и форм свободных колебаний, а также критических параметров нагрузки и форм потери устойчивости , для

консервативной дискретной системы рассматривается уравнение

(с-^г)м)и{г) = о,

где С - матрица жесткости; М - матрица инерционных либо кинематических коэффициентов, обе матрицы квадратные симметричные положительно определенные.

Следуя тем же рассуждениям, получаем соответственно:

<р = с'(К 'С„,К - Л^К 'М,„к)с = с'Вс, ёй В (//) = с1е1 {К 'С т К - ц К1 Мт к) = 0 ,

Остальные положения и основные условия те же, что и раньше,

ОБЩИЕ ВЫВОДЫ

1. В диссертационной работе дана комбинаторная постановка экстремальных задач строительной механики, относящихся к оптимальному проектированию конструкций и к оптимизации процессов расчета многократно статически неопр;делнмызГсистем.

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

3. Дан критический анализ существующих методов оптимизации конструкций в сопоставлении с методом, указанным в п.2. Выполнены контроль и настройка программного комплекса АВРОРА-75М.

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

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

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

7. Дан свободный от механической интерпретации алгебраический вывод формулы экономного перерасчета при локальной' модификации многократно неопределимой системы (формула алгоритма Аргнроса-Келси).

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

9. Дан критический анализ алгоритмов многоэтапного перерасчета систем строительной механики при их локальной модификации. Установлено, что после преобразования алгоритма Аргироса-Келсн, признаваемого непригодным для многоэтапного перерасчета, этот алгоритм и в условиях многоэтапной модификации оказывается весьма эффективным (по вь!числительным затратам) и по этому показателю конкурентоспособным пс отношению к методу, указанному в п.8 (однако требующим существенного увеличения объема памяти ЭВМ при значительном количестве этапов модификации). Установлено также, что так называемый алгоритм параллельных элементов (единственный из предложенных для многоэтапны? перерасчетов) значительно менее эффективен, чем повторяемый на каждох этапе модификации системы полный новый ее расчет.

10. Построены и спектрально оптимизированы итерационные процессь перерасчета дискретной системы при не слишком резком измененш жесткости многих или всех ее элементов. Установлено, что коэффицненть

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

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

!2. Данные в работе взаимоувязанные а одно целое постановки задач и методы их решения можно, по нашему мнению, вполне обоснованно рассматривать как решение научной проблемы: Разработка теоретических основ комплексного решения экстремальных комбинаторных задач проектирования конструкций,- имеющей серьезное прикладное значение.

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

' I. Проблемы оптимального проектирования конструкций. Сзройиздат, 1971 (в соавторстве с А.И.Богатыревым).

2. Zu einigen Grundfragen des Gegenwärtigen Standes der Theorie der Optimalprojektierung von Konstruktionen. V1.1KM, Berichte, Berlin, VEB Verlag für Bauwesen, 1974. (В соавторстве с А.И.Богатыревым.)

3. Расчет статически неопределимых систем при их многоэтапной последовательной модификации. Строительная механика и расчет сооружений, 1975, N 6.

4. К расчету статически неопределимых систем при их многоэтапной последовательной модификации. Строительная механика и расчет сооружений, 1976, N 4.

5. О минимизации числа арифметических операций в задачах с разреженными симметричными матрицами. Ж. вычислительной _ математики и математической физики, 1975, N 5.

6. Корректировка результатов факторизации при модификации невырожденной квадратной матрицы. Ж. вычислительной математики и математической физики, 1978, N 3.

7. Поиск оптимального варианта несущей конструкции с использованием динамического программирования и статистических оценок / Краткое содержание докладов к XXVIII научной конференции ЛИСИ. Изд. ЛИСИ, Л., 1969. ...

8. Поиск оптимальной конструкции в упорядоченной последовательности вариантов ^ минимизацией функции суммарного риска / Труды ЛИСИ, N63. Изд. ЛИСИ, Л., 1970.

9. Экстремальные комбинаторные задачи оптимального проектирования конструкций и реализация их решения на ЭВМ / Труды ЛИСИ, N 68. Изд. ЛИСИ, Л.. 1971.

10. К вопросу о контроле и настройке алгоритмов оптимального проектирования конструкций / Сб.. трудов ГПИ Ленпромстроппроект "Расчетно-теоретнческне исследования и применение ЭВМ в строительстве". Л., 1975.

11. О рациональной схеме решения системы линейных алгебраических уравнений со слабозаполнснной матрицей коэффициентов / Труды ЛИСИ, N 57. Изд. ЛИСИ, Л., 1968.

12. О рационализации расчета стержневой системы при его многократно»! повторении / Краткое содержание докладов к XXXI научной конференции ЛИСИ. Изд. ЛИСИ. Л.. 1973.

13. О сокращении числа арифметических операций при решении системы линейных алгебраических уравнений со слабозаполнснной симметричной матрицей / Исследования по расчету и проектированию соорхжений. Сб. трудов ЛИСИ. N 104, Л., изд. ЛИСИ. 1975.

14. Расчет статически неопределимых систем при их модификации I Труды ЛИИЖТа. вып. 287. Л.. "Транспорт". 1968.

15. Задача о статически неопределимой ферме минимального веса при учете нескольких вариантов нагрузки / Краткое содержание докладов к XXVII научной конференции ЛИСИ. Изд. ЛИСИ. Л.. 1968 (в соавторстве с А.И.Богатыревым).

16. О применении статистических методов поиска при оптимальном проектировании несущих конструкций / Труды ЛИСИ, N 60. ¿1зд. ЛИСИ. Л.. 1969.

17. Вопросы оптимального проектирования конструкций / Л.: изд. Ленинградского Промстройпроекта. ТП-426. 1966 (в соавторстве с А.И.Богатыревым).

18. О расчете кинематически неопределимых стержневых решеток координатного типа. Строительная механика и расчеч сооружений. 1980. N 6.

19. Анализ работы и '.обеспеченно надежности решений программной системы Ленпромстройпроекта АВРОРА, 75-М / Новые методы расчета строительных конструкций: Межвуз. сб. тр. // Л11С11. 1983.

20. К вопросу формализации расчета статически неопределимой системы методом сил / Межвуз. тематич. сб. тр. // Л| 1С П. 1991.

21. О формировании системы локализованных базисных циклов непла-нарного графа в связи с формализацией метода сил / Мсжв\^. тематич. сб. тр. //ЛИСИ, 1991. >

.22. Итерационные процессы перерасчета стержневых и конечноэлемент-ных систем при их, модификации / Межвуз. тематич. сб. тр.. СПбГАСУ. Санкт-Петербург, 1994.

23. Интерполяция векторов состояния в пространстве вариантов линейной дискретной системы / Межвуз. тематич. сб. тр.. СПбГАСУ. Санкт-Петербург. 1994. . /'У :-. /

У

/ /