Математична модель та чисельні методи розв’язання задачі оптимізації розміщення прямокутників

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

Національна академія наук України

Інститут проблем машинобудування ім. А.М. Підгорного

УДК 519.6:514.1

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

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

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

кандидата фізико-математичних наук

Рудюк Лідія Василівна

Харків - 2006

Дисертацією є рукопис.

Робота виконана в Житомирському державному технологічному університеті МОН України

Науковий керівник:кандидат фізико-математичних наук, доцент Яремчук Світлана Іванівна, Житомирський державний технологічний університет, доцент кафедри програмного забезпечення обчислювальної техніки

Офіційні опоненти:заслужений діяч науки і техніки України, доктор фізико-математичних наук, професор, Яковлев Сергій Всеволодович, Харківський національний університет внутрішніх справ, професор кафедри прикладной математики;

кандидат фізико-математичних наук, доцент Гребеннік Ігор Валерійович, Харківський національний університет радіоелектроніки, докторант.

Провідна установа:Київський національний університет імені Тараса Шевченка, факультет кібернетики, кафедра обчислювальної математики, МОН України, м. Київ

Захист відбудеться “22” червня 2006р. о 16.00 годині на засіданні спеціалізованої вченої ради Д 64.180.01 в Інституті проблем машинобудування ім. А.М. Підгорного НАН України за адресою: 61046, Харків, вул. Дм. Пожарського 2/10.

З дисертацією можна ознайомитися у бібліотеці Інституту проблем машинобудування ім. А.М. Підгорного НАН України за адресою: 61046, Харків, вул. Дм. Пожарського 2/10.

Автореферат розісланий “16” травня 2006р.

Учений секретар спеціалізованої вченої ради,

доктор технічних наукО.О. Стрельнікова

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

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

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

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

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

Дисертаційна робота продовжує дослідження, що проводяться в Інституті проблем машинобудування ім. А.М. Підгорного НАН України під керівництвом чл.-кор. НАН України Ю. Г. Стояна, і присвячена питанням оптимального розміщення геометричних об'єктів прямокутної форми.

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконана на кафедрі програмного забезпечення обчислювальної техніки Житомирського державного технологічного університету в період з 2001 по 2006 роки у відповідності з тематикою та загальним планом досліджень кафедри.

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

Основними задачами дослідження є:

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

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

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

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

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

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

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

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

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

- вперше розроблено модифікацію методу проекції градієнту, яку було названо метод G-проекції, що враховує специфіку множини припустимих розв'язків поставленої задачі оптимізації; доведено теорему про теоретичну оцінку та надано статистичну оцінку часової складності методу G-проекції;

- вперше доведено теорему про збіжність побудованого методу G_проекції до стаціонарної точки;

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

Практичне значення. Обчислювальні методи, що були розроблені в процесі досліджень, реалізовані програмно. Створений програмний комплекс “Optimal rectangles placement” може бути застосований для розв'язання широкого кола прикладних задач, які зводяться до оптимізації розміщення прямокутників.

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

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

- IV Міжнародному молодіжному форумі “Радіоелектроніка і молодь у XXI столітті” (11-13.04.2000, м. Харків).

- Четвертій міжнародній науково-практичній конференції “Системний аналіз та інформаційні технології” (1-3.07.2002, м. Київ).

- ECI'2002 - Fifth International Scientific Conference on Electronic Computers and Informatics (October 10-11th 2002, Koљice-Herѕany, Slovakia).

- 6-ій міжнародній науково-практичній конференції “Современные информационные и электронные технологии” (23-27.05.2005, м. Одеса).

- Науково-практичній конференції “Научные исследования и их практическое применение. Современное состояние и пути развития” (1-15.10.2005, м. Одеса).

- Наукових семінарах відділу математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України (м. Харків, 2002р., 2003р., 2005р.).

- Науковому семінарі кафедри програмного забезпечення обчислювальної техніки факультету кібернетики Київського національного університету імені Тараса Шевченка (м. Київ, 2006р.).

Публікації. Основні результати роботи опубліковано у 5 статтях (3 з них у виданнях, що затверджені ВАК України) та у 5 матеріалах конференцій.

Особистий внесок здобувача. Усі основні результати дисертаційної роботи отримані особисто автором. В роботах, написаних у співавторстві, дисертантові належать такі результати. В роботах [1], [6] - обґрунтування можливості використання методу Розена для розв'язання задачі оптимізації розміщення прямокутних геометричних об'єктів в прямокутнику. В роботах [2], [7] - реалізація методу Розена для розв'язання задачі оптимізації розміщення прямокутних геометричних об'єктів в прямокутнику, реалізація методів повного та спрямованого переборів для розв'язання задачі оптимізації та порівняння часових і точносних характеристик цих методів. В роботі [3] - побудова методу G-проекції для розв'язання задачі оптимального розміщення прямокутників, формулювання та доведення теорем про часові складності класичного методу проекції градієнту Розена та побудованого методу G-проекції. В роботі [4] - реалізація методу G-проекції для розв'язання задачі оптимального розміщення прямокутників, формулювання та доведення теореми про збіжність методу G_проекції. В роботі [5] - розробка принципу декомпозиції множини припустимих розв'язків задачі оптимального розміщення прямокутників, доведення можливості заміни розв'язання вихідної задачі оптимізації розв'язанням ряду побудованих підзадач. В роботі [9] - адаптація алгоритму методу G-проекції для розв'язання практичних задач, що зводяться до задач оптимального розміщення прямокутників. В роботі [10] - створення алгоритму використання методу G-проекції для розв'язання задач будівельної механіки.

Структура та обсяг дисертації. Дисертація складається із вступу, п'яти розділів, висновків, списку використаних джерел із 102 найменуваннями (11 с.) та трьох додатків (11 с.). Загальний обсяг роботи складає 131 сторінку, включаючи 23 рисунки та 19 таблиць.

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

У вступі обґрунтовано актуальність теми дослідження, визначено об'єкт та предмет дослідження, сформульовані мета і основні задачі роботи, визначені наукове і практичне значення отриманих результатів.

Перший розділ присвячено обґрунтуванню необхідності подальшого дослідження задач геометричного проектування, зокрема задач розміщення прямокутних геометричних об'єктів. Розглянуто літературу, яку присвячено задачам розміщення прямокутників. Вивченню цього класу задач присвячені праці багатьох вчених, серед яких можна виділити роботи В.Л.Рвачова, Ю.Г.Стояна, М.І.Гіля, С.В.Яковлева, В.М.Комяк, М.В.Новожилової, Т.Є.Романової, О.О.Ємця, І.В.Сергієнка, Л.С.Магаса, І.В. Гребенніка та ін.

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

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

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

В другому розділі наведено математичну модель задачі оптимізації розміщення прямокутників та описані методи її розв'язання.

Постановка задачі

Нехай задані m взаємоорієнтованих геометричних об'єктів прямокутної форми (D_j R², j = 1,…, m) та область розміщення цих об'єктів Щ, яка теж має форму прямокутника, розміри якого визначаються вектором a(a₁,a₂).

Основними характеристиками прямокутного об'єкту є його розміри та положення у просторі, яке визначається координатами його полюсу z^j(о^j₁, о^j₂), j = 1, 2,…, m. Полюсом прямокутника будемо називати точку перетину його діагоналей. Очевидно, розміщення m прямокутних об'єктів буде визначатись вектором z = (z¹, z², ..., z^m).

Необхідно знайти таке розміщення прямокутників в області, при якому досягає екстремуму обраний критерій якості

f(z) extr, zG,(1)

де f(z) - неперервно диференційована функція,

G - множина припустимих розв'язків поставленої задачі оптимізації.

Розглянемо властивості множини G. На розміщення об'єктів прямокутної форми накладаються геометричні обмеження, які являють собою:

- умови взаємного неперетинання прямокутників - для кожної пари D_s, D_p прямокутників існує хоча б одне і {1,2} таке, що

(2)

- умови належності прямокутників області розміщення Щ - для кожного прямокутника D_j виконується

(3)

Наведені обмеження описують множину G, яка є багатовимірною та має складну структуру.

Тобто отримано задачу оптимізації функції цілі (1) на множині складної структури G.

Застосування класичних методів умовної оптимізації до розв'язання задачі (1) є досить проблематичним через неопуклість множини припустимих розв'язків поставленої задачі.

Декомпозиція множини припустимих розв'язків

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

Нерівність, яка описує умову взаємного неперетинання прямокутників, можна представити у такому вигляді

(4)

Для кожної пари прямокутників обирається одна з двох координат, за якою буде задана умова неперетинання. Для обраної координати визначається одна з двох умов неперетинання (4). Потім до побудованих умов додаються нерівності (3), що визначають умови належності прямокутників області .

(5)

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

Кількість опуклих підмножин, що описуються системами (5), дорівнює

,

де n =2 - вимірність простору, m - кількість прямокутників.

Можна показати, що об'єднанням цих підмножин є множина G

Кожен із багатогранників G_k описується системою лінійних нерівностей, кількість яких залежить від кількості прямокутників (m) та вимірності простору (n = 2) і становить

Запропоновано розв'язання задачі оптимізації розміщення прямокутників в прямокутній області, що є задачею оптимізації неперервно диференційованої функції цілі f(z) на складній множині припустимих розв'язків G, замінити розв'язанням r підзадач оптимізації тієї ж функції цілі на кожній з підмножин G_r (r = 1, 2,…, M), які являють собою опуклі багатогранники, тобто замінити розв'язанням r підзадач

(6)

До розв'язання кожної з побудованих підзадач (6) можна застосувати різні класичні методи умовної оптимізації.

В третьому розділі описані методи розв'язання задачі оптимізації розміщення прямокутників.

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

Метод Розена для розв'язання побудованих підзадач

Було проведено порівняльний аналіз таких методів як метод умовного градієнту, метод можливих напрямків та метод проекції градієнту Розена. Перші два методи для знаходження вектора спуску потребують побудови та розв'язання задачі лінійного програмування на кожній ітерації. Для розв'язання кожної з підзадач оптимізації (6) було обрано метод проекції градієнту Розена завдяки порівняно невеликому об'єму обчислень на ітерації.

Послідовність наближень до розв'язку задачі за допомогою методу Розена будується за правилом

z^k+1 = z^k + _kd^k, k = 0, 1, … , d^k = P(-f(z^k)),

де Р = Е - А₁^т(А₁А₁^т)^-1А₁ - матриця проектування на множину припустимих розв'язків, А₁ - матриця обмежень, активних в поточному наближенні,d^k - вектор спуску.

Метод G-проекції для розв'язання побудованих підзадач

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

Розглянемо матрицю активних обмежень.

Рядки цієї матриці, які відповідають обмеженням (3), що описують умови належності прямокутників області розміщення, містять 2m-1 нульових елементів та один одиничний елемент з відповідним знаком. Номер стовпчика, який містить одиничний елемент, визначає координату відповідного прямокутника.

Рядки матриці активних обмежень, які відповідають обмеженням (2), що описують умови неперетинання прямокутників, містять 2m-2 нульових елементів та два одиничних елементи з протилежними знаками. Номери стовпчиків, які містять одиничні елементи, визначають координати відповідних прямокутників.

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

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

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

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

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

Алгоритм методу G-проекції.

1. Оберемо початкове наближення - точку z⁰ G_r. Представимо матриці А і b у вигляді (А₁, А₂) і (b₁, b₂), відповідно, де А₁ z⁰ = b₁, A₂ z⁰ < b₂.

2. Визначимо вектор спуску d^k - проекцію напрямку антиградієнта в поточному наближенні, точці z^k, k = 0,1,…., на множину припустимих розв'язків G_r обраної підзадачі.

(7)

де(8)

Z_k - множина, утворена перетином напівпросторів, що обмежені гіперплощинами, які описуються активними в поточному наближенні обмеженнями.

Координати вектора спуску d^k знайдемо таким чином.

2.1. Якщо А₁ порожня (не містить жодного стовпця), то покладемо
d^k = -f(z^k) і перейдемо до п.4.

Інакше (якщо А₁ для поточного наближення не порожня) перейдемо до п.2.2.

2.2. Напочатку покладемо d^k = -f(z^k). Для кожної координати антиградієнта функції цілі (i = 1,…,2m) перевіримо відповідний стовпчик матриці А₁.

Якщо s-тий (s {1,…,2m}) стовпчик матриці А₁ містить хоча б один одиничний елемент, знак якого збігається із знаком s-тої координати антиградієнта функції цілі, то s-та координата вектора z вважається “стримуваною” (тобто її зміну необхідно заборонити). В векторі спуску s-та координата прирівнюється нулю.

Інакше s-та координата вектора спуску співпадає з відповідною координатою антиградієнту.

3. Якщо d^k 0, то перейдемо до п.4.

Якщо d^k = 0, то зупинимось. z^k - стаціонарна точка.

4. Наступне наближення до розв'язку задачі знаходиться за правилом:

(9)

де знаходиться з умови

.

Збіжність методу G-проекції

Сформульовано та доведено наступні леми.

Лема 1. Нехай точка є проекцією точки у на опуклу замкнену множину Z_k, . Тоді для будь-якої точки виконується наступна умова:

.

Лема 2. Для будь-якої точки , де G_r - опукла замкнена підмножина припустимих розв'язків задачі (6), при використанні методу (7), (8), (9) буде виконуватися умова

З використанням наведених лем доведено теорему про збіжність методу G_проекції до стаціонарної точки.

Теорема 1. Нехай G_r - опукла, замкнена й обмежена множина з R^2m, функція - неперервно диференційована та обмежена знизу на G_r, градієнт цієї функції задовольняє умові Липшиця на G_r з константою . Тоді для послідовності , отриманої методом (7), (8), (9), при будь-якому початковому наближенні гранична точка послідовності буде стаціонарною, тобто

.

Порівняння методів Розена і G-проекції

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

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

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

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

Крім того, на відміну від методу Розена, в методі G-проекції при визначенні вектору спуску не будується матриця проектування Р. Це дозволяє на кожній ітерації отримати наступне наближення до розв'язку підзадачі методом G-проекції за менший проміжок часу, ніж методом Розена.

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

Теоретична оцінка часової складності методів

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

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

Було сформульовано та доведено теореми про часові складності знаходження наступного наближення методом G-проекції та методом Розена.

Теорема 2. Часова складність знаходження наступного наближення до розв'язку обраної підзадачі оптимізації розміщення прямокутників методом G_проекції оцінюється величиною О(m³), де m - кількість прямокутників, що розміщується.

Теорема 3. Часова складність знаходження наступного наближення до розв'язку обраної підзадачі оптимізації розміщення прямокутників методом Розена оцінюється величиною О(m⁵), де m - кількість прямокутників, що розміщується.

Методи розв'язання вихідної задачі оптимізації

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

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

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

Алгоритм методу спрямованого перебор

1. Задається початкова точка z⁰G₁; s присвоюється значення 1.

2. Методом Розена або методом G-проекції знаходиться розв'язок підзадачі

f(z) extr, zG_s

та отримується відповідна точка z^s* на підмножині G_s.

3. Знаходиться номер підмножини припустимих розв'язків G_t, якій належить знайдений розв'язок z^s* і для якої виконується умова st.

4. Якщо розв'язок z^s* належить тільки підмножині G_s, то процес розв'язання припиняється, і знайдене наближення z^s* приймається за розв'язок задачі.

В іншому випадку z^s* вважається початковою точкою, s присвоюється значення t і здійснюється перехід до пункту 2 алгоритму.

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

Критерії якості

Розглянемо функції цілі, що використані як критерії оптимізації.

1. Сума квадратів відстаней від заданої точки області до полюсів прямокутних об'єктів

де - задана точка прямокутної області розміщення;

- і-та координата полюсу j-того прямокутника, j = 1,…,m; i = 1,2.

2. Сума квадратів відстаней між полюсами прямокутників (довжина єднальної мережі)

де - і-та координата полюсу j-того прямокутника, j = 1,…,m; i = 1,2.

3. Сума квадратів відстаней від початку координат до полюсів прямокутних об'єктів

де - і-та координата полюсу j-того прямокутника, j = 1,…,m; i = 1,2.

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

Нехай в просторі R² є обмежена замкнена прямокутна область , розміри якої описуються вектором а(а₁, а₂). Область розміщення містить навантаження D_j, (j = 1,…, m), які діють у прямокутних областях. Основними характеристиками навантажень є їх величини P_j та розміри, що описуються відповідними векторами l(l₁^j, l₂^j).

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

де - абсциса полюсу j-того навантаження, j = 1,…,m,

,

.

Як бачимо, всі наведені критерії якості відповідають умові (1).

Чисельне порівняння методу G-проекції та методу Розена

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

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

Побудовані часові складності методів співпали за ступенями із розрахованими часовими складностями ітерації цих методів: часова складність розв'язання обраної підзадачі оптимізації за допомогою методу G-проекції виявилась поліномом третього ступеня, часова складність методу Розена - поліномом п'ятого ступеня.

Звідси випливає, що побудованим методом G-проекції розв'язок обраної підзадачі знаходиться значно швидше, ніж методом Розена.

Порівняння методів повного та спрямованого переборів

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

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

В п'ятому розділі наведено загальний опис програмної реалізації розроблених методів, а також представлено структури класів програмного продукту “Optimal rectangles placement” з деталізацією основних методів та властивостей кожного класу.

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

В додатках наведені результати статистичних експериментів, за якими будувалися оцінки часових складностей та точностей методів розв'язання задачі оптимізації. Наведено приклад розбіжності в знаходжені вектору спуску за допомогою методів Розена та G-проекції. Також наведено довідку про використання результатів дисертаційної роботи.

висновки

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

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

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

2. Розроблено метод побудови опуклих підмножин множини припустимих розв'язків. Доведено можливість заміни розв'язання вихідної задачі оптимізації на множині складної структури розв'язанням ряду побудованих підзадач на опуклих підмножинах.

3. Розроблено спеціальний чисельний метод G-проекції для розв'язання обраної підзадачі оптимізації, що використовує специфічні риси поставленої задачі.

4. Доведено збіжність методу G-проекції.

5. Доведено теореми про часову складність ітерації методу G-проекції та методу Розена. Розраховані статистистичні оцінки часової складності розв'язання обраної підзадачі оптимізації методом G-проекції та методом Розена. Зроблено висновок, що розробленим методом G-проекції знаходиться розв'язок обраної підзадачі оптимізації за значно менший проміжок часу, ніж методом Розена, так як часова складність методу G-проекції є поліномом третього ступеня, а методу Розена - поліномом п'ятого ступеня.

6. Розроблено метод спрямованого перебору побудованих підзадач для розв'язання вихідної задачі оптимізації.

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

8. Розроблено програмне забезпечення для розв'язання задачі оптимізації розміщення прямокутників у прямокутній області.

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

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

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

Жовновський Д.О., Рудюк Л.В., Саваневіч К.Є., Яремчук С.І. Оптимізація розміщення джерел фізичного поля модифікованим методом Розена // Вісн. Житомир. інж.-технол. ін-ту. Технічні науки. - 2000. - № 13. - С. 188-191.

Яремчук С.І., Рудюк Л.В. Оптимізація розміщення прямокутник джерел фізичного поля в прямокутнику // Вісн. Житомир. інж.-технол. ін-ту. Технічні науки. - 2001. - №18. - С.142-147.

Яремчук С.І., Рудюк Л.В. Порівняльні характеристики методу G_проекції розміщення прямокутників // „Радиоэлектроника и Информатика”. - №4. - 2004. - С.126-129.

Яремчук С.І., Рудюк Л.В. Збіжність методу G-проекції // „Радиоэлектроника и Информатика”. - №2. - 2005. - С.69-73.

Яремчук С.І., Рудюк Л.В. Алгоритми розв'язання задачі розміщення прямокутників в прямокутній області // Вісник Київського університету імені Тараса Шевченка. - №2. - 2005. - С.339-343.

Жовновський Д.О., Рудюк Л.В. Применение метода проекции градиента Розена для решения задачи оптимизации размещения источников физического поля в случае, когда область размещения и источники имеют форму прямоугольников. Сборник научных трудов по материалам 4-ого молодежного форума “Радиоэлектроника и молодежь в 21 веке”, ч.2. - Харьков. - 2000. - С.34-35.

Svetlana I. Yaremchuk, Lidia V. Ruduyk. Practical solution of the problem of rectangular physical field sources arrangement in rectangle // Proceedings of the Fifth international scientific conference “Electronic, Computers and Informatics”. - 2002. - P.243-247.

Рудюк Л.В. Порівняльні характеристики P- та NP-алгоритмів для розв'язання задачі оптимального розміщення прямокутних джерел фізичного поля в прямокутнику. Збірка наукових праць конференції “Системний аналіз та інформаційні технології”. - 2002. - С.47.

Яремчук С.І., Рудюк Л.В. Розв'язання задачі оптимального розміщення прямокутних джерел фізичного поля // Труды 6-ой международной научно-практической конференции “Современные информационные и электронные технологии”, Одесса. - 2005. - С.129.

Рудюк В.В., Рудюк Л.В. Використання методу G-проекції для розв'язання задачі найневигіднішого розміщення вантажів на будівельні конструкції // Сборник научных трудов по материалам научно-практической конференции “Научные исследования и их практическое применение. Современное состояние и пути развития”, технические науки, Одесса. - 2005. - С.53-57.

Анотація

Рудюк Л.В. Математична модель та чисельні методи розв'язання задачі оптимізації розміщення прямокутників. - Рукопис.

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

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

Для розв'язання задачі розроблені нові ефективні методи.

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

Обґрунтована можливість використання методу Розена для розв'язання побудованих підзадач оптимізації. Доведено теорему про часову складність ітерації методу Розена. Надана статистична оцінка часової складності розв'язання обраної підзадачі оптимізації методом Розена.

Розроблено метод G-проекції розв'язання побудованих підзадач оптимізації. Доведено теорему про збіжність методу G-проекції. Доведено теорему про часову складність ітерації методу G-проекції. Надана статистична оцінка часової складності розв'язання обраної підзадачі оптимізації методом G_проекції.

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

Розроблено програмне забезпечення, яке реалізує побудовані методи.

Ключові слова: математичне моделювання, оптимізація, розміщення, прямокутник, метод G-проекції.

Аннотация

Рудюк Л.В. Математическая модель и численные методы решения задачи оптимизации размещения прямоугольников. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт проблем машиностроения им. А.Н. Подгорного НАН Украины, Харьков, 2006.

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

Для решения задачи геометрического проектирования разработаны новые эффективные методы.

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

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

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

Разработан численный метод G-проекции решения построенных подзадач оптимизации. Доказана теорема о сходимости построенного метода G-проекции к стационарной точке. Сформулирована и доказана теорема о временной сложности итерации метода G-проекции. Приведена статистическая оценка временной сложности решения выбранной подзадачи оптимизации методом G_проекции.

Для решения исходной задачи оптимизации разработан метод направленного перебора подзадач оптимизации. Приведена статистическая оценка временной сложности решения задачи оптимизации методом направленного перебора.

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

С использованием разработанного программного обеспечения методами G_проекции и направленного перебора решены задачи оптимизации размещения прямоугольных объектов в прямоугольнике для следующих критериев качества: сумма квадратов расстояний от полюсов прямоугольников до некоторой заданной точки области; сумма квадратов расстояний между полюсами прямоугольных объектов (длина соединительной сети); сумма квадратов расстояний от начала координат до полюсов прямоугольных объектов; значение наибольшего изгибающего момента в заданном сечении строительной конструкции.

Ключевые слова: математическое моделирование, оптимизация, размещение, прямоугольник, метод G-проекции.

Abstract

Rudyuk L.V. Mathematical model and computational methods for solving a problem of rectangles placement optimization. - Manuscript.

Thesis for a candidate's degree (physic-mathematical sciences) by specialty 01.05.02 - mathematical modeling and computational methods. - A.M. Pidgorny's Institute for Problems in Machinery NAS Ukraine, Kharkiv, 2006.

The dissertation deals with researching problems of rectangular geometrical objects placement.

New effective methods were developed for problem solving.

Presentation of a non-convex feasible set in a form of convex sets union is used for a building of mathematical model of the problem. A possibility to substitute a given problem solving with solving of sub-problems series is granted.

The possibility of Rosen projection method using for each sub-problem solving is granted. The theorem on time complexity of Rosen method iteration is proved. A statistic estimation of time complexity of chosen sub-problem solving by Rosen method is built.

G-projection method for each sub-problem solving is developed. The theorem on G-projection method convergence is proved. The theorem on time complexity of G-projection method iteration is proved. A statistic estimation of time complexity of chosen sub-problem solving by G-projection method is built.

The method of directional sorting of sub-problems for initial problem solving is developed. A statistic estimation of time complexity of initial problem solving by directional sorting of sub-problems method is built.

A software product which implements developed methods is made.

Keywords: mathematical modeling, optimization, placement, rectangles, G_projection method.

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