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

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

рГ О С.; На правах рукопиоу

евсЕевА лвдмила ГригорИвна

КОМБШТОРНА 01ГОМ13АЩИНА ЗАДАЧА Р03М1ЩЕННЯ ПРЯМОКУТНЮШ ТА ЫЕТОДИ II РОЗВ'ЯЗАШЯ 3 УРАХУВАННЯМ ПОХИБОК ПОЧАТКОВИХ

ДАШ

/з. Я

-01.06;<3й - математична моделвваяня та обчисдаальн! метода 8 НауКОВИХ Д0СЛ1ДК9ННЯХ

Автореферат дисертацП на здобуття наукового отупеня кандидата ф1зш<о-математичних наук

Хврк1в - 1995

ДасертадХяо в рукопис. Робота виконава у в1ддШ матамаотшого моделювання та оптимального проекгувашш 1нстигуту проблем машиноСудування НАН УкраГнн.

Науков! керШшки: член-коре спондент НАН Укра1ни, доктор техн1чша наук, профвсор Стояв Юр1й . Григорович.

кандидат ф1зико-Ы8теыатичних наук, доцент Снедь Олег Олеко1вович

0ф1ц1Ан1 опоненги: доктор ф1зйКо-математичнщ наук, профвсор Яковлев Сэрг1й Всеволодович, кандидат ф!знко- матаматичних наук, профвсор Мельниченко Олаксандр Савович

Цров1даа орган1зац1я: Ки1всышй нац1оналы$ий ун1верситет Ш.Тараса Шзвченка, МШстерство осв!ти УкраХни, м.КмХв.

Захист вЦбудаться 1996 р. о 1Б годин]

в аудитор!I 11-го поверху на 8ас1данн1 спэц1ал1зовано! вчено! рада Д 02.18.03 в 1нститут1 проблем ыашиноОудуванш НАН Укра1ни за адресою: 310046, м.Харк1в, вул. Дм.Пожарського, 2/ю. •

3 дис8ртац1ею можна ознайомитися у б10л1отец1 1нотитут] проблем машиноСудування НАН Укра1ни за адресов; 310046, м.Харк1в, вул. Дм.Поаарського, 2/10.

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

Вчений секретер

сдац1ал1зовано1 вчено! рада /-г/^

канд. ф!з.-мат. наук, с.н.с. /] [Г Рервтельник В.В

1. ЗАГАДЬНА ХАРАКТЕРИСТИКА РОБОТИ

Ашуальн1стъ проблеш. Серед велико! к1лькост1 наукових га практичная задач особливе м1сце звймбють огггим1зац!йн! задач1 гесметричкого проектування, в тому числ1 оггпшХза-ц1йн1 комб!наторн1 задач! розмИдення, що виникають при вир!шенн1 проблэмп оптимального розкрою матер1ал1в, проек-гуваннi схем генералъних план1в промислових пШриемств, розмХщэнн! обладнання' цбх1в тощо, е також задач1, пов'язан1 з шбором одного з вар1ант1в д11 (при вирИзшн! проблем улравл!ння 1 плвнування виробничих процес!в, у задачах геоматричного проектування 1 перспективного планування га 1н.).

Р13НИМ аспектам розв'язання проблем, исв'язаних s досл1даенням цього кпасу задач, створеяням адекв8тних математичних моделей га розробкоп на ц1й ochobI матод1в оптим1зацИ', присвячен1 роботи пров!дних центр Lb L до-слЦшик!в. Серед них В.С.Михалёвич, 1.В.Сврг1внко, В.Г.Сго-ян, Н.З.Шор, В.Л.Волковяч, ЮЛ.Журавльов, В.А.Бмел!чев га 1н. У Харков! п!д кер1вшщтвом Ю.Г.Сгояна 1 С .В. Яковлева, з Полгав! п1д кер!внщгвом О.О.Бмця розробляюгься п1дходя до розв'язання джжретшх ептим!зац1йттх задач,. заснованиг на в1дображеян! комб!наторних множин в арифметичнпй енклШв npocrlp."

математичн1 модел1 1 метода розв'язання 1деал!зоваяо1 (без врахування похкбок початкових данях) оптим1зац1йно1 задач1 розм!щення прямокутник1в у достатньо довг1й смуз! до-сл!дкено в роботах члена-кореспонденга НАН УяраХни Ю.Г.Сгояна га його учн!в С.Л.Магаса, О.О.бмця, М.В.Новояклово1. I.B. AplcroBoI та 1л- Спроби врахуваня гохабок початкових данях при розв'язаЕн1 задач! розм1щення на основ! вгкорястання апарату обчислювально! геометр!! носять локадьний характер.

Кауков! розройш ©.Г.Стсяна в 1нгервальн1й магематиц! та звстссувазн! ц!е! ново! галуз! математичнвх знань в гео-м?тркл2ому проектуванн1 заклали основу для розвитку яово! страт&гИ рэзв'язання оптим1заи1ЙНЕХ задач геометричного пройктуЕэтая, то доззоляе враховувати похибки початковкх да-ззс, тобто дае моелиб1с?ь одеркувати реальн1 розв'язки прак-т:пнах задач.

Б дгоергад12к1й робот1 прозонуеться п!дх1д до моделю-взння L рсзв'ягення задач! розмЩення прямакуткик1в у дос--сгньо дозг1й смуз! з урахуванням похибок початкових данхк, со Сазуеться ка вккорястанн! елемент!з 1нтервальио1 матема-тша;.

Робота вяконувалася в лерХод з 19Э1 по 19Э4 р. у В1дд1-л1 матемзтичного моделяшання та оптимального проектування ИШат HAH Укра1ни у в1даов1дност! з планами науково - до-сл!дких poßir за: .

а) ДБрзйЕДкетною темою "Математичне моделювання склад-них техн1чних систем модульного типу" № ДР 01900009.448);

