Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Математична модель та метод розв'язання оптимізаційної задачі розміщення правильних многокутників з урахуванням похибок початкових даних

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Загальна характеристика роботи

Актуальність теми. Дисертаційна робота є неперервним продовженням досліджень задач геометричного проектування задач, пов'язаних з перетворюванням геометричної інформації. До даного класу відносяться, зокрема, задачі оптимального розміщення геометричних об'єктів, що виникають при розкрої матеріалів, проектуванні радіоелектронних плат, технічних систем, розробці планів промислових підприємств, розміщенні обладнання, вантажів, тощо.

Інтерес до задач розміщення визначається, з одного боку, дуже широким спектром практичних застосувань, а з іншого складністю та нетривіальністю побудови математичних моделей, необхідних для їх адекватного опису.

Множинність початкових даних, які включають інформацію про форму, розміри геометричних об'єктів, технологічні обмеження та функцію цілі, породжують велику кількість оптимізаційних задач розміщення. Але незважаючи на різноманітність цих задач, всі вони можуть бути сформульовані таким чином: необхідно розмістити дані геометричні об'єкти у даній області з урахуванням технологічних обмежень так, щоб функція цілі досягала екстремального значення.

До останнього часу розв'язання задач оптимального розміщення було зорієнтовано, в основному, на використання ідеалізованих математичних моделей матеріальних об'єктів та їх взаїмодій, коли похибки задання початкових даних не враховуються. А внаслідок того, що мова йде про оптимізаційні задачі, виникає проблема точності, стійкості та вірогідності отримуємих результатів.

Потреба у вирішенні зазначеної проблеми породила необхідність створення нового математичного апарату. Їм стало започатковане у 1992 році членом-кореспондентом НАН України Ю.Г. Стояном нове застосування інтервального аналізу в геометричному проектуванні інтервальна геометрія.

Дана дисертація присвячена прикладенню елементів цієї нової теорії до розв'язання оптимізаційної задачі розміщення правильних орієнтованих многокутників з урахуванням похибок початкових даних.

Робота виконана у відповідності з тематикою та загальним планом досліджень, що проводились на кафедрі прикладної математики Харківського державного технічного університету радіоелектроніки і у відділі математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М.Підгорного НАН України в період 19921998 рр.

Метою дисертаційної роботи є побудова математичної моделі оптимізаційної задачі розміщення правильних орієнтованих многокутників з урахуванням похибок початкових даних та розробка метода її розв'язання.

Основні задачі дослідження включають:

постановку оптимізаційної задачі розміщення правильних орієнтованих многокутників у напівнескінченній смузі (що надалі, для скорочення, називається смугою) з урахуванням похибок початкових даних;

побудову математичної моделі зазначеної задачі в інтервальному вигляді (надалі інтервальної математичної моделі) з використанням елементів інтервальної геометрії;

подання інтервальної математичної моделі в арифметичному евклідовому просторі;

розробку методу розв'язання поставленої задачі на базі методів, призначених для розв'язання задач геометричного проектування;

створення комплексу програм, що реалізують метод розв'язання.

Наукова новизна результатів дисертаційної роботи:

математична модель оптимізаційної задачі розміщення правильних многокутників у смузі, що побудована на основі понять інтервальної геометрії, надає можливість раціональним чином враховувати похибки початкових даних (не пов'язані з обчислювальними процесами);

запропоноване подання інтервальної математичної моделі в арифметичному евклідовому просторі дозволяє водночас враховувати похибки початкових даних і застосовувати добре відомі методи оптимізації та геометричного проектування;

досліджені властивості побудованої математичної моделі у вигляді доведених теорем надають можливість використати для розв'язання поставленої задачі методи многокритеріальної оптимізації та метод гілок і меж;

розроблені ефективні правила відсікання безперспективних вершин дерева розв'язків задачі та доведені теореми про екстремальні властивості лінійной функції цілі на області припустимих розв'язків дозволяє модифікувати метод гілок і меж.

Практичне значення отриманих результатів полягає в розробці та реалізації на ПЕОМ комплексу програм для розв'язання оптимізаційної задачі розміщення правильних орієнтованих многокутників з урахуванням похибок початкових даних. Створений програмний комплекс «Regular interval polygons» (RIP) може бути безпосередньо заcтосований при проектуванні будівельних об'єктів, транспортних засобів, радіоелектронних плат, при розв'язанні проблеми раціонального розміщення обладнання у цехах та економічному плануванні. Комплекс RIP може також використовуватися при розробці схем нарізки металу у машинобудуванні, при розкрої тканин та шкір відповідно у текстільній та взуттєвій промисловостях, що дозволяє враховувати похибки початкових даних, підвищувати ефективність використання різних матеріалів, а також скорочувати час вирішення зазначенних задач.

Апробація результатів дисертації. Основні результати досліджень доповідались:

на семінарі наукової ради НАН України з проблеми «Кібернетика» «Математичні методи геометричного проектування» (м. Харків, 1994 р.);

на семінарах відділу математичного моделювання та оптимального проектування Інституту проблем машинобудування НАН України (м. Харків, 1996, 1998 рр.);

на семінарі «Математичні моделі та методи оптимізації систем з дискретними джерелами фізичних полів» кафедри програмного забезпечення обчислювальної техніки Житомирського інженерно-технологічного інституту (м. Житомир, 1998 р.);

на семінарі кафедри прикладної математики Харківського державного технічного університету радіоелектроніки (м. Харків, 1998 р.);

на семінарі наукової ради НАН України з проблеми «Кібернетика» «Системний аналіз, математичне моделювання і прийняття рішень у соціально-економічних та технічних системах» (м. Харків, 1998 р.).

Публікації. Основні результати дисертації викладено у 4 статтях.

Особистий внесок дисертанта в роботи, опубліковані у співавторстві є таким. В статті [1] автор здійснив побудову математичної моделі задачі розміщення правильних орієнтованих многокутників з урахуванням похибок початкових даних в інтервальному вигляді. В публікації [3] дисертантом запропонований та обгрунтований метод розв'язання зазначеної задачі як двокритеріальної задачі мінімізації, наведені результати експериментів.

Структура та обсяг дисертації. Дисертація складається зі вступу, п'яти розділів, висновків та списку використаних джерел. Повний обсяг дисертації становить 117 сторінок, серед них 101 сторінка тексту, 23 рисунки, 4 таблиці та 206 найменувань літератури.

Основний зміст роботи

інтервальний математичний модель евклідовий

У першому розділі зроблено огляд літератури, присвяченої задачам геометричного проектування, зокрема, робіт, спрямованих на розв'язання двовимірних оптимізаційних задач розміщення. Дослідженням цього класу задач займалися і займаються багато вчених, у тому числі Рвачов В.Л., Стоян Ю.Г., Гіль М.І., Комяк В.М., Яковлев С.В., Смеляков С.В., Новожилова М.В., Sweeney P.E., Dyckhoff H., Dowsland K.A., Beasley J.E., Li Zh., Milenkovic V. та ін. Тут також наведено перелік основих публікацій з інтервального аналізу, що містить роботи, присвячені побудові інтервальних арифметик (Moore R.E., Kaucher E., Markov S.M., Sendov B., Нестеров В.М., Зюзін В.С. та ін.), дослідженню інтервальних матриць (Kulisch U., Hansen E., Alefeld G., Herzberger J. та ін.), методам розв'язання систем лінійних та нелінійних інтервальних рівнянь (Rohn J., Hansen E., Rump S.M., Neumaier A., Krawczyk R., Moore R.E., Калмиков С.А., Шарий С.П., Лакеєв А.В. та ін.), обчисленню інтервальних інтегралів та похідних (Ratschek H., Schroder G., Nickel K., Moore R.E. та ін.) і т.ін. Надано коротку анотацію публікацій Стояна Ю.Г. з викладенням основ нового застосування інтервального аналізу в геометричному проектуванні інтервальної геометрії, а також вказані роботи Романової Т.Є. та Євсеєвої Л.Г. з прикладення елементів цієї теорії до розв'язання оптимізаційних задач розміщення з урахуванням похибок початкових даних. Крім того, обгрунтований вибір напрямку досліджень.

У другому розділі здійснено постановку задачі розміщення правильних орієнтованих многокутників у смузі з урахуванням похибок початкових даних; наведені означення та аналітичний опис інтервальної смуги й правильного інтервального многокутника.

Викладемо основні положення другого розділу докладніше.

Розглядається оптимізаційна задача розміщення в такій постановці.

Нехай маємо смугу ширини w. Похибки задання по осях ОХ і OY її власної системи координат дорівнюють та відповідно. Нехай заданий набір орієнтованих правильних m-кутників , i={1,…, n}. Радіуси кіл, описаних навколо , дорівнюють , i. Похибки задання складають , i. Необхідно, прийнявши до уваги похибки початкових даних, розмістити набір m-кутників у смузі таким чином, щоб довжина l зайнятої частини смуги з урахуванням її похибки була мінімальною.

За математичні моделі геометричних об'єктів, що мають змінні метричні характеристики, які породжуються похибками початкових даних, обираються інтервальні множини, котрі розглядаються як точкові множини інтервальних просторів.

Задамо бієкцію між початковими даними поставленої задачі та елементами розширеного простору центрованих інтервалів = { x=(c+d)/2,

=(dc)/2, c, d } таким чином:

, i; (0, ) , (0, ) , (w, ) .

На основі поняття опуклого інтервального m-кутника введено наступне означення.

Означення 1. Опуклий інтервальний m-кутник називається правильним інтервальним m-кутником, якщо на підпросторах та системи інтервальних нерівностей

 і

, i; , ;

, ; ,

відповідно визначають правильні m-кутники.

Використовуючи означення інтервального прямокутника, правильного інтервального m-кутника та враховуючи початкові дані поставленої задачі, інтервальну смугу можна описати як

= int fr , (1)

а правильний інтервальний многокутник як

= int fr , (2)

, , , p;

, ,

int () внутрішність множини (), fr () інтервальна межа множини ().

Таким чином, задачу розміщення правильних многокутників , i у смузі з урахуванням похибок початкових даних можна представити як задачу розміщення правильних інтервальних многокутників , i в інтервальній смузі , де = .

У третьому розділі побудовано інтервальну математичну модель оптимізаційної задачі розміщення правильних орієнтованих многокутників у смузі з урахуванням похибок початкових даних; здійснено подання інтервальної математичної моделі задачі в арифметичному евклідовому просторі, яке дозволяє, з одного боку, врахувати похибки початкових даних, а з іншого використати для розв'язання апробовані методи оптимізації.

Використовуючи поняття інтервального дотикання опуклих інтервальних многокутників, умови розміщення правильного інтервального многокутника (2) в інтервальній смузі (1) подаємо у вигляді структури лінійних інтервальних нерівностей

, (3)

де набір інтервальних нерівностей:

а умови взаємного неперетину правильних інтервальних многокутників та описуємо структурою лінійних інтервальних нерівностей

, (4)

де = набір інтервальних нерівностей вигляду:

, p

у випадку, коли m парне, та набір інтервальних нерівностей вигляду:

, r,

, q

у випадку, коли m непарне;

, ,

, , , ,

, ,

, ,

, ,

, ,

, , , k =

З урахуванням (3), (4) математична модель поставленої задачі має вигляд:

inf , (5)

()D

D: [] [], (6)

,

.

З метою використання надалі існуючих методів розв'язання оптимізаційних задач розміщення переходимо від інтервальних просторів , g до ізометричних їм евклідових просторів .

Структура інтервальних нерівностей (3) у просторі зводиться до набору:

а структура інтервальних нерівностей (4) до набору в :

(8)

у випадку, коли m парне, і до набору в :

у випадку, коли m непарне,

, , , , .

Позначимо множину, що описується набором (7), через , а множини, які описуються наборами (8), (9), через та відповідно. З урахуванням введених позначень образ ID у просторі інтервальної множини D (6) буде таким:

ID: [] []. (10)

Відмітимо деякі особливості множини ID: ID int ID, ID cl ID (cl () замикання множини ()), ID в загальному випадку незв'язне, необмежене та неопукле, fr ID (fr () межа множини ()) кусково-лінійна.

Під час переходу від інтервальних просторів до евклідових за функцію цілі обирається вектор-функція . Тоді, в результаті зазначеного переходу, математична модель (5) набуває вигляду:

inf , (11)

ID

де .

В частинному випадку, коли =0, =0; =0, i, математична модель (11) співпадає з математичною моделлю ідеалізованої оптимізаційної задачі розміщення правильних многокутників у смузі.

У четвертому розділі досліджені властивості математичної моделі оптимізаційної задачі розміщення правильних орієнтованих многокутників у смузі з урахуванням похибок початкових даних у вигляді доведених теорем, котрі надають можливість використовувати для її розв'язання методи многокритеріальної оптимізації та метод гілок і меж.

Для розв'язання двокритеріальної задачі (11) розглядається допоміжна задача:

inf l. (12)

ID

Задача (12) розв'язується методом гілок і меж, модифікованим для оптимізаційних задач геометричного проектування.

Перед побудовою дерева розв'язків введені наступні означення.

Означення 2. Множина називається псевдомногогранною множиною вимірності s, якщо вона задається довільною структурою * лінійних нерівностей (серед яких можуть бути як строгі, так і нестрогі нерівності).

Позначимо через T* набір рівнянь, котрі відповідають всім нерівностям структури *.

Означення 3. Точка x Cr (Cr () край множини ()) називається псевдовершиною , якщо її координати є розв'язком системи не менш як s рівнянь набора T*, серед яких s лінійно незалежних.

Теорема 1. Якщо лінійна функція цілі f досягає свого глобального мінімуму в деякій точці , то псевдовершина множини .

Теорема 2. Функція цілі l задачі (12) досягає свого глобального мінімуму в псевдовершині множини ID.

З урахуванням теореми 2 в (12) inf можна замінити на min:

min l. (13)

ID

Нехай Т=(), j=1,2,…, (4k+8n) набір рівнянь, які відповідають нерівностям, що беруть участь в описі ID (10). Для розв'язання задачі (13) використовується стратегія побудови систем рівнянь із набору Т, котрі описують всі псевдовершини області ID.

Структура дерева розв'язків має деяку специфіку, зумовлену особливостями рівнянь, що входять до набору Т. А саме, як видно з (7) (9), рівняння, котрі містять змінні

i; l, та рівняння, які включають змінні i; , жорстко зв'язані між собою, утворюючи системи. Враховуючи це, алгоритм побудови дерева розв'язків описується таким чином.

Кореню дерева розв'язків ставиться у відповідність простір . Кожній вершині i-го рівня, i відповідає лінійний многовид вимірності 4n+22i, здобутий як переріз лінійного многовиду з двома гіперплощинами, рівняння яких містять змінні та з ненульовими коефіцієнтами відповідно, якщо і непарне, і змінні та з ненульовими коефіцієнтами відповідно, якщо і парне.

На останньому (2n+1) - ому рівні дерева кожна його вершина відповідає точці простору . Ця точка здобувається як переріз деякого лінійного многовиду з двома гіперплощинами, рівняння яких містять змінні l та з ненульовими коефіцієнтами відповідно.

Кількість систем рівнянь, побудованих на (2n+1) - ому рівні дерева розв'язків, дорівнює величині

k* =

Для скорочення кількості систем рівнянь, які необхідно розв'язувати на останньому рівні (а також на більш високих рівнях), запропонований набір правил відсікання безперспективних вершин дерева розв'язків.

Повертаючись до задачі (11), вводимо такі позначення:

= min l; (14)

ID

= min ;

ID

= min l,

ID*

ID* = {ID }.

Розглядається задача:

min ; (15)

ID'

ID' = {ID l l'},

