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

АЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

МЕТОДЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ДЛЯ ЗАДАЧ О РАЗМЕЩЕНИИ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ И ПРИБЛИЖЕНИИ ПОВЕРХНОСТЕЙ

05.13.18 — Теоретические основы математического моделирования, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

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

Тагиров Тагир Салихович

Казань—

1998

Работа выполнена на кафедре общей математики Казанского государственного университета.

Официальные оппоненты: доктор физико-математических

наук, профессор В. Н. Паймушин

кандидат физико-математических наук, доцент В. Р. Фазылов

Ведущая организация: Факультет вычислительной математики и кибернетики Московского государственного университета

Защита состоится 16 апреля 1998 г. в 15.30 в ауд. 324 НИИММ КГУ на заседании Диссертационного Совета Д053.29.10 при Казанском государственном университете (420008, г. Казань, ул. Университетская, 17).

С диссертацией можно ознакомиться в Научной Библиотеке Казанского государственного университета.

Автореферат разослан « & » 1998 г.

Ученый секретарь Диссертационного Совета, ^^ Е. М. Федотов

Общая характеристика работы

Актуальность темы. Методы для отыскания оптимального размещения некоторого множества объектов в заданной области или же получения некоторой оптимизированной области в результате эптимального распределения некоторого множества объектов этносятся к так называемым труднорешаемым задачам, изучению которых в последние 15-20 лет уделяется большое внимание исследователей многих математических школ. Подобными и близкими задачами занимались в разное время В.Л. Рвачев, И.В. Кузьмин, Л.И. Нефедов, В.В. Евсеев, В.Н. Паймушин, М. Гери, Ц. Джонсон, X. Пападимитриу, К. Стайглиц, Р. Тамассиа, Ф. Препарата, Дж. Лиотта и другие. Решение таких задач в некоторых случаях осложняется тем, что a priori оптимальное решение может быть получено лишь в результате полного перебора всех возможных размещений (распределений), что само по себе невозможно из-за ограниченности машинных ресурсов. Не менее актуальными являются также и исследования по нахождению методов математического моделирования для решения задач о процессах приближения заданной поверхности определенными классами других поверхностей, что, в частности, является необходимым при поиске новых подходов и создании технологий обработки деталей машин, механизмов летательных аппаратов и т.д. Способы решения как первого класса задач, представляющих интерес в виду многочисленных и разнообразных приложений в самых различных областях проектирования, так и задач второго класса, необходимость решения которых является очевидной также в связи с большим числом приложений, затребованы развитием современных технологических процессов, процессов организации управления и контроля и т.д. Методы математического моделирования для таких задач во многих случаях не были разработаны до сих пор. В то же время развитие

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты докладывались на городском семинаре по конструктивной теории функций (рук. проф. Б.Г.Габдулхаев, 1991г., 1993 гг.), Международной конференции "Лобачевский и современная геометрия" (Казань, 1992 г.), Итоговых конференциях Казанского государственного университета (1994г.), Международной конференции "Алгебра и анализ", посвященной 100-летию Б.М.Гагаева (Казань, 1997 г.), семинаре кафедры вычис-

лительной математики Казанского государственного университета (1997 г.).

Публикации. По теме диссертации опубликовано 5 работ, список которых приведен в конце автореферата. В работе [1], выполненной совместно с И.А.Литвиновым и Н.М.Бухараевым, автору принадлежит постановка задачи, разработка основного конструктивного метода и алгоритма решения задач, соавторам - создание программы алгоритма, создание программы метода случайных испытаний, использованного для сравнения, и проведение численного эксперимента для ряда задач.

Структура и объем работы. Диссертация состоит из введения, двух глав, разбитых на параграфы, списка литературы из 65 названий и имеет общий объем 110 страниц машинописи.

Краткое содержание работы

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

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

Первый параграф этой главы посвящен постановке задач указанного вида и анализу их параметров. Рассматривается некоторый набор (упорядоченное множество) объектов Х—{а1,аг... ..., Оу}, N е М. Для простоты изложения геометрические размеры всех объектов предполагаются одинаковыми, что не уменьшает общности постановки задач.

Формулируются в общем виде и анализируются 5 задач о различных условиях оптимального размещения объектов на плоской области. Указываются условия по которым должен достигаться оптимум: сумма длин путей (которые учитываются в целевой функции с весами для класса взвешенных задач) проходов (маршрутов) по определенному набору таких проходов должна быть минимальной.

Во втором параграфе главы рассматривается математическая формулировка задач о распределениях, вводятся основные определения объектов, множеств, функций и особенностей тех или иных задач на поиск оптимального распределения. Известно, что даже при числе объектов Лг> 70 метод прямого перебора потребует более 70! (> 10100) испытаний для отыскания полного экстремума, что превосходит все возможности любых существующих вычислительных устройств. Здесь же рассматриваются некоторые категорные особенности объектов исследования. Определяются временные и пространственные характеристики задач, вводятся понятия дисплея, петли, целевой функции, объектного множества, пространства состояний, ограниченности и т.д.

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

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

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

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

Собственно построение одного такого алгоритма для задачи, сведенной к целочисленной постановке, и исследование его расширений и модификаций занимают основное место последнего параграфа первой главы. Вводятся понятия частотных характеристик Р}'], которые лежат в основе предлагаемого метода, п~ дименов (иначе говоря, направленных массивов со специальным индексированием). Приводится и доказывается

Предложение. Пусть #(Д[,)) - количество чисел в Р.111, пусть огс1(/>.!Ч) — количество чисел, за которыми следуют меньшие числа, а с!е$(.Р,[11) — количество чисел, за которыми следует такое же или большее число. Тогда

