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

АКАДЕМИИ НАУК УКРАИНЫ ИНСТИТУТ ПРОБЛЕМ МАШИНОСТРОЕНИЯ

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

Стоянов Александр Феликсович »

ОПТИМИЗАЦИЯ НАЗНАЧЕНИЯ ДИСКР2ТШХ ИСТОЧНИКОВ

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

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

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Харь коп -

Работа выполнена в отделе математического моделирования и оптимального проектирования Института проблем машинострсош АН Украины

Научный руководитель: доктор технических наук,старшй

научный сотрудник Путятин В.П.

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

доцент Яковлев C.B.

кандидат физико-математических наук доцент

Попивщий В.И.

Ведущая организация: Харьковский государственный университет

Защита состоится "/У" OZ _1992 г. в ¡Ц часов в

ауд. j» III2 на заседании специализированного совета Д 016.22.02 при Институте проблем машиностроения АН Украины

по адресу: 310046, Харьков-46, ул.Д.Пожарского, 2/10

С диссертацией можно ознакомиться в научной библиотеке Института проблем машиностроения АН Украины

Автореферат разослан " М« 04 1992 Г.

Ученый секретарь

специализированного совета ___ И.В.Аристова

- 3 -

ОЬШ ШАГЛН'ИДй'Л РАБОТЫ

.ктусльпость теш. При проектировании (компоновке) слон-

яя различной ц:1тенс:.;>:юстк.

Задел;; такого рода зознккапт при реиешя самых разшас прккл4у4лк вопросов. Так, в области скслопш весьма актуальна проблема оптиматьниго расположения предприятий - псточш-ков виброссв аэрозолел в заданном районе с учетом ограничении на уровень загрязнения (решению этой задачи посвящен ряд работ Г.П. ларчука). При проектировании элементов мпкр о электронной аппаратуры (ЛЬ А) необходимо разместить на платах микросхемы - источники теплоты (задачи такого рода рассматриваются в работах Г.Л. дульаева, .и.Г. Отояна, В.II. Луманна, Б.О. Ьлькина). Воз.\!и^иы поотаповкц задач расположения источников полей и другой физической природы.

Значительный практическим интерес представляют задачи шштеза систем, связанные с назначением их Лемеитов - источников полл различно:: интенсивности на фиксированные посадочные места. В этом случае пеиоходпмо осуществить оптимизацию назначения источников поля с учетом конструктивных технологических ограничений, накладываемых на их взаимное расположение и па характеристики (Тлзкческсго поля. Существенной особенностью синтеза этих систем яаътется то обстоят&тьство.что область определения целевой (¡ункции является дискретной. Поэтому дяя решения таких задач, наряду с применением числен-них методов математической физики (для расчета поля) необходимо последовать существующие методы дискретной оптимизации (работы С.С. Лихалевича, И.В. Сергиенко, Ю.Г. Отояна.С.З. Яковлева) и на основе этих исследований модифицировать или адаптировать алгоритмы комбинаторной оптимизации с учетом особенностей рассматриваем задач таким образом, чтобы мо» но было осуществить синтез системы за время, приемлемое для практического проектирования.

Постановка и методы репешш задач оптимизации назначения лдскреишх источников поля на (Тиксированнке посадочные места

рассматриваются в работах ¡О.Г.Стояла, В.Л.Путятина, и.Ю.Соколовской. ;

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

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

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

Диссертация соответствует основным научным направлениям работы отдела й 52 ШЫаш АН Украины и выполнена в рамках государственной бюджетной темы "Разработка математических методов геометрического проектирования" (Г.Р. й 01860049704) и государственной бюджетной темы "Математическое моделирование слонных технических систем" (Г.Р. $ 01900009448 ). Результаты работы использовались'при выполнении хозяйственных договоров й 342-91 и й 398-92, заключенных с Тешоком-нунвнерго (г. Харьков).

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

- а -

ьПаучная новизна работы заключается в следующем;

§¡1. Проведен анализ особенностей технических систем, со-деркшцих дискретные источники физического псиш. Сформирована-содержательная постановка задачи оптимизации.

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

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

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

5. Получено представление решения нелинейной краевой задачи математической уизпки в'виде, удобном для комоинаторнол оптимизации. Разработан алгоритм назначения источников поля на 4кксированные посадочные места для случаев, когда пале описывается как линейной, так и нелинейной краевой задачей.

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

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

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

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

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

Апробация работы, Ооновные результаты диссертационной работы были .доложены автором на республиканской научно-технической конференции "Эффективные численные методы решения краевых задач механики твердого деформируемого тела" в сентябре 1989 г. и на постоянном городском семинаре "Междисциплинарные исследования и оптимизация в задачах математической физики" • (г. Харьков, 1990 г.).

Публикации. По теме диссертации опубликовано 4 печатных работ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Диссертационная работа содержит 105 страниц основного текста, 12 рисунков, список литературы из 60 наименований.

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

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

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

Б общем виде система уравнений, описывающих поле, монет быть представлена в виде:

АИ^и); кеОс я5

В1/|г =Ф(х);кеГ. Г = 30. (I)

На основе анализа свойств конкретных технических систем уравнения (I) могут быть записаны в виде:

А17-Е К Г(Х)Чо(Х)

Б1Г|Г-Ф(Х-). хеГ; Г-ЗСР. (2)

В правой части первого уравнения системы (2) учитывается влияние источников поля, которые характеризуются скалярными характеристиками - ийтенсивностями р, . Рг > ••• ^ .

Рассматриваются общие свойства систем типа (2).

Проведена математическая постановка задачи оптимизации -назначения дискретных источников поля на фиксированные посадочные места. Показана сеязь между множеством перестановок

X с П ; X = \ I; } из М чисел 1,2.....N по

Н элементов и полем 1Г в рассматриваемой области О .

Сформулированы два вида целевых функции они определяйся требованиями, предъявляемыми к рассматриваемым техническим система!/;

зе, (X) = ПЮг У(Х.Х) (3)

ХеР

3^(1) = шах и (Х,Х). (4)

ХеО

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

= пи а -зг (X) ГеП"

jl = агд min эе( , 3 згеЛ'

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

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

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

Во второй главе рассматривается случай, когда поле описывается линейными уравнениями с линейными граничными условиями.

Решение линейной краевой задачи математической физики можно построить по принципу суперпозиции: ы

V = £ Fu VJ(X)+1MX). (5)

Функцию UJ (X) определим следующим образом

' hiJ(x>; хе^сО' х*/

где jbJ4x. хеО; VJ(M*£}.

Величину £ зададим, как минимум среди величин, удовлетворяющих условию:

/П Vl.j 1 < s N.

Соотношение (5) можно переписать в виде:

ТГ(Х.Х) = (Т. Х)*о1Г(Х.Х), (6)

где

д U * о : х е р*', j -jji

ЗУ s о •- х i У pj'.

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

Рассматривается следующая вспомогательная задача оптимизации:

nun, max V (JT, X). (7)

JTsfl xcQ

г*

В работе показано, что максимум функции If при любом назначении источников поля (т.е. при любой перестановке ЛГе П ) достигается на более чем в N * t точек области Q . Вследствие этого задача (7) сводится к выяснению существования такого назначения источников поля, при котором экстремум равен каждому из N М известных 4Howi:Wlj , i=1,lJjj = i. N '» Ц,0 Величины Wij и Woo определяются следующим образом:

Wsj - max С Ft U4X) - lfp(X))