де l'[].

Точка множини ID тоді й тільки тоді є розв'язком двокритеріальної задачі (11), коли вона є єдиним з точністю до еквівалентності розв'язком задачі (15) при l'[]. А для того, щоб кожний розв'язок задачі (15) при l'[] був єдиним з точністю до еквівалентності (а значить, і ефективним), достатньо виконання такої умови: множина

W* = {gw g}, (16)

W ={ww = , ID},

w g , i =1,2,

повинна бути опуклою.

Перш ніж довести опуклість W*, будуємо cl ID та його проекцію на площину . Множина cl ID описується структурою лінійних нерівностей

, (17)

де

, ;

F=; (18)

симетрична матриця вимірності v v, причому

= 0, , , =+1,…, k,

а всі інші елементи матриці дорівнюють 1.

Коефіцієнти, що входять до перших 4n нерівностей набору (18), обчислюються за формулами:

= 1, = 1, ; = 1,

= 2, = , = ,

=, =, .

Далі, якщо індекси , , пов'язані співвідношенням:

( 1) (n 0,5) < k( 1) + (n 0,5 0,5), , , ,

= k( 1) + , = n( 1) + 0,5( + 1).

Нарешті,

= , , .

Всі інші коефіцієнти , i, s в (18), крім описаних вище, дорівнюють 0.

