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

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

РГб ОД

Я П ДОГ (ВЯЗ На "Р803* рукописУ

ЧОРНОМОРЕЦЬ АндрШ Олекс1йович

.1

МАТЁМАТИЧНА МОДЕЛЬ ТА МЕТОД РОЗВ'ЯЗАННЯ ЗАДАЧ! Р03М1ЩЕННЯ ТРИВИМ1ШХ МНОГОГРАННИХ ОБ'ЕКПВ

05.13.16 - застосування обчислювальнок техн1кй, матенвтичного моделевання та я математичних метод(в у наукових доеждженнях

А в т с^р е ф е р а Т дисертацН на здобуття наукового ступени кандидата техн!чних наук

Харк1в - 1993

Роботу виконано у в1дц1л! матёматичиого моделгвання та оптимального проектуваьня 1ист1ггуту проблем машинобудування AJÍ Украпш

Пауков! кер1шшки: член-коре'спондент АН Укра1ни,

доктор тохШчннх наук Стоян П.Г.,

доктор /еХШчтос наук.

старашя наугсов.й спIврой1тник Г1ль M.I.

ОФ1ШШ11 опоненти: доктор телН1чких наук, профосор С1рода 1.Б., кандидат техн1чних наук, доцент Струк^а В.М.

Пронина установа: Дн1пропетровсысий державнии ун1верснтет (м. Дн1пропетровськ)

Захист в!д<3удеться /О . 1S93 р. о /Jrгод. у

ауд. .« 1112 на зас1данн1 спец1ал1зовзно1 вчено! рада Д 016.22.02 при 1нстнтут1 проблем мяшиноОудування АН Укра1ни за адресов: 310046. м.Харк!в. вул.Дм.Пожареькэго, 2/10.

3 дис<;/гац1ев можна ознаш лтись у 01(3л1отец1 1нституту проблем маишюбу дуванил АН Укра1ни.

Автореферат роз1сланий " а- я? 1993 р.

Вчений секретар спец1ал1зовано1 вчено1 ради доктор техн1<ших наук

T.I. .'L'eííKO

- 3 -

1. ЗАГАЯЬНА ХАРАКТЕРИСТ ИКА лРОЕОТИ

*

Актуадьн!сть проблеми. При {эозв'язанн! багатьох'задач проектування необх!дно враховувати 1х оссблнвост!, пов'язан! 3 ц1леспрямованим перзтворенням гебметрично! 1н4ормац!( у в!дпов!днсст! до певного критер!я опткмальност!, що дозволяе : вилучитИ ц! задач! у клас задач геометричного проектування. До числа цих задач в!дносяться задач! оптимального рознЩення геометричних об'ектЦ, як! потребувть для свого розв'язання розробки спец!альних математичгак мзтеп!в та алгоритм!в. Вэж-ливим напрямом розвитку 'проблеми, що досл1джуеться, е розроб-ка метод!в розв'язання задач нерегулярного рознЩення. в яких зд!йснюеться пошук оптимального розм1щення об'ект1о дое1льно! форки в дэяк1й облает! простору при додержанн! ебмежень на Шсцезнаходження об'ект!в.

Робота виконувалась у пер1од з 1938 по 1992 р!к у в1дд!-л! математичного .моделвзання та оптимального проектування 1ПМаш АН Украгни у з1дпоб!дност! до плану НДР з: д/б теми •'розробка математичних нетод!п геоиотриЧного проектування" (.4 . ДР 01860049704); д/0 теш "Математичне моделквання склад]'шх техн!чних систем модульного типу" (,\1 ДР 01900009440); г/д теми "Розеиток метод!п автоматичного еск!зного компонувадьно-го проектування автономно! електроф!знчно! установки" з Науково-досл1дним !нститутом елек?рсф!зично$.апаратури Ш. Д.В."Ефремова (Рос!Ксы;а ФздзреШя» й ДР 01910017869).

Метою робота е розробка матемаг.мно! модел! та нзтоду -' •розв'язання задач1 оптимального розШяення ?рив;а4!рт!х нного-гранннх геометричних об' ект1в у задаша многогранних областях простору

Наукоза новазьи результат^ #1сер?ац1й&>! роботи:

- розроблено та досл1дакзно глтемитМну иоде?'?* |эозгляду-вано! задач! оптимального нерагуляриого розмШ&Й'ш-Мйогогран-них об' ект!в, що грунтуемся на вш<ориЬтанй1 апа£ату <Мй?ик-ц!й. На Шдстаз! зд!йсненого анализу особливостёА г'аусм'зт;!5;- ■ но? модел! запропоновано катод резв'язаннЯ ц!е!.задач!;'

- запропоновано алгоритм побудови уйэа вз&тюхо [тперё-■, тину дов!льних, неопуклих многогранников простору Яэ за допо- .

- 4 -

М0Г0П ПОВСрХОНЬ 0-р1вня Ф-Функц!й:

" розроблено алгоритм побудови многозв'язних граней поверх» 1 0-р1внн Ф-Функц!!;

' - розроблено алгоритм точного розв'язання задач! розмЬ пення прямокутних г1перпвралелеп1пед!в у прямокутному г1пер-паралелеп1псд! простору р>3. Сформульовано лог1чн! правила в!дтинання сор1антIв розм1шення, як! зав!домо не визначають екстремалышх розв*язк!в задач!.

В1рог!дн!сть результат!в проведе»их досл!джань. Теоретичн! дасл!дивння, викоиаН! у дисертаЦ1йн!й робот!, • Оззусться на(фундамцнталышх положениях теор!! Ф-Функц1п та террН оптим!зацП. Математнчка модель та метод розв'язання •поставлено! задач! 6 обгрунтованими на Шдстав! в!домих, ап-;; робованих. ^еоретичних та експеримантальних результат^, одержат« ров! шё п1д час розробки метод!в оптимального розм1щеннй плоских та об'емних об'ект!в. В!рог1дн!сть висновк!в та результатов дисертац!йних досл!£гень заснована на доказах сфор-. мульоваких у робот! теорем, а такоа Шдтварджуеться 1х задо-в!льним пор1внянням з результатами вксперимеит!в, шосоканих ца п!дприеметв! А-7682, та з1стааленняМ з в1домши розв'яз-кани ряду задач.

Практична ц!нн!сть роботи полягае у тому* шо розроблен! метой1 та алгоритм;!, в такой комплекси програм: "Поверхня" -для побудови поверх«1 0-р1вня ©-функцП дов1яьнйх иногограи-ннх об'ект!в- та "Оптимум" - для поиуку глойайшэго оптимуму у задач 1 роамШенш? оряжхутюсс г 1 перяарагк?.Еэа{взд {в - над ал! можиа твсористовуватн Для розв' язання р!зща задач оптимального розм!згння. Ш задач! вшшса&ть п1д час процесу автома-тизацИ прогктувакш у машйнобуд,ваш!, буд1Еництв1, рад1о-елвктронн1й промасловост1 та на транспорт!, а такоа для розв'язанил задач оптимального розпод!лення ресурс!в. як! з во деться до задач розм!щекня геометричних об'ект!в. Ц! программ 1 комшшкси ножна використовувати. наприклад. для компо-нувального проектування та побудови схсМ завантаження транс-портнях засоб!в (морських та ,пов!тряних суден. 38л1зш''чш Вагон!в, контейнер!в 1 т. 1н.)( ио дозволяе зионшити час розв'язання наведеких виде задач, а також п1двищити е^ектив-И1сть використання в!дпов!дних матер!ал!в та примШень.

Впровадження. Результати. одержан! у дисертацН (алгоритм побудови умов взаемного нсперетину тривим1рних oö'cktIb. лог(чн( правила в1дтинання вар(ант(в розШщення, що не визна-чають екстренальних розв'язк!в задач!), використано при роз-робц! комплексу програн тривиМрних упаковок та впровалжено у 1988, 1989 рр. на ШдпрмемстЫ П/я A-7S82 з загальним еконо-м!чнин ефектом 37,8 тис, крб.

Апробац!я роботи. Основн! положения роботи допов!дались та обговорювались на: •

,- всесоюзна конференц! 1 "1нтегрован! систени автомати-зованого проектування" (м. Вологда, 1989 р.):

- TV обласн1й м!жгалузваш науково-технШнШ конференци "Роботизац!я технолог!чних dpauecia у мадаяобудуваин! та при-ладобудуванн!" (н. Штотгр, 1991 р.);

- TV всесоюзна конфербнцп "Метода та засоби обробки складно» граф1чноК 1«Формац11" (м. Нижм1й Новгород. HJ91 р.);

- XV конференцП Молодих вчених та фах(ва!в 1ПМаш АН УкраКни <м. Харк1В, 1987 р.),

Публ1кацП, Основн! результати дисертац!йно! роботи опубл1ковано у S працях.

Структура та обсяг дйсертацП. Робота складаеться !з. вступу, чотирьох роздШв, висновку, списку л!тер&тури 1з 118 найменувань. 25 рисунк!в та 3 таблиць; усього - 135 стор!нок.

2. 3MICT РОБОТИ

У першому розд1л1 сформульовано загальну задачу розн!-щення геометричних об'ект1в у деяк!й облает! простору R3. Приведено формальний опис початкових об' екТ1в. Зд1йснено ан?(-л!з математично! постановки досл1джувано$ задач!, що грунту-еться на використанн! теорИ Ф-Функц!й.

Б1льш!сть задач розм1щення геометричних об'ект!в перед-бачае присутн!сть критерПв, що визначаьтЬ як!сть розм1щення. Оберено критер1ем якост! деякий фуккц!онаЛ ИХ), де К - век- . тор параметр!в розм1щення. Тод{ загальну задачу розм1щення геометричних od'eKTlB ссЬормулюемо таким чином.

Задача. Маемо v-об'екти S , i=l, 2.....п,' як! пот-

I

р(бно розм!стити, з параметрами розм!щення х1 та область роз-

Шщення S0. Потр!бно визначити значения параметр1в розн1щення

Xo=íx*.хг.....х">, до давть екстремалънв значения критер1я

якост! розн1щення та задовольнявть yol обмеження, як! накла-давться на параметри розм!щенкя.

Процес поСудови математично! нодел1 задач1 розм1п$ення об'ект!в вимагае форнал!зац11 опису II головких конпонент1в: oO'ektlb, то розм1иувться, обмежень на параметри розм)15ення (умови взаимного попарного неиероТину сб'ект!в, умови 1х розм1щення в облает!) та критер1я якост!'.

¡снують р1зн!' способ» опису многогранник 1в, наприклад за допомогов структур л1н1йяих нер1внянь або деякого опису тонок 1х поверхн!. Многогранники' Оудано зэдавати мноаино» 1х вершин та граней тому, цо у запропоноввному алгоритм! поСудови умов вэьемного непереткну №югогранник1в кеобх!дно знати ус! точки поверх»I кожного з об"а..1в. Грзн1 об'ект1в визна-чимо через поел!довн!сть координат вервин.

Для анал!тичного опису геоматричних п1дног"!1Ь Mis об'ек-тами. во розм1иусться, канриклад непарзтин таторкання, у ро-Сот1 використовуеться алврат Ф-фукхц1я. ©-¡йжкцГя пари об'ск-т(в S((x') та (х1) дозволяе формально сизкачпти'м!ру близь-кост!, р. такоа Mtpy 1$; нерзтину у зплегиэст1 в!д значения парамстр!в розм!цекил я' та s1.

На п!дстап! означения-СнёуикцМ вираз J (х' )>0 задас умову ^заемного иеперзтаку cS'cktIb S(<х' ) та S^x1 ). За допомогов апарату §-функц!й>такоа зручне ояису&йти умоаи розн!-щення о облает!: Ф,(х1) ) О.

Псверхнн. визиачена р1внянням ф- (х* ,х') » О, мае незву поверхн! 0-р!в:к С-£уккц11.

HeofixIjcîOB GZY&:t>T> задач KJ^oy, то досл!джуеться, е присутк1еть дежаге заажрЗя якост Г. У Ц1Я'робот' критерии якост! е sossEîiâ, г süüítt-S-честкио0даст1' розмизеннл S0 уздовж ocl CS свивка координат.

ypexcEjîra оптем1зш(!йиу задачу розм1Е<жня

ечшгогранк&йь прзстору R3 у деяк!й облает!. запшемо так:

г" = nun г., * (1 )

.(D

да область пркпустнмих розв'пзк!в D визначаеться умопами

Фи(х',х') > 0. Ф^х1) > 0. 1о=1.2.....п. (2)

У другому роздМ зд1йсн8но анал!з нетод!в побудови умов неперетину дов!льних геометричних многогранних о6'ект!в простору !?3, що грунтуються на зь'язку теоретико-множинно! опера-ц1! суми Шиковського та поверхн! и 0-р1вня ф-фуикц11. Запро-ваджено поняття "псевдограней", Розглянуто правила побудови граней поверхн! и за допомогов множини "псевдограней".

Сформулюемо принцип побудови множини граней поверхн! о 0-р!вня Ф-Функц!I двох многогранник^.

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

2) Грунтугчись на ц!й Множим! "псевдограней", необх!дно побудувати, використовувчи певн! правила, занхнену многогран-ну поверхнв, тобто визначити множину граней, сувдтаЮть яких

е поверхнвв 0-р!вня Ф-фуккц1» йочаткоекх оЙ'ект1в та 52.

Тону що поверхня и визначае умови сильного розм!щення об'ект!в (тобто фактично уноси 1х тсркашя), у робот! проаиа-л1зовано пари межових точок об'ект!в та Б.,» що характеризуют головн! типа торкання многогранник!в, та зазначено правила побудови "псевдограней", що в!Дпов!даютЬ цим типам. Зазначимо, що грань та ребро е парадельн!, якщо паралельн! площина та пряма, як1 були ними задай!. Позйачимо ~ результат воображения об'екта Sj в!дносно нуля простору I?3

Б* = < г. | t=-t' , ^ е 8 >. •

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

д1 = д ® Ь" = < Ъ | ь = х1 - х2, х4 е д, х4 с И >,

де операц!я ф - операция суми М1нковського.

- В -

Якщо ребро г одного з об"гнт1в та грань Ь другого з об'ект!в е парвлельними та н1 одна з гранеп першого об'екта, яка м1стить у соб1 ребро г, не б паралельною до гран1 Ь, то нс1ляк1 мири точок к та у, хсг, у с И, визначавть "псевдогрань" другого типу. Отже. в1дооа1дн1 ребро г4 об'екта Б, тя грань об'екта а такоя ребро гг об'екта та грань об'екта Б визиачаоть "псевдогран Г" д* 1 д* другого типу:

ч; - г, • ^ - < ь | I- » х(- г, хг* Ьг

ч'.- = • г] ■ (Ч I С « х, - Хг. х, I Ь,. х., I \ ?

Якщо ребра г та гг об'ект1в Б, та 5г розм!щен! на непаралельних пряних та в1даов1д"' гран! двох об'ект!в, що м!стять у соб! ребра г1 та гг, не е парвлельними м1ж собою, то пари точок, як! налэжать в1дпов1дно до ребер г, та гг» визначапть "псевдогрань" у1 третього типу:

()' = ♦ Г^ » ( I I С » *1 - Ха, Х( С Г,. Хг « Г2 >.

Яйцо ребро г( об'екта е паралельним до ребра г^ об'екта Б , то ребро г( е паралельним такоя до деяко! гран! об'екта яка м1стить у соб1 ребро гг. Отже, пари межових точок. що належать до паралельних ребер об'ект!в та Бг, вже були використан! п(д час побудови "псевдограней" другого типу.

Вершина V одного з об'ект!в та точки гран! Ь другого з об"ект1в визначавть "псевдограг" четвертого типу, якщо вершина V не належить н! до одн1е! з граней чк до ребра, що е парвлельними до гран1 Ь. В!дпов1дн1 .вершина V об'екта та точки гран! Ь об'екта а також вершжа и об'екта та точки гран1 д об'екта 55( визначапть "псевдогран1" д} та д' четвертого типу:

д| V • Ь~ « ( I. | I ■ V - х, х е. Ь >, в

д* ■ д"• Ц~ = < 1- | I. = х - и. х с д >,

де v, и - значения координат вершин V та 11 у в1дпов!дних системах координат.

Теорема. Множина ус!х "псевдогранай", побудова-них для многогранник!в та S., обмежуе многогранний об'ект о, що зб!гаетъся з т1лом

о0(0) =s,(0b»s;(0).

поверхня якого с поверхнею 0-р!вня Ф-Функц11 об'ект1в St та

Г. '

о. ,

Доведен н я. Позначимо А як множину точок, що належать до "всевдограней". Грунтуич^-ь на способ! побудови "псевдограней", для кожно1 точки множини А зд!йсняеться така умова: - .,

•

s, (О) ,-i s,(x) * с. (3)

Зобразимо множииу Л як об'едияння неперетиниих множин А( та А., таких, пю коли х е А(, то зд!йснюеться сп1вв!дношення

ini. S1 (0) п ''И. Яг(х) = й. (4)

Якщо х с А.,, то (4) не вихонуеться.

. У робот! було показано, що ловерхня оо(0) т!ла по(0; зб1га5тьсй з поверхне» 0-р1вня ф-функц11 ?б'ект1в S, та S2. Отже, грунтуючись на характеристична властивост! <В-функц11, якщо полке об'екта S., розм!стити у деяк1й точц1 х на поверх-Hl ио(0), то для обЧкг1в S3 (0) та S2(x) вйконувться вирази (3) та (4). Тому що п!д час побудови "псевдограней" було розглянуто вс!ляк! nt, и межовик точок об'ект!в St та S2, множина точок поверхн! иа(0) належить до множини А,

<•>„(0) с А, та uQ(0) - A(.

Грунтуючись на властивостях Ф-функцП, точки множини A внутр!шн!ми точками т!ла oit (0). '

Тому що множина А м!стить у соб! ус! точки поверхн! т1-ла оо(0) та деяк! його внутр!шн! точки, теоремй е доведено*).

- 10 -

У робот! розглянуто алгоритма побудови "псевдограней", описано також головн! правила визначення "псевдограней", що зав!домо не м1стять у саб! точок поверхн! 0-р!вня Ф-функцП. .'озроблено алгоритм побудови окремо! гран! поверхн! 0-р1вня ф-функцИ, приведено правила знаходження зовн!шнього та внут-р!шнього контур!в II меж!. При цьому враховано, що ¿ран! по-чаткових об'ект1в можуть бути неопуклими. Описано укрупнений алгоритм формування множили граней поверхн! и, особливост! побудови "псевдограней" для ¡випадку, коли початков! многогранники масть неопукл1 {ран!.

. У третьому розд!л! розв'язання задач! Ш. (2) оптимального розм!щення тривим!рних т!л у многогранно облает1 простору К3 пропонуеться зд1йснювати в два етапи. На першому ета-п1 знаходиться точний розв'язок задач! упаковки прямокутних паралелап!пед!в простору R3, як! мають взаемно паралельн! гран! та апроксиыують початков! об'екти. На другому етап! визначаеться локально оптимальне розм!щення v-многогранник!в простору R3, при цьому початковим розм!щенням е упаковка, одержана на перщому етап1. Для знаходження оптимального роз-Mi щення об'ект1в у робот! використано !терац!Яний метод локально! оптим!зацП*.

Розглянемо метод пошуку точного розв'язку задач! упаковки г1перяэралелеп!пед!в простору Кр, р ) 3, Припустимо, що маемо множину прянокутних г!перпаралелеп1пед!в £S4>, i=l,

2....... як! визначен1 у евкл!довому простор1 Rp та ребра

яких е паралельними до координатних осей цього простору. Роз-М!ри кожного з об'ект!в St уздовж в!дпов!дних осей координат

дор1вн»>лъ , k=lrZ.....р. Припустимо також, що визначено

нап!внеск1нченну область

So в < <VX2.....V I х, > 0.

О i х < аь, к =2.....р }. •

к It

* Стоян Ю.Г, Новожилова М.В., Картров A.B. Математическая модель и оптимизация линейных Ek(R")задач размещения.-

Харьков. - 1991. -'27 с. - (Препринт/' АН Украины. Ин-т проблем машиностроения; № 353).

Задача по л яга с ось у чому. Необх1дно розм!стити п Нперпара-лелеп!пед1в в област1 S0 таким чином, щоб довжина зайнято! частшш област1; (уздовж координатно! ocl ОХ,) була м!н1маль-нов.

Мзтематична модель задач1 мае вигляд: знайти

min i:, ' (5)

де область припустимих розз'язк!н D у еькл!довону простор! R". m = p n tlv визначаеться-структурою л1'н1йних нер1ЕКОстей

П G(5 (х1 „х1 ).й°,2р) rn <i(a(x',хг,...,к",г),л,,2рп),

I. i

(6)

и = n<n-l )/2. uj - 1,2.....л, i < j.

Структура (х' ,xi М°.2р) визначае умови взаемного нетга-

ретику об'ект!з та S , i.j~l,2.....п. Kj. га зобрежуеться

об'еднанням наступних нар!пнес гей:

- < - ( а' . а' ).

к « V к

- х' 4 х' < - ( а? . а;-). к-1,2.....р,

як ■ к *

Система с(з(х,,хг..».,х".г:).л,,2рп) визна'йе умови розм) ¡ценил oÖ'ektIb St, i-l,2,,,..и, на частин! облает! Зо довжинов z та зобрчжуеться системою таких кер!вностей:

- х| . а; < 0. х^ - 7. < я\ < О,

I

- х' « а' <0, • х! - а ♦ а' < О, к=2.....р.

Ь к к к к 1

Незначимо як Т = { Ц >, 1-1,2.....(2рп+рп(п-1)), наб!р

р!внянь, що описуггь множнну г 1 пзрплоЛг, як! формують нежу облает! 0. <»

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

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

Розглянемо спос1б точного розв'язання задач! (5), (6), що грунтуеться на схем! методу г!лок та меж. В першу чергу опишема структуру дерева розв'язк!в А ule! задач!,

ЗПдио з властивостяни систем р!внянь задачу знаходження вектора параметр!? розм!дення х", що визначае екстремальне значения функцИ мети z, можна розв'язати, використовуючи таке дэрево розв'язк1в. Кореню дерева розв'язк!в А - вершин! А0 поставимо до в1дпов!дност! прост1р Pm",=Rpn. Кожна вершина первого р1вня A(0,j¡) описуе деяку л!н!йну многостатн!сть I/, до Мае вим!рн!сть ш-2, та отриману в результат! .перетину простору R*"1 та Пперплоцинн, р!вняння яко! м!стить у соб! Незалешу ам!нну к} 1 мае вигдяд:

- к| + = - С а* . а'1) або - xj = - -а|.

Число вершин на першому р!вн! дор1внве п. Вершина А(0,j',j^). i=L2,...,ri, другого р1вня дорера розв'язк!в визначае л!н!йну многостатн!сть, що мае вим!рн1сть ш-3, 1 отриману аа допомо-Гою перетину л!н!йно! многостатност! I/ та г!перплощини, р1вт няння яко! м!стить у соб! зм!нну xí, з негативним знаком. Ана-лоНчНо будуються вершини третього та наступних р!вн1в До pn-го р!вня.

0ск1льки кожн1й вершин! р~-го р1вня в!дпов!дае система (т-1) р!йиянь, то побудоване дзрево розв'язк!в дозволяе отри-мати на останньому р!вн! ус! системи (гп-1) р1внянь з набору Т. Отже, за допомогою цього дерева е можлив1сть ироанал!зува-■ти п!дмножину точок облает! D, що м!стать у соб1 точку глобального м1н!муму функцИ z. Показано, що на множин1 об'ект!в íSj>, 1=1,2«...,п. що Нають вектор параметр!в розм1щення х**, е Можлив!сть визна^ити загальний порядок, тобто можна таким чином перенумерува^и об'екти, що кожн!й sMiHHfñ у систем! р!внянь, яка визначае точку глобального м!н{муму функцИ мети z, в!дпов!дае одне з р!внянЬ вигляду: "

- х' + X? = к к

- 13 -

- ( а' » 3 < 1,

■ хк 3 ■ К • ■

I ,

Отже, задачу пошуку глобального м!н!муму можливо звести до перебору множим п = {я >( 1=1,2,....п!. перестановок л( но-мер!в об'екг1в, що розм1щуються, та для кожно! перестановки -до одержання вар!ант1в розм!щення, грунтувчись на дерев1 розв'язк1в, побудсваного за допомогов алгоритму, який описано вище.

Нехай п!д час побудови вар1ант1в розМщения отримано вершину х* облает! 0. У загальному вшадку, 1снуе деяка, мно-яина аж* систем р!внянь, кожиа з яких опйсуе цю точку х*, тобто у дерев! розв'язк!в на останиьому р!вн! маемо дек1лька вершин, що визначають один 1 той же вар!ант розмИцення. У . робот! сформульовано правила в!дтинания, що зменшуить число систем р!внянь у множил! ав*. Також досл!джено симетричн!стЬ розм1щень, що в!дпов1давть'деяким системам р1внянь. ' ' у

Показано, що оШнка швидкодИ описаного методу розм!-пення прямокутних г1перппралелеп1пед1в дор!внюб

Т\*я/2>*л.

Укрупнений алгоритм розв'язання початково! задач 1 (1Ь (2) полягас в наступному. . ' * 1

1. Побудувати поверхн! 0-р!вня ф--функц!й ус1х пар йочаткоййх об*ект!в.

2. Знайти початково наближвкня функц!{ мети (1).

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

2.2. Визначити глобальний оптимум задач1 (5), (6) розм1-иення побудованих паралелеп!пед!в у прямокутнШ, нап!внеск!н-ченн1й облает!. °

3. Застосувати !терац1йний метод локально! оптим!зац!1, *де як по'чаткова точка використовуеться розм!щення, отримане на попередиьону кроц!.

У Четвертому розд!л! описано практичну реал!зац!ю дос-

л!джених метод!в, Запропонован! метода та алгоритм« побудови поверхн1 0-р1вня Ф-фуикц11 дов1льних р-многогранник!в простору R3, а також метод оптимально! упаковки прямокутних rinep-пар8пелеп1пед1в реал!зовано у вигляд! комплекс1в програм для ГВМ-сум1сшш персональных конп'втер1в, що пращэють у опера-ц!йному сер- ~,Emi DOS. Ус! програми комплексГв написан! на мов! програмування С! та м1стять 7980 виконуваних опера-

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

' , , Працездатн1сть та ефсктивн!сть розроблених програм виз-

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

За матер!алами виконано! дисертац!йно! роботи можна сформулавати так! основн! висновки 1 результати:

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

2. Розроблзно алгоритм р2ал!зац1! умов взаемнсго непере-тину кеопукаик шюгогранних об'ект!в простору fr на основ i повэрхонь 0-piсил ф-функцЩ. Опис цих поверхонь запропоновано адШснззэати за дояомогою мнойини так званих "псевдограней".

3. Запропоноаано cnocifi та алгоритм побудови "псевдограней". Пршедено основн! правила визначення п!дмножини "псев-дограиш:'» що зав!домо не м!стять у соб! точок шукано!

nOBSpXHi.

4. Розроблено алгоритм побудови многозв'язних граней-поэзрхн! 0-р!вня ®-функц!1. Приведено правила знаходаення

' внутр!{знього та зовн!шнього контур!в мех: цкх граней. ■ 5. Запропоновано та описано алгоритм пошуку точного

■ розв'язку задач! розм!щення прямокутних г!перпаралелеп1пад!в У облает! простору Rp, р > 3. Сформульовано лоПчи правила

• вЦтинання вар!ант!в розмЦення, що вав!домо не визначають екстремальних розв'язк!в задач!.

- 15 -

6. Розроблений алгоритм побудови умов взаемиого непере-■гину тривим1рних об'ект!в, лог1чн1 правила в1дтинання вар1ан-т!в росм!щення, як1 не визначають екстремальних розв'язк1в задач!, використано при розробц! комплексу програм тривим1р-них упаковок. При1 цьому було- продемонстровано 1х високу ефзк-тивнIсть п!д час впровадження зазначеного комплексу на п]д-приемств! п/я- A-7S82.

7. На п! летав! розроблених алгоритм!в створено комплекси програм: "Поверхня" - для побудови поверхн1 0-р!вня Ф-Функц11 дов!льних многогранних об'екТ1в то "Оптимум" - для пошуку глобального оптимуму у задач! розм1щг"ня прямокутних rlnepna-ралелеп!пед!'в. За допомогос проведсного тестуваиня програм визначено основШ фактори, шо вплпзають на час розв'язання задач!. Так, отримаи1 результат« обчисливальних експеримент1в св!дчать„ що за допомогоп комплексу програм "Оптимум" можна розв'язузати задач1 розмШення до ЗО'об'екПв.

8. Розроблен! комплекси програм можна використовувати для розв'язання р!зних задач оптимального розм!щення, що ви-никаоть п!д час процесу автоматизац!I проектувзння у машино-будуваннГ, буд!вництв!, рад!оелектроннт промисловост! та на транспорт 1. Ix застосузання дозволить зменшти час розв'язання зазначених вше задач, а також п!двищити ефективн!сть використання в!дпов!даих матер!ал!а та прим!щень.

Основн!' результати дисертацП описан^ у таких роботах:

1. Черноморец A.A. Графический процессор программной систем?: пространственной1 компоновки- // Интегрированные системы автоматизированного проектирования: Тез. докл. всесоюз. науч.-техн. конф., Вологда, 17-18 окг. 1989 г. - М.. 1389. -С. 153-154.

2. Черноморец А:А. Алгоритм удаления невидимых линий для изображения многогранников с выпуклыми гранями // Прикл. геометрия и ииж. графика. - 1990. - Вып. 49.- С. 123-125.

3. Черноморец A.A. Определение условий беспрепятственного движения робота в пространстве // Роботизация технологических процессов в машиностроении и приборостроении: Те а*. . докл. TV обл. межотрасл. науч.-техн. конф.Житомир, 24-^25 мая 1991 г. - Житомир, 1991. - С. 36-38.

4. Панкратов A.B., Черноморец A.A. Обработка геометри-

- 16 -

ческой информации при размещении невыпуклых многогранных объектов в пространстве //Метода и средства обработки сложной' графической информации: Тез, докл. IV всесоюз. конф., Н. Новгород, сент. 1991 г. - Н. Новгород, 1991. - С. 63.

5. Пономаренко Л.Д., Панкратов A.B., Черноморец A.A. Элементы графического интерфейса пакета компоновочного синтеза технических систем // Методе и средства обработки сложной графической информации: Тез. докл. IV всесоюз. конф., Н. Новгород, сент. 1991 г. - Н. Новгород, 1991. - С. 64.

6. Гиль Н.И., Черноморец A.A. Метод построения поверхности О-уровня Ф-функции произвольных многогранников. - Харьков, 1992. - 29 с. - (Препринт/ АН Украины. Ин-т проблем машиностроения; JS 359).

7. Гиль Н.И., Черноморец A.A. Особенности алгоритмической реализации построения годографа функции плотного размещения многогранных объектов. - Харьков, 1992. - 33 с. -(Препринт/АН Украины. Ин-т проблем машиностроения; К 363).

8. Новожилова М.В., Черноморец A.A. Об одном способе поиска оптимального размещения прямоугольных гиперпараллелепипедов. - Харьков, 1992. - 27 с. - (Препринт/АН Украины. Ин-т проблем машиностроения; № 365).

В1дпов1дальний за випуск чл.-кор. АН УкраИни Божко 0.6.

Шдписано до друку

Формат 60x90 1/16. Пап1р друк. № 1. Ум.друк.арк. 1, Обл.-вид.арк. 0.S6. Тираж IOJnp. Зам. №97Г .

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

ВВЕДЕНИЕ.

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

ЕЕ ОСОБЕННОСТИ

1.1. Постановка общей задачи размещения геометрических объектов

1.2. Формализация описания объектов в задаче размещения.

1.3. Математическая постановка задачи размещения трехмерных объектов с использованием теории Ф-функций.

Выводы по главе.

2. ФОРМАЛЬНОЕ ОПИСАНИЕ ГЕОМЕТРИЧЕСКИХ ОГРАНИЧЕНИЙ В ЗАДАЧЕ РАЗМЕЩЕНИЯ ТРЕХМЕРНЫХ МНОГОГРАННЫХ

ОБЪЕКТОВ.

2.1. Описание поверхности и О-уровня Ф-функщш с помощью набора "псевдограней"

2.1.1. Принцип построения поверхности и

2.1.2. Основные правила построения "псевдограней"

2.2. Правила определения избыточных "псевдограней"

2.3. Исследование "псевдограней" на принадлежность поверхности и.

2.3.1. Построение сечения объекта, ограниченного поверхностью ы

2.3.2. Алгоритмы нахождения внутренних контуров границы отдельной грани поверхности и.

2.4. Особенности построения поверхности О-уровня

Ф-функции многогранников с произвольными гранями.

Выводы по главе.

МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО

РАЗМЕЩЕНИЯ МНОГОГРАННИКОВ В R

3.1. Двухэтапное решение задачи оптимального размещения многогранников в пространстве R3.

3.2. Математическая модель задачи размещения * 1 прямоугольных гиперпараллелепипедов пространства Rp.

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

3.4. Правила отсечения вершин дерева решений задачи [ оптимального размещения гиперпараллелепипедов . . • 84 . 3.4.1. Определение одинаковых вариантов размещения гиперпараллелепипедов.!

3.4.2. Определение симметрия на множестве 1 размещений

3.4.3. Вероятностное правило отсечения.^

3.5. Схема метода решения задачи размещения ! произвольных многогранников пространства R

Выводы по главе

ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИИ . . . 106 4.1. Комплекс программ "Поверхность" построения поверхности О-уровня Ф-функции произвольных ! многогранных объектов

4.2. Комплекс программ "Оптимум" поиска глобального оптимума в задаче размещения прямоугольных гиперпараллелепипедов.

4.3. Результаты решения тестовых примеров.

4.3.1. Примеры построения поверхности

Ф-функции.

4.3.2. Примеры размещения параллелепипедов . 114 Выводы по главе.

Актуальность проблемы. Успехи в развитии современного программного и аппаратного обеспечения средств вычислительной техники позволяют в короткие сроки эффективно решать многие проблемы, возникающие при автоматизации проектно-конструктор-сжих работ. При решении многих задач проектирования необходимо учитывать их особенности, связанные с целенаправленным преобразованием геометрической информации в соответствии с некоторым критерием оптимальности, что позволяет выделить эти задачи в класс задач геометрического проектирования f1]. К числу задач геометрического проектирования относятся задачи оптимального размещения геометрических объектов, возникающие при компоновке радиоэлектронных плат [2-4], эскизном проектировании технических систем [5], разработке генеральных планов промышленных предприятий [6,73, оптимальном раскрое материалов [8-10], размещении грузов на судах и самолетах [11-13] и т.д.

Сложность задач оптимального размещения геометрических объектов потребовали для своего решения разработки специальных математических методов и алгоритмов [14-16].

Большое исследование в области геометрии было проведено Е.С.Федоровым при изучении кристаллов как природных многогранников [17,183. В работе [16] П.Л.Чебышев рассмотрел вопросы конструирования выкроек и разверток при производстве одежды.

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

Одной из первых фундаментальных работ, посвященных изучению методов размещения геометрических тел с учетом их формы и размеров, является монография Л.В.Канторовича и В.А.Залгал-лера [20]. Изложенные в ней методы и алгоритмы построения оптимальных планов раскроя линейных материалов и прямоугольных листов на прямоугольные заготовки оснозаны на теории разрешающих множителей (индексов), предложенной Л.В.Канторовичем в работах [21-22]. Результаты этих и других работ [23-27] предвосхитили развитие теории линейного и динамического программирования [14,28,29].

Вопросы, связанные с определением плотнейших укладок и редчайших покрытий области (обычно всего пространства) трансляциями одной фигуры, были выделены в виде теории дискретной и комбинаторной геометрии [ 30-32]. Многие задачи комбинаторной геометрии не решены до настоящего времени, хотя их постановки известны давно (например задача плотнейшей упаковки равных шаров в R" при п>3). Постановки и решения некоторых основных задач комбинаторной геометрии приведены в [33-35], полученные для них схемы размещения являются регулярными.

Интенсивное развитие математических методов решения экстремальных задач [36-39] (методов линейного и динамического программирования, выпуклого анализа [40], дискретной оптимизации [31,41], а также численных методов синтеза оптимальных систем [19,42]) обусловили успехи в выборе оптимальных решений задач геометрического проектирования [43]. Разработка проблемы оптимального размещения геометрических объектов осуществляется по различным направлениям.

Алгоритмы регулярного размещения объектов сложной формы в прямоугольной области, в неограниченной полосе и в ограниченных областях пространства R2, а также алгоритмы фигурного раскроя описаны в работах [44-47].

Публикации [48-503 посвящены созданию методов прямоугольного раскроя, ориентированных на гильотинную технологию резки материала.

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

Фундаментальные исследования в этом направлении выполнены В.Л.Рвачевым [51-543. Разработанная им теория R-функций позволила автоматически описывать геометрические тела сложной формы. В работах [55-583 приведены основанные на данной теории методы формализации и решения некоторых задач размещения. Затем появляются работы Ю.Г.Стояна и его школы [15,59-653, в которых исследуются вопросы формализации и решения задач размещения на основе понятий векторной функции плотного размещения и ее годографа [15,643. В работах [66-683 приведены результаты, устанавливающие связь между суммой Минковского двух тел [691 и годографом их векторной функции плотного размещения. Дальнейшие исследования привели к разработке теории Ф-функций и ее поверхностей г-уровня [70,71]. Данные работы явились теоретической основой описанных в [72-74] алгоритмов и программ размещения на плоскости геометрических объектов сложной формы.

Особое место среди задач размещения занимают задачи оптимального размещения прямоугольных объектов в прямоугольной области со сторонами, параллельными сторонам размещаемых объектов. Это объясняется простотой задания условий взаимного нелересечения и условии размещения в области. Для случая пространства R2 для решения данной задачи разработаны точные методы решения [75,76], основанные на использовании схемы метода ветвей и границ [77].

Работ, посвященных вопросам размещения трехмерных объектов, опубликовано значительно меньше, чем для решения задачи размещения плоских объектов. Особое место -среди них занимают работы Ю.Г.Стояна и его учеников [67,78-83]. В данных работах рассмотрены проблемы размещения в основном простейших тел -параллелепипедов, цилиндров, шаров, а также составных тел, являющихся объединением перечисленных выше простейших тел. В то же время представляет интерес разработка эффективных методов размещения трехмерных тел произвольной формы.

Диссертационная работа продолжает исследования, проводимые в Институте проблем машиностроения АН Украины (ИПМаш АН Украины) под руководством члена-корреспондента АН Украины Ю.Г.Стояна.

Работа выполнялась в период с 1988 г. по 1992 г. в отделе математического моделирования и оптимального проектирования ИПМаш АН Украины в соответствии с планом научно-технических работ по:

- госбюджетной теме "Разработка математических методов геометрического проектирования" ГР 01860049704);

- госбюджетной теме "Математическое моделирование сложных технических систем модульного типа" (J6 ГР 01900009448);

- хоздоговорной теме "Развитие методов автоматического эскизного компоновочного проектирования автономной электрофизической установки" с Научно-исследовательским институтом электро-физической аппаратуры им. Д.В. Ефремова (Российская Федерация, № ГР 01910017869); : * и планом обучения в аспирантуре ИПМаш АН Украины.

Целью работы является разработка математической модели и метода решения задачи оптимального размещения трехмерных многогранных геометрических объектов в заданных многогранных областях пространства R3.

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

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

Ф-функций. На основании проведенного анализа особенностей i i математической модели предложен метод решения данной задачи;

- предложен алгоритм реализации условий взаимного непересечения произвольных, невыпуклых многогранников простра^ 1 ства R3 на основе поверхностей 0-уровня Ф-функций;

- разработан алгоритм построения многосвязных граней поI верхности 0-уровня Ф-функции;

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

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

Ф-функций и теории оптимизации. Математическая модель и метод решения поставленной задачи обоснованы исходя из известных, I апробированных теоретических и экспериментальных результатов, полученных ранее при разработке методов оптимальных размещений плоских и объемных объектов. Достоверность выводов и результатов диссертационных исследований основана на доказательствах приведенных в работе теорем, а также подтверждается их удовлетворительным сравнением с результатами экспериментов, выполненных на предприятии п/я А-7682, и сопоставлением с известными решениями ряда задач.

Практическая значимость работы состоит в том, что разработанные метод, алгоритмы, а также комплексы программ: ' "Поверхность" - для построения поверхности 0-уровня Ф-функции произвольных многогранных объектов и "Оптимум" - для поиска глобального оптимума в задаче размещения прямоугольных гиперпараллелепипедов в дальнейшем можно использовать для решения различных задач оптимального размещения, возникающих в прот цессе автоматизации проектирования в машиностроении, строительстве, радиоэлектронной промышленности и на транспорте,' а также для решения задач оптимального распределения ресурсов, которые могут быть сведены к задачам размещения геометрических объектов. Эти программные комплексы могут быть применены, например, при компоновочном проектировании и построении схем загрузки транспортных средств (морских и воздушных судов, железнодорожных вагонов, контейнеров и т.п.), что позволит сократить время решения указанных выше задач, а также повысить эффективность использования соответствующих материалов и помещений.

Результаты, полученные в диссертации (алгоритм построения условий взаимного непересечения трехмерных объектов, ; логические правила отсечения вариантов размещения, не определяющих экстремальные решения задачи), были использованы при разработке комплекса программ трехмерных упаковок и внедрены . в 1988, 1989 гг. на предприятии п/я А-7682 с общим экономическим эффектом 37,8 тыс. руб."

Апробация работы. Основные положения работы докладываi лись и обсуждались на

- Всесоюзной конференции "Интегрированные системы автоматизированного проектирования" (г. Вологда, 1989 г.); ! г

- IV областной межотраслевой научно-технической конференции "Роботизация технологических процессов в машиностроении и приборостроении" (г. Житомир, 1991 г.);

- IV Всесоюзной конференции "Методы и средства обработки сложной графической информации" (г. Нижний Новгород, 1991г.);

- XV конференции молодых ученых и специалистов ИПМаш ;АН I

Украины (г. Харьков, 1987 г.).

Публикации. Основные результаты диссертационной работы опубликованы в 8 работах [98,102,103,104,113,116,117,118]. I

Структура и объем диссертации. Работа содержит введение, четыре главы, заключение, список литературы из 118 наименований, 26 рисунков и 3 таблицы; всего - 135 страниц. j

Выводы по главе

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

2. На основании проведенного тестирования разработанных программ определены основные факторы, влияющие на время ре1 шения задач. * !

3. Полученные результаты вычислительных экспериментов свидетельствуют о целесообразности применения разработанных : ' i методов для поиска точного решения задач размещения параллелепипедов, в которых рассматривается не более 30 объектов. i I

I »

1 ; , {

• • I f f Г I I t t t i \

ЗАКЛЮЧЕНИЕ

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

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

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

3. Предложен способ и алгоритм построения "псевдограt ней". Приведены основные правила определения подмножества ' "псевдограней", заведомо не содержащих точки искомой поверхности. 5

4. Разработан алгоритм построения многосвязных граней поверхности О-уровня Ф-функции. Приведены правила нахождения внешнего и внутреннего контуров границы этих граней.

5. Предложен и описан алгоритм поиска точного решения' задачи размещения прямоугольных гиперпараллелепипедов в области пространства Rp, р > 3. Сформулированы логические праf вила отсечения вариантов размещения, заведомо не определяющих j экстремальные решения задачи.

6. Разработанный алгоритм построения условий взаимного I непересечения трехмерных объектов, логические правила отселения вариантов размещения, не определяющих экстремальное реше-; ние задачи, были использованы при создании комплекса программ трехмерных упаковок и продемонстировали свою высокую эффективность при внедрении данного комплекса на предприятии и/я А-7682. t

7. На основании разработанных алгоритмов созданы комплексы программ: "Поверхность" - для построения поверхности О-уровня Ф-функции произвольных многогранных объектов и "Оптимум" - для поиска глобального оптимума в задаче размеще нкя прямоугольных гиперпараллелепипедов. С помощью проведенного тестирования программ определены основные факторы, влияющие на время решения задач. Так, полученные результаты вычислительных экспериментов свидетельствуют х что с помощью комплекса программ "Оптимум" можно решать задачи размещения до 30 объектов.

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

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

2. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронныхустройств. Львов: Вища школа, 1981. - 168 с. jf

3. Автоматизация конструирования больших интегральных микросхем / А.И.Петренко, П.П.Сыпчук, А.Я.Тетельбаум и др. -Киев: Вища школа, 1983.312 с. j *

4. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичус В.А. Автоматизация проектирования ЭВМ. М.: Сов. радио, 1978. -272 с.i

5. Программная система КТС автоматической компоновки 'iбокса сложной технической системы блочной конструкции / .f Ю.Г.Стоян, Л.Д.Пономаренко,' А.В.Панкратов, А.Ф.Лойко.

6. Харьков. 1987. - 34 с. - '(Препр./АН Украины. Ин-т пробл.!• . »машиностроения; № 264). « ;

7. Минаков Н.П. Решение компоновочных задач в автоматиiзированном проектированйи // Пром.стр-ю.-1973.-^4.-С. 17-19.I

8. Плужников Л.Н., Андреев В.О., Клименко Э.С. Применение метода случайного поиска при промышленном проектировании // Изв. АН СССР. Техн. кибернетика.-1971.-№2.- С. 26-33.: |

9. Белякова Л.Б. Об оптимальном раскрое листового металла. В кн.: Автоматизация технологического проектирования при помощи ЭВМ. - М.: Наука, 1966. - С. 105-115. • j

10. Мойжес Ю.Л. Геометрические основы рационального раскроя полосового и листового металла. М.: Машиностроение,1966. 108 с. • i f

11. Романовский И.В. Решение задачи гильотинного pacJкроя методом переработки списка состояний // Кибернетика. -1969. №. 1. - С. 102-103.

12. Гаврилов В.Н. Реализация проектных требований в задаче оптимальной компоновки приборного отсека // Автомат тизация проектирования авиационных конструкций. Куйбышев1, 1979. - С. 95-99.

13. СтоянЮ.Г., Кулиш Е.Н. Автоматизация проектирования компоновки оборудования летательных аппаратов. -М.: Машинои строение, 1984. -192 с.

14. ДЗ. Тихомиров В.А. Об автоматизации компоновки авиационного оборудования // Управляющие системы и машины. 1980J -J®2. - С. 126-128.

15. Данциг Д.Б. Линейное программирование, его применение и обобщение. М.: Прогресс, 1966. - 600 с. \

16. Стоян Ю.Г. Размещение геометрических объектов.-Киев:

17. Наук, думка, 1975. 237 с.' , j\

18. Чебышев П.Л. О кройке одежды: Полн. собр. соч. в s '5-ти т. M.-JL: Изд-во|АН СССР, 1951. - Т. 5. - 475 с.

19. Федоров Е.С. Начала учения о фигурах // Зап. минералогического общества, 2-ая сер. 1885. - Т. 21. - 410 с. ;

20. Федоров Е.С. Симметрия и структура кристаллов. М.:

21. Изд-во АН УССР, 1949. 631' с. • i1.!

22. Вычислительные методы выбора оптимальных проектныхIрешений / Михалевич B.C., Шор И.З., Тамустова Л.А. и др.,

23. Киев: Наук, думка, 1977. 178 с. .|

24. Канторович Л.В., Залгаллер В.А. Расчет рациональногораскроя промышленных материалов. Л.; Лениздат, 1957.-197 с.

25. Канторович Л.В. Математические методы в организацииIи планировании производства. Л.: Изд-во при ЛГУ, 1939. -}250 с.

26. Канторович Л.В. 00 одном эффективном методе решения некоторых классов экстремальных задач // Докл. АН СССР. : 1940. - Т. 23, J6 3. - С. 212-215. !

27. Залгаллер В.А. Об одном необходимом признаке плот1i нейшего расположения фигур // Успехи мат. наук. - 1953. - г1. Т. 8, М. С. 153-162. ;

28. Залгаллер В.А. Применение математических методов !вsпланировании раскроя материалов // Математические методы Bfтехнико-экономических .расчетах: Материалы науч. совещ., М.чIапр. 1960 г. М., 1961. - Т. 6. - С. 80-91. !I

29. Залгаллер В.А. Рациональный раскрой как средство ! экономии материалов // Использование методов оптимизации в текущем планировании и оперативное управление производством: Материалы всесоюз. конф., М., окт. 1979 г. М., 1980. - :j1. С. 44-47. ! :

30. Залгаллер В.А. , Круглов А.И. Рулонный принцип pacj-кроя // Материалы всесоюз. науч. семинара, Уфа, июнь 198оА -Уфа, 1981. С. 70-76.

31. Канторович Л.В., Залгаллер В.А. Рациональный раскрой1 iпромышленных материалов. Новосибирск: Наука, 1971. - 299: с.

32. Беллман Д. Динамическое программирование. М.: Цздfво иностр. лит., 1960. 400 с. j

33. Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. М.': Мир, 1991. - Т. 1. - 360 с. 1

34. Теория и методы автоматизации проектирования вычислительных систем / Под ред. М.' Брейера. М.: Мир, 1977. -283 с.f

35. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование.- М.: Наука, 1969.-386 с.

36. Сергиенко И.В., Лебедева Т.Т., Рощик В.А. Приближенные методы решения задач дискретной оптимизации.-Киев: Наук, думка, 1980. 172 с.

37. Тот Фейеш Л. Расположения на плоскости, на сфере и в пространстве.- М.: Физматгиз, 1958. -363 с. >

38. Шклярский Д.О., Ченцов Н.Н., Яглом И.М. Геометрические оценки и задачи из комбинаторной геометрии. М.: Наука, 1974. - 383 с.

39. Роджерс К. Укладки и покрытия.-М.: Мир, 1968.-134 с.

40. Васильев Ф.П. Методы решения экстремальных задач.- -М.: Наука,'1981. 400 с. 1

41. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методыiоптимизации.- М.: Наука, 1978.-352 с. jJ

42. Карманов В.Г. Математическое программирование.- М.: Наука, 1980.-352 с.

43. Бейко И.В., Бублик Б.Н., Зинько П.Н. Методы и алгЪ« ? ритмы решения задач оптимизации. - Киев: Вица школа, 1983.' 512 с. '

44. Пшеничный Б.Н. Выпуклый анализ и экстремальные зада1 Iчи.- М.: Наука, 1980.-320 с. '

45. Сергиенко И.В.; Математические модели и методы реше■ ' ' • ' • - jния задач дискретной оптимизации.- Киев:: Наук, думка, 1985;. i . . > • '. ' -384 с. ! i ;

46. Моисеев Н.Н. Численные методы^в теории оптимальных систем.- M.: Наука, 1971.-424 с. . , j

47. Stoyan Yu.G. Mathematical methods: for'geometric de-sign.-In: Advances in CAD/CAM:. Proc. of PROLAMA? 82 (Leningrad, USSR, 16-18 may 1982^.-jAmsterdam--':n.y.- Cbcford, 198$.p. 67-86.

48. Белякова JI.Б. Вопросы оптимального расположения конгруэнтных фигур на плоскости: Автореф. дис. канд. физ.-мат. наук. Горький, 1970. - 13 с.

49. Белякова Л.Б., Рябина Н.О. Об алгоритмическом обеспечении геометрических расчетов при проектировании на ЭВМ Ьп-тимального раскроя сложных форм // Математическое обеспечение расчетов линейного и прямоугольного раскроя. Уфа, 1981.1. С. 142-145. 1

50. Стоян Ю.Г., Винарский В.Я., Абаляев В.Н. Регулярноеразмещение' геометрических объектов в ограниченных областях?! R . Харьков. - 1990. - 24 с. - (Препр./АН Украины. Ин-т !пробл. машиностроения; $ 282).

51. Винарский В.Я.Дубро Г.В. Оптимальное двухрядное периодическое размещение многоугольников.-Харьков.-1987.-20 |с.1. I . 1

52. Препр. /АН Украины. Ин-т пробл. машиностроения; JG 247).

53. Мухачева Э.А. Алгоритм решения задачи рациональногоiраскроя прямоугольных листов на прямоугольные заготовки //

54. Математические методы решения экономических задач. 1969.»1. J6 1. С. 23-26. |

55. Мухачева Э.А. Расчет рациональных раскроев в системе автоматизированного проектирования технологической подготовки гильотинного раскроя // Кузнечно-штамповочное производство;. -1982. $ 7. - С. 31-37. • !

56. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984.-176 с.I

57. Рвачев В.Л., Ющенко Е.Л. О классе функций, удобныхг *для аналитического описания некоторых геометрических образов // Кибернетика и техника вычислений. Киев: Наук, думка, ;I