б) дбргбюджетяов темою "РозроЗка й досл!дження 1нтелек-гуалыю! систем* в!добракення гэомотркчно! ЛвформацП для omiKisaiUI та моделЕвшня ф1зкко - М8хен1чнкх црсцес1в i теди'чнпх сксгем" (>: ДР 018=0049704).

СкугЛнь босл1дхення jaaapLcuy. В роботах Ю.Г.Стояза i О.О. С;,'ля розгдядзеться 1деал1зовака задача розм1дення пгя!йокуг1й-:к1в ас комб1наторка сптим1заа1йка задача. С.Л.Ма-гасок i М.В.Нэвэкшювою запропоновзн1 структура л1н!йеих EsplBHocTsJt для описания умэз взаемаэго неперетинаквя прямокутник!в I вм1иэЕня прямокутник1в у скугу. У В1Щ[Ш матеыатичного модэдквзяня та оптимального цроектування ШЫаш УкраХнк розроблено метода рэзв'язання оптим1зац1Яно1 задач!

розмШэнЕя прямокутник1в, шо Сазуються на зпксристспн! класичних ыетод1в магемагачного програмузання.

Петою работа е модедювання ош;им1зац1йно1 задач! рсс:.;1-щмшя прямокутшгк1в з урахуввккям поякЗок пэтатхоздх дз:-:;е як ком01наторно! задач! гэометрячного проектувйшл та с:з-робка п1д1од1е до II ефентиыюго розз'язання.

Основтиеи. завдашхии робаги з:

1) постановка оп?им!зац1Яно1 оадзч! рсзм!£гннл пр.г.и--кутник1в у достатньо довг12 сг.-ул! з урахуганпэл генсек по--чзтковит. дашпс;

2) побудова Хнтервально! матемастою! модод! задач! розм!щення прямокутшк1з у достатньо довПЯ смуз! з враху-заняям отхкбок початкових даннх на основ! Ежсрхстзння елэ-мент!в !нтервального анал!зу;

3) здШзнення вХдобракешя !нгервальких- мнояин в арифметичн! евхл!доз! простора; подакня 1ктэрзах;,нэ1 матеиа-тично1 модэл! в ари£ыеткчнсиу эвкл1довому простор! к11;

4) досл!дження математично! модэл! доставлено! задач! як комб1наторнс1 оптим!зац1йно1 задач! геста тричкого проек-гуваняя;