Нехай проекція cl ID, заданого структурою (17), на площину . Для побудови використовується модифікація методу виключення невідомих. Завдяки специфіці нерівностей набору (18), множина буде або співпадати з площиною , або описуватися структурою лінійних нерівностей

,

де

, .

Теорема 3. Множина є або площиною , або напівплощиною в ній.

Лема. Нехай А деяка множина, A ; ортогональна проекція А на підпростір (t < s); ортогональна проекція cl А на . Тоді int ()=.

Теорема 4. Множина W* (16) опукла.

З теореми 4 витікає, що розв'язок задачі (15) при будь-якому l'[] є єдиним з точністю до еквівалентності. Обираємо за l' значення . Тоді область припустимих розв'язків задачі (15) набуває вигляду:

ID' = {ID l }.

Але в силу (14) l не може бути менше за . Тому

ID' = {ID l = }.

Таким чином, розв'язання задачі

min (l, )

ID

зводиться до розв'язання задачі

min

ID

при l = , де визначається згідно з (14).

В п'ятому розділі наведені результати тестових прикладів роботи програмного комплексу «Regular interval polygons», який реалізує пошук оптимального розв'язку поставленої задачі модифікованим методом гілок і меж, а також пошук її наближеного розв'язку методом послідовно-поодинокого розміщення з наступним перебором. З метою проведення порівняльного аналізу здобутих результатів для тих самих тестових прикладів знайдені оптимальні розв'язки ідеалізованої оптимізаційної задачі розміщення правильних многокутників, точні нижні та верхні оцінки оптимального розв'язку поставленої задачі.

