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

9 П 9 Я Й '

* Томский ордчна Октябрьской Революции и ордена Трудового Красного Знамени государственный университет имени В. В. Куй б ыше ва

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

ЯКОВЛЕВ Сергей Всеволодович

УДК 514.75:519.85

ТЕОРИЯ И ОПТИМШАЦИОН11ЫЕ МЕТОДЫ ГЕОМЕТРИЧЕСКОГО ПРОЕКТИРОВАНИЯ В СИСТЕМАХ УПРАВЛЕНИЯ, НАБЛЮДЕНИЯ И КОНТРОЛЯ

05.13.01- управленио п тохпичпрких систпмах

Автореферат

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

Томск - ] 989

Работа выполнена в Харьковском ордена Трудового Красного Знамени институте радио электроники имени академика М.К.Янгеля

Официальные оппоненты — академик АН УССР,доктор физико-

математических н аук, профеecoр РВАЧ ЕВ В. Л.

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

БЕРЕЗНЕВ В. А.

- доктор физико-математических наук профессор ТЕРПУГОВ А. 'Ф.

Ведущая организация — ордена Лонина Институт кибернетики

им. В. М. Глушкови АН УССР

Зашита состоится ч&З » •^M^-J^Cl^ g Q 0 в /0час> на заседании специализированного совета Д 063.&3.03 при Томском ордена Октябрьской Революции и ордена Трудового Красного Знамени государственном университете им.В. В. Куйбышев а по адресу: 63 40 1 0, г. То мс к, п р о с п . Лен и и а. 36.

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

Автореферат разослан " д 9 0 г.

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

доцент РЫЖАКОВ А. П.

I. ОБЩАЯ ХАРЙГГЕР1СТШ РАБОТЫ

-^'.Актуальность работ. Одним из основных путей повышения эффективности функционирования сложных технических систем являет-. :я выбор рациональной структуры системы и оптимизация ее пара-штров. Это позволяет улучшить характеристики систем, упростить 'правление, повысить ¡¡ццедность использования, увеличить быстродействие обработки информации, а также сократить сроки и стоимость лроектно-конструкторскюс работ по их созданию.

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

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

Диссертационная работа представляет собой обобщение и развитие результатов в области теории геометрического проектирования, основателем которой является член-корреспондент АН УССР Ю.Г.Стоян .

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

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

- разработаны теоретические основы формализации зддач геометрического проектирования в технических системах, построены ! исследованы информационно-геометрические модели задач;

- выделены основные классы оптимизационных задач геометрического проектирования и исследованы их математические модели;

- исследованы схемы последовательного анализа и отсева вариантов' для решения, ^атимизациошак задач размещения и покрыт и?.

- исслед&вани мрдели оптимизационных задач на евклидовых комбинаторных множествах, разработаны и теоретически обосновань: методы их решения;

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

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

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

Экономический эффект от внедрения результатов работы состав ляет свыше 230 тыс.руб. в год.

Диссертационная работа выполнялась в период с 1УЬ2 г. но 1989 г. на кафедре прикладной математики Харьковского ордена Тру дового Красного Знамени института,радиоэлектроники имени академика М.К.Янгеля в соответствии с планами следующих научно-исследовательских: работ:

- "Разработка математических моделей и оптимизационны/: методов решения задач геометрического проектирования и внедрение результатов п учебный процесс" тема 01.08.02.02 проблемы 01.08.0i "Разработка и внедрение программных средств автоматизированных обучающих систем"(№ гос. per. 01660130224);

- b -

- "Разработка математического обеспечения компоновки РЭл а борту транспортного самолета" (IF* гос. per. 01870093264);

- "Разработка математического обеспечения для решения за-ач проектирования радиоэлектронной аппаратуры и использование ззультатов в учебном процессе" тема У.9.3.7 проблемы У .9 "Ношение эффективности и качества учебного процесса на основе ipoKoro использования ЭВМ и видеотерминальных устройств" (Г- гос. зг. 01821030930);

- "Разработка математических методов геометрического пробирования", утвержденной Постановлением Президиума АН УССР 474 от 27.11.85 г.;

- "Разработка математического обеспечения для проектирова-щ двуслойных печатных плат" (№ гос. per. 01640062175};

- координационным планом работ Совета по комплексной проеме "Кибернетика" АН СССР (проект "Конструктор", п. 15), ут-¡рвденным Постановлением Президиума АН СССР от 2.ü6.60r.

