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

М1ШСТЕРСТВ0 0СВ1ТИ УКРА1НИ

ХАРК1ВСЫШИ ДЕРЖЛЕНШ ТЕХН1ЧНШ УН1ВЕРСИТЕТ

ЯКОВЛЕВА 1рина .Олексанщлвна МАХЕМАТИЧНЕ ТА АЛГОРИТМ!ЧНЕ ЗАБЕЗПЕЧЕННЯ РОЗВ'ЯЗАШЯ ЗАДАЧ покгаття ПРИ ПРОНСГУВАНШ ТЕХН1ЧНЙХ систем

05.13.05 - системи.эвтомэтиззцП проектування

Автореферат

дисертацп на здобуття вченого ступени

РЛДМЕЯЕКТР0Н1КИ

I и

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

кандидата техн1чних наук

Хзрк1в 1995

Робота виконана в Харк*вському державному економ!чному ун!верситет1.

НауковиЯ кер1шшк: кандидат ф1зико~математичних наук, доцент БУЗЬКО Яросллв Павлович

0фщ1ЙИ| опоненти-. I. Доктор трхн!чних наук, професор - СЕМЕНЕ! 1Ь Валер Ш Вягяиьович

2. Кандидат тохнИних наук, доцент СТРУКОВ Бйлодимир Михайлович

Провхдня оргашзащя 1нститут прошлом мчшиноОудуь^ння НАН УкраТни^ ,

Захист вадбудеться -1993" рл;гу _о -¿j} годин?

на зас!данн1 спеЩал1зованэ! вчено! ряди К 02.25.03 в Хзрк1вському державному техн!чному ун1в"?рситет1 рад!оелектро~ н!ки (3I072S, м. Харк1в, просп. Ленша, 14). ...

Fax: (0573) 40-91-13. .

3 дисертац!ею мовда ознайомитися у ОКШотец! ларк1вського техШчного ун!верситету рзд1оеляктрон!ки. за адросою: 310^26, к. Харк1в, просп. Лен!на, 14. .

Автореферат роз1сланий •£3- ьсси^юлам^м'д ff року. ■

Вчешй секрет ар слещял|зоваяо1 вчено! рада

В.В. БЕЗКОРОБАУЭД!

ЗАГАЛЬНА ' ХАРАКТЕРИСТИКА РОБОТИ

Актуялыпсть i степень досл1дхеност1 теми робота.

Одн™ !з шшхгв п!двищення ефективност! I якост! проектуемях техн!чних систем е розробка математичного та алгорктм!чного заЗезпечення в!дгов!дних . САПР. 0птим!зац!я сгруктури i параметров систем проектування. дае мозишв1сть покращити характеристики систем, п1даищити 1х над!йн!сть í ефектиЕн!сть, скоротити час розробки, зменшити варт!сть науково-досл!дгащьких роб!т по 1х строренню. ^

При проектуванн! широкого класу систем спостереження, д!апюстики та контролю доц!льно зд!йснювати перэтворення' !нформпц!1 про р1зноман1тн1 по свои ф!зичн1й природ! об'екти проектування в единий вид ' геометрично! 1нформац!1. Це стосуетюя, .зокрема, задач синтезу оптимальних структур при ,проектуванн! систем акустично!- д!агностики í контролю, рад!олокац!йшх систем спостерэкегая, систем' виявлення рухомих ц!лей. При розв'язанн! кояно! з таких задач • необх!дно врахсвупаги такок реальн! геометричн! особливост! елемент1в систем, 1х тип, к!льк!сть параметри розм!иення тощо.

Югас задач проектування, пов'язания з в!добракенням гзометрично! 1нформац11, одержав назву задач геометричного прс,ектувзяня. ' '

Задач! геометричного проектування десять широко описан! в л!торатур!. Це задач! оптимального розкрого мзтер!ал!в. задач! автоматизовзного проектування гэнеральних пяан1в промислових п!дпри:мств. об'емно-гианованого р!иення шхТв та виробництв. задач í конструкторського етзпу проектування рсд!оелектронно'1.1

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

Зазначен! задач!, 1х математичн! модел! та метода розв'язування стали основою створення в!дпов!дних автоматизованих систем геометричного проектування на баз! загально! теорИ САПР. Математичне забезпечення таких систем базуеться, як правило, на моделях та методах розв'язання задач розм1щэння геометричних об1ект!в. Однак щодо розробки систем геометричного проектування, заснованих на модрлюванн! задач покриття, уваги прид!лялось недостатньо. Мльш того, задач! проактування широкого класу об'ект!в 1 систем взагал! не ставились та не досл!джувались як задач! покриття. Цв, можливо, було пов'язано !з труднощами формал!зац!1 задач покриття,

, в!дсутн!стю в!дпов!дного математичного апарату та ефектавних

■ оптим1зэц1йтос метод!в розв'язування-цього югасу задач. Разом з тим результата сучасно! теорИ геометричного проектування дозвэляють п!д!йти до р!шення ц!х питань.

Дисертац!йну роботу виконано на протяз! 1983 - 1995 p.p.- на кафедр! вгацо! математики Харк!вського державного економ!чного ун!верситету в!дпов!дно до план!в деркйвдоетттх НДР: "Розрсбка математичних моделей та 01тгим1зэц1йяих метод!в розв'язання задач геометричного провктувння I шровпджештя рсзультат!в в

■ навчальний процес" (n ДР 0I860I30224); "Розробка математичних метсд1в гоомэтричного проектувшшя" (м ДР ' 018в00049?04); "Матоиатичнэ моделювання склвдних техн!чннх систем модульного типу (n др 01900009448); науково-гехн!чних програм Державного.