#(Р„Ш) = огадГЧ) + (Ь»(Р.[Ч) + 1, причем, если огс!(.Р,[и) = #(Р,|1]) — 1, то Р\1] — вполне упрядочено,

если = #(/*,т) — 1, то последовательность Р}1] является

полностью неопределенной (или стационарной).

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

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

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

Второй параграф посвящен технике усредненных сплайнов для непрерывных функций одного переменного. Теория сплайнов развивалась в работах многих математиков, например, В.А. Василенко, О.С.Завьялова, Б.й. Квасова, Н.П.Корнейчука, В.Л. Мирошниченко, С.Б.Стечкина, Ю.Н.Субботина и других; приложениям сплайнов к инженерным задачам посвящены работы Ю.С.Завьялова, В.А.Леуса, В.А.Поспелова.

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

ренцируемая функция.

Приведем классы получаемых в работе новых сплайнов (для аппроксимирующих кривых, которые не являются параболами, формулы выглядят так же, но обозначения класса par должны быть заменены в этом случае соответствующим образом на hyp и ell):

a) простой геометрически усредненный сплайн второго порядка:

?£(*) = [ pari(*)-parAW;

b) взвешенно—арифметически усредненный сплайн второго порядка.

- (at Pari(*> + Pk Par¿(*)). Ph w - ~7> '

«k + Pk

c) взвешенно—геометрически усредненный сплайн второго порядка некоторой функции flx):

i

pf(x) =[(par¿(x))e .(рагА2(*))4Г',

причем resg(x) = res^x) s res^(x) н res(x),

а в формуле, задающей соответствующий сплайн, стоят следующие индексы:

N

sg(x) = res4'(Л) + • ind(jre),

s"(x) = resw(x) + 12>:(x) • indOrJ. s"(x) = res^(x) " fpr(x) ■ indfrj • В этом же параграфе приводятся следующие предложения:

Предложение 1. Пусть ТГ — множество узлов на сегменте [а,Ь]а с Ш . Пусть s(x) — простой (арифметически) усредненный сплайн второго порядка некоторой непрерывной функции j[x) на сегменте [a,é]c lí¿ по системе узлов П. Тогда имеет место свойство

d2 s

-= const V х & П.

dx

1J

Предложение 2. Все описанные выше сплайны второго порядка в шах всякого разбиения интервала интерполяции непрерывны.

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

В следующем параграфе определяются основные математические объекты, например такие, как z = S(x, j>) с R} — поверхность, соторую необходимо получить, z — Sn(x,y) — поверхности 1риближения, получающиеся при л—ом шаге (этапе) обработки ^нулевой индекс соответствует стадии заготовки). Определяется депочка поточечных неравенств:

S(x,y) = Sn(x,y) < S^(X>y) <...< Sfay),

lля всех точек (х, у) из некоторого множества Dei?2, которая служит моделью технологии (этапов) обработки. Точность обработки определяется так:

Errmean(/i) - Jj (S(x, у) - Sn(x, y))dxdy,

Q

тн

ЕггаЬз(л) = Jj \(S(x, у) - S„(x, y))\dxdy,

Q

з предположениях наличия допусков обоих знаков; здесь Q -проекция обрабатываемой поверхности на плоскость XOY. Так условия наличия допусков только положительного знака (припусков) выглядят так:

Егггаеап(и) - JJ|№,y) - Sn(x,y))\dxdy= Errabs > 0. n

Эффективностью k— го этапа является величина:

Effabs(*) - flOS1*., (*,.?) - Sk(x,y))dxdy =

о

n

В качестве примера приводится постановка задачи такого рода:

Задача. Пусть z — S{x,y) — выпуклая вверх по оси z поверхность в пространстве R3 при (х,у) е П cff, причем не имеет значения ее гладкость (поверхность может быть кусочно—гладкой или иметь несколько границ гладкости). Требуется обработать деталь с целевой поверхностью S(x,y).

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

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

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

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

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

ледугащие шаги:

1. ввести поправочные (корреляционные) коэффициенты, :оторые бы учитывали прогиб кромок инструмента, их износ и т.д.

тем, чтобы реализовать возможность максимально корректного фогноза точности обработки;

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

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

Указываются также и другие пути управления (контроля) для :истем станков с таким инструментом.

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

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

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

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

На защиту выносятся следующие положения диссертационной работы:

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

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

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

4. Предложены новые типы (гиперболический и эллиптический) инструментария для обработки.

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

Основное содержание диссертации опубликовано в следующих работах:

[1] Бухараев Н.М., Литвинов И.А., ТагировТ.С. Об одном методе решения задач на размещение. // Прием и обработка информации в

сложных информационных системах. — вып. 10. — Казань: Изд-во ИГУ, 1980. - С.68-76.

[2] Taguirov Т. S. Quaternion structures in the sense of differentiability.

// Тезисы докл. Междунар. научн. конф. «Лобачевский и современная геометрия». — Том II. — Казань: 18—22 авт. 1992 г. — С. 99-100.

[3] Тагиров Т.С. Об одной модели построения сплайнов 2-го порядка. // Тезисы докл. Междунар. научн. конф. «Лобачевский и современная геометрия». — Том II. — Казань: 18—22 авг. 1992 г. — С. 98-99.

[4] Тагиров Т.С. Об оптимизационных дискретных геометрических задачах на распределение. // Казан, ун-т . - Казань, 1997. -30 с. - Деп. В ВИНИТИ 29.07.97, № 2534-В97.

[5J Тагиров Т.С. Некоторые задачи геометрического моделирования. // Казан, ун-т . - Казань, 1997. - 26 с. - Деп. В ВИНИТИ 29.07.97, № 2533-В97.