Апробация работы. Основные результаты диссертационной рати представлялись и докладывались на 14-й Международной кон-ренции по системному моделированию и оптимизации (Лейпциг, 89г.), 9-й Международной конференции по математическому про-ашированию (Токио, 1988г.}, 10-й Пражской конференции по тео-и информации, статистическим решениям и случайным процессам para, 1967 г.), 2-й конференции по автоматизации проектирова-я (Будапешт, 1986 г.), Международной конференции по стохасти-ской оптимизации (Киев, 1984 г.), УП.УШ Всесоюзных конферен-ях "Проблемы теоретической кибернетики (Иркутск, 1985г., Горь-й, 1988 г.), Всесоюзной научной конференции "Декомпозиция и эрдинация в сложных еистемах'ЧЧелябинск, 1986 г.), ill Всесоюз-4 школе "Диснретная оптимизация и компьютеры" (Таштагол, 37 г.), Уп1, IX, X Всесоюзных симпозиумах "Системы программно— обеспечения решения задач оптимального планирования (Нарва->суу, 1ЭЬ4-1Э88 гг.),. Щ Всесоюзной школе "Проектирование авто-?изированиых систем контроля и управления сложными объектами 'anee, 1988 г.), УП Всесоюзном совещании "Методы Ыонте-Карло ьииалительной математике и математической физике" (Ношеи-)ск, 1985 г.), И! Всесоюзной конференции'"Математические t-.'ivo-распознавания образов" ( Львов, 1987 г.), Есесоизнмх со; и-

- О -

щаниях по проблемам случайного поиска (Таштагол, 1985 г., Между-речинск, 19Ь6 г.), координационном совещании по проблемам распознавания образов { Новгород, 1968 г.), республиканских семинарах по дискретной оптимизации'( Ужгород), научных семинарах Института математики АН УССР, Института математики и Института вычислительной техники и автоматизации АН Венгерской республики, ' Будапештских технического университета и университета им. Э.Лорана, Индустриального университета им. й.Атиллы (г.Сегед), а также на семинарах Научного совета АН УССР по проблеме "Кибернетика" .

Публикации. Но теме диссертации опубликовано свыше 70 печатных работ, в том число I монография. Цикл работ в области теории геометрического проектирования отмечен премией Щ JIKCM Украины в области науки и техники.

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

2. СОДЬШШШ РАБОТЫ

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

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

Приведены содержательные постановки ряда практических задач управления, наблюдения и контроля п технических системах, для 'построения адекватных моделей задач осуществлена формализация понятия геометрической информации..Геометрическая информация о точечном множестве S*- {^((^представляется в виде о П"*},

1р}) , где - пространственная форма S , t"1} - метрические характеристики, {р} - параметры размещения. Компонента t^J представляет собой класс эквивалентности на совокупности множес: соответствующего топологического пространства. Пространственная