Основні висновки по роботі

1. Побудована інтервальна математична модель оптимізаційної задачі розміщення правильних орієнтованих многокутників у смузі з урахуванням похибок початкових даних.

2. Здійснене подання інтервальної математичної моделі задачі в арифметичному евклідовому просторі.

3. Досліджені властивості отриманої математичної моделі у вигляді доведених теорем, котрі надають можливість використовувати для її розв'язання методи многокритеріальної оптимізації та метод гілок і меж.

4. Запропонована модифікація методу гілок і меж для розв'язання згаданої задачі зі скалярною функцією цілі, побудовано дерево розв'язків та сформований набір правил відсікання безперспективних вершин цього дерева.

5. Розроблений програмний комплекс «Regular interval polygons», який реалізує: пошук оптимального розв'язку поставленої задачі модифікованим методом гілок і меж; пошук її наближеного розв'язку методом послідовно-поодинокого розміщення з наступним перебором.

Порівняльний аналіз отриманих результатів надає можливість зробити висновок, що побудована в дисертаційній роботі на основі понять інтервальної геометрії математична модель оптимізаційної задачі розміщення правильних многокутників у смузі дозволяє раціонально врахувати похибки початкових даних.

Опубліковані праці за темою дисертації

1. Стоян Ю.Г., Романова Т.Е., Сысоева Ю.А. Математическая модель оптимизационной задачи размещения правильных многоугольников с учетом погрешностей исходных данных // Доп. НАН України. - 1998. №5. С. 104-111.

2. Сысоева Ю.А. Математическая модель и метод решения оптимизационной задачи размещения правильных многоугольников с учетом погрешностей исходных данных // Радиоэлектроника и информатика. - 1998. №2. С. 43-50.

3. Стоян Ю.Г., Романова Т.Е., Сысоева Ю.А. Оптимизационная задача размещения правиль-ных интервальных многоугольников // Доп. НАН України. 1998. №9. С. 114-120.

4. Математическая модель и метод решения задачи размещения правильных ориентированных многоугольников в полосе / Сысоева Ю.А.; Ин-т пробл. машиностр. НАН Украины. Харьков, 1996. 20 с. Рус. Деп. в ВИНИТИ 22.01.96, №242В96 // Анот. в ж. Математика, №5, 1996.

Размещено на Allbest.ru