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

АКАДЕШЯ ЬаУК УКРА1НИ

! « • 1

\ ! и

ПГ г. ОД

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

1 з ;:::з

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

Коняк Валентина Михайл1Бна

МАТЕМАТИЧНЕ ТА КОМП'ВТЕРНЕ МОДЕЯВА1ШЯ НЕРЕГУЛЯРНОГО Р03М1ЩЕННЯ ПЛОСКИХ ГЕОМЕТРИЧНИХ С-Б' 6КТ1В У ОБЛАСТЯХ Д0В1ЛБН01 ПРОСТОРОВО! СОРЧИ

05.13."$^- натенатичне моделявання у наукових досл!дженнях

Автореферат дасертацП на здобутг» ¡¡лукового ступени, доктора техн!чних наук

Харк1в - 1996

Дисертац1ею е рукопис

Робота виконана у в1дд!л1 математичного Моделювэння та оптимального проектування 1нституту проблем машинобудуванйя HAH Укра!НИ

Науковий консультант : член-кореспондент HAH У1фа!ни доктор техн!чних наук.професор Стоян Вр1й Григорович 0ф1ц1йн1 опонентй : доктор ф!зико-Матенатичних наук,

Пров1дна установа - Дн1пройетровський державний

уШверситет (MtH-во осв1ти Укра1ни, м. Дн 1пропетровск)

ауд.М112 на зас1данн! спец1ал!зовано1 вчено! ради Д 02.18.02 в 1нститут1 проблем машиноС- дування HAH Укра!ни за адресов: 310046,Харк1в, Вул.ДМ.Пожарського, 2/10

3 дисертац1ею можна ознайомитися у б1бл1отец! 1нституту проблем машинобудування HAH Укра1ни за адресов 310046Дарк1в, вул.ДМ.Пожарського, 2/10

Автореферат роз1сланий " J9- ob 1996 р.

Вчений секретар спец!ал1зовано! вчено! ради . ВеретельНик В.В.

щх эсор

Шевченко Олександр Миколайович доктор техн1чних наук.професор Петров Ёдуард Георг1йович

доктор техн1чних наук.професор Пан1жев АнатолШ Васйльович

загальна характеристика ровоти.

Актуальн!сть робота. Одним !з основних нащщмк!в науково-техн!чного прогресу е розробка нових базових технолог1й, що дозволять Шдвищити ефективн!сть використання ресурс!в та знизи-зити енерго - та матер1алоемк!сть виробництва. В. уыовах »орет- • ких обмежень ф!нансових та енергетичних ресурс!в у наш!й кра!н1 створення таких технологий ножливо при умовах розробки та впро-вадасення натематичних моделей та оптиы1зац1йних ыетод!в, що до-зволяють знаходити розв'яэання на необх!дному р!вн! оперативно-ст1 та економ1чност1. При створе нн! ресурсозбер!гаотих та без-в1дх!дних технолог1й важлива роль в!дводиться задач! нерегулярного розмщення об' ект!в, яка е математичнов моделлв таких ваас-ливих практичних задач, як задач! розкрою пронислових матер!а-л!в, задачI рац!онального використання в!дход!в, задач! розм!-¡цення обладнання з урахуванням його центровки, задач1 розн!щен-ня р!зногабаритних модул!в на монтажних платах, задач! ноделю-вання зернистих середовиц сипучих матер!ал1в 1 т.!н.

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

Дисертац!йна робота виконувалась у в!Дд!л1 математичного моделювання та оптимального проектування 1нституту проблем машинобудування НАН>Укра!ни з 1980 р. по 1995 р. у в1дпов!д-ност! до план!в науково-досл!дних роб1т за програмани: ДКНТ (1992-1996рр.) (6.4.1 'Чнтегрован! комп'втерн! технолог И проектування" Д.Р. N 0193Ш20060, Д.Р. N 0193У020061): ПрезидП АН УРСР (1981-1985 рр.) (1.12.12. "Проблема ТеорИ автоматиза-цП проектування" Д.Р. N 01817013807); ПрезвдИ АН УРСР (19861989 рр.) (1.13.5. "Застосування обчиелввально! техШки у про-

цесах керування, проектування, наукових досл1дженнях " Д.Р. N 01860049704 ); ПрезидП HAH Укра1ни (1990-1993 рр.) (1.12.5. "Проблеми автоматизацП проектування техн!чних систем " Д.Р. N 01900009448).

Метою робота е розробка методолог!! ыатематичного та комп'итерного моделгаання нерегулярного розн1щення об'ект!в у

областях дов1лъно1 просторовоГ форми для створення нових

/

технолог1Й проектування та планування, що забезпечують рац!ональче використання сировини та pecypcle. Основы 1 завдання:

1. На основ! анал1зу !снуючих метод!в формал1зац!! голов-них обнежень задач! нерегул°пного розм!щення об'ект!в розроби-ти апарат формал!зац1! умов шперетину об'ект1в та умов !х роз-м1щення у облает! для об'ект!в та областей доЫльно! просторо-во! форми. .

2. Виходячи э математично! модел1 основно! задач! нерегулярного розм1цення об' ektIb, анал1зу 1снуших метод!в розв'язан ня задач класу, що розглядаеться, розробити методолог!в розв'я-зання основно! задач!. На основ! запропонованих метод!в створи-ти алгоритм!чне та програмне забезпечення класу задач нерегуляр ного розм1щення об' ект1в у областях дов!льно! просторово! форми

3. Проанал!зувати метода та алгоритми з точки зору обчислю вально! складност1 та ст!йкост1 до накопичуваних обчислювальних похибок.

4. Розробити проблемно-ор1ентован1 математичн! модел1 задач геометричного проектування та провести Ix досл!дження. Провести досл1дження особлйвостей оптим1зац!йних метод1в та алгоритм1в розв'яэання задач нерегулярного розм!щення об'ект!В Jr реальних умовах впровадження.

Основн! нов! науков! результата, що виносяться на захист.

1.Математичний апарат формал!зац!1 умов розм!щення об' ект1в у областях дов!льно! просторово! форни у К2, що грунтуеться на понятт! годографа вектор-функцП щ!льного розм!щення (г.ф.щ.р) об'екта та область Засоби побудови г.ф.щ.р об'екта та облает!, нов! властивост! г.ф.щ.р.

2.Методолог!я розв'язання основно! задач! нерегулярного розм!щення, що грунтуеться на комплексному застосуванн! наближених та точних метод!в:

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

- метод (в та апроксимувчих процедур моделювання розм!-¡цення об'ект!в дов!льно! просторово! форми у заданих областях;

- точного методу пошуку глобального екстремуму.

3.Алгоритм!чне забезпечення класу задач нерегулярного розм1;цення з:

- оЩнками обчиелввально! складност! алгоритм!в;

- оЩнками на ст!йк!сть до накопичуваних обчислювальних похибок.

4.Программа забезпечення розв'язання задач нерегулярного розм!щеннн об'ект!в у областях дов!льно! просторово! форми.

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

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

Теоретична ц!нн!сть робота. Математичний апарат формал!-

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

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

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

Окрен! алгоритма та прогреми можуть оути використан! при обробц! 1н$ормац11 у еколоПчних задачах та задачах МоШТоршп-у Вемл1.

Реал1аац1я та впровадження. Розроблен1 метода, алгортми та програмн! комшюкси впроваджен! у ряд! установ р1зних галу-зей народного господарства ери розробц! систем автоматизованого проектування схем розкрою листових та рулонних натер!ал1в (Волзький автомоб1льиий завод, (1983-1985рр.)), карт розкров трикотажних вироб!в (ПКБ автоматизованих систем керування

текстильно! проыисловост! РРФСР, 1984 р.), при створенн1 "САПР об'ект1в буд!вництва ( п/с М-5588, 1987 р.) з аконом!чним ефектон 758,2 тис. крб. (у Шнах 1987 р),

Матенатичке та програмне забезпечення задач1 нерегулярного розм1щекня опуклих об'ект!в у прямокутних областях викорис-тано з Гнститут! геотехн!чно! механ!ки АН Укра!ни при моделю-занк! структура силучих матер!ал!в в уновах в!брац!й (1987р.). Модал!, метода та алгоритми задач! нерегулярного розм!щення в скуз! и1н!мально! довжнни з урахуванняи обнежень, характерних для швейно! Гфомислсвост!, впровадасен! в учбовий процес ДержавноI акаден!! легко! проыисловост! Укра!ни у 1995 р.

Апробац!я роботи Основн! результата досертацП допов!дались та обговорювались на: республ!канськ!й конференц}1 "Обчис-жаальна математика у сучасному науково - техн!чному прогрес!" (Кихв.1982 р.); всесоюзному науково-практичному сем!нар! "Засто-совн! аспекти керування складними системами (Кемерово,1932 р.); всесоюзнШ конференц! 1 "АвтоматизаЩя технолог!чного проекту-вання" (Пенза, 1985 р.); П та Ш всесоюзних конференц1ях "Метода та засоби обробки складно! граф!чно! !нформац!1" (Горький, 1985,1988 рр.); всесоюзн1й конференц!I "Застосування випадкового пошуку при розв'язанн! застосовних задач"(Кемерово, 1985 р.); всесоюзнШ конференц!! "Математичнз забезпечення ра-Щонального розкрою у системах автоматизованого проектування" (Уфа, 1987 р.); всесовзн!й конференц!! "Автоматизация проектування в машйнобудуванн1 та приладобудуванн1" (Рига, 1988 р.); м1жнародн!й школ! "Проектування автоматизованих систем контроля та керування складними об'ектами" (Туапсе, 1992 р. ); сем!нар! "Математичн! метода геоматричного проектування" (Харк!в, 1991-1995 рр.) при науков!й рад! по проблем!

- 8 -

"К!бернетика" НацЮнально! академ!! наук УкраИни.

Публ!кац!1. За темою дисертац!! опубл!ковано 30 рск31т, в тому числ! 1 монограф!я, 11 статей, 1 депонований рукопис, 7. препринт!в, 10 тез допов1дей.

Особистий внесок. Ус! результата ■ дисертад!йно! робота

отримано за особистов участю автора. У працях, натшсаних у

t

сп!вавторств1 дисертанту належать: Г1] - апарат формал!за-