W00 = max lip U).

x f L)?1"

Разработан алгоритм, который позволяет за конечное число шагов оцениваемое, как О С N ^ ^ решить вспомогательную за-

- 10 -

дачу (7). Выполнена такке оценка точности решения:

I \Г - V I УхеО ; Ухе П.

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

^ ^ ^ ; матрица В имеет размерность С N -1)х(НН)или N * N . Выполнена оценка погрешности и для этого приближения.

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

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

N . Ц Ьг Ьк

V - Е Ть и) + £ £ ■ ■ ■ Z

Л -5"'

Сх) +

4 " 6«ч Сг"1 СкЧ

ч к. к

(6)

При этом функции и^СХ); . ^ получены посредством решения конечного числа линейных краевых задач.

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

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

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

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

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

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

Алгоритм, основанный на идее локализации использован для решения задачи оптимизации назначения источников теплоты цря-моутальной формы в прямоугольной области. Локализация поля дает возможность аффективно проводить оптимизацию для достаточно большого количества источников' (в рассматриваемом случае - до 50).

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

" ■ » « I ¡,

Г« '

- 12 -

Проведена оптимизация назначения источников поля для разных Ы , показано, что основное время при расчете тратится на решение краевых задач. При реиеш;и задачи дискретной оптимизации принимался алгоритм, в основе которого лежит схома ветвей и границ.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ II ВЫВОДЫ

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

2. Выполнен обзорный сравнительна;, анализ с^чостоущих методов решения задачи оптимизации назначена"! дискретных источников поля на фиксированные посадочные песта.

3. Предложены понятия локатизации патя и носителя поля дял случая линейкой краевой задачи. Установлена связь между локализацией поля и принципом местного влияния. Осуществлена постановка вспомогательной задачи оптимизации ("нулевое" приближение), учитывающей локализации псля в окрестности его источников. Предложен алгоритм, позволяющий за коночное число шагов решить вспомогательную задачу оптимизации. Локаза-но, что необходимое число шагов можно оценить, ка;0(Н1|)'-К,~ количество источников поля и посадочных мест.

4. Установлена связь мелду исходно, задачей оптимизации к вспомогательной задачей полученной с помощью локализации патя. Предложен критерии, определяли« класс паче«!, для

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

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

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

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

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

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

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

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

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

■ - 14 -

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ИЗ-Ю/сЕНЫ В РАБОТАХ:

1. Стоянов А.Ф. Оптимизация назначения источников физических полой, описываемых нелинейными уравнениями с нелинейными граничными условиями. - Харьков, 1900. - 23 с. -(Препринт АН Украины. Ин-т проблем машиностроения; í¿ 323).

2. Столп Ю.Г., Путятин В.П., Элькин B.C., Зусмановский И.И., Цепляев А.Н., Стоянов А.Ф. Оптимизация расположения дискретных источников теплоты на подложках БИС. - Харьков, 1990. - 34 с.-(Препринт АН Украины. Ин-т проблем машиностроения; № 327).

3. Яловкика Е.Б., Стоянов А.Ф. Оптимизация назначения источников физического поля в случае линейных краевых задач.-Харьков, 1939. - 19 с. - Деп. в ВИНИТИ 6.11.139, i/có2-b39.

4. Стоянов А.Ф., Яловкина Е.Б. Оптимизации назначения точечных нагрузок на прямоугольной пластине с учетом ограничении на величину прогиба / Эффективные численные методы решения краевых задач механики твердого деформируемого тела: Тез. докл.респ.науч.-техн. конф. - Харьков: ХИСИ, 1939. - 4.2. С. 116.

Отсетствэнный на выпуск - д-р техн.наук, проф. Гда.ко А. 1С. Подписано к печати 03.01.1992.

Формат 60x90 I/I6. Бумага типографская fí 1.Ус.л.п?.ч.л.1,0. Уч.-изд.л.О,96. Тираж 100 экз. Заказ В ¥)7, Бесплатно.

Изготовлено на ротапринте ИПМал АН Украины 310045, Харьков-46, ул. Дм.Пожарского, 2/10