форма произвольного множества представляется суперпозицией элементарных форм. Предполагается, что компоненты и {р} являются векторами конечномерных пространств, т.е. Ш. = (АН,,..., .....

В качестве носителей геометрической информации вццелен класс Щ -объектов-моделей точечных множеств, адекватных материальным объектам.

Если компонента {4} состоит из одного элемента, имеющего элементарную пространственную форму, то информация ^ называется канонической. В работе^рассмотрено евклидово пространство канонических информации С> . , изоморфное пространству & ,

Пространство & — * ,,.* £ц называется простран-

ством геометрических информации. Задавая различные отображения В на совокупности точечных множеств 5^,..., 5П, строятся точечные множества Б" В .^^соответствующей структуры, геометри-чекая информация о которых индуцирует пространство информации <£ с элементами а=({4ЦтМр})= (»£4...,пг\т.п,

Геометрическую информацию назовем параметрической, если ее компоненты являются функциями некоторого векторного параметра , т.е. £аФСх)в({М*)},{т(х»,{р(х)>.

Пусть. Ц , <3-(х)-{§(х):х£9)} . Отображение 9 & назовем геометрическим полем,-а семейство {?(&)- геометрической реализацией поля. При соответствующем задании топологии (г рассматривается как пространство параметрических геометрических информации.

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

Пусть в- и 9 пространства геометрических информации. Под задачей геометрического проектирования будем понимать реализаций отображения Р ^ &' * В задачах геометрического проектирования возникает два класса оптимизационных задач, б зависимости от того, в каком пространстве осуществляется оптимизация - прост-

ранстве переменных геометрической информации или в пространстве операторов " . В первом случае при известном отображении Р должна досгигать';:э'кстремума заданная на множес ве V/ допустимых значений переменных'геометрической информаци!

функция , т.е. оптимизационная задача состоит в 01

ределении таких переменных ИГ* геометрической информации С для которых

^ ' иге УГсЙГ

Во втором случае для заданных € О и ^критерия качества Е-(г —требуется найти такой оператор Р ^из допустимого множества V пространства-,опера-торов и такое

^ ^ Г(Рд-). (т)

В работе выделен класс Ек -задач геометрического проекта ровання .и сформулированы-требования к ним. Основными классами Ек -задач являются задачи размещения в области 50 геометрических объектов и задачи покрытия области 80 совокупностью объектов . В зависимости от того, являются ли переменными геометрической информации ({$в},{ГС.6.1,{.рйУ) метрические характеристики {ГП0} Е(< -задачи относятся к кла су задач с подвижными и неподвижными границами.

Пи совокупность объектов 8а в задачах размещения и

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

Основная задача размещения геометрических объектов состоит в следующем. -Имеются точечные множества , Iе {0} у П,^, ивдуцируеше геометрическими »формациями а1=((41},{ГпИ, ,

где компоненты {.р"} .{б^^ГП1-}, I £ {0} 0фиксирован!.:.Положим р°-(0,..„0). Требуется определить такие значения параметров размещения {.р} , I е3гг,при которых выполняются условия взаимного непересечения объектов и размещения их в области Эо • Обозначим через 1€{0}и соответственно объекты, пара-

метры размещения которых р1 € К* . Тогда область У\/ допусти-

- У -

х решений в основной задаче размещения формируется следующим разом .

МСр1,.../)«^: St(pbc S0(0),mt S-^Hmt j63a,jeRt(iH>xCSo(0)QSJx Rt(rl-'°}П

Itfl fU + R?(HW>x ff(}"H)x cC-uiSL(p1)©

ruotsrCpOlxR^j,

e @ | 0 - операции суммы и разности Минковского; С -ция дополнения; uni- - оператор топологической внутренности; ) - отраженный относительно нуля R, объект.

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

ьектов SL » при которых выполняется условие покрытия. Область

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

V=t(p,,...,pt)êR- : S.(0)с$ =

•СП-^ i(p, U P,)ea.t «pl.. ,р')х(Дс stlf)n s.(0))l}=

; rrRnt - ортопроектор на пространство R , {uj - нуль ) странства R5 .

Вторая глава посвящена построению и анализу магических моделей осЩън^х задач геометрического проектирова-

Представление множества допустимых решений W позволяет

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

«tjCp'.^O, (2)

£oi(pl)>0, leî ; (3)

адачах покрытия

А(р\...,рй)>0, (4)

(>) подлежащие

чализации функции, которые описывают соответственно условия-

взаимного непересечения, размещения й области и покрытия области.

Для определения вида функций, входящих в (2)-(4),использован класс Ф -функций. Ф -функции можно рассматривать как функции, определенные, на прямых произведениях.пространств геометрических информации. Если информации —({^/ГО-'ЗХрО)16 Зп. индуцируют пространства геометрических информация 1 , то Ф -функция объектов и , описываемых этими информация-

ми, определяется иа С и обладает следующим характеристи-

ческим свойством;

ф^ (р\ р»> > о , если

"'г/ ыъ^фп да« 0;

( Р1) 0 , если 1гЛ Ср1)П ( р>) £ 0 ,

где - оператор топологического "замыкания.

Таким образом, при формализации ограничений в задачах размещения в неравенствах (2),(3) в качестве (•) можно выбрать Ф -функцию объектов 81 и , а в качестве У^О) -Ф -функцию ${ иС$0.

Для формализации с помощью Ф -функций условия (4) положим

вер1.....р^сДБ^р1). ^ .

Тогда Л(') -ф -функция объектов и 5(р\---1р ).

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

Пусть геометрический информации ^,I € индуцируют точечные множества и порождают пространства геометрических информации ^ б- ". Положим Се=(?е<Х...Х (г Рассмотрим множество 5= В..., Б»), индуцируемое геометрической пи-формацией Н , т\...Хр1...., где ^

- фиксированные компоненты пространственных форм. Зададим в пространстве (т функцию

где - мера множества. Уту функций назовем СО -функцией.

В работе исследованы метрико-топологические свойства

со

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

а условия взаимного непересечения объектов и размещения их в области п

что эквивалентно систс.ле неравенств (2),(3) в вцце

0)б1(р1, рЫ о, ц/р1ко, в, в^ЭД^е^фса.п я •

Если множество допустимых решений в задачах размещения (покрытия) непусто, то условия (2),{3) (условие (4)) можно представить в единой форме 63ц (р1, ... , ра) —" 1Г1ЛХ.

В работе рассмотрены вопросы описания области М с помощью структур неравенств. Структурой Неравенств ¿(Э^ОС^А^) назовем упорядоченный набор Зр,} с определенными для каздой пары неравенств операциями конъюнкции и дизъюнкции, представленными в виде симметричной матрицы Д^С б^З^щ- Операции конъюнкции соответствует _ 8- •= \ , а операции дизъюнкции - 8^ = 0 . Полоним 8ц= ^ » С На множестве структур неравенств определены теоретико-множественные операции.

Пусть множество 30 (Отписывается структурой неравенств Д , а множества С 5^(0), - структурами ие-

равенств ^ Сформируем структуру неравенств

(5)

и обозначим через Vе К множество, описываемое этой структурой.

Теорема. Для того, чтобы выполнялось условие покрытия области системой объектов Б^Ф1) , Iе , необходимо и достаточно, чтобы

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

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

мализацни, названный принципом разбиения области. Пусть & -кольцо множеств, поролденное множествами 80 (0),5-с ^

Сформируем систему множеств удовлетворяющую условиям

и Тк=.у и, БДО),^'Т, 01п1 \~0, г, ^ ^

Введем булевые переменные ___ ГI, если Э^В^р') > Г1' если ТсС $1(р0.

(0, в противном случае ; И), в противном случе

Тогда условия взаимного непересечения объектов и размещения их в области примут вид

*'1'К6 ^; 11 аЧ*21Г 0' € Зр.

а условие покрытия п. I Лри этом £ 1 ^

В принципе разбиения области отап формирования системы

ТЕ

можно исключить, рассматривая в качестве представителей ТЙ. , как классов эквивалентности, их одноточечные подмножества. Уто позволяет в качестве

пг

при достаточно малом 8>0 выбирать

£ -сеть множества $0 .

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

В третьей главе рассматриваются декомпозиционные методы, решения основных задач геометрического проектирования. Основное внимание уделено схеме последовательного 'анализа вариантов, предложенной В.С.Михалевичем и развитой и работах Н.Э.Шора, ВЛ.Волковича, Д.И.Куксы и др. Эффективность применения методов в рамках этой схемы и простота их реализации значительной степени зависят от учета специфических свойств решаемых задач.

В работе исследуется применение методов последовательного ¡ализа и отсева вариантов для решения задач размещения и покры-1я. В качестве области размещения (покрытия) и'размещаемых юкрыващих) объектов рассматриваются многоугольники. Кусочная шейность их границ позволяет легко конструировать варианты зшения и формализоват: операторы анализа и отсева вариантов.

3 основной задаче покрытия структура бОТ^^хД... ,ХИ')) Д ,т) ща (5) описывает область V*-I£ Осуществим ортогональную юекцию V на пространство переменных 3£{..,,Ха. Полу-

шное множество обозначим \/0 . Способ построения ортогональ-эй проекции множества, заданного структурой неравенств, описан работе. Пусть множество задается структурой неравенств 1(5' (ос\,..,ХГ1))Л*)т.). Эту структуру можно представить в виде

;е , ^ € - единичные матрицы.

Сформируем множество Уу — ° Рассмотрим совокуп-

ить логических переменных 2ц...., установив соответствие гжду номером неравенства из , X*1) и индексом логи-

гской переменной. Тогда множеству IV соответствует к.н.ф.

1е - множество номеров неравенств, входящих в набор_ ^ ... , ^ ^ Зд, , а логической переменной 2t со~

¡•ветствует Ь -ое неравенство структуры (э(*(зс',.,., ОС*'), Д* зятое с противоположным знаком, причем строгое неравенство за-зняется на нестрогое, и наоборот.

Преобразуем к.н.ф. в д.н.ф. и представим ее в виде 1е и й)^ дизъюнкции таких конъюнкций переменных, которым рвечают соответственно совместные и несовместные системы нера-;нств* При этом множеству допустимых решений в задачах покрытия >ответствует д.н.ф. . На К -ом шаге преобразования и исклю-гния конъюнктов, соответствующих несовместным системам неравенств, леем д.н.ф.

кк , П.»с ' „

Ч = М( А,

^ "Ц,, и множества определяются со-

к

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

Сформируем дерево решений задачи. На К -ом уровне каждая вершина А^ дерева определяет множество \Z\Zj , ^которое описывается^ системой неравенств, имеющих номера из в наборе (х, ... ,ЭСП) . Этому множеству соответствует д.н.ф. , следовательно, процесс построения вершин дерева решений определяется представлением , К£ нх-

Множества , ^ =4,... назовем допустимыми множествами решения, а множества > ~ ^ > • • • »^К » К <-Л - частичными множествами решений. Множество назовем допустимым частичным множеством, если его родовое множество непусто.

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

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

В работе разработаны методы решения задач решетчатого покрытия плоскости. Задача редчайшего решетчатого покрытия заключается в максимизации плотности покрытия при условии, что основной параллелограмм решетки $0 .покрывается системой транеяян-тно эквивалентных множеств Б (р1), 1= 4,2,3,4 , параметры размещения р1 которых являются координатами вер'лин -

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

Общая схема последовательного анализа и отсева вариантов

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

Четвертая глава посвящена исследованию ком-шаторных моделей задач геометрического проектирования. В осно-/ положена формализация задач в виде (I), где оператор Р за-з.ется булевой матрицей. В этих случаях оптимизационные задачи зометрического проектирования формулируются как задачи оптими-щии некоторого функционала на подмножествах комбинаторных зостранств перестановок и размещений. Элементы этих пространств урождаются как метричесрми характерситиками {Ш1} , так и па-аметрами размещения Ср) геометрических информации аЧДр1}, ивдуцирующих размещаемые (покрывающие) объекты.

Пусть Д - конечное множество различных элементов. Мно-;ство, элементы которого являются упорядочены!,пли подмножества-1 А , назовем евклидовыми комбинаторными множествами. В ра->те ^осуществлено отображение евклидовых комбинаторных множеств

К . Обозначим образ множества П, -перестановок элементов 1={СЦ,...,С1ц},а,€„.4£Ц через Еп. , а образы множеств ГЬ - раз-гщений элементов В ••• » , с повторе-

1ями и без повторений соответственно Ек и Е* . При указан-)м отображении исходная задача оптимизации функционала в ком-шаторном пространстве эквивалентно формируется как задача оп-шизации некоторой функции на конечном множестве пространства

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

Теорем а. Точки множества Ец. лежат на семействе ги-фплоскостей {Т4}, 6 ^ , ^ , = М I /6 ! !

'.Да Ал л л

Приведены аналогичные теоремы разложения для подмножеств Еп, лежащих на указанных семействах гиперплоскостей._Сформу-фованы также теоремы разложения для множеств Ек и Е^ и 1СС

подмножеств.

Выделены классы комбинаторных множеств» предст'авимых в виде пересечения многогранника и гиперсферы.

Теорема. Точки множества только они,удовлет-

воряют системе п к.

£ д^ - Е «-1,

Й 1 1=4 1

т (я

' Хы. М t

> Т. а^ ', i=< 1

Ы-Ы- (6)

ы iM _ л

Аналогично указано представление множества как пересечение гиперкуба и гиперсферы пространства R

Исследованы свойства функций, заданных на вершинах многогранников. Пусть М - многогранник в пространстве £ . Обозна-

Х= corar И, Е88 m. = cwcd Е.

Теорем а. Для любой функции f iE~*"R существует выпуклая функция Щ'. X""*" fv , такая что Ц>(х)~ f(OCj для всех Е • Функцию ^(х), удовлетворяющую указанному в теореме свойству, назовем выпуклым продолжением функции ^(зс) на множество X Положим

т

где А(а)=СС^,...,ссЛ)€|Г:^ос1=н, o^oc^-l ,¡c¿€E,

набор {X-^CÍ^ 0} аффиннс^ независим }. Теорема. Пусть f'. • Тогда функция ^С(Х), задан-

ная выражением (7), является выпуклым продолжением функции на множество X , причем = СО/lí/ f.

Теорема. Для любой функции j",' E~*Rи для любого р>О существует силпо выпу1слая с параметром не менее О функция Ф-'X^R » такая что ф(х) = К*) для всех £С<=Е .

Теорема. Дня гобой функции f; Е-" R1 существует выпуклое дифференцируемое продолжение tj Xtt<R • ■ B.)-t

В силу того, что E^v&ttCOm/Eft,Én = ire%tcorurEn, Ej ^ (ШEj из приведенных- теорем следует возможность построения выпуклых,

- х!/ -

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

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

Сеп(х) = ' • ■-4 и^16 ^ •

(i) _ Г)^ Ск'-^=(£......1,КП1к......

где й—(С1|1...)а.п_)}П{К^..^К|- множество перестановок чисел

Построение выпуклого продолжения для ^^ осуществляется итерационно. Определим выпуклую функциюр»® в (&), такую что

Ге1;..е^=с)го, хе^. ^ (в,

Чтобы отличить равенство функций на Еп.от равенства в здесь и далее используем знак . ^

Лри

еч

имеем линейную неотрицательную на функцию

• I^ '•• где Ь АЛЯ : ¿которого ^П- •

Пусть для любых К^ГП построены выпуклые функции

г—(0 . .

Гк ^ (х) , удовлетворяющие (8). Определим функцию Е?1(рС)

при фиксированном наборе + П^Н . Пусть для некото-

рого Тогда

+ £ос?+ г [СжЛ^Р . {9)

& <к.....

} „ « («-М) . . а

пункцию и правой части (9) обозначим с « (СС) . Тогда

.(т+О _(т+'()

Пусть - выпуклое продолжение функцт f: ЕЦТ"

п. п

Тогда функция фСЗС)51 $>>0 является

сильно выпуклым с параметром > ^ продолжением функции

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

Теорема. Пусть функция (Ç(X) сильно выпукла с парам: ром О^ 0 и дифференцируема на замкнутом выпуклом множестве X=3JEa. Тогда для любых Х€Х

> ï «чй

где последовательность различных чисел {К},..., Кц}, такова что

» Ч" * / * *\

Теорема. Для того, чтобы точка ЗС — (Х^,... > бы

точкой минимума на множестве Ец сильно выпуклой^ с параметром р^О н дифференцируемой на COftl/Ецфункции С^(З-), достаточно чтобы существовала такая последовательность различных чисел {^i-чКц}, что

QWX») Спх* . ^ ) ,аг ^rt

Теорема. Пусть функция ¿^(дЛвыпукла и дифференциру на выпуклом замкнутом множестве X—'Е* • для любого Х<

где последовательности ,[ïlh} ... , 6Л} таковы, что

ЪЦ(х)р ЪЩХ) I Г L , если о,

вЯщ'" если з^(дс) ^-Q^gt

Теорема. Для того^ чтобы точка была т

кой минимума на множестве Ек сильно выпуклой с' параметром и дифференцируемой на COiilT^функции ^(Х), достаточно, что£

у IIЩ '(х*) t- ( Ц'(х*),х*). о

О

Задача минимизации в левой части неравенства (10) полиноми-шю разрешима.

Теорема. Пусть функция Ч^ЗЬ) сильно выпукла с пара-зтромр^О и дифференцируема на замкнутом выпуклом множестве ЭЕК . Тогда для лобого X еХ

ГЩП<4(Ц)> СР(сс)- Е^^СХс-х^^рНх-х0!!2, К ^.если г^зр^,

если |НГг I < 12^2

| НГ гр I, € и >,

если ¿^2Рёк, % ОлТ вУШ . . ч

Указанные теорема экстремальности могут быть использованы ия оценки погрешности и доказательства глобальности решения в эмбинаторных алгоритмах локальной оптимизации, предложенных .И.Журавлевым, И.В.Сергиенко и др., при предварительном отобра-энии комбинаторных множеств в .

Б основу решения оптимизационных задач на евклидовых ком-инаторных множествах положены декомпозиционные схемы. Разработ-з и исследованию декомпозиционных методов посвящены работы •С.Танаева, В.И.Цуркова, В.Л.Волковича, А.П.Уздемира и др. диссертации рассмотрены особенности решения релаксационных за-ач и способы редукции размерности при оптимизации на евклидо-« комбинаторных множествах.

В общем случае рассматривается релаксационная задача опти-!зации на комбинаторных многогранниках, теория которых развита работах В.л.шеличева, М.М.Ковалева, Л.Н.Исаченко и др. Пока-дна возможность учета свойств комбинаторных многогранников при зализации методов условного градиента, проекции градиента, про-сции обобщенного градиента. '—¡^ .

В задачах оптимизации на множествах Е-^ и обоснована злесообразность релаксации по гиперсфере.

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

Рассмотрены методы оптимизации на множестве Еп. квадратичных функций , где С - симметричная пхп -матрица,¿6 . Для этого класса функций конкретизированы теоремы о построении выпуклых продолжений Щх) на {ц^, сформулированы достаточные условия минимума ^(х) на Е^ , указаны выражения для локальных минимумов ^(ос) на гиперсфере (6) и гиперсферах семейства ! ("П.— ! , получены усиления оценок для минимумов (ас) на •

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

В оптимизационных задачах геометрического проектирования большой размерности получить решение в рамках точных методов но удается. Это обстоятельство побудило к разработке статистических методов оптимизации, основанных на вероятностном описании свойств минимизируемых функций. Статистическая теория глобальной оптимизации нашла свое отражение в работах И.Б.Моцкуса, Ю.М.Ермольева, Л.А.Растригина, С.М.Ермакова, Ф.П.Тарасенко, А.Г.Жилинекаса, А,А.Жиглявского, Р.Г.Стронгина и др.

Пусть Х^Я ~ компактное множество, а - ^ -алгебра его борелевских'подмножеств. На X задана - измеримая ограниченная снизу функция св(х) . Необходимо найти точку такую, что д. д заданного £>0 Эе(£*К8е(Х)+£ при всех

Пусть УсХ . Отождествим пространство элементарных событий с У . Пусть<^У,ЗЬу,^-вероятностное пространство, где % - б -алгебра борелевских подмножеств У , &

- вероятностная мера на . Тогда <й(С0):йЗ€ У есть случайная величина (с.в.) на вероятностном пространстве <У, 3?>у,Ру>.

Свойства функции на У в значительной степени заложены в функции распределения К(У) с.в.

. Отметим,

что для любого £>0: Г^+Е)?* О , г'це

Будем характеризовали экстремальные свойства функции вЭ(&)

- ?л -

на множестве X и его подмножествах некоторым функционалом

который назовем критерием перспективности множества У^ • Значение Ху(Р)оценивается с помощью функции распределения близкой в определенном смысле к Р(У) и зависящей от конечного числа параметров 0 . Величину 6*={*^(Р)_2^(Р!*}|назовем погре-аностью вероятностной модели.

Поставим функции распределения Р (и") в соответствие такую функцию распределения {"Т^")» что для некоторого £ 0 и для любого £>0 : Н^ + г^О , Р*(!?и)=0 . Величина П* яв-

ю распределения 1" *&), что для некоторого 17у £ 0 £>0 : Р*($ + £)*0 , Р*(|£*)=0 . Величина ^ ллется вероятностной оценкой минимума функции 6в(Ьс) на У 11 • может быть выбрана в качестве )■ огом

Другими критериями перспективности множества V являются математическое ожидание и мода наименьшего значения с.в. вероятность генерации п соответствии с С&О) значений с.в.

зе(Ю):и)£ У,

меньших заданного, и др. Выделим класс 7(0^3) функций распределения, зависящих от конечного числа параметров 0 , выборочные оценки которых характеризуются свойством § . Пусть § л В соответственно пвойства состоятельности и асимптотической нормальности выборочных оценок параметров 0.€0 , £ - объем выборки, С-ООЯ^.

Пусть существует такая система множеств^ , что I) I) для любого У^'СТ можно указать коневое число измеримых множеств

, таких что

сV ('Г), VУ,/ с</ (X);

5) для любого У£ ^ определена вероятностная мера ¡3 (с&й) так, пюадН-^ИК*, где П:(Г)€?(Э,^) , ¿«-погреш-

гость вероятностной модели. '

предложена общая схема методов последовательной статисти-оско;1 оптимизации, состоящая в последовательном сужении облас-1! поиска экстремума ¡га основе вероятностных свойств 88(&) на поксствах спстемн

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

Но выборке оценивается значе-

ие критерия перспективности оСу(р) множества У и определяется аправление поиска. При выборе в качестве оС^ 0~) величины ^у редлагаемая схема представляет вероятностный аналог метода вет-ей и границ. В зависимости от используемого критерия перепек-

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

Осуществлено теоретическое обоснование сходимости методоЕ последовательной статистической оптимизации.

Пусть Y множество, полученное на последнем этапе поис: Теорема. Дяя любых £->2£*и 8>0 можно указать так Н=}|(£ ,8) , что для методов, основанных на статистической оце ке минимума по Е*5"N испытаниям,

Р(п|л 82(x)-|gi ае(х)>£} < 8.

Аналогичные утверадения имеют место методов, основанных i других рассматриваемых в работе критериях перспективности множеств

Вцделен класс функций распределения , для которых

при заданной точности оценка критерия перспективности оСу (F) требует меньшего числа испытаний, чем оценка минимума с.в. сб(и)): lD € Y ПО первой порядковой статистике.

Пусть V - с.в. с функцией распределения F(ü')í<J:(0,S*)i функция распределения с.в. V*. такая что i

некоторого

Г[€0* и для любого I>0: F*ty+6)>0, F*0?)=0.

Осуществим выборки в Z независимых размещений с.в. V и с.в, УI . Обозначим минимальное выборочное значение с.в. V чере! ¿О , а выборочную Оценку & € 0 через ^ . Зададимся

е>с

и поставим оценкам оС и ^ в соответствие вероятности

Теорема. Если для заданного В*>0 при указанных вьи предположениях

» Р,= ofRÍ).

Теорема. ПустьО^Р^^ , а ^с(р) и соответстве! решения уравнений Р{£е-|р£*} = р и 'p{||í-l|,l>£> = p . Тогда для класса распределений S) » удовлетво-

ряющих условию (II), имеет место асимптотическое равенство

et(p)=o(Up)) • р—о.

Теорема. Пусть система множеств Т такова, что ля функций распределения 8 ) дополнительно вы-

олняется условие (II). Тогда для достаточно малого £ >0 суще-твуют такие £в>0 иО^Р^, что при лю^их^Р уммарное число испытаний, необходимое для определения решения точностью в и вероятностью р в методах, основанных на гатистической оценке оптимума, меньше, чем при случайном пере-эре на множестве X •

Аналогичные утверждения имеют место для методов, основан-ах на других рассматриваемых в работе критериев перспектнвно-ги множеств системы Т" .

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

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

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

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

Описаны задачи уравновешивания масс вращающихся частей, 'Зникающие в Турбо- и авиамоторостроении. Критерием качества ютупает суммарный небаланс системы.

Теоретические результаты использованы при формализации опи--ний и преобразований плоско-объемных динамических сцен в сис-

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

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

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

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ И выводи

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

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

3. Исследованы свойства ф - и Ю - функций в пространстве геометрических информации, на основе которых осуществлена формализация ограничений в задачах размещения и покрытия.

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

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

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

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

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

9. ^еследои'шн вопросы сходимости,выделены условия эффективного применения методов последовательной статистической О'пч: ываук,

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

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

1. Стоян Ю.Г.,Яковлев C.B. Математические модели и оптимизационные методы геометрического проектирования.-- Киев: Наук, думка. 1986. - 268 с.

2. Стоян ¡0.Г.,Яковлев C.B. Свойства выпуклых функций на перестановочном многограннике // Докл. АН УССР. Сер. А. -19Ь8, № 3. С. 69-72.

8. Стоян 10.Г. .Яковлев C.B. Построение выпуклых и вогнутых функций на перестановочном многограннике // Докл. яН УССР. Сер.Л. - 1988, ;г> 5. С. 68-70.

4. Стоян Ю.Г..Яковлев C.B. Оптимизация покрытий трансляциями ограниченных множеств // Докл. ЛН УССР, Сер. Л. - 1988, .Ф 7. С. 20-23.

5. Стоян Ю.Г.,Яковлев С.8.,Паршин 0.В. Оптимизация квадратичных функции на множестве перстановок, отображенном в R.

// Докл. АН yCCF. Сер. А. - 1989, J? 5. С. 72-76.

о. Свиридов В.В.,Стоя! Е.Ю.,Яковлев С.Б. Отображение параметрической геометрической информации в задачах предупреждения -! контроля // Докл. АН УССР. Сер. А. - 1989, № II. С. 67-70.

7. Яковлев C.B. Оценки минимума выпуклых функций па эвклидовых комбинаторных множествах // Кибернетика. - 1989, № 3.

89-97.

8. Шеховцов С.Б..Яковлев C.B. Формализация и решение одного :ласса задач покрытия при синтезе систем управления и контроля У Автоматика и телемеханика. - 1989, № 5. С. 160-168.

9. Яковлев C.B. Решение малых задач геометрического покры-!ия с использованием структур линейных неравенств // Методы приходной математики в машиностроении. - Киев, 1988. С. 32-37.

10. Яковлев C.B. О некоторых схемах поисковой оптимизация / АСУ и приборы автоматики. - 1985.. Вып. 75. С. 9-14.

11. Яковлев C.B. Об одном классе геометрических задач о окрытии // Проблемы бионики. - 1986. Вып. 37. С. 84-87.

12. Яковлев C.B. Некоторые модели покрытия при решении за-ач оптимизации физического поля //Математическое обеспечение ма-

щиностроения. Киев. - I9B6. С. 51-55.

13. Яковлев C.B. Об одном классе функций и его применении при формализации задач геометрического проектирования // Матемг тические методы в проектировании. - Киев, 198Ь. С. 36-40.

14. Яковлев C.B. Элементы теории выпуклости в задачах опт! мизации на евклидовых комбинаторных множествах // Исследование операций и АСУ. - 1989. Вып. 35. С. 27-32.

15. Яковлев С.В.,йеховцов С.Б. 0 классе задач решетчатого покрытия ограниченной области // Вестник Харьк. ун-та. Управля* мые системы. - 1988. Вып. 315. С. ЮЗ-ЮЬ.

16. Стоян Ю.Г..Аристова И.В.,Яковлев C.B. Геометрическое проектирование: модели, методы оптимизации, применение // Теор; и применение моделирующих систем. - Киев, 1986. С. 36-25.

17. Кухаренок М.А..Струков В.М.,Яковлев C.B. Формализация и решение задач компоновки размещения, трассировки и покрытия // Проблемы машиностроения. - 1987, № II. С. 31-44.

18. Яковлев С.В.,Струков В.М. Направленный перебор вариантов в задачах трассировки )/ АСУ и приборы автоматики. - 1987. Вып. 81. С. 27-31.

19. Яковлев С.В.,а1еховцов С.Б. Об одном подходе к решению задач покрытия системы отрезков // АСУ и приборы автоматики. -1987. Вып. 82. С. 9-13.

20. Яковлев C.B..Гребенник И.В. Экстремальные свойства функций на комбинаторном множестве'размещений // АСУ и приборы автоматики. - 1989. Вып. 42. С. 37-43.

21. Яковлев C.B.,Паршин О.В. Приближенные методы оптимиза ции на вершинах перестановочного многогранника // Вестник Харь ун-та. Управляемые системы. - 1989. Вып. 368. С. 93-98.

22. Яковлев С.В.,Шеховцов С.Б. Об одном подходе к решению задач покрытия системами отрезков // АСУ и приборы автоматики. 1987. Вып. 82. С. 9-13.

23. Яковлев C.B..Гребенник И.В., Стоян Е.Ю. Решёние одног класса задач назначения геометрических объектов // Математичес кое и электронное моделирование^в машиностроении. - Киев, 1989 С. 19--24.

24. Яковлев С.В.,Герасин С.Н. Метод минимизации класса бу левых функций с учетом л|здикатных ограничений // Проблемы био ники. - 1985. Вып. 35. С. 59-65.

25. Яковлев- С, В, 0 вероятностных методах оптимизации на дискретных множествах //Acta Cybernetica .- 1987, £,№2, p. 219-226.

28. Яковлев С. В. ( 0, 1)- модель одного класса задач размещения и покрытия //Program designers . - 1 9 8 6, № 2, p. 1 5 3-1 5 6 .

27. Yakovlev S. On a class of problems on covering of a

bounded set 11 Acta Mathematica. - 1989, ¿2(3-4), P. 141-154«

28* Yakovlev s. Sequential approach for optimization problem // Newsletter. - 1986, N 4, P. 16-19.

29" Yakovlev S. The statistical approach for global optimization // Program designers. - 19S6, И 2, P. 237-24C.

О Л

• Stoyan Yu., Yakovlev S. Optimization problem on Euclidean combinatorial sots // Abs. of 9th Int. Conf. on Mathematical Programming. - Japan, Tokyo, 1988, P. 37-40.

31. Stoyan Yu., Yakovlev S. Quadratic function optimization on Euclidean combinatorial sets // Abs. of 14th IFIP Conf. on Syatem Modelling and Optimization. - GDR, Leipzig, 1989, 1, P. 145-147.

Ответственный за выпуск д.т.н., проф. А. Д. ТЕВЯШЕВ Подл, к печ, 18.12.89 г. ВЦ №15861.Формат 60x84 1/16. Бумага тип. Печать офсетная. Усл.печ.л. 1,75. Уч,-изд.л. 1,75. Тираж 150 экз. Зак, if 557. Бесплатно.

Отпечатано на ротапринте Институт проблем машиностроения АН УССР 3 10046, Харь ко в,ул. Дм, По жарског о, 2/10.