5) розробка ефэктивних набор!в правил з!дтикання без-перспектаззих верх!вок-1 досл1даеняя екстремалыпа власти-востей опукло1 нвда£аренц!йовно1 функцП, модиф!кац!я методу в!ток та меж на основ! доведения правил ! теорем;'

6) розроСка модаф1кац11 ксмЗЬзованого методу задач! м!-а!м!зац!1 опукло! функцП на сфзр! як дексгсгозиц!! метода проекцП суСград!ента га умоеного град1ента;

7) створення комплексу програм для розв'яззння ксмб!на-торно! оптам1зац!йно1 задач! рсзм1аення прямокуткик!з у до-статзьо довгШ смуз!.

Жеподиха дослЮхення. У робот! вшсористано результата, одержан! в рамках теор1й геометричного проектування, 1нтервального анал1зу та матеыатичного програмувавня.

Моделювання' початкових даних задач! розм1щення прямо-кутник1в як задач! геометричного проектування з урахуванням похибок ïx задання зд1йснено на основ! теорП !нтервально! - геометрИ, розроблено! Ю.Г. Стояном.

Досл1дяення екстремальних властивостей опухло! недафе-ревд!йовно1 функц11 базуеться на основних положениях опукло-го анал1зу ! дасл!дхеннях, виконаних Ю.Г.Стояном та його учнями 0.0. ©вдем ! C.B. Яковлввим.

Науяова новизна результат 1в дасертацШо! робота:

1) Залропоновано постановку оптим!зац!йно1 задач! роз-мЩення прямокутник!в у достатньо довг!й смуз! з урахуванням похибок початкових даних.

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

3) ЗдШснене подавая матвматично! модел! задач! розм!-тшя прямокутшк1в у достатньо довгШ смуз! з урахуванням похибок початкових даних як оптш!зац1йноГ коыб1наторно! задач! геометричного проектування (доведено теореми про оцШш й достатн! умови м1н!муыа Щльво! функцщ, що надае змогу використовувата апарат опуклих функцш та ориг!нальн! метода комбШаторно! оптш!зац11.

4) Розроблено п1дходи до ефективного розв'язанкя комбШаторно! оптам!зац!йно1 задач! розм!щення прямскутшк1в у достатньо довг!2 смуз1 у вигляд! мод2ф!яац!й метода в1ток та меж 1 комбЛнованого методу правки!I субград! ента та умовного

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

5) Наведено алгоритма й комплекта програм, до реал!-зують запропонован1 пХдходи розв'язання номб!наторно1 оп-гим1зац1йко1 задач! розм!щення прямокутник!в з урахуванням похибок початкових даних.

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

Теоретична ц1ннЮть резулътт1в робот.

1) Бобудовзна на основ! використання елем9нт!в !втер-вального анал!зу 1нтервальна математична модель оптам 1зац1й-но! задач! розм1щання лрямокутник!в у достатньо довг!й смуз! дае можлив1сть враховувати шхибни початкових даних. .

2) ЗдШснене подання !нтервальна1 математично! модел1 оптим!зац!йно1 задач1 розм!щення прямокутншс1в у достатньо довг!й смуз! у арифметичному евкл!довому простор! к11 дозволяв одночасно враховувати похибки початкових даних та вино-ристовувати традиц!йн! метода геомэтричного проектування в евкл1дових ариЭиетичних просторах.

3) Досл!дзен! властивост! математично! модел! поставлено! задач! як комб1наторно! задач! у вигляд! доведение теорем надають мзяпив1сть застосувати ориг!нальн! мэтодк комб!-ааторно! оптам1зац11.

4) Ьозроблен! ефехтизя! праЕлла в!дтазакяя безпэрспек-

тивних EepziBOK дерева розв'язк1в задач! та доведен! геореми про екстрем&льн! властивост! опуклol функц11 дозволягть модиф1кувати метод в!ток та мен i комб!новавий метод проект I субград!ента та умовного град1ента.

Праишчне значения робота полягае в розробц! й реал!за-ц!1 на ПЕОМ комплексу програм для розв'язання комб!наторних оптим!зац!йних задач геометричного проектування з урахувалиям шхжбок початкових даних. Створений програмний комплекс "Метод"- "Сфера" може бути безпосередньо застосований. при проектуванн! буд!вельних об'ект1в, транспортних засобХв, ра-д1оелектронного обладнання, при вир1шенн! проблеми рацЮ-нального розм1щення обладнання у цехах, в економ1чному плануванн!.

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

Р1венъ реаНзацИ й впровавхекня. Результата роботи впровадаен! у в!дд!л! математичного моделювання та оптимального проектування ШЫаш HAH Укра1ни при виконанн! держ-бюджетних тем "Математичне моделювання складних техн!чних систем модульного типу" 1 "Розробка rs досл!дкенпя !нтелэк-туально! системи в!добрахення геомэгрично! !нформац!1 для оптим!зац11 та моделювання ф!зико-механ1чних ггроцэс!в 1 тех-н!чних систем".

Апробац1я робот. OchobhI положения роботи допов1далися 1 обговорювалися на:

- сем!нарах НауковоГ ради HAH УкраГни з проблеми "К1-.

бернэтика" - "Математичн! метода геометричного проектування" (м. Харк!в, кв!тень 1993 р., литий 1994 р.);

- 46-й науковШ конференцП викладач!в та студент 1в Полтавського 1нженерно-буд1вельного Хяституту (м. Полтава, 1994 р.);

- 4Т-й науковШ конференцП викладач!в та студент1в Полтавського техн!чного ун1верситету (Полтава, 1995 р.);

Публ1кац11. Основн! результати дасертац!йяо! роботи опублХковано в 6 науковжс працях, з них статей у зб!рниках наукошх прадь - 2, депонованих рукопис!в - 1, тез допов1дей - 3.

Особистй внес он. Bel результати дисертац1йно1 роботи одержано за особистов участю автора. У працях, нашеаних у сп1вавторств1, дисертанту належать: [1]- побудова доведения наведених у робот! теорем; 121- доведения правил в!дтинання безгорегоктивних верх!вок дерева розв'язк1в задач! розмЩення, алгоритми й результати чиевльннх експеримент!в; [3] - доведения теорем про яижн! меж! ц1льово! функцИ оптим1зац1йно1 задач! розмЩення прямокутншс1в у достатньо довг1й смуз!; [61 - побудова математично! модел1 задач1 розм1щення прямокутвик1в у достатньо довПй смуз1 з урахуванням похибок початковах даних.

Струшура й обсяг дисерюцИ. Робота склздаеться з вступу, чотирьох розд!л!в га висновк1в - 9! стор!нка маданошеного тексту, однШ таблвд1, 10 рисунк!в, б1бл!ограф!1 з 137 найменувань - всього 106 стор!нок.

аист РОБОТИ

7 nepmjy розЗШ зд!Зснено постанозку оптам!зац!йно1

. -10-

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

Наведемо.основн! положения першого розд!ла докладные.

Розглядаеться оптим1зац!йна задача розм1щення в так1й постановд1-

Шхай С^}, 1« ..,т>- ск1нчанна мновзна прямо-

кутник1в довжини в1дггав1дяо ■ 1 . сднаково! шрш ь, 0={(Х,У)|Х« СО,!)«*!1, 1г«о, увСО.ЩсЕ1}- достатньо довга сму-га, початков!,дан! про як! задая1 з дэякими'похибками ,

НйобПдо розм^тати задену мнохину прямокутаг-

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

Задамо в!дпов1дн!сть м1ас почаисовими данями 1 елементэ-розширеного простору центроввшх 1нтервал!з 1в(й):

(а1'га1) ~ <а1'"уа1>=<А1>' ~ <Ь.^Ь>=<В>, ^^

(Е,1>ь) ♦-» <Ь,^11>=<Ь>, <И,УД>=<К>.

Озжхчечня. Ыатвматячною модэллв прямокутника Тей2, давании а 1 ширина Ъ, як! задан1 з похибками va т в 1н~ тервадьному простор! !?№)=! (Н)х1(Н), називаеться множила

-lili, що мае вигляд

И=Ихх1Ту. (2)

де множили nzds(R), Иус1в(й) описуиться системами 1нтер-вальних нер!вносгей:

<X»<0,vx>

<X>^<x,-lval> у <Х>«х, |vai>.

'<Y>?<0,o>y> <Y>«b,V > <y>í<y,-ivbi> L<y>«y, (Vbl >,

(3)

тсбто П=Г <й>=(<Х>, <У> )«11 (Н)1 <Хх=ГТ2, <У>е1Ту}.

Аналог1чио визначдао математичну модель достатньо Д0ВГ01 СМУТИ ПсИ2 ЯК 1НТерВЭЛЬНУ МНОШШу ИЫП^хЮуС:!^ (Н).

Тод! ошгим1зац1йну задачу розмШення пр.тионутник1в З^сй2, в смуз! ПсЕ2 з урахуванням похябок почэткоеих

данях мсжна подати як задачу розмицення 1нтервальвих множин И,с12(Н), в 1ятервальн1й област1 1П=1|(Й).

Виходячи з комб!нэторно! природа поставлено! задач!, деякому розм!щенню множин в облает! И ставиться у

в1дпов!да!сть 1нтервальне пэреставлення

>,...,<Аа^>), ౫ ¿п, ' . (Б)

елемэнт!в мультимножики 1й=С<0>,...,<0>,<А}>,...,<АИ>>- з п=М элементов, г з яких р!зн! (К- максимальна к1льк1сть горизонтальяих смут Р3_, на як! розпод1лявться область О з урахуванням похибок почагкових даних, г=и-к+1). Мнокину вс!х 1нтервальних переставлень Ш виду {5) позначшо через

ЗдШснювться занурення многшни аР^СМ) в п-внм!рни2 ЮТервальний прост!р 1д(Н)=1в(й)*...*1е(Ю. лрн якому Интервальному переставлэнню Ш в!дпов1дае елекент <Х>=«Х1>,<Хг>,...,<Хп>Ы^(Й), що <Х1>=<Аа^>. и!п-

Тод! матемзютка модель наведено! задач! Суда мзтг взгляд:

визиачити

т1п шах ЬЛ<Х>), (6)

<Х>«ЕЕпг(1в) 151£к х

де ^«Х», 1«^,- 1нтервальна функцХя, що ошсуе довжину

смути Р^ з урахуванням похибок почагкових даних;

П^ДЮ)- образ мнокини ГР^М) при зануренн! в ^(й).

Враховуючи те, що на цей час не розроблено мегод!в, що

реал1зушь математичну модель. (6) в ШГврвальнсму простор!

ггропануеться один з можливих п!дход!в до моделювання

наведена! задач! через представления II 1нт'ервально1 матема-

тично1 «одел1 в арифметичному евкл!довому простор!.

В сйлу гомеоморф!зму В: 1В(Н) Н2 та теореми про пря-

мий добуток гомеоморф!зм!в зд1йснюзться в!дображення !нтер-

вальнит многая простору в ариЯыетйчшй евкл!д!в

прост!р й4 та в1добракення А11:'^(НЬН211 .

Наводяться в1доСрахення

цо в в1дношвнням екв1валэнтност! в 1нтервальномУ простор1 1„(Ю, тобто ' _ " " '

<Хг>*<Х2>, яйцо , та вХдобрахагвя __

що в вХдношвнням екв!валентност! в 1нтервальному простор1

■ 12(Н), тобто ■

8 р _ _ _ . _

<2;1>*<22>, яйцоч»(<Х1>)=*«Х2>), „,«т1>)» 1><Т2», да <г1>=.«Х1>,<Т1>). <£>>= «Х^,<Т2>)с!^(Н).

ЗдЩснвння цкх в!дображень надае моаигав!сть гвести задачу- (5) в !нтзрвальнсму простор! I®(В) до задач! в арвф-метитаому евкл!довому простар!' й11: яччинчцти

mln max 7 IX.(?) IWEE^dO) ISiifc Д J

дэ IEj^IQ) - образ мноиши IE^dQ) в арифметичному евкл!до~ вому npocTopl Rn, k=[(l»«W>)/4>«B>)b

IX=(H11,....IXlt.....IXkl.....1Хк1.)=(ф(<Х1>),..., ф«^).

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

Досл1дауеться математична модель !деал!зовано! задач! розмЩення прямокутник!в у достатньо довг!й смуз!: визначити

а

min . max У х^ (8)

хяЕ^ДС!) Д ^

дэ k=[W/b] (W-шзрина смута, b-пшрша црямокутника),

x^-eQ, 3«JB.- давший прямокутнш1в, як1 вмЩено в смуту

CKqrq2.....qn}=.£0,...,0,a1.....a^í,

'^.«DéR?- множила переставлень, да породауеться мульти-меохшою Q, п1сля заяурэння в арифмвтичний евкл!д!в арост!р.

Эсщвахекня. К1льк!СТь р!зних елемент!в мульгимноашн IQ i Q нэ зб!гавться.

Виходячи з того, що Ejjj.CQJirert П^ДО) 1 E^ÍQ)^ Sn, де n^CQ)- загальний переставний многогранник,

^ - а п Sn- (п-1)- сфера, яка е перетином п-сфери £ х|= J q| 1

1=1 1=1

n n . . г1лерйлодааи 2 J ^i* 1=1 1=1 розтлядаються дв! задач!:

визначити

та

визначити

mln Г(х) (9)

х^Ю)

Туг

mln Их). (10)

xes

t

i(x)= max I. (x), (И)

1Шк 1 t

liW-Xxy. (12)

. 3=1

Задач! (9) i (10) в релаксацШими до задач! (8). В дасертац1йн!й робот! на ochobI власхивостей переставного многогранника 11^,(0 )=conv E^tQ) та (п-1)-сфери Sn досл!дкуеться ц!льова функц!я f(x) як опукла недиферен-Щйовна функц!я. Доведено теореми про екстрекальн! власти-восг! функцП (11)-(12). .

Нехай довзшни ia.^}, leJffi прямокутник!в, що розм!щу-ються. е Д1л1 числа, d- Ix найб1лышй сп!льний д!льник. Не

вграчаючи загальносг1, вважаемо, що а^а^.-.^а^. * Е

Позначимо Z =( £ а.)/к, 1=1 1

J

I [Z*]+d ,

якщо Z*~ ц1ле число, у противному раз! .

ТЕОРЕМА 1. Якщо Г(х0)=С, то ^«¿Е^ДО) е точкою м1н!мума

функцП Их).

ТЕОРЕМА 2. Якщо i(x0)=aa в деяк!й точц1 х^Е^С!), то

с

х0- точка м!н1мума.

Побуду ем олукле продовження дискретно I ФункцП f(x) на опуклу множину X=Rn, EIU,(Q)cX. Будемо вважати, що саме Г(х) 1 б опуклою фуйкЩею, задано® на X. Нехай rlntX- вХдносна внутр!щн1сть множини X, множила 1ндекс!в R(x)=.ilel^j f(x)= ^ШУ.

-15-

3f(yj=C0OTC лг£(х)/1« R(x)}-субдиферэнЩал фувкцП Z е точц! у. Сс^}, ieJn.- наб1р !н-декс1в вектора субград!ента p(y)««i(y) такий, що

Pct^" Pag(y?--*-ä \17)' (14)

ТЕОРЕМА. 3. Для м!н!мума функцП i(z) на множин!

дареставлень 1 v yeS^Q) маз м1сце оц!нка

п

min Г(х) 5> max Е Рп (y)q,-• (15)

Xei^iQ) p(y)e у) t=lai

ТЕОРШ 4. Для. Tofo, щоб точка y^E^lQ) надавала м1н1-«ума функц!! f(x) на IL (Q)crint X. достатньо, эоб

(р(У).УН £ра <16)

1

У третъому розд1л1 .наведено метода розв'язання ком-Янаторно! аптим!зац!йно1 задач1 розмЛщення'прямокутник1в у [остатньо довг1й смуз!, а сама: модиф1кац11 методу в!ток та в« 1 комбШоЕаного методу оптам1зац11 опукло! функц!! на фер!. Описуегься схема йобудови дерева розв'язк!в постав-еноГ задач!,' обгруятовуються правила' в'1дтинання безперспек-ивних верх1вок дерева. Модиф!кац!я • комб!нованого . методу эдавться як ■ декомпозицГя метода проекцП субград1ента та аовного град!ента, до базувться на викорястанн! особш-)стей облает! допустит значень задач! та релаксацШ на (реставний многогранник. -

При розв'язанн1 задач! (9), (11),(12) методом в!ток та ■ж вакшша роль прид!ляеться знаходженяя початкового змИдення, тобто кореня дерева розв'язк!в задач!. Для цього стосовано дек!лька евр!стичних мэтод!в розмЬюння ямокутник1в у смуз1.

На кожному р1ш! дерева здЦсшзеться рвдукц!я задач1 на псу in-2)-грань x^gg^.iej^, переставного многограя-

а, а таяоа на ашшв зменлузться зям!ря1сть задач!. На

останньому р1вн1 дерева розв'язк1в одержуемо систему р1внянь, що визначае вершину ^(Q) за критер1ем вершини.

Наведемо один з набор1в правил в!дтинання безперстк-пгвшга верхХвон; Верх!вка в Оезперспективнои, якщо;

- хоча б одна смута Pi, i«Jk. в пустою;

- хоча б в одн1й смуз! Р^, W^, для довжин вм1щених в не1 прямокутник1в не виконувться умова

- оц!нка розм1щення т?£т]0, де tj0~ оц1нка початкового розм1щення;

- прямокутник вмЩено в смуту Pit довжина зайня-то! частини яко! на попередньому кроц! зб!галась з довжиною зайнято1 часкши смути Р^, 3*1, J<1.

- к прямокутник1в найменшо1 ненульово! довжини, що розмйцуемо останн1ми, вмЩен1 в смуту не методом посл!довно-пооданоким розм1дення.

За од1нку розм1щання мохна взята праву частину нэр1вно-ctL (15). Критер!£ зупинки алгоритму- повний пербб!р верх1-вок дерева або виконання достатн!х умов (теореми 1, 2 1 4).

При розв*язанн1 задач1 (10)-(11), (12) комб!нованим методом зд!йснветься 1терац!Яшй продес по вим1рност1 сфери.

За початнову точку задач! на (п-!)-сфер! Sn_i_1, 1=1,2,...,п-2, Сереться вершина переставного многогранника nn_iiI,^(Q), яку шукаемо модиф1кованим методом в1ток та меа,

ошсаним вище, з використанням обмежувача часу.

•Виэедено форму ли знаходження проекцИ точки xeR11-1 не (п-!)-сферу Sn-i-1. Запропоновано шлях здШсненкя редукц!) задач! на найближчу грань або найблизгай перер!з перастав-еого многогранника.

Четверти poadlA мЮтить алгоритма, що реад1зукп

тоди розв'язання задач! розм!щення прямокугник!в в статньо довг1й смуз!, наведен1 в дан!й робот1, в такса зультати експериментального досл1даення цта мегод1в 1 1х вл!з. Для випадк!в, коли ц!льова функц!я е ц1льчнс9льн0ю 1 зниця м1к верхньою та никньою оШнками незначна, засто-вуем дахотом!ю !нтврвала Са.рз, дв смпахСС.а^),

02=

max z р„ (y)g,-. ягацо цв число ц1ле, p(y)««i(7) i=i i 1

Г max г р_ (у)&1 + 1, у противному раз1.

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

ВИСНОВКИ : '

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

2) ЗдШшено подашя 1нтервально! математично! модел! тим!зац!йно1 задач1 розм!щення прямокутник!в в доотть дов-11 смуз1. у арифматачному евкл!довому простор1 к11.'

3) Досл!джено властивост! математично! модвл1 поставле-I задач! як комб!яаторно1 задач!, а саме: доведено теореми I задач! як комб!яаторно! задач!, а саме: довадено теореми э екстремальн1 властивост! ц1льово! функц11.

4) Розроблено ефективн! правила в!дпшання Сезпер-эктивних верх1вок дерева розв'язк!в задач1 та доведено эреми про екстремальн! властивост! опукло! функцП на ожин1 пвреставлень.

5) Модиф!ковано метод в!ток та меж! комб1нованиа метод эекцИ субград!ента та умовного град!5нта.

6) Розроблено алгоритма, що реал1зувть запропонован! цходи до ефективного розв'язання наведено! задач!, у

бигляд1 програшого комплексу "Метод"- "Сфера".

7) Виконан1 експериментальн1 досл1дження розроблених в робот! метод!в. Наведено результата розрахунк!в. 5д!йснэно ' Ix пор1вняння.

ПРАЦ1, 0ПУБЛШ0ВАН1 ЗА ТЕМОЮ ДОСЕРТАДИ

1. Емец O.A., Евсеева Л.Г. Метод решения комбинаторной задачи размещения прямоугольников с использованием оценки и достаточного условия минимума выпуклей недифференцируемой функции. - В кн.: Математическое моделирование и оптимизация технических систем и процессов, СО.науч.тр. - Киев: ИК HAH Украины, 1993. с. 37-40.

2. В>;&ц O.A., Евсеева Л.Г. Одна комбинаторная задача размещения прямоугольников : алгоритмы решения, численные эксперименты. - В кн.: Автоматизация архитектурно- строительного проектирования: Меавуз. сб. ваучн. тр. /Рост, госуд. архит. ин-т.- Ростов-н/Д, 1994- С.130-138.

3. бмець 0.0., бвееева Л.Г. Никн! ме»1 та достатн1 умови м!н1мука в задач! розм!щвння прямокутник1в у нап1внеск1нченну смуту. - В кн.: Тези допов1дей 46 наук, конф. црофвсор!в, викладач1в, наук. прац!вник!в, асп!рант!в га сгуденг!в 1н-ту. 4.1 / М1носв1ти УкраГнв. Полг. 1нж.-буд!в. 1н-т.- Полтава, 1994. - С.87.

4. бвееева Л.Г. Дихотом1я при розв'язуванн! одн!в1 ком01наторно! задач1. - В кн.: Тези допов!дей 46 наук, конф. црофесор!в, викладач!в, наук. црац!вник!в, асп!рант!в та студент!в 1н-ту. 4.1 / М1носв1ти Укра1ни. Полт. !нк.-буд!в. !н-т.- Полтава, 1994. - С.88.

5. евсевва Л.Г. Пошук наблихеного розв'язку одн1б1 комб!наторно1 задач!. - В кн.: Тези допов!дей 47 наук, конф. дрофесор!в. викладач!в, наук. прэц1вник!в, асп!рант!в та студенПв ун-ту. 4.1 / М!носв!ти УкраШг. Полг. техн.

-19-

ун-т.- Полтава, 1995. - С.72.

6. Евсеева Л.Г., Романова Т.Е. Математическая модель' задачи размещения прямоугольников в достаточно длинной полосе с учетом погрешностей исходных данных. / Полт. техн. ун-т. - Полтава, 1995.-13 е.- Депон. в ГКГБ Украины 4.09.95, * 2011-УК95.

SUMMARY

I.G. Yevseyeya. Combinatorial optimisation problem of rectangles placement and solution methods of It taking Into account Initial data errors.

TMs thesis 1s a manuscript being submitted for a Candidate of Sciences Degree (Physics and Mathematics) in the speciality 01.05.02 - mathematical modelling and numerical methods in scientific reseachea. Institute for Probleme in Machinery of the National Academy of Sciences of Ukraine, Kharkov, 1995.

The problem of rectangles placement In fairly lengthy strip taking Into account initial data Is considered. Mathematical model of the stated problem aa combinatorial optimisation problem Is constructed on the basis of using the geometric design theory and the interval mathematics elements. To solve the problem modifications of the branch-and-bound', • method and combined method for optimization of convex function on sphere are suggested. Proposed are algorithms of their realizations. Experimental Investigation of methods and their comparison are fulfilled. The results of numerical solution of teat problems are given.

АННОТАЦИЯ

-га-

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

Диссертация является рукописью, представлэкной на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02.- математическое моделирова-. ние и вычислительные мэтоды в научных исследоЕшиях. Ия-т проблем машиностроения HAK Украины, Харьков, 1ЭЭ5.

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

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

В1ддов1дальш1й за випуск к.т.н. Куценко о.С. Шдписано до друку

Сармат 60z90 i/16. Danlp друк. J& i. Ум.друк.арк. 1. Обл.-Бид.арк. 0,96. Тираж 100 пр. Зам. Л