I

ц11 геометричних обмежень для об'ект!в та областей дов!яьно1 просторово! форми, способи побудови г.ф.щ.р. об'екта та облает!, нов! властивост! г.ф.щ.р., методологtя розв'язання задач! нерегулярного розм1щення об'ект1в у областях дов!льно! просторово! форми, [3,4,5,121 - проблемно - ор1ентован! матема-тичн! модел!, метода моделювання розм1!цення об'ект!в, [2.7,113-алгоритмичне забезпечення класу задач, що розглядаеться.

Структура робота. Дисертац1я складаеться !з вступу, 6 розД1л!в, висновку 1 м1стить 268 стор1кок основного тексту, 82 малюнки, 17 таблиць, список використаних джерел з 158 наймевувань та додатку, де розм!щен1 акти впроваДження результат!в, на 109 стор1нц1, усього - 377 стор!нок. 3MICT РОБОТИ.

У первому розд!л! "Постановка задач! нерегулярного розм!-щення геометричних об'ект!в у задан!й облает! у Rz на ochobI анал!зу застосовних задач розм!щення та проектування показана необх!дн!сть побудови загально! модел! нерегулярного розм!щен-ня об'ект!в у областях дов!льно! просторово! форми, поставлено основну оптим!зац!йну задачу та досл!даен! I! особл!вост!.

Сформульовйна зм!стовна постановка основно! оптим!зац!й-но! задач1 нерегулярного розм!щення геометричних об* ект!в, яка полягае ось в чому. "Маемо певну к!льк!сть плоских геометричних

об'ект1в (1=1,...п) та область розм1щення Б0. Необх1дно об'екти 3^1=1, ...,п) розм!стити у област1 Б0 . за умов виконання заданих обмекень таким чином, щоб критерШ якост! приймав екстремальне значения.

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

Моделями реальних об'ект1в.та областей обран1 геометричн1 об'екти (ср-об'екти), що являють собою клас точкових мнокин, як! в!дпов!дають спец1альнш вимогам. Кожний геометричний об'ект характеризуемся геометричною !нформац!ею: просторовою формою {Б}, метричними характеристиками {М>, положениям у Н2 (У}=Сх, у,в).У дан!й робот1 розглядаються об'екти та облает!, що мають просторову форлу многокутник1в, як опуклнх, так ! неопуклих,. як! в!др13няються св01м гомотоп1чш5м типом: однозв'язн1, много-зв'язн!, незв'язн!. Метричн! характеристики (значения координат вершин, площа 1 т. 1н.) дозволяють в1др!зняти один геометричний об'ект в1д 1шого. Параметра (V}, що характеризуете положения об'екта в простор!, називаються параметрами розм!щення об'екта. У дан1й робот! розглядаеться такий клас об'ект1в та областей, як! можна характеризувати сталими компонентами , СМ) та зм!нною {V}, до того к можлив! лише аф1нк! перетворення компонента {V} типу трансляцП та повороту.

КритерШ якост! розм!щеннй може мати р!зний ф1зичний зм1ст, одаак в1н залетть в!д компонента геометрично!

9 '

!нформац!1, яка являе собою вектор пэраметр!в розм1щ9ння и(У1,У2,... ,УП). Таким чином, функц1ю метй ае(и) основно! задач1 нерегулярного розм!щення геометричних о6'бкт!в можна подати як зе(и)=зе(У1,...,У;.,...,Уп ).

Основними обмекеннями задач! е:; умови бзаемного

''■..'( • ( нвйвретину об'ект!в та умови розмХщення у облает!. Просторова

, • *. t

форма об'екта задаетьей у вигляд1:{3}={011,...,а^-,з21

да число комтойвнт зв'язност1 S^-ro об'екта, к^-число

компонент л1н1йно! зв'язност1 g-I-компонента меж1 об'бкта S^.

Аналог1чно задавться йросторова форма облает1 SQ:

(S ) = Гч" я9 ч° я0 я0 а?

= ibjj..... lm^' 21..... s2m2 '•■',akl Чср

fl° s° s. 1 • ■ ■ ' "

'••-'Чту-*-'0!^»"-'3!^ J-

о

Умови взаемного непвретину об'екг1в Si та' S^ з урдхуванням ,м1н1мально1 заде Л. в!дстан1 г^ маша подати за допомогою теоретико-множинних опарац1й:

ifltcu t )®-?r- B)\ U (S-iV^) e -у- В)П n

g=l 6 x q=l 84 1 * {1)

1j ' rld ! kr rl3

int ri^ [(S^Vj)®-^- B) \ Д (S^fVj) В)]} * 0,

де В 'коло оданйчного рад1уса з Центром у нул1 простору R2, * , ö-символи операц1й суми та р1зниц1 М1нковського, int(-) -множила внутр!шн1х точок точково! мнЬжйни (:).

Умови розм!щення об'екта Si у облает1 SQ з урахуввнням м!н1мально1 задано! в1дстан! г1озапишуться у вигляд!:

Ч- i rio = ■ У ri

rio ' "k „^lo

(2)

Int { ü l(S° В) 4. U (S^ ®-5- B)]} = k=l K ^ p=l «P *

1i , rio kg rio

lntni^isj^)®-^- (Sgq(V^) e B)]>.

Математична постановка основно! оптим1зац1йно! задач!

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

Визначити вектор и*=(?*,....V*.....V*), за- якого

эе(и*)=ех!;г ае(и), (3)

иеЯ

де И - область прнпустимих розв'язк1в, ¡до описуеться системой нер1вностей

Ф1>1(и1.г1;|)>г13,1>3=1,2.....п-1,1<п; (4)

Ф10(и1)>г1оД=1,2.....п; (5)

1=1,2.....п, (6)

де Ф, .(.,.)-Ф-функц!я об'ект1в Б, та Б., що запропонована у.ро-ботах Ю.Г.Стояна, 1 описуе умову (1), Ф1о(.;.)-Ф-функц1я об'екта Б^ та облает! Зо,що описуе умову (2),Ф^.(-)-Ф-фупкц1я, що описуе технолог 1чн1 обмежэння задзч1, як! виникають додатково.

Наведена математична постановка задач1 у терм1нах геомет-ричного проектування як в1добракення геометрично! !нформац!1.

На основ! проведеного аяал!зу задач! (ЗМ6) • робиться висновок, що вона належить до типу нел1н1йних, многоекстремаль-них задач математичнего прогремування з великим числом п1К*(п1к*+1)/2+гп, де 1=шах{1 ,1к), !ипах{к }) нер1вностей-

О о

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

- 12 -

Виходячи з особливостей задач! та 1снуючих методов роз-в'язання у робот1 запропонована методология розв'язання основно! задач! нерегулярного розм1щення гэометричних об'вкт!в, яка грунтуеться на комплексному використанн! наближених та точних °. метод1в розв'язання. Наближен1 метода локально! та глобально! оптиМЛзацП, що пропонуються у робот!, грунтують-ся на апроксимуючих процедурах, як! дозволяють ; значно зменшити обсяг геометрично! 1яформацП, що в1дображуеться при оптим1зац11. Д1 метода баЗуються на математичному апа-рат1 г.ф.щ.р. об'екта та. облает!, що е основою моделювання розм1щення у областях дов1льно! просторово! форми. Для ряду задач даного класу, для яких характерна наявн1сть Жорстких обмежень (6), ровроблен1 точн1 метода оптимХзацП.

У другому роздШ - "Побудова област1 припустимих знзчень параметр1в розм1щення об'ект1л. ТеорДя годографХв вектор-функцй щ1льного розм1щення (г.ф.щ.р.)"-викладаються основн1 положения математичного гапарату, що дозволяв описувати умови' взаемного неперэтшу та умови розм1щення у област1; дослХджуються його констргстивн1 властивост!; розглядаються засоби його побудови для р1зних клас!в об'вкт1в та областей, а також питания формал1зац11 основних обмежень задач!.

■ Наводиться означения Ф-функцП пари об'ект!в та як всюда визначено! функцП у В4, що зв'язуе параметра розм1щоння об'ект1в та волод1е такою характеристичною властив1стю

Ф1;}(%.-иг)=а, яйцо си^}.*.

де с!(•) - замикання точково! мнокини (•).

- 13 -

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

Наводиться поняття г.ф.щ.р. об'ект!в Б1 та 32, цо запропоноБано у роботах Ю.Г.Стояна та М.1.Г1ля як годографа вектора, що з'еднуе полюсн та 0£ щ1льно розташованих об'ект1в та (найкоротша в1дстань м1ж якими дор!внюе заданШ величин!). У геомвтричнШ !нтерпретац!1 г.ф.щ.р. об'ект1в е геометричним м!сцем розташування полюса об'екта 32 при його трансляцН в!дносно об'екта при виконанн! умов С13, (V. )Л с139(У0)^о,

• (7)

При ф!ксованих значениях V* г.ф.щ.р. являв собою поверх-

ню у тривим!рному простор1 або л1н1ю на площин1,якщо 92=сопз1;.

о

Розглядаеться поняття г.ф.щ.р. об'екта та област1 як годографа вектора, що з'еднуе полюси О0 1 02 облает1 та об'екта, щ!льно розташованого у н!й (об'ект належить облает!, а найкоротша в1дстань м!ж межами об'екта та облает1 дор1вгаое заданШ

величин!). У геометричнШ 1нтерпретац11 г.ф.щ.р. об'екта Б2 та о

област1 е геометричним м1сцем розташування полюса 0Р об'екта

о • ,

32 при його трансляцН у облает! 51 при виконанн1 умов

Г С132(72)П С18°«, ' (ау

I 1глз2(У2)П з°=1пгз2(У2).

Наведен! властхшост! г.ф.щ.р. об'ект!в, а тако* г.ф.щ.р.

сб'екта та - облает 1. Для формал1зац!1 основних обме^сень задач! та. наступного 1х чисельного коделювання на ЕОМ розроблявться способи побудови г.ф.щ.р. об'ект1в, об'екта та облает!, а також досл1дкуються 1х конструктивн1 властивост1.

Пропонуеться спос!б побудови г.ф.щ.р- неопуклих однозв'язних многокутних геометричнях об'ект!в та Б2, доводяться твердкення, зг!дно 3 якими запропонований. спос1б формуе множину точок, яка налехить множш1 г.ф.щ.р.. Нехай многокутниЯ об'ект задано координатами вершин А^{х;1,у1) (1=1,...,пг) в1дносно нерухомо! системи координат х01у, а об'ект Э2 - координатами вершин ^(х^.у^) и=1......г^)

в1днрсно рухомо! системи координат х02у. Напрямок обходу мех многоокутник!в та Б2 виЗерем проти ходу годинниково! стр1лкй. Необх1дно побудувати г.ф.щ.р. у об'ект1в та 82- .

Множила 7 мокэ м!стити у соб! дек1лька компонент л1н!йно! зв'язност! - зовн!шню та множину внутр1шн!х

4=7! иТц 0 Ъг У и • ■ ,Пропонуеться такий спос1б-яобудови г.ф.щ.р. об'ект1в та Формуеться множина 7' напрямлених в!др1зк!в С^, яка в геометричним м1сцем полокень полюса 02 при трансляц!!:

а)кожно! опукло! верпшни В.. многокутника Б2 по сторон! многокутвкка 31, для яких виконуються вимоги

^и^.у^«) <0. (0)

ння вершини в1д прямо!, що проходцть через точки А.,А;1+1;

б)сторони по .опукл1й вершин! А^, для яких

вшсонуються вимоги ,

в)сторони В^В^ по сторон! Л^А,.^ при виконанн! вимоги

- 15 -

» « I ♦ * »

чч^-г^х.0' ■<10)

Позначимо множину вёктор!в (С-у) через СС1(С1,С1+1)}, де Сх~ початок, а С1+1- к!нець вектора С^. Визначимо сторони та вершили об'ект!в 31 та , що належать 1х опуклим оболоккам. Позначимо 1х таким чином: {А^+^у* ^Эу, ^З^дЧ^У В робот! доведено ряд тверджень:

Тверджения 2.1.Множина вектор!в, що утворилися при транс-ляц11 вершин {В-}у по в!дпов!дних (з урахуванням вимог(8))

и *

сторонах та стор1н по вершинах {А±>у з

виконанням (9) належить до мнодани вектор!в г.ф.щ.р.

-» I

Твердження 2.2. Якщо вектор С1(С1,С1+1)е7 ! мае' з векторами з множини 7' т!лыси т1 точки перетяну, що сп1впадають з к!нцями цього вектора, 1 в точц! Сх виконуються умови (7), то вс! точки вектора належать г.ф.щ.р.

Твердження 2.3. Якщо Еектор С1(С1,С1+1) перетинають деяк!

вектори С^, Ск, Ср в!дпов1дно у точках С^, С1р 1 точка

С1 е точка г.ф.щ.р., то вектор Сд^^.С.^) належить г.ф.щ.р., де С1д. - найближча до точки Сх точка перетину.

Твердження 2.4. Якщо 1з точки С1+1 (к!нця вектора С-^), у

як!й виконузться умова (7), виходять к1лька вектор1в ■+ *

як1 утворюють з вектором С^ в1диов1дн! кути а|+1, а]^, то вектор, що належить г.ф.щ.р., мае напрямок, який сп!впадас з вектором , що мае найментий кут

*

На п1дстав1 тверджень (2.1-2.4) формуеться множщш 71, що утворюе певний контур.

Твердження 2.5.Множила 7} сп!впадае з множиною вектор1в 7г, що утворюють зовн!шню компоненту л!н!Яно! зв'язност! г.ф.щ.р. Розглянемо випадок, коли та Э2 однозв'язн!,. а 1х

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

вектор1в, для яких п де Р. -п1вплощина, для дов1льно!

1

точки яко! (х,у) винонуеться умова ф1(х,у)<0. 3 точки' С-^ по викладеному вще способу формуеться замкнений контур, що складаеться з множили вектор1в. Ц1 вектори позначимо як • множину В цьому випадку в1рне твердження 2.6.

Твердження 2.6. Якщо !снуе точка С^ет, з яко! починаеть-ся формування замкненого контура, що мае напрямок обходу по ходу годинниково1 стр1лки, то множина належить множин! 7.

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

Нехай 3®-дов1льна однозв'язна многогокутна область, яка мае ф!ксован1 параметри розм1щення 3®(х*,у*). Область Б® задана координатами вершин А1(х1,у1)(1=1,...,ш1) в!дносно нерухомо! системи координат хО^у. Напрямок обходу меж1 област1 вибрано по ходу годинниково! стр!лки. Об'ект Б2 може припускати дов1льн! трансляцП у облает!- Необх!дно

визначити та побудувати г.ф.щ.р. 70 об'вкта 32 та област1

Один 1з способ!в побудови г.ф.щ.р. об'екта та област1,що протонубться, засновано на ТЕердженнях 2.1-2.4.

Припустимо, що 1снуе точка С^, яка належить г.ф.щ.р. об'екта 32 та облает! 3 ц1е! точки, зг!дно з твердаеннями

2.1-2.4,формуетьея замкнений контур, що складавться з множили вектор1в. Позначимо його . В цьому випадку слушне

Твердження 2.7. Якщо 1снуе точка С1<з70, яка е початком замкненого контуру 7д', що мае напрямок обходу по ходу годинниково! стр!лки, то множила 7^ налэжить множин! 70.

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

Розглянемо об'скт £=Р, де Р - дов!льна однозв'язна область, така, шо РзБ^. Под1лшо об'ект £ на два дов!льних однозв'яз!шх об'екти та х^ таким, чином, щоб Е=Е[и£2,

^^п 1пгЕг=о. Нехай 7®- г.ф.щ.р. об'ект1в Э2 та а -г.ф.щ.р. об'ект1в Бг та

Доводиться такв твердження та його виеновок Твердження 2.8. Межа об.яает1 г=г°иг2 е г.ф.щ.р. об'ект1в йл та с, да гЯ - така область, межа 7(? яко! в г.ф.щ.р. о0'ект1к 3.;, та £^и=1,2).

Виеновок. Зг!дно з (8) внутр!шн1 компоненти меж! облает! Г е г.ф.щ.р. об'екта Б2 та облает! Б®.

Доводяться твердження, як! е основою способ!в побудови

г.ф.щ.р. усього класу многокутних об'ект!в та областей.

к1

Твердження 2.9. Якщо об'екти 3,= А И ШЭ, та 32=3рл - > 1 р=2 •

2

и ШБд - мнбгозв'язн1, то г^ф.щ.р. цих об'ект!в е або

—о

межою

ч=2 к

1 .

облает! = Г\ I) Г . або межою облает! Г,5=Г\ и Г ( .де Г -р=2 °Р ^ 4=2 04

область, межою яко! е г.ф.щ.р. об'ект1в та 321,1^р-область, межою яко! в г.ф.щ.р. об'екта Б21 та обдаст1 31р, а Г —

область, мекою яко! в г.ф.щ.р. об'вкта та облает!

11 . г2 0 Тверджьння 2.10. Якщо Зч = и та 30= и Б" - незв'язн1 -:--1 к=1 бР ^ г=1

об

'екти, то г.ф.и.р. об'ект1в Sj та S2 в межа областей . 12 fi

Г?0= U ( U Г®?), де rf£ е область, межою якоХ в г.ф.щ.р. г=1 g=l 1¿

многозв'язних об'ект1в sl_(p=l.....k„) та SÍL(q=l,;.).

gp о *

Твердження 2.11. Якщо область З^-однозв'язна, а об'ект S2

-не;

= S21\ U Int Sgq - многозв*язний, то г.ф.щ.р. об'екта S2 та,

област1 S® е межою облает! Г0, тобто сп1впадаз с г.ф.щ.р. для

в!дпов1дних однозв'язних об'ячта та област1.

Твердження 2.12 Якщо область S^-одйозв'яааа, а об'ект 32 2g

so= U - нэзв'язний , то г.ф.щ.р. оЗ'Екта S0 та

2 r=i ГЧ * г 2

2

област1 с межою област1 U Г0г, де Г0р- область, межою яко! е г.ф.щ.р. об'екта S^ та област1

. Нехай область S0=3?\ U1 In tsL,- многозв'язна, де S?- одно-

gs J *

зв'язна, sL.(p=l.....k )-y загальному випадку -многозв*язна.

Твердження 2.13. Якщо область SQ- многозв'язна, а об'ект

S2 - незв'язний , то г.ф.щ.р> об'екта S2 та облает! SQ може

бути зображвний як мека област1 Г^**=Г**\Г*2, дв Г^-область,

межою яко! в г.ф.щ.р. незь'язного об'екта S2 та област1 S®, а

♦ 3-1 i Г12- г.ф.щ.р. незв'язних об'ект1в S2 та U S^.

Твердження 2.14. Г.ф.Щ.р. об'екта S2 та незв'язно! облает!

so=lcü1 Sk мож0 бути зображений як межа облает! ü Г^* *.

У робот! доводиться твердженйя, що дозволяють вггерже ЗД1ЙСНИТИ формал1зац1ю умов (4)-(5) для об'ект!в та областей дов1льно! просторово! форми.

Нехай Sj та S2- геометричк! об'екти дов1льно! -тооторово1 форми з параметрами розм!щення (х*,у*) та (x¿,y2), а

712(22,У2) - г.ф.щ.р. об'ект1в Б1(2*,у*) та 32,у2),. що е мэжою деяко! облает1 Г12-

Необх!дно визначити множину значень параметр1в I (х2,у2)> (означимо II як!й в1дпов1дають так1 положения об'ект1в та 32, що:

ШБ^х'.у*) п 1М32(х2,уг)=0. (Ш

Твердаення 2.15. Для об'ект1в Э^х^.у*) та В2(х2,у2)

викопуеться умова (И), якщо параметри розм1щення (х2,у2)

належать множин! У»1=Н2\1п№12, тобто (х2,у2)е«1=Нг\1п№12.

Нехай Б®(х£,у*) - область дов1льно1 просторово1 форми.

Об'ект 32(х2,у0) можа 'здШснювати дов1льн! трансляцИ в'Н2.

Нехай 70(х2,У2) - г.ф.щ.р. об'екта г^х^у^ та област1

3®(х*,у*), а Г0 - область, межою яко! е г.ф.щ.р. 70-

Нообх!дно визначити множину №0 точок {(х2,у2)), як!й

в1дпов1дяють так! положения Б2 та Б®, що:

шз°(х*,у*) п шгз2(х2,у2)=1пгз2(х2,у2). (12)

Твердження 2.16.- Для об'екта 32(х2,у2) та облает1

(2*.у*) дов!льно1 гфосторово! форми виконуеться умова (12),

якщо параметри розм1щення (х2,у2) належать множин1 що

совпадав з Г0, тобто (х2,у2)е¥?0=Г0.

У третьому розд!л1 "Алгоритма побудови г.ф.щ.р. об'"ект1в,

об'ект1в та областей та 1х анал!з" описуються основн! алгоритми.

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

ру трудом!сткост1, нитрат пам'ят1, 1х обчислювальних похибок.

Доводятьсл к!лька тверджвнь стосовно до властивостей

в

г.ф.щ.р., що необх1дн1 для одержання оц1нок алгоритм1в.

Нехай та - неопукл1 ф-многокутнйки, що м1стять п^ та п2 стор!н'.

Твердження 3.1. К1льк1сть вершин г.ф.щ.р. об'ект1в Б1 та

- 20 -

Бг обмежена зверху величиною 2пгп2-

Нехай область Б® - ср-многокутник, що мае стор!н.

Твердження 3.2. Г.ф.щ.р. опукло! област1 та' об'екта Б2 дов1льно1 просторово! форми е межа опукло! облает!, що м1ститв не б1льша, н!ж пц стор1н.

Твердження 3.3. К1льк1сть вершин г.ф.щ.р. неопукло! област1 та об'екта Б2 дов1льно! просторово! форми обмежена зверху величиною 2ш1п2.

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

Спос1б 1 базуеться на доведених твердженнях 2.1-2.5. У робот1 показано, що час, необх!дний для побудови г.ф.щ.р. двох об'ект!в та Б2, од1нювться величиною 0(п4), п=шах(п1,п2), витрати пам'ят! при цьому складають величину, пропорц1йну 4пг. Похибка обчислювального процесу побудови г.ф.щ.р. двох об'ек-т1в, зг1дно з його графом, мае в!дносну похибку, що не перевер-шуе 370, де 8 - в1дносна похибка зображення д!йсних чисел.

Спос1б 2, запропонований у роботах МЛ.Иля, полягав у посл!довному виконанн1 операц!й: роЗбиття об'ект!в на опукл!, побудови г.ф.щ.р. опуклих об'ект1в, об'еднання опуклих областей, межами яких е ц1 побудован1 г.ф.щ.р.. Якщо внасл!док об'еднання визначаеться не т1льки зовн1шн1й контур, а й внутр1шн!, то г.ф.щ.р. е многозв'язннм. Для способу 2 побудови г.ф.щ.р. одержан1 так1 оц1нки: трудом!стк1сть алгоритма побудови г.ф.щ.р. оц!нюеться величиною 0(п4); витрати пам'ят! пропорц!йн! - 10п2; похибка обчислювального процесу алгоритму не перевершуе 1876.

Спос!б 3, що запропонований у роботах МЛ.Иля та

В.Г.Оценка, базуеться на моделюванн! щ1льного руху об'ект'а S2 в!дносно Sj. Трудом1стк1сть способу 3 оц1нювться величиною 0(пэ), витрати пам'ят1 пропорц!йн1 6п. У цьому алгоритм! координата чергово! вершини г.ф.щ.р. визначаються як координата точки перетину вектор1в, один з яних вже нэсе у соб1. похнбки визначення координат попередньо! вершини г.ф.щ.р. У зв'язку цим похибка обчислень в1д вершини до вершини зб!льшурться.

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

У робот1 охшсуеться алгоритм побудови об'еднання, перетину та р!зниц! двох неопуклих многокутних областей, який мае як самост!йне значения, так ! можв використовуватись для побудови г.ф.щ.р. об'екта та облает!. Характеристики цього' алгоритму: будь-яку теоретико-множинну операц1ю можна виконати за час, що оц!ню8ться величиною 0(q2), де q=max(qj,q2), qt та q2- к1льк!сть верши початкових областей; витрати пам'ят! не перевершують 10q. В1дносна похибка обчислювань - 70.

Запропоновано способи побудови г.ф.щ.р. об'екта та облает!.

Спос1б 1 базуеться на твердженнях 2.1-2.4, 2.7. Час, що витрачаеться на побудову г.ф.щ.р. об'екта та облает!, оц!нюеть~

(О

ся величиною 0(п4), де n^maxOn^rig); витрати пам'ят1 пропорц1й-н1 4п2; в1дносна похибка обчислень не переворшуе 187S.

Спос!б 2 грунтуетьея на твердженн! 2.8 та висновку з нього. Трудом!стк!сть алгоритму оц!нюеться величиною 0(п4).витрати па-

- 22 -

м'ят1 пропорц1йн! 6п2, в1даосна похибка обчислень - 259Q.

Розглянуто штання, що присвячен1 розробц! еконбмних, з

точки Зору обчислювальних витрат, алгоритм1в, що забезпечують

ст!йк1сть метод1в модэлввання розм1щення об'ект!в.

Првцес моделювання розм!щення об'ект1в можна зобразити як

к1ицеву суп8рпозиц1ю в1дображень геоМэтрично! 1нформац11, що

вм1щуе теоретшго-множинн1 отрацП, спврацП побудови г.ф.щ.р.

oO'cktIb, o6*ekt1b та областей, аф1нн1 перетворення. Кожна з

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

к1нцево! суперпозицП операц1й зб1гу точок, належност1 точки

до в!др1зку, визяачення паралельност1 в1др!зк!в. Перэл1чен1

оперзцИ е некоректними 1 для них у роботах МЛ.Иля 1

Смолякэва C.B. розроблен! регуляризуюч1 оператори та стискую-

ч1 в!добрвження при визначенн! зб1гу двох точок R1(Xj,Xj,a);

належцост! точки до в!др1зку паралельност1 в!д-

р!зк1в HjCl^.I^a), де Х*(х,у)=Х®еВ, 1*=1®£В, Е*-частина

прямб! I, що обмежена точками X*, X*+i, Е=Ъ®еВ, де £-деяка

величина, що враховуе початкову похибку зобрааення точок.

У робот1 розглянут1 питания оц1нки параметра

регуляризацП a оператор1в Rj (•,•,• bRj ( •, •, • ) •

Для • кожного з алгоритм!в Aj визначаеться обчислювальна

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

Параметр регуляризацП ai повинен забезпечувати ст1йк1сть

рвал1зацП алгоритму А^ з урахуванням похибок зсбразкення

вх1д1шх даних та типу ЕОМ, що використовуеться, 1 може бути

визначеннй як найб1льша абсолютна похибка ai= С^бих», де яхя-

пеЕна норма вх1дних даних. Трудом1стк1сть ст!йкого алгоритму . р

А£, що застосовуе регуляризуюч! оператори,,оц1нюеться як

ïf = Sa+SIV^V2^ '

- 23 -

де - трудом1стк1стъ алгоритму А1, - коеф1-

ц!енти, то залежать в1д к1лькост! викорибтаних регул'яризую-чих оператор1в даного типу в А^, 3^(3=1,2,3)-к1льк1сть операции що потр1бн! Для визначення ситуац11, при як!й виникав Н8Коректи1сть, та. для йиконання регуляризуючого оператора.

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

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

У четвертому ропдШ "Метода та алгоритмй. розв'язання задач! нерегулярного розм1щення в областях дов!льно! ' просторово! форми" вккладена методолог1я розв'язання Основно! задач! нерегулярного розм1щення, що полягав у комплексному застосуванн1 наближених метод!в з апроксимуючимй процедурами та точних метод1в оятим1зац11. ■

Задача (3)-(6) за своею постановкою е детерм!нованою. Одержат и точний розв'язок детермШованимя .методами нэ вдаеться з огляду на II велику вим!рн!сть. '• Нйжня оц1нка к1лькост! локальних екстремум1в п!, тон при п>7 про перебирання ус1х локальних екстремум1в не мо'же бути Й мови.

У п!дрозд!л1 4.1 використовуеться метод посл1довно1 ста-, тистично! оптим1зац11, запропонований у роботах Ю.Г.Стояна та С.В.Яковлева,який, з одного боку, грунтувться на 1деях теорИ статистичних розв'язань, а з 1ншого-пристосований для специф!-ки класу задач геометричного проектування. Суть методу посл!дов-

но! статистичю! оптим1зац11 полягае у звуженн1 ( на основ1 1мо-

в1рн!сних властивостей функцП, що оптим!зуеться) облает! пошу-

ку, да вибираються точки, з яких зд1йсюоеться локальний спуск.

Оск!лыш реал1зац!я локального спуску в задачах нерегулярного

розм1щвння об'ект1в (коли розглядаються об'ект та область до-

в1льно1 просторово! форш) потребуе великих обчислювальних

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

Щ. процедури полягають в апроксимацП меж! об'ект1в

розм!щення з р!зною точнХстю, причому стратег!я вибору

точноет1 така. На : початку пошуку точн!сть апроксимацП

передбачаеться самою грубою, пот1м вона зб!льшуеться ! на

останн1х етапах пощуку, що зд!йснюеться в малому окол1

вайкращо! точки, зб!гаеться з точн!стю зображоння вх1дних

даних. Точн1сть апроксимацП об'ект!в приводить до розв'язку

на деякШ област1 Ир, що в1доов!дае ц!й точност!.

Нэхай ае(и )=ех1:г ае(и)-значення функцП мети, визначене на Т и*Яр

облает! Wpt що ошеана з ер-точн1стю. П!д ер-точн!стю опису облает! Жр будемо розум!ти зображення умов неперетину та умов роз-м!щення в облает!'з £р-точн1стю апроксимацП об'ект1в. Нехай

ае(ип)=ех1;г ае(и)-значення функцП мети, визначене на област1 ие"о '

що описана з е - точн!ств (е-точн!сть подання вх1дних даних).

• Р!зницю. м1к ае(Цр) 1 ае(и0), що виникла за рахунок приведе-них спрощень, будемо зобракати як функц1ю втрат:Ь(ер,и)=эе(ир)-ае(и0). Втрати, що породжен! приведеною виде апроксимац1::ю, будемо характаризувати математичним спод!ванням функцП Ь(ер,и).

Розглянемо дв1 област1 В1 та д2. Множин1 Ба поставимо у в!дпов1дь величину М1(1), а множин1 Т>2 - величину М2(1), де М„(1)(п=1,2) -• математичнё опод!вання найменшого значения

функцП мети в виб1рц1 1.Оптимальною. назвеМо множиау Dr, що в1дпов1дае умов!: Мр(1) < Мп(1),п = 1,2. ПяоТеЗою Нд назвемо г1готезу про певну мнокину D_, яка е оптимальною. Прмйняттю гШотези Нп в!дпов1дав остаточний розв'язок а = а^. Функц1ю втрат розглянемо у такому вигЛяд1:

М(1), ■ якщо'М(1)>0,

l(alf М(1));=

На,, М(1))

О, якщо М(1)<0,

-м<1),.' якщо m<d'<cv О, , якщо M(l)>t),

де М(1) = Нг (1) - М2( 1 j. '11ерев1рка г1потези Нд за обмежено1 функцП втрат 1(ап, М'(1)) проводиться за такою схемой. Остаточний розв'язок приймавться у вигляд1' 1. ■ ■

at, якщо М (1)40,

а =

. (13) а2, якщо М(1)>0.

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

f(J)=r(d)+3(i)» ; . (14) де г(3)-функц!я ризику, a(f) - функц1я втрат на обчислення. Нехай

з(3)=0-3. _ (15) де С-в1дносна варт1сть одного'локалЬйого сйуску (випробуВання),

со

rU^r^aj, tj) - J gj(t/tj)tdt, gjtt/tj) - щ1льн1сть параметра О

t нормального закону розпод1лу при ф1ксованому коли

а=а , п=1,2; Т. - оц1нка параметра М(1).

a j

Показано, що г(j) при ф1ксованих величинах е спадна

функц1я в!д 3. Отже, функц1я (14) мае один м1н1мум, Тод1 при

3=к вибирання припиняеться , якщо С + гк(гк) > о, до гк(К) -значения пох1дно1 г(3) у точц! 3=к, 1 прийматься остаточне вир1шення по правилу (13).

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

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

ФункцП мети) та подальшим розв'яэанням задач 1.

Для реал1зац11 локального спуску у п1дрозд1л1 4.2 пропонуйться метода моделювання розм1щення об'ект1в у облает! дов1льно1 просторово! форми.

В основу методу1 моделювання розм1щення об'ект!в покладено метод м!н1м1зац11 по групах зм!нних та апарат г.ф.щ.р., який викладений у'розд1лах 2, 3.

Метод м1н1м!зац11 по групах зм^нних виражаеться 1терац1йною формулою

ае1(У^,У*.....^У^) =ех!;г ге^У^.У*.....У^.У^, (16)

V «1

да ае0=«0(у1.), ае1_1- значения функцП мети п1сля частково! II

м1н1м!зац11 по зм1нним 7^(3=1,2.....1-1)-

параметри ои'ект1в, що розм1щен1, У^ - параметр об'екта, що розм1адвться, 1?.- область припустимих значень параметра V..

- 27 - ■

Область Я. будуеться за допомогою г.ф.щ.р. об'иста Б. та 1-1 * ;

сблясг 1 = Бп\ и Я,(V.) на основ1 тверджень 2.7-2.8 для и и ¿=1 з з

однози'язш! област1, твердженнй 2.13 для многозв'язно! облает! та тзтзрпження 2.14 для незв'язно1 облает!. В робот! розроблено Е<зк:;:м:з способ1в побудови облает! як'1 породжують р1зн1 алгч|;!7'5И моделювання розм1щёння ор1ентованих об'ект1в.

Ко.тл розглядаються неор!ентован! об'екти, 1хн1й г.ф.щ.р. б сбласт1, яка являв собою с1м'ю давэрхонь. Для побудови тшгл.г г.ф.щ.р. не !снуе ефэктивного подходу. У зв'язку з цвм в р::'-т1 пропонуеться [1дх1д, що дозеоляй виключити этап побудив:! г.ф.щ.р. неор!ентованих об'ект!в та областей шляхом . внбору пайб1лыз перспективно! ор1ентац!1 об'екта з подальшою побудовоч г.ф.щ.р. для ор!ентованих об'ект!в.

Нохай область - одяозв'язна. Для .визначення

перспективно! ор1ентац!1 об'екта, що характеризуемся параметром оц!нимо момента 1нерц!1 облает! Зд та; об'екта Эр що характеризуюсь 1х 1нерц1йн1сть щодо повороту.; Момента 1нерц11 залежать в!Д' маси та мбтричних характеристик об'екта (облает!)* що досл1джуетьея. • 0ск1лькй йоверхнёба'. густяна пост1йна, то момента 1нерц11 будуть залежати т1лькй в1д геометричних -характеристик об'екта (област1). Залежн1сть величина моменту 1нерц11 в1д напрямку характеризуй центральний ел!пс 1нярц11, причому найб!лыпий та найменший момента; 1нерцП в1дпов!дають головним осям цього ел1пса.

Напрямок одн1е! з головйих осей ел1пса для об'екта

I

визначаетьея за формулою:

•V - Ъ + А^г - ^ +

№ ----

2<1

ХУ

- 2В -

де.Л та .1 - момента 1нерц!1 стосовно до осей Ох, Оу, а Л -хх уу л-У

в!дцентровий момент.

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

За результатами • анал1зу областей 3^(1=1,2,...,п), що утворпоться в процес! оптим1зац11 по трупах зм!нних, у робот1 показано, що ц! облает! можуть мати так! д!лянки меж!, як1 не беруть участ1 у формуванн1 метричних характеристик г.ф.щ.р. Так1 дЦинки меж1 назвемо виродкеними. Наявн!сть вироджених д!лянок мех1 вносить 1стотний вклад у величини момент1в ШерцП, позначаючись на Ьараметр! 8*.

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

(Бо)" = ° в8) Л 0(Д • ев), (IV)

(з£)а = (б*)" • еВ, 1 = 1.....п, (18)

де е - параметр апроксимацП.

У робот1 прошнувться наближений метод глобально! оптим!зац11 -з застосуванням апроксимуючих процедур на його етанах. На першому втап! оптим!зац11 за об'екта, що розм1щуються, вибираютьел описан! навколо них прямокутники. В ЩдроздШ 4.2 роароблано спо<51б локально! оптим!зац!1, де

икористовуеться апроксимац1я об'ект1в описаними прямокутниками ; урахуваетям специф1ки задач розм!щення прямокутник1в. На фугому етап! оптим1зацП об'екти зобракаються як 1х опукл1 ¡болонки. Для локального спуску, у цьому випадку рбзроблено ?етод моделювання розм!щення опуклих об'екТ1в, що використовуе IX властивост1. Коли задана припустима похибка опису об'екта, го необх1дно до методу локально! оптим1зац11, що реал1зуёться за 1терад!йною формулою (16), в етап побудови област1 звести апронсимуючу процедуру (17).

Таким чином, у робо""!. розроблено ряд наближених метод!в моделювання розм1щення об'ект1в у областях дов1льно! просторо-В01 форми, що мають широкий спектр можливостей 1. викорйстовують-ся в залежност1 в1д особливостей нласу прахтичних задач геометричного проектування. Ц1 метода використовуються для одерження оц1нок та початкових точок для -точних метоД1в розв'язання задач оптим1зац11, а також у Наукових досл1дженнях, наприклад при моделюванн1 зернистих середовищ, що дозволяв зменииги обсяги багатокоштовного ф!зичного моделювання.

Отримана оц!нка трудом!сткност1 методу оптим1зац11' по трупах зм1нних, що наведений ран1ше, яка складае величину

ш6п(п2-1)(ЗП+2) X = -Г2- . (19)

де п - число многокутних об'ект1в з к1льк1стю вершин п1(1=1,2, ...,п), т0 - к1льк1сть вершин област1 30, ш=тах{п1,...,пп,ш0)» 0ц1нка (19) дае можлив1сть стверджувати, що к1льк1сть вершин об'ект!в т? област1 розм1щення суттево впливае на трудом1ст-к1сть методу локально! оптим1зац11 по трупах зм1нних, а, таким чином, 1 на коеф1ц1ент С у вираз1 (15), тобто на варт1сть одного локального спуску у метод! глобзльно! оптим!зац!1.

- 30 -

Показано, що 1снуе ряд застосовних задач нерегулярного розм1щення об'ект1в, як! по 1хн1й математичн!й постанови! можно звести до класу задач дискретно! оптим1зацП. Це пояснюеться даскретно-неперервною структурою таких задач, яка викликана короткою системою обмежень (6), що накладаютьея на параметри розм!щення об'ект!в. Отже, виникае така задача дискретного програмування: необх!дно знайти ех1:г ае<и> ,

иеСсУ/

да С - певна ск!нченна множина. С може бути множиною опуклих п!дмножин облает! Ж, множиною вершин облает! И 1 т.1н.

У п'ятому розд1л! - "Модель та метод глобального пошуку в задачах розкрою з урахуванням спец!альних технолог1чних обме-жень" - зд!йснена математична постановка задач! нерегулярного розм1щення об'ект1в з системою жорстких технолог1чиих обмежень, досл!джуються II особливост!, доводиться, що вона наложить до класу задач дискретно! оптим!зацП. Конкретизуються питания побудови оц1нок та правил в!дтинання для ц!е! задач1.

У робот1 розглянута така задача розкрою.

Генуе комплект з п об'ект1в. Означимо його €3^>. Задана область розм1щення Б з деяким малюнком.яка являе собою смугу шириною (1 в нерухом1й систем1 координат хОу. Означимо Б0 частину смути довжиною г, де г - достатньо велика величина. Малинок може бути трьох вид!в: у вигляд1 безл1ч1 паралельних л1н1й, розтащованих на в!дстан1 11 одна в!д одно!, кл!тинок, що створен1 двома наборами паралельних Л1н1й з кронами Ь 1 Н, або у вигляд! певних геометричних ф!гур (многокутник1в И1(х*,у*)), що задан! координатами вершин ве(х8»Уё> (в=1.2,...,пн) у власнШ систем1 координат хО^у 1 апроксимують дов!льний малгаок ), що пер!одично повторюються з кроками Ъ 1 11 вздовж

осей Ох та Оу. Необх1дно об'екти 3^1=1,2,.. . ,п) розм!стити в

облает! Б« з урахувапням умов неперетину об'ект1в, ровм1щення ^ * 1

!х у облает1, а такок умов збереження жорстко! ор1ентац11 та ц1лосност1 малинку при сум1щенн1 стор1н певвих пар об'ект1в та Зг(1,г=1,2,...,п1,п1^п) таким чином, щеб довяина зйловнэко! чаетини облает! Сула м1н!малыкда." Нэ втрачаючи загальност! м!ркувань, полюси об'ект1в та Зг, еторони яких сум!щуються, виберем у будь - як!й 1з сп!льних точок цяз етор1н.

Розглянемо питания формзл1зац11 сшщ1альних технолог1чних обможень, що виникають пр.. розм!щэнн1 у областях з малгаком. У випадку наявност! малинку у впгляд1 наберу паралельнйх л!н1й для збережэння його ц1лосност! нэобх1дно виконати вимогя, ео полягають у одявковому э!ддалвн1 полжо!в об'ект!в та Зг, еторони яких су?,?1па'ються, в!д набору парадэлыш: л!н!Й:

чИИ! . :

ф (х,у)=0(ф1:(х,у)=у-кх-ь{;,ь1;=ь04-ь-+.,ь=—^—При к=0, Ъ=Ь),

1=1,...,К. Аяал1тично ця вимога можв бути записана так: :

Гр( х*,^)=ф^х1,у1)У(хг,уг)=о, ' " (20)

де 1,г=1.....1т, х^Сп, 1;Д=1,...Д, К - к1льк!сть л1н1Й у

облает! Б0 довжиною г; п1 - к1льк1сть 6б'ект1в,; Для йких повинна виконуватись вямога (20) , .

Коли малинном в наб!р многокутних об'вкт1в 1^(1=1,...,К) (кл!тинок), вимоги збереження ц!лосност1. мадюнку виражаються у ' однаковому в1ддаленн! полюс1в.об'ект1в 3^ та Зу, сторойй яких сум!щувться,- в!д g-I та ^+1 )-1 стор1н малюнку (поздовжньо! та поперечно! л1н!й кл1тинки). Анал1тичний запис цих вимог мае

вигляд: ?р(х];,х;)=ф^(х1,у1)-^(хг,уг)=0,

де Д,? =1,...,К, 1,г=1, ....п^ 1*г, п.^.

По аналоги з структурами нер1вностей, що запропонован! ран!ше у роботах Ю.Г.Стояна та С.Л.Ыагаса, розглянемо систему р1вностей. Нвхай , 2, Ъ) - система рХвностей, да

Щ^.зф - наб1р р!вностей вигляду 1р(Х*,ф=0 1,г=1

...,п1, 1*г, р=1,...,1<), що визначаються, виходячи з умов вико-нання вимоги зберажешш ц1лосност1 малюнку або 11 в!дсутност1 для коашо! пари об*ект1в та 8^(1,3=1,... пД^З). Ц1 умови задашься у вигляд1 симетрично! матриц! 1=|51^|пхп. При цьому виконаншо технолог!чно1 вимоги зберекення ц!лосност! малюнку м1ж та в!дпов1дае значение 6^=1, а в!дсутност! вимоги -0^=0, причому завжди 6^1,1=1,..,,п.

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

сум!щанн1 стор1н певних пар об'ект1в та Бг отримаа вигляд

1г К к + т . в - и ( и.0(У(Х{.хЪ, I, Ь>),

де 1=^/2 - для малику у вигляд! набору паралельних л!н!й, а Ь=п1 - для дов!льного малюнку (кл1тинки).

Означимо черва Ф°= п Ф(Р(Х1,а), А1,4)- структуру

1=1 1 'у

нер1вноствй ,що орисув (б), а через Ф1^ п Ф(Р„(Х1,Х^), Д,

ч

ш^)-структуру нер!вностеЙ, що описуе (4), де Л1 - матриця операцШ а одиничаимн элементами, г>=С^, 1x3=1,... ,п-1, 1<п.

3 урахуванням викладеного, математична модель задач! розм1щення об'ект1в 3^(1=1,...,п) у област1 з малюнком полягае у ось. в чому. '

Визначити ;

33 -а

иеЯ

г*= т1п С%, (22)

дэ и=(х1,у1.....Хд.Уд.г), а?=(0,0,...,0,0,1),. / Я - область

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

^п^п'^- * (23)

у робот1 ШЯВЛ8Н1 та досл1джен1 так1. особливост1 ёадач1

(22)-(23): функц1я мети z л1я1йна ! як везалбяна зм1нна входить до структури Ф°; область Я, що г описуеться: виразом

(23), в загальному випадку неоПукла, незв'язна, з кусково -л1н1йною межею; ИсН211*1; глобальний м1н1мум фуйкцП г досягаеться в одн1й з вершин област1 < ь.- ;- * .

у випадку з малинном у виг ляд!; набору паралельнйх л!н1й 'вершину област1 Я описують пг/2 р1вносТ1 впгляду (20) та (2п+1-п1/2) р1вност1, у як1 перетворюються Нер1вност1 Структури ф°п фЧ у задач! з дов1льним малинном (кл!тинкою) вэрспшу описують п1 р1вностей вигляду (21) та (глИ-п^ р!вностей, у як! Перетворюються нер'1вност1 структури ф°п ®ч Таким чином, вершину област1 V описують 2п+1 л1н1йно тазалежних р1бнянь. В окремому випадку, коли полней оо'ект18, сторони яких сум1Щують-ся, належать вершин! малюнка (вершин1,кл1тинки), ,'йри 1^01 задача з дов1лЬним малюнком в частково дискретною,\ а при п1=п - дискретною на ск!нченн1й множ!йн1 щшпустимих розв'язК1в.

Таким чином, для пошуку глобального екстремуму необх!дно перебрати ус1 вершини або дискрета! точки облает!; И. Для перегляду ус1х вершин облает! Я у роботI описано принцип побудови деревз розв'язк1в. 0ц1нка к1лькост1 вершин на' останньо-му р!вн! мае величину К=[(п-1)М+2+К2]2п-п при 1^/2 I К=[(п--1)м+2+2к2]2п-п - при ь=л1, де м-шахСп.-п^; 1,^1,...,п; 1*3).'

Розроблено наб1р правил в1дтинащя, що використовуютъ сгоциф1ку задач1 (22)-(23) i дозволяють на верхнЛх р1внях дерева^ розв'яз-к1в на ochobI анал1зу часткових розв'язк1в в!дтинати безперспек-н! вершини. Берхн! оц!нки, що одержуються методами розм!щення об'ёкт1в, як! викладено у роздХл! 4, такой дозволяють в1дтинати безперспективн1 вершини. У процес! оптимХзацП по дереву розв'язк1в зд1йснюеться перерозрахунок верхн1х оц!нок.

Отримано глобальний екстремум задач1 (22)-(23) при L=n}/2 та п=7 за 25 хвилин на IBM PC/AT 386 (40MHz, без сп!впроцесора). Ы'етод мохе використовуватись при розв'язанн! задач 1ндав1дуаль-ного розкрою, який характеризуемся малим обсягом вироб!в, що вапускаються. До пере'ваг, методу можна в1днести 1 те, що розв'я-зання задач! може бути зупинене будь-коли з одержанням наближе-ного розв'язку. У раз1 потреби, якщо наближений розв'язок не за-дов!льняе, розв'язання задач1 може Ьути поновлено, при цьому за верхню оц1нку функцП мети приймаеться наближення, що отримане ран1ш9. Шляхами п1двищення ефективност! запропонованого п1дхо-ду е розв'язання задач на багатопроцесорних ЕОМ, а також пошук нових правил в1дтинання, що використовують специф!ку задач!.

У шостому роз'д1л1 "Комп'ютерне моделювання практичних задач нерегулярного розм1щання об'ектХв у областях дов1льно!, просторо-во! форми" розробляються проблемно-ор!ентован! модел1,розглядаються питания практичного застосування математичного та комп'ю-терного забезпечення вадач! нерегулярного розм1щення об'ект!в.

Поставлено, досл!дкено та розв'язано так1 задач!.

Иаемо смуту S ширини d. Означимо як SQ частину смуги довжиною z, де z - дооить велике число. Маемо комплект, що складаеться з п об'ект!в S1(l=l,.,.,n). Необх!дно об'екти Si розм!стити в облает! S0 з урахуванням виконання умов

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

г;*=т1л СТи, : (24)

дв и=(х1,у1,в1,...,Хд,уп,0п* з), СА=(0,0,0,...,0,0,0,1)1 Я -область припустимте розв'язк1в, що описувтЬся ' системою нер!вностей: •'.''.'

' .....' (25)

Ф1о(х:.,у1,е1(2)>0»; 1=1,2,...,п, , (26)

. ■ , ( . ; . (27) ,

Розглядаються так! реал1заЦ1! модел! (24)-(27)1 1 ПросторОва форма оО'бкт!в, 1 що розм!щуйться - однрзв'язн! прямокутшпеи. Значения кута може приймати два значения; 0°»90°. Як приклад: розв'язуеться • задача розм!ще{шя, 197 прямокутник!в на смуэ! задано! ииринп та м1н1мально! дрвжини.

Наведено рзз^шлати |юзв'яэання задач! розкрою, тканина. Просторова форма об'ект!в - одназв'язн! неопукл1 мпогокутникя, ' що апроксимують викро! з задаНою точн!стю. вибираеться з мнояши значень СО0.+Д8°Л80°±А6®),А9®- кут баййукост!. Як,приклад, розв'язан! задач! (24)-(27), коли розглядаеться 82 не опу к лих об'екти (2 комплект шкро1в-чолоз!чого костШй) та 36.об'ект1в (2компл0кти викро!в пальто)..

Як приклад розв'язання задач! (22)-(23) , у област1 м!н1-мэльно! довшни розм!щуеться 58 неопуклих об'вкт1в з урахуванням технолог 1чних вямог:. розм!щэння в облает! з малюнкЬм у виг-ляд! набору паралельних л1н!Й або з двома мйожинами пэралельних л!н!й (кл!тинками).;В облает! м!н!мальноГ довжини" з дов!лытм мзлюнкам розм!дуеться 42 неопуклих об'екти.

- 36 -

У робот! поставлена та розв'язана така задача. toagMo об>

лчрть SQ (лист) задание: розм1р1в та наб!р об'ект1в £Sj>i=1- Не-

обх1дно розгИстити об.'екти S^(1=1,...,m,msn) з заданого набору

в област1 SQ таким чином, щоб, з одного боку, в1дходи були м!н1-

мальними, а з 1нтого- - щоб кожний в!дх1д дозволяв розм!стити

деякий об'ект Sj (наприклад пристр1й, що скрШляе к1лька шар!в

лист1в) з набору (Sj). При цьому повинн1 бути витриман! м1н!-

мальн1 в1дстан1 R м1ж об'ектами 1 об'ектами та межою област1.

Математична модель задач1 зводиться до такого.

Визначити переставлення Р*(р1,...,pm,msn), елементами

якого е порядков! номерй об'ект1в, що розм!щуються, в1дпов!д-

ний йому вектор параметр1в розм1щення u* 1 таке число К компо-

о

нент. л1н!йно! зв'язност1 мак1 S¿= SQ\^U ( S^S^RB) , за яких

площа в1дход!в буде м!н1мальною4 тобто знайти Р*=(Р*.....р*) ;«=; arg min ае(р),

u'Otf.V*.....V" (V- )*,...(V.. Г.....(V. Г.....(\

1 ^ т. » 1 1 гА 1 kj к

гк

= arg min х (u), (28)

ucW .

Де x (u)- . площа област1 W - область припустимих

розв'язк1в, що задаеться оиотемою нер1вностей:

®ir(Vi'V*R' i»*1«2.....i11"1' ' (2Э>

®io(Vl^R- i=1.....n- ! (3Q)

3*1 ,..•••»» 1=1.....k- (31>

<VJ)*0, 3=1.... (32)

Де (•."■"> - Ф-фунвд1я oö'bktIb S^ та R^tS^)1, <&t(-) -Ф

. -функц!я, що задав технолог1ю розм1щення об'ект1в SJ.

Просторова форма об'ект1в CS^) - однозв'язн! та много-

- 37 -

зе'язн1 многокутншш. Параметр приймае дов1льн1 значения. Розз'язана задача розмЩення 35 об'ект1в з. Оаданого

40 1 ^

наберу {S^} т^ на лист! а м1я!мальними в1дходами, для яких в »зконуютъ с я в!Моги рсзм1щення на кожному з них об'екИв is'.}.

' * и

Розглядзються йриклади задач ■ розм1щення ' у : областях дов!лшэ1 просторово! форми. . ■ ■ ,

Маемо обмекэну область SQ .та наб1р об'ект!в .

Я«>сбгЛлло об'яктн з задаюго' набору розм!ститй ■ в облает! S0 тяк1м чином, щоб коеф!ц1ент заповнення був максимальна*.. ?<!атемаигша модель задач! зводиться до такого.. Визначити пореставлэннл Р*(р1,...,ря кт). та в1дпов!дний, йог«у вектор парамэтр1з розмйцеиня ц*. за яких ■ коеф!ц1ент заповнення будо максимальним, тобто знайтя '

Р*(р*.....?*> = arg pax а(Р), ' ■

р . ...

U*(V*......V*)- arg max <e(u), ' ,/ (33)

ueW ;

дч s(u) - коеф1и!ент заповнення област1 S0, W - . область припус?имих'розв'язк1в« що задана системою кер1вностэй: . ■'

®ij(Vi'vd)K)' .....п~1' ' • . .

®10<V». i=l.....п. ■ ''}" \ ■ ;(35) '

Розв'язан1 так1- застосовн! задач1,для яких просторова форма об'вкт1в, що; розм!щуються - однозв'.язн! 'неопукл1 мйогокутники, а параметр Q^const:

область S0 однозй'язний' неопуклий мйогокутник. Розв'язана задача розмйцення 46 об'ект1в з заданаго набору при максимальному коеф1ц1внт1 заповнення област1; область S0 - многозв'язна многокутна область. В. облает! S0 розм1щуеться 94 об'екти з заданого • набору (S^)^ 3 максимальним коеф1ц1ентом заповнення; ,. ••

область SQ - незв'язна область, що складаеться з набору'

неопуклих многокутник!в. В облает! Б0 розмЩуеться 72 об'екти а урахуваннян аимог (34)-(35).

ВЙСНОВКИ.

У рвзультат1 проведених досл!дженъ досягнута основна мета робота - створена методология математичного та коып'втеркого иоделшання задач! нерегулярного розм1щення об'ект1в в областях дов!льно1 просторово! форми. При цьему:

1. аапропоновако математичннй апарат формал1зацП геомет-ричних обмехень для об'ект1в та областей дов!лько! просторово! форни, який дозволив значно розщрити коло застосовних задач нерегулярного рознЩання об'ект!в, що можуть <3ута розв'язан!;

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

3. на основ1 побудовано! загально1 математично! модел1 задач! нерегулярного розм!щення запропонована методолог!я розв'язання задач!, що базуеться на комплексному використанн1 наближе-них матод!в з апроксимусчими процедурами та точних метод1в оптим1зац!1;

роаробяено мода$1кований наближений метод глобально! оп-тнм1зац!!, що базуеться на використанн! ащхжеимувчих процедур у метод! посл1довно! статистично! оптим!зац!1; метод дозволя$ за прийнятний" час при м!и!мальн1й функц!! ризику, що враховуе втрати, як! викнакан! алроксимац!ею, отримати розв'язок задач!;

Б, створено точний метод пошуку глобального екстремуму для вадач! дискретно! оптим!зац!1 розкроп натер!ал1в;

- 39 -

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

7. розроблено алгоритм1чне звбазпеченкя класу задач нерегулярного розн!щення об'ект!в:

8. одержано теоретичн1 оц!нки трудом1йткоСт1 для метод!в та алгор5!тм1в моделюзання розм1щекня об'ект!в:

9. отримано оц!ики ст!йкост! алгоритм!в ta програм до накопичузаних обчислввальних похибок;

10. створено банк програмнкх' модулla, Mo . становлять програмне забезпечеккя для розв'язашгя задач нерегулярного розм1г»ення об'ект!в; программе зэбззпвчення реал!зовано у операц!йн1й систем! DCS на айгорнтм1чн1й йов! FORTRAN;

И. вироблен! практичн!- рекомендацП Ьрдо вшгаристакня проблемно - ор1ентованах моделей, иатенатичнбго та коми'втзркого забезпечення задач! нерегулярного розм1щення об'ект!в,шо е оа-тан1зац!йним ядром д!ячих систем аатоматкзбваного проектування;

12. результата робота вяровадавШ 1 Еакорйстовуиться в наукових досл1д*вннях, 1нженерн1й практвд! t учбоёоМу iipoiieci буз!в, науково - досл!дяйх, дссл1дй;о Коиструкторських ! промиславих орган1зац!ях. , .: , '

Таким чином, створено певний 1нтелектуашш {нструмен-тар1й, який дозволяв формувати шрспекгайн! САПР, ор1ентован! на створення ресурсозбер!гавчих та бвзв1дхоДних твхйолоГ!й.

ОСНОВЙ1 ПУБД1КАЩ1 ПО ДИСЕРГДЩ1:

МонографН:

1. Яковлев C.B.,Гиль Й.й.,Комяк в.М. и др. Элементы теории геометрического проектирования.- Киев: Наук, думка.

1995. - 240 С.

Статт! та матер!али Всесовзних конференц!й:

2. Пономаренко Л.Д..Луканина В.М. Матричный способ организации вычислений при решении задач размещения геометрических объектов // Комбинаторная геометрия и оптимальное размещение. -Киев: Ин-т кибернетики HAH Украины, 1974.-С. 17-22.

■ 3. Гиль Н.И.,Коняк В.М. Об одном подходе к решению задачи раскроя промышленных материалов // Теория и метода автоматизации проектирования..- Минск: Ин-т техн. кибернетики АН БССР, 1984.-С.46-52.

4. Гиль Н.И., Комяк В.М..ОпанасЕк А.Б. Об одном алгоритме составления рациональных схем раскроя однотипных листов на нногосвязные заготовки // Теория и методы автоматизации проектирования. - Минск: Ин-т техн. кибернетики АН БССР, 1985, 2..-С.123-128.

5. Коняк В.М. .Пандорин А.К. 00 одном способе локальной оптимизации в задаче построения плотнейшей укладки неориентированных многоугольников // Математическое и программное обеспечение задач оптимизации технических систем.-Киев: Ин-т кибернетики HAH Украины, 1987.-С.28-33.

6. Комяк В.М. Об одном способе оптимизации в автоматизированных системах управления раскроем промышленных материалов// Автоматизированные системы управления и приборы автоматики.- Харьков: Вица школа.,1989.-Вып.89.-С.95-100.

7. Винарский В.Я.,Комяк В.М. О способах построения некоторых оптимальных положений транслянтов геометрических объектов в R2 // Прикладная геометрия и инженерная графика .Киев: Будивэльнык, 1990. -С.67-69.

в. Конях В.Ц. Размещение в областях произвольной простран-

ствекной формы с учетом специальных технологических ограничений // Математическое и компьютерное моделирование в машиностроении. - Киев: Ин-т кибернетики НАЛ Украины, 1994.-С.4-8.

9. Комяк В.М. Анализ вычислительной сложности и погрешности некоторых алгоритмов построения годографа вектор - функции плотного размещения //Метода оптимизации технических и информационных систем.-Киев:Ин-т кибернетики НАН Украины*, 1995.-С.4-9.

10.Комяк В.М. Оптимизация размещения геометрических . объектов в несвязной области со сложной формой границ / АН УССР. Ин-т проблем машиностроения. -Харьков, 1984.-11 с.-Деп.

В ВИНИТИ 23.02.84, №4353.

11. Гиль Н.И.,Луканина В.М. Автоматизация построения Функции плотного размещения // Автоматизация технологической подготовюа проиводства в машиностроении с помощью ЭВМ-Материалы 1 ВсесоЕЗ. межвуз. научн.-техн. конф. -Киев-Донецк:Вица школа, 1976. - С.142-147.

12. Гиль Н.И.., Вценко В.Г., Комяк В.М. Построение с помощью ЭВМ рациональных планов раскроя материалов фигурными заготовками // Использование методов ойтимизации в текущем планировании и оперативном управлении: Материалы Всесоюз. конф. - М. : Всесопз. НИИ систем, . исслед., 1981» - С.227 -231. ,' - ' ; '

Surrmary. Komjak V.M. Kbthematical and aimputer/modelling irregular placement of planar geometric objects indomains of arbitrary spatial form. This thesis is submitted for an academic Degree of Doctor• of Technical Science an the speciality 05.13.02 - mathematical modelling in scientific research. Institute for Problems in fechinery, National-Academy of Sciences of Ukraine, Kharkov, 1995.

Thesis develops methodology of mathematical and computer raodelling irregular placement of geometric objects in detrains of arbitrary spatial form, being main optimization body of workable CAD which are oriented for creation of resource saving and wasteless technologies. In this connection mathematical apparatus to formalize the geometrical restrictions of the problem when objects and domains have arbitrary spatial fora-, is created. Approximate methods with a number of approximating procedures and exact methods of irregular placement of geometric objects are developed. Software with estimates of its computational complexity and stability concerning accumulated errors are created. Problem-oriented models are developed and problems appliedare solved in real conditions of practical application. Application of results into educational process is realized in highër educational institutes .

Аннотация. Коняк В.М.Математическое и комьютврное моделирование нерегулярного размещения плоских геометрических объектов в областях произвольной пространственной формы. Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.02 - математическое моделирование в научных исследованиях. Ин-т проблем машиностроения НАН Украины, Харьков, 1995.

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

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

Ключов! слова: Геомлфичне проектуёання, впарат г.ф.Щ.р., огггиМ1вац1я, моделювання, алгоритм1чйа 1 программа аабезпечення.

4

В1доов1далышй за шпуск к.т.н. Кащенко О.С. • Шдаисано до друку М.РА Формат 60x90 1/16. Пап{р друк. N1. Ум.друк.арк. 1. Обл.-вид.арк. 0,96. 1щ>вх1£0 пр. Зам N 94

Ротапринт 1нституту проблем машинобудування КАН Укра!ни. 310046 Харк1в-46, вул. Дм.Пожарського, 2/10