■ ком!тету Укра1ни з питань науки i технологШ: проект 06. П4.01 -004-92 "1нт8грована компьютерна технолог1я проектування

■ складнкх систем", проект 08- 04.03У005-93 "Компоновния синтез

ск.пудних техн!чних систем", проект 06.02.05^016-94 "Метода 1 засоби модолювання лрийняття рйпень па рог1ональночу р!внг.

Мета робота та основш завданнл наукового досл1д*ення.

Метой дасертзц!йноГ робота е розробка математичного 1 алгоритм 1чного забезшчення розв'язання задач нерегулярних покритт!в при геомотричному проектуванн! тахн1чних систем, створення комплексу прияладних програм.

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

2)клас1ф1кац1я задач покриття'при проектуванн! техн!чних систем;

3)досл1дк<зння метод!в перетворення ф1зично! 1иформац11 в геометричну га анал1з 1нформац1йно-геометричтк моделей основних •,клас1в задач покритгя; 4)розвиток теор!1 геометричного проектування ' у напрямку. розробки зйгальноГ концопцИ формал!зац11 задач покриття; 5)побудова та анал!з математичних моделей основних клас!в задач покриття; . б)розробка та ■досл1даення математичних метод!в розв'язання задач нврегулярних покритт!в, 1х программа реал!зйц!я; 7)впровадтання математичного та ялгор!тмичного забеспечэння розв'язалня задач покриття при проектуванн! техн1чних систем.

Метода досл!дження грунтуються на використанн! теорН гео'датричтгого проектування, теорИ систем п!цтримки прийняття рйнень. теорИ оптимизпцИ; прогрзмне забезпечення створено на принципах об'ентно-ор!ентованого програмування.

Теоретична цншсть досл1дкешм та його науковз новизна.

Дисертац1я е- закйченою науково-дослШою' роботсп, в як?Я

- б -

розвиваютьея основн! теоретичн! положения теор!! геометричного проектування в напрямку 'формал!зац1! задач покриття, ' Тх розв'язку та застосування.

Наукова новизна результатов робота

-видШено клас задач геометричного прсегтування техн!'ших систем, математичними моделями яких е олтишзацНШ! задач! покриття облает! сукупностю об'ект!ь;

-запропоновано метода перетворепня ф!зкчнс<1 1нформац1! про оО'екти проектування в геометричну для подальшого застосування теор!! геометричного проектування;

-розроблено та досл!джено математичн! модел! штимхзацШшх задач нерегулярних покритт!в; -

-сформульован! ! доведен! неоОх!дн! та достатнх умови -покриття облает! сукупШстю об'ект1Е у дискретному та ' неперервному вкладках; • ''..' "■•.,■

-розроблено алгоритм!чне забезпечення рояв'язування задач покриття при проектуванн! систем спостережошш, д1ягностики та контролю. . •

Ступень достов1рност! результата дисертацШюга досл!дження забезпечуються коректн!стю математичних доведень, застосуванням в!домих та апробованих досягнень сучаснох теор! г автоматизованих ■ систем проектування, нокрема теорхГ геометричного проектування. Теоретичн! еисновки- п!дтверджино результатами чисельних експеримент!« при розв'занн! тостових та моделыгах задач.

Практична цишють тв впровадашпш наукових розробок, . Практична ц!нн!сть дисертаци полягае в доведенн! теоретичних результат^ до конкретних '1нжинерних методик, а такса* в розробц! комплексу прикладах програм, що забзапечуе

- г -

можлив!сть його винористання при створенн! САПР галузей та пЕдприемств р!зиого р!вня.

Розроблене в дисертацП математичне та алгоритм!чне загКзпечення для ироектування складних систем передано до Державного ком!тету Укра1ни з питань науки t технолог!й 1 впровадкено в рамках науково-технично1 ■ програми 06.04.01 -"Тнтегрован! кош'ютерн! технолог!! проекгування". Мзтематичн! модпл! та оттм1зац1йл1 метода геометретного проектування, ззнсопокослн! в робот!, вгасористовуються в Гиститут! проблем магаинобудування HAH УкряТнп, а такоя впровэджэн! в навчалышй прп'нс у 'Харк!вському державному економ!чнсму ун!верситет'1, Xapwtвсякому техи1чиому университет! . рад!оелектрон!ки, Унш?рпитет! внутр!ин1к справ.'

Апробатя роботи. Сснсвн! результата дисертзцМно! роботи док.падэлися та обговорквалкся на наукоЕо-техя!чних KonrJepeimliK Хэркхвськсго' державного экономичного ун!вэрситбту (1983-1990 p.p.), на роспубл!канських сем!нарях HAH • УкраГни з проблем к10-.*7н8п«и "Математичн! методи геометричного проектування" (19:.'0-1905 р.р.),"Проб.1теми економ!чно! к!беркетики" (1988-19ЭЗ p.p.), in 3 робоч!й нарад! "Статистичн! методи в вуг!льн!й протасловсст!", на УкраГнськШ - науково-практичн!й конфэренцП з проблеу економ!ко-прем;тслового розвитку (Харк!в, 1994 р.), на I И1»продн1й конфоренц! I з нетрадиц!йяих метод!в оптам!ззцН с/иг.погорсък, 1991 р.).

Иг5лнсац11 робота. Основя! результат!! роб-тга спуЛл!ковзп! у 7 впугоегх роботах.

Особиитвй внесок автора. Ус! результата лксзргшИйю! potoTK отрсшю за on »лкск-п учлстю тегорп. у прапях. яэгогсзкк* у (Ч.!г:.п-;р?тв1. дкс-'гп'пог-i наедать: ИЗ - <гьра<с1гг::}!я

- а -

к-кратного нерегулярного покриття, розробка математичних моделей та матод!в 1х розв'яза&ня; £21 - класификаЩя, спойрби , формвл1зац11 та оптим!згц1йн1 метода розв'язашя задач покриття облает! сукутистю od'eKTle; [41 - розробка 1нформац1йно -гвометркчних моделей задач побудови оптималы-глх структур систем спостереження, д!агностики- та. контролю; 15,71- теорь гичний анал!з зображення структур даних в СУБД, розробка моей описування даних," приклада! аспекта; [61 - розробка структура пакету прикладних програм AICKTD, розробка оснобних програшшх модул!в.

Структура та обсяг роботи. Работа складаеться з вступу, п'яти розд!л!в, заклзочно! частини, списку використано! л!тератури з 107 иазв, 9 малюшйв, 5 таблиць, додатку - обсятом . всього 112 сюр. машинописного тексту.

ЗШСТ РОБОТИ

У встуш дано коротку характеристику об'екту досадження, обгруитовано. актуальность теми дисертацШна! роботи, •наведено' огляд л!тератури з досл!джувано! проблема. 0£ормульовано мету, основн! задач!, наукового досл1дження, обгруптована наукова новизна та практична ц!нн!сть отриманих результатов.

У першоиу розд1Л1 наведено ям!стоыи- постановки ряду 'практичних задач оптимального прооктування техн^чних систем, математичною моделлю яких -е задач! покриття. Дано загалшу характеристику нерегулярна покритт1в, наведено ix класифжапш.

При проектуванн! систем споствроження, диагностики . 1 контролю toiye широкий клас задач, в яких критарШ якост! задаетьея як оц!нка характеристик об'екту' не безпос&редньо, а за '.нопряшми дашаш, -наприклад, по сигнэльШй .!нформац!1. У такому

тападку задача Шернрчтпц!! стешшя е оборноною'по в1дноаенню до модел! процесу. Ф!зична модель, яка пов'язуе характеристики огЗ'екту та спостер!гаему 1нформац1ю, поеиннэ бути побудована так, [¡¡об булэ моютивгсть зд!йснювати контроль 1 д!агшстування влпстипоскй об'екту.

Впрт1сть та складн!сть проектуемих систем контролю та • споотереження при дотрнмувпнн! -вимог до 1мов1рност1 виявлення сигналТв залежать в основному в!д розм!р!в контрольовано! площ! обо поверхн!, НаЙголовн!ш! вимоги иодо систем д!агностики ! контролю так!: -

-гшсгемз повинна внявдяти джерела сигнал!я у козш!й точц! контролюемого об'екту та визначага його м!сце знаходкення;

-контроль за кожяою точкою облает! повинен зд!йс?жватися м!н!мчльним числом контролкючих датчик!в, прр!&?ач1в, т.!4;

-еплив зовШпШх фактор1в та. дуСлозэ1ШЯ_ Ф1ксзц1й ситаал!в р!зними приПмачами мають бути змэшьшен!, тобто перекриття зон д!Т об'.ект!в повинно Оути мВДмэльним.

В роздШ розглянуто задач! проектування систем акустичноТ ем!с!1, рад1олокац!йни систем, систем сшстер!гання небезпечнях явит, систем автоматизац!! ви6ух1ених роб!т тоцо.

Показано, що при в!дпов!дному перетворенн! ф!зично1 !нформац!! про об'ект у- геомэтричну ц! задач! мояуть бути сфорглульован! як задач! покриття контрольовано! облает! системою об'ект!в, геомотрична форма ягасс Б1дпов!дэе коиф!гурац!ям зон впевненого прийому сигнзл1в та зон виявлення, котр! визначаються типом приймач!в, датчик!в, станц!й поперздтсння, т.!.

В робот! проведено клас!ф1кац1ю задач покриття за формою облает!, за формою иокривяючих об"ект!в, за влзстивостя\га метрйчких характеристик об'ект!в, за критер!яш'якост! покриття.

В другому розд1Л1 описано 1нформацШга-геометричн1 модел! задач покриття, заснован! на'поняттях геометричноХ 1нформаци, !1 вЗдоОраашнь та геометричшх полхв.

Для зд1йснення ыатематично! постановки задач пскриття необх!дно здМснити перетворення ф!зично! 1нформац11 про проектуемний об'ект в геометричну. Геометрична 1нформэц!я мозг.е бути представлена у вигляд!

{-}■ №

де - компонента простороЕо! форми, <и> - метричн!

характеристики об'екту, <р - параметра розм1щення, що задаить м!сцезнаходаення оО'екту в-простор!.

Геометрична 1нформац!я g=({s),{m},íp}) явпяеться элементом

простору геометричних !нформац!й С. Задача покриття, як задача гвомэтричного проектування, . нолягае в вхдображенн! . простор 1в геометр!Чних 1нформац1й, що йдикуються сукупн!стю об'ект!в проектування.

Геометричну 1нформац!ю % назкемо парамотричною, якщо П ксмпоненти е функцП деякого векторного параметру х «¿Р^, тоото 8=г(х)=[{з(х)}. {т(х)}. {р(х)}).

Нвхай Б о й*5. П1д Б розум!еться к-м!рний многовид, шкдаша 1зольованих точок'тощо.

ц{хух еБУ. Мдображешш виду Б.-» б назвомо

геометричвдм полем, а с!мейство С(х).- геометричною роал1зац!ею поля. При завданн! в!дпов!дно1 тополог!I можна розглядати як прост!р параматричних геоматричних !нформац!а.

Розглянэмо двяк! класи параматричних геометричних !нформац!й та 1ндукованих ними геометричних полай.

Нахэй компонента геометрично! 1нформац1Г е функцЬши часу

t^D=rîj. Таку 1нформац1ю назвемо вдстац1онарною геометричною 1нформац1ею i позначимо " , '

g<t)=({s(t)J. {m(t)}. ,{p(t)}j.

1нформац1я g(t) породжуе npocTip нестац!онарних геометричних

1нформац1й G(t) та 1ндикуе в кожний ф!ксований момент часу■ tQsR] точкову множину S(tg) с R1.

Геометричне полэ r| -f G назвемо.нестац!онарним геомётрачним полем. Так, нестац!онарною геометричною 1нформац1ею визначаеться параметризована по часу с1майство "поверхонь р!вня нестац!онарного ф!зичного поля. В1добрая8иня, що 1йдукуеться при цьому, е нэстац1онаршш геомэтричннм полей.

Нехай п!д вектором х розум!иться параметр« розм!щення <р> гесметрична! 1нформацН g=({s),{m);{p)) ' _

В цьому вшадку • ■. •

g'g(p>= ({э<Р>}. {»(р)}. {р}}' . Таку геометричну 1нфоркац1в назвеио аф!нно-залекною. Ящо {pî=<p(t)>; то маемо нестац1ояарну афйшо-залеЕну геометричну 1нформац1ю тощо.

* • g

Геометричне поле <р> -» G, що 1йдукуеться 1нфориац!еп g(p),

назвемо афйно-залежним геометричним полей.

В1дзначимо деяк! властивост! геометричних пол!в. Нэхай S={s>, М={ш>, Р={р> - кношни просторов® . форм, значень ме'тричних характеристик î параметрîb розм1щення геометрично! 1нформац!1 g=({s},{m},{p}).

Геочетричне поле в ? G мажоруе геометричне поле D -» ' G 1 позначаеться

D f1 G * D £ G.

якщо для будь-яких Хе D ■. •

^ <х)-({з, (х))-{пи №)}.{р1 (х)}) 2е

-о {Че^)} - {Ра<х>}} •

де >а - ь!днсшення часткового порядку на декартовому добутку ЗхМхР.

При заданому в!дношенн! часткового порядку ге на множил г С &

гйоштричне поле С ■> 0 иьляеться монотонно неспадаючим (незростаючим), якщо для будь-яких х,, х2 «= Б, такта що хх х, мае м!сцв включения Б(в(х1))=> 5(£(х2)) Б(в(х1))).

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

Розглянемо точкоеу мнокияу 5<х1,г) с- р/. обмежену поьархною р!вня яестац1онарного ф!зичного поля, яке описуе в кожаий момент часу г ' розпод!л поширення в!дпов!дного процесу, виникяеного ,

о

в точц! Х^е й11. Таким чин аф1зшо-залекне геометричне поле ■ Е

де И1 =€х1. х2,..., Хд}.

Це поле е.монотошшм по г «-Н* 1 а!даов!дко може бути

В

задане у вигляд! вхдобракення ^ С, яке рзал!зуе параметричне по х с!мейство геометричних !нфэрмац!й

Вх = 8(х1,1(х1)) = ({з(х1)},{ш(х1>>,{х1}), де Их^) - момент часу досягання'зоня контролюпроцксом,

со 1кглк в точу! х1. --

СИмейство геометричних■1нформац!й ,я2,...,£п> шдукуе в простор! й2 систему точновех мнонош ..

в точц! х^е й11. Таким чином, рвал!зуеться нестац!онарне

ле -^х ?

1 мт!т.плы;е нал Uten системою к1.чьц8 o-CtS^}). Розглянемо систему множил c-Us^) с c<cs^>>. що задов 1льняе настушшм умовам: 1. int S^ n Int о v

2. У J з "l- sjn Sj:

3. us,=u st 1. 1

Ця система породхуеться сукупн!стю геометричних 1нформац!й

ig").

Задача проектувзяня оптимально! по >шслу датчик!в контролю пистиуШ спостережешш може . бути сформулъована у терм!нях геометричних !нформац!й як задача визначення м!н!мально1 по включении Шдсистеми о(f)) точкових образ!в Sj(g^). Рспв'ялашгя задачи м!стить у с об! так! ётапи:

- модолювання несгац!онарного аф!нно-залеят?ого поля

ч g(x.t) D, х • С;

визначення t^Kx^),. 1=1,2,..; ,п - та. стац!онарнкх

аф!нно-залежних геометртших !нформац!й g1^g(x1,t(x1>);

* »

- "г.обудовз Шдскстеми ' W ТОЧКОВИХ 0брэз1в Sj(ßj), що чкв!галантно формуванню одноточкових представник!в ,элемент!в Hier систем як клас!в екв1валентност!;

- покудова дискретно! модел! задач! на обмеженМ систем! клас!з вкр,!взлентност!;

- розв'язання зпдзч! методами дискретного прогрзмувэння. Розглянемо 1!гформац!йно-геометри,шу модель клзсу задач

гыкриття у вштадку, коли мегом проектуваши стетемп е контроль макс/ма";ыю mokuhboI шгогц! (псверхн!) контроляемого об'екту.

№"Х1хг.дно слротатувати мережу об'екПв контроля таким

чином, пк''' п

U SO -» шах. 1=1 1 .

де м!ра (П.ГСЩЗ) зони вилвлення контролгагчого об'екту. ил

зона описуеться пачатковою. .геометричною 1нформац1ею

g={g1.....gn} 1 залететь в!д 'вектора параметров V, що визначае

м!сцезнаходаення контролюючого об'екту, Його д!аграму направленной!, потужн!сть, т.!.

Таким чином, £=£<»). Звврнемо увагу на те, що вектор параметр 1в ш, як правило, не включае в себе час I- , тобто !нформац!я g(w) являеться стадЮнарною. Параметрами розм!щення {р> при цьому виступають координади м!сцезнаходкення ■ контролюючого об'екту, а компонента (з> ! {ш> задають характеристики меж облает! виявлення.

Отже маемо параметричну аф!нно-залекну стац!онарну геометричну 1нформац!ю - в(р) = <Сз(р)},{т(р>>,{р>), що 1ндукуе'стац!онарна оф!нно-залежне поле.

. В!дзначимо, яйцо область д!1 контролюючого об'екту з параметрами розм!щеш1Я р^ е п1дшюжиною зони д!! 'об'екту з параметрами розм!щення р^, то гесметричне поле . Щдукоьане 1 (форматов в(Р^) мажоруе геометричне поле,. 1ндуковане !нформац!ею,г(р^). ' .

ТреТ1й розД1Л присвячено досл!джвнню основно! задач! покриття, побудов! II математично! модел!, формал!зацх1 умов покриття !з використанням апарату Ф-функЩй та ш-функц!й.

(фэрмулюемо- осювну задачу покриття облает! сукупн!стю

геометричшх об'ект!в. Нехай геометричн! об'екти 1=0,1.....п

1ндукуються .геометричниш !нформац!ями е1=({з1),{и1>,{р1>), де компонента {р01, {з0>, (ь^), <ш1)> 1=1,?,...,п - ф!ксойан!. Пргаустимо р0"{0,...,0) 1 позначямо через 51<р1) • об'екти з

параметрами розмйцеяня р^й1", 1-1.2.....п • в!дпов!дно. потр1бно'

тазначиги так! параметра розмйцекнн -Ср±>, \-л-,г.....и, при яких

ваконуютася умоьи' покриття, тобто коша точка мношпг й(р0)

належить хоча б до одн1е! з множин Бф^), 1=1,2,..; ,п'.

Область W допустимих р!шень в основнГй задач! покриття формуеться таким чином: .

W = {(p1.p^...ppn>/SD(m0) s U S1{p1)J-

' ' n

= сРг + { U ир^,...^)^ n cS1(p1) л s0(m0))]>= (p1 .Рг.....Pn>

Rnt /n „ и i 1-1

= Pr С U KPpPg.....pn)x(.US1(p1) e Sq^q))] n

R (^.Рг.....Pn> '

n R^xiO», '

да Pr^nt - оператор ортогонального проектування на прост!р Rnt, {Q}- нуль простору Rnt, acte- символи операц!й доповнення i •р!зниц1 за МШковським в!дпов1дно.

■ Оптим!зац!йна задача покриття формулюеться як задача пошуку экстремума функцИ якост! покриття на мнокин! W допустимих параметра розм!щення покривних об'ект1в, тобто extr • п (р^рз.....рп).

(Pv-'-Pn^W

Таким чином маемо задачу математичного програмування, в як!й область W моя» бути описана нер1вн1стю г<т0,р, ,р2.....рп) г О,

Для формал!зац11 вигляду функцИ г(т0,р1 ,рг,.,. ,рп) в робот! було вякорлста'ло апарат ф-фуннцш. Маема

Ф(П10.Р1,Рг.....РП1) * О, да Ф(ш0,р1,Р2,...,рп) - Ф-функц1я об'екПв S0(mQ) 1 S(p1,p2.....Рп )= йЧ US^).

Використання Ф-функц1й мовдшво ли© в задачах з невеликим

числом покривних об'ект!в, !накше виникають труднощ! з формувэнням функци ФОЛд.р, ,рг,... ,рп).

В загальному випалку для формал!зац11 анал!тичкуго вигляду

функцН rinig.p^.pg.....рп) пропонуетьоя клас <о-функц1й.

Нехай геомстрична 1нформ-.щ!я .....sT>,

{Ш1 . . ,ШП}, <p1 ,Pg, . . . ,pnJ) 1ИДУКУЕ .В npOOTOpi R1 H'lfitp

гочкових множил S1 ,S2. • • • .Sn» Зд!йснемо вЗдобранэтшш В, що те бути суперпозиц!ею теоретико-множиншх онеран!й. 1: побуду-:мо множину

n = b(s,,s2.....5п) е r1,

яка задасться геомвтричнои !нформац!ею

gB=(B(s, ,s2,... ,sn), {ш, ,Big.....mn), {р,,рг.....pn>).

Розглянемо функц!ю

,®2'''" ,mii'Pl *Р2'''' 'Pn

)=м <n>.

да > - Mlpa Лебега. Таку функц!ю назЕемо «-функцию.

В робот! наведен! основи! якост! ш~функц!й, щэ дозволять Еикориатовупати 1х при формал!зац11 задач покриття. За дспомогою ю-функц!й умова покриття ' при ф!ксовпних метричних характеристиках покривних об'ект!в мае вигляд и,в(РгРг.....pn> = ы1<Ро>»

да bcs1 ,5г.....sn) - s^ [ usj. ks0) = s0.

.Яйцо множима допуотамих р!ш,ень в задачах покриття не пуста, то умозу покриття можна представити в Форм!

, ыв<Р1'Р2.....рп} ** шах:

" Таким чином, лошук пзраметр!в розмйцешш об'ект!в, зздогсльняючих покриття облает!, мохе Сути введений до задач! 6tгумовнсI.опткм1зац11. '•'

У роздШ наведено приклада розв'язання моделью« задач

покриття з використанням и-функц!й.

У четвертому розд1Л1 розглянуто питания формал!зац!1 умов покриття за допомогою структур нер!вностей та пропонуються оптим!зац!йн! метода розвЬ'зування задач нерегулярного покриття, побудопан} на загальнШ схом! посл!довного анал!зу та в!дс!ву варiант in.

Структурою народностей S(F(x), д, т) назвемо упорядкований набгр норШюстей F(x) =Cii(x)>o. i= TTro, х <= R^}. з визначеними для кожно! пари нер!вностей операц!ями кон'шкц!! 1 диз'юннц!!, зображеними у вигляд! симетрично! матриц! ОперацП

кон'юнкцП м1ж 1--ю ! J-ю нер!вностями в!дпов!дае <5^=1. а операцИ диз'юшсцП - <5^=0; при цьому j=1, J7m, j="T7m.

Ha6ip F(x) с Г(х) нер!вностей структури S(F(x); а, и) назвемо повною. системою нер!вностей ц!е! структури, якщо ус! nepiBHOcTi набору ?<х) зв'язан! м!ж собою опера!ею кон'юнкцП, а г-^ид нер!вностей набору F(x) немае н! одного, зв'язаного одночасно опермц!ями кон'юнкцП з ус!ма нар!вностями з ?(х).

Безл1ч знячень х R , при яких сум!сня точа б одна повна система неровностей структури S(T(x), д, и), назвемо множиною, заданог, ц!ею структурою.

Нл множил! структур.нер!вностей Еизначен! операцИ перер!зу ! об'едаання, в1дпов!дн1 перер!зу 1 об'еднаннш многая, заданих цими структурами. Якщо вс! нер!вност! набору F(x) л!н!йн!, то структуру S(F(x),'&, га) назвемо структурою лШйних нер!вностей.

Позначимо через S(F1(x),&1,m1) структури неровностей, як1

задзють у np-SCTopi Rk зм!ннкх х=(х1 ,Xg.....хч) множищ S^xb,

1=0,1,... ,ti, з через S(F1(x),A1,m1> - структур,и, як! зэдчют*-множили сЗ.(хЪ. 1=1,2..'..,п.

Розглянемо множину • .

[ n cSj/x1» n SQ(0).

1=1

При фЬссованих параметрах розм!шення об'ект!в S, ,Sg.....Sn

вона задаеться шретином структур

5*(Г*(х).д*,т*) = S(F0(x),A0,m0) n I n^StFjU-x1).^^)].

Нехай . елвмэнти вектор!в х=(х1.х^,...та x^x^.xg,... , 1=1,2,... ,п приймають дов1льн1 значения. 1од! ця структура нер1вностеЙ описуе деяку множину f в простор! Rk(n+1 ) ортогояальну проекц!ю множини W на прост!р R101 з системою координат Ох].. .х^ х^.. .х^.. .х^1.. позначимо через V, тобто

Покриття облает! 50(0) сукупн!стю об'ект!в S^ix1), 1=1,...,п мае бути, коли

I п cSjiX1)) n SQ(0) «= о.

Таким чином, область SQ буде покрито тод! ! т!льки тод!, коли параметра х1=<х|,х|,...покривапчих об'ект!в ■ S^, 1=1,2,...,п задоЕольняттшуть умов!

. <x1,x2,...,xn) « R101 \ lnt V.

Для формал!зац!1 облает! I припустимих шкритт!в необх!дно посл!довно .'провести наступи! опзрац!!: •

-сформувати структури S^Cx),^.^) та S(F1(x-x1),AjL,rai), що задають.точков! множини S0(O), cSi(x1), 1=1,2,...,n;

-сформувати структуру S*(F*(x),A*,m*);

-побудувати множицу V, як ортогональцу проекц!ю множини, що задана структурою S*(F*(x),A*,m*), на прост!р R101 зм!нних х].. .х^

kn

-знайтя додаток множили intV до простору Rm .

Нехай область покриття i покриви! об'екти являють собою

многогранники у простор! R^. Тодх вони описуються структурами

лдпйгах нер!шостей 1 Кожина V таков задаеться структуре!

лШШшх неровностей S*(F*(x),A*,m*); Вид!лимо ус! повн! системи

нар 1 внос; те it структури S*(F*(x),д*,п*) 1 перенумеруемо ix. Нехай

число повних систем дор!вш>е Тод!

к ,

S*(F*(x),д*,тж) = U S(Fl!(x),Д-,,п1-|),

, 3=1 де Aj - одиничн! матриц!, 3=1,2.....

Сформусмо множину V - R501 \ int 7. Розглянемо сукупн!сть

ЛОГ1Ч1ШХ EMimnix z^.....»2шж> встановивши в!дпов1дн!сть м!ж

номером нирияюст! з F*(x) ! индексом лог!чно! зм!нно!. Тод! йнокин! W в!дпов!дае к.н.ф. •

X

■ D = л ( V z1), j=1 lelj 1

!j - шгспкина номер!в нер!вностей, щэ входять до набору ' Fj<x), а логтчшй змшн!й z^ в!дпов!дае i-а нпр1вн!сть набору, взята з прстилеюпш знаком.

Деретьоримо к.н.ф.- у д.н.ф. 1 зобразимо D = В2, де D1 ! ü2 -■ дипюнкцИ таких кон'юшаЦй зм!нних, лким в!дпов!дають сум1сн! 1 нооум!сн! системи нер!вност9й' в!дпсв!дно. При цьому множин!. допустима р!шень в задачах покриття в1дпов!дэе д.ц.ф. D,. На k-му етап! перетворения 1 виклкпення кон'шктгв. що в!дпов!дають несумгашм системам нер!вностей. маемо д.н.ф.

h _ h. к -Q = Ч ( л u z.) = У IÄ,

3=1 1*1» 1 J

де множшп! I.j£i1,2,...,n*), J=1.2,.tk визначэються складом Ej.

Сформуемо дерево ршень задач!. На k-ому р!вн! кокна

к ^ 1т

вершина А^ дерева визначае множину- И^ .яка описуеться системою нер1вноотей.маючих номери 1з ' в набор! Г*(х) . ЦМ мношн! в!дпов!дае д. н. ф. В^. Таким чином, процес побудови вершин дерева р!шень визначвгться представлениям к=1,2,'.. .х.

Мнокини «Ц, 3=1,2,... ,1;х назвемо допустимими множинами х к

р!шення. а множини 3=1.2,,.. к<л - частковими множинами р1шень. Множину назвемо допустимою частковою множиною. якщо II родова множила непуста.

В робот! розглянуто питания формування часткових допустимих множив р!шень. сформульован! правила, що дають моклив!сть в!дс!ву неперспективних вар!ант!в на пром1шшх етапах р!шеш!я задач!. Запропонований процес формування мнокини допустимих покритт!в. дозволяе подати II у вигляд! об'еднання м!н!мального числа випуклих мнохин. для описування яких- використовуеться м!н!мальне число нер!вностей з набору Гж(х).

Розроблэно комплекс програм для розв'язування задач покриття !з застосуванням структур л!н!йних нер!вностей. Наведено результата р!шэння модедьних задач.

П'ятай роздгл присвячено формал!зац!1 ' дискретних оптим!зац!йнкх задач покриття, виникаших при проектуванн! систем- попередження та контроля). Побудовано класичн! модел! булевого покриття та нел!н!йн! модел! з булевими зм!ннкми. Досл!даено питания адекватност! дискрйтних та неперервних моделей. Запропоновано метод квпдратично! булево! оптим!зац!1.

Розглянемо клас задач покриття, в няих параметри розм!щення об'ект!в 51р52,...,5п приймають кХнцеву множину значень

р1 ,р2.....рт. Нехай К -к!лъце множин, що породкено множинами

50(0),51(р;)),1=1,2,...,п; 3=1,2.....и. Сформуемо систему ТеК,

Т=(Т1 ,Тг,... ,Т»>, 1=сагй Т.-яка задов!льняз умовам

г

и тк= з0(0), ш п шг 1^ = о,

К— 1

В робот! приведено засоби формування система мнокин

,Тг.....Т(_>. Доведено, що зам1сть формування вс!х елеменИв

кхльця X можна розглядати !х одноточков! птдмношни як класи еквтвалентност!. При цьому при достатньо малому «>0 множина Т ноже бути е-с!тк0ю множшш Бвэдемо булеЕ! зм!нн!'

Г1, якщо об'ект мае параметри розм!щення р^;

С:

21 г

10, в противному випадку. Визначимо константи

•I,. якщо Тк с Э^р^; 0, в противному випадку. Тод! об'ект Зд буде покрито сукупн!стю об'ект!в 31Р...,5П при умов! п п

Ь К=1'2.....

Яшцо при розм!щенн! об'ект!в 51,5г,...,Бп виникае додаткове обмеження, щоб кожна точка облает! покриття належила не меньш,

н!к г об'ектам, маемо умову п • ш 1=1 ¿=1 ^

0ск!льки на кожна м!сце пригначаеться т!льки один об'ект !

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

наступи! додатков! обмеження га

Е < 1, 1=! ,2.....п,

ш .

г; ^ 1, 3=1,2,....и. 1=1 .

Розглянемо , задачу, покриття облает! м!н!малытм числам покривних об'ект!в. Тод1 критер!й якост! покриття мае еигляд

п ш

E E 2-i-i -» min. i=1 - 3=1 13

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

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

Для кожного об'екта з параметрами розм^щення pj знайдемо

м!ру (площу) то! його .частили, яка налепить облает! покриття,

toöto C^=/j[Si(p;j)\Sg]. KpiM того, вичислимо м!ру (площу)

попарного пэре тину об'ект!в CijW=p[Sl(p1)nS)í:(pl)]. Тед!

критер!й якост! покриття мае вигляд

п m п ш n m п

Е £ Е Е cliklzi lzlcl + е e c1íz11 + т1п-1=1 з=1 k=1 1=1 101U 13 ш i=1 3=1 J J

Сформульована задача нзлекить до класу задач квадратичного програмування з булевими 'змйгаими. Для, I! розв'язування запропоновано метода оптим!зац!!, побудован! на можливостi описування облает! ,допустимих р!иень у вигляд! " перетину Пперкул! ! г!перкуба. Досл!джено питания збхгання та ефективност! метод!в.

Розглянуто результата застосуззння розроблених- моделей, метод!в 1 алгоритм!в для розв'язапня оптим!зац!йних задач покриття при розм!щенн! станц!й контролю та поп-зредження за критер!ями м1н!мально! к!лькост! станц!Й 1 максимально! плещ! контрольовано! поверхв!. Запропонован! в робот! метода та-алгорктмп реал!зовано в вигляд! комплексу прогряад на мов! TURBO PASCAI, як! ор!ентован! на ПЕОМ.

Сдераан! результате пхдтверглуать • ефективн!сть м<п?мпт;пного' та алгоритмг-шого габгзпоченна, г,о р^зреблено в

ВИСНОВКИ

Сформулюемо основн! результата, здобут! в дисертац!йн1й робот!.

1. На тпдстяв! перетвв'рення ф!зично! 1нформац11 про оО'ект проектування в геометричну вид!лено класи задач покритт!в в системах геометричного проектування. Наведено !х загальну характеристику, анал!з та класиф!кац!ю.

2. Дослг;жено заеоби описування та в!добракення геометрично! тформацН в задачах покриття, побудовано та досл!дзшно 1нформац10но-тебметричн1 модэл! цих задач. ,

3. Зд!йснено розвцток теорИ геометричного проектування у. напрямку розрооки та реэл1зац11 загально! концепцН формал!зац11 задач покриття. Побудовано математичн!-' модел! основних клас!в задач 1з застосуванням функц!Й сдец!ального

■ типу ( Ф-функц!й та ш-функц!й).

• 4. РозроСлено метода . конструювадая облает! допустима р!шень в яеперершшх задачах нэрегулярних покритт!в у випадку, коли область та об'екти покриття е многогранники. Метода грунтуютьЬя на використанн! структур л!н!йних нергвностей.

5. Розроблоно процедуру реал!зац!! метод!в посл!доеного анпл!зу та в!дс!ву вар!ан!в в задачах покриття обмежено! облает!. Досл!джено правила формування дерева р!шень та критер!! в!дс!ву неоптимальних покритт!в.

е.. Побудовано дискрета! модел1 задач покриття. Зд!йснено дискретизац!и облает! покриття в непарервних задачах, досл!джено питания адекьйтност! дискретних 1 неперервних моделей. .Доведено, цо при достатньо малому кроков! дискретизацП неперервна та дискретна модел! екв1валентн1.'

7. . Розрсблено . метода оптим!заЦЦ квадратичних фуккц!й на

О

множилi булевих зм!нних для класу задач покриття за критериями спеШального виду.

8. Реал1зовано програмне забезпечення на алгоритм!чн!й мов! TURBO PASCA1 для розв'язування практичних задач покриття в системах спостереженяя, д!агностики та контролю.

Надрукован1 пращ за темою дисерта'Ч I

1.Бузько Я.П., Яковлева И. А. Дискретная модель оптимизационной задачи k-кратного нерегулярного покрытия // Математическое и компьютерное.моделирование. - Сб. научи.трудов.

- Киев, 1994. - с.82-85.

2.Бузько Я.П., Шеховцов C.B., Яковлева И. А. Задачи покрытая в технических системах: вопросы формализации //Математическое моделирование и оптимизация технических и информационных систем.

- Сб. научн. трудов.- Киев," 1995. - с.63-67.

3.Яковлева И.А. Специфика реализации оптимизационного пакета для решения одного класса задач покрытия // Украинская научно-практическая конференция'.- Тез. докл.- Харьков: ХГЭУ, 1994. - с.21.

4.Бузько Я.П., Яковлева И.А. Задачи покрытия области и их экономическая интерпретация // Украинская научно-практическая конференция. Тез. докл.- Харьков:, ХГЭУ, ,1994. - с.22.

5.Кудрявцев В.А., Яковлева И.А. Об одном подходе к рациональному размещению информации в системах управления базами данных // АСУ и приборы автоматики. - Харьков: Вища школа.-1985. - Вып.74.- С.71-77.

6.Кудрявцев В.А.,Яковлева И.А. Разработка пакета прикладных программ автоматизированной информационно-поисковой системы AICKTD // . Материалы республиканской научно-технической

конференции молодых ученых. - Харьков, 1983 . '- с.25-27.

?.Бузько Я.П., Кудрявцев В.А., Яковлева И.А. Технология обработки запросов в автоматизированных информационно-поисковых системах // 3-е рабочее »'.совещание "Статистические методы в угольной промышленности". -.Тез. докл.- Кемерово, 1984. -с.9-10. '

Summary

Yakovleva I.A. Mathematical and algorltnic support for solution of covering problems In designing technical systems.

The thesis is presented for the candidate science degree in technology. The speciality code. Is 05.13.05 - automatic design systems. 'Kharkov State Technical Unlvferslty of Radioelectronlc.s. Kharkov, 1995.

The dissertation work Investigates theoretical foundations fc formalizing the problems of covering in geometrical design systems,' proposes inf о hmt ion-geometrical ana mathematical simulation of the .problems, describes tie» optimization methods of ^eir solution. The research results have been put in practice in the form of an applied programs s*\t for IBM PC.

Аннотация

Яковлева И.А. Математическое и программное обеспечение решения задач покрьгпш при проектировании технических систем.

Диссертация является руксшсью,представленной на соисканка ученой степени кандидата технических наук по специальности 05.13.05 - системы автоматизации проектирования. Харьковский государственный технический университет радаоэдаетрстаси. Харьков, 1995.

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

КлвчовI слова: геометричне проектуваняя, задач! шкриття, матемзтичн1 модел1, отим1зац1йн1 методи, алгоритмов забезпе-чення.