Математичні моделі і методи розв’язання нелінійних задач розміщення геометричних об’єктів

визначити: min z, (10)



умова взаємного неперетину об'єктів S_i та S_j визначається структурою

Вилучено такі основні характерні властивості області D.

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

2. Область D може бути зображена у вигляді об'єднання скінченого числа неопуклих областей D_{s_nonlinear}, кожна з яких задається системою нелінійних і лінійних обмежень структури (11):

D=D_s__nonlinear. (12)

3. Покриття (12) не є розбиттям, тому для деяких точок X області D має місце співвідношення:

4. Область D в загальному випадку є незв'язною множиною і кожна її компонента зв'язності має “яружний” характер.

5.У перерізі області D гіперплощиною f_const={f_i}_i=1,2,...,n=const маємо певну багатогранну неопуклу множину

D_linear =D_{g_linear}= D_{g_s_linear} R²ⁿ⁺¹,

де D_{g_linear} - компонента лінійної зв'язності області D_linear,

D_{g_s_linear} - опукла багатогранна підмножина.

6. Область D_linear є областю припустимих розв'язків задачі вигляду

знайти: z. (13)

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

Через властивості 1-4 області D, задача (10-11) класифікується як багатовимірна багатоекстремальна оптимізаційна задача з лінійною функцією мети і, в загальному випадку, нелінійними неопуклими обмеженнями.

У розділі розглядаються кілька підходів до побудови початкового аближення Х₀ (f_constfconst), які аналізуються з точки зору якості Х₀ і обчислювальної складності алгоритмів. На підставі поглибленого аналізу вибір робиться на користь для методу локальної оптимізації задачі (12). Точка Х₀ є вершиною області D_linear і визначається системою рангу (2n+1) активних у точці_. лінійних обмежень

F(f_const)Х₀+ C(f_const)=0, (14)

де ліві частини рівнянь системи (14) приймають вигляд

{A_g( -) + B_g( -)+C_g; A_q(-) + B_q(-)+C_q; z- -C_k (15)

-C_l; -C_w; -+C_e },

g=1,2,...m₁; k= m₁+1, ...,m₂, l= m₂+1,..., m₃, w= m₃ +1,..., m₄, e= m₄ +1,...,2n+1.

В загальному випадку точка Х₀ є виродженою і належить більш ніж одній області D_{g_s_linear}, що визначається системою нерівностей порядку n(n-1)/2 +4n +(К-1)n

G(f_const)X+C(f_const) 0, (16)

де ліві частини рівнянь системи (16) мають вигляд (15).

Метою розв'язання задачі (10-11) є знаходження одного локального мінімуму, тому обираються певна підобласть D_{g_s_linear}D_linear, яка містить Х₀ і визначається системою (16), певна система рівнянь (14), що задає Х₀, і здійснюється занурення у простір всіх змінних R³ⁿ⁺¹, у якому розглядається задача

визначити (X^*,f^*)= arg min z ,

D_{s_nonlinear}D R³ⁿ⁺¹

де множина D_nonlinear, задається системою обмежень вигляду

, (17)

де система G(?)X-C(?) 0 породжується системою (16), система містить n(n-1)+8n+2(К-1)n нерівностей вигляду (6).

Розглядається також підобласть D_equation межі області D, що задається системою обмежень порядку (2n+1), .... (3n) вигляду

(18)

де система F(ф)Х+ C(ф)=0 породжується системою (14).

Загальна схема метода локальної оптимізації задачі (10-11) є ітераційним процесом, k-а ітерація якого полягає в сукупності таких дій:

1. У околі певної початкової точки (X_k,фф_k) розв'язати задачу:

знайти (X_k^*,fф_k^*) = arg min z , (19)

(X,ф D_{s_nonlinear}

де підобласть D_{s_nonlinear} описується системою вигляду (17).

2. Перевірити умову

(X_k^*,ф_k^*) = arg min z , (20)

(X_k^*,ф_k^*)Df__nonlinear=1,2,...,.

Якщо умова (20) виконана, точка (X_k^*,фф_k^*) є локальним розв'язком задачі (10-11). Якщо ні, вилучається наступна область D₍__nonlinear, що містить (X_k^*, ф_k^*), точка (X_k^*,ф_k^*) позначається як (X_k+1,ф_k+1) і виконується (k+1)-а ітерація. У розділі запропоновано розглядати задачу (19) в вигляді двох підзадач:

Задача 1. Визначити:

(X*,ф*)=. (21)

Задача 2. Визначити наступну систему вигляду (18) шляхом доповнення або поновлення списку активних обмежень.

Задача (21) розглядається як задача нелінійного програмування з обмеженнями-рівностями (обмеження-нерівності вигляду (6) ураховуються тільки на етапі визначення величини кроку ?_k), для розв'язання якої застосовується модифікована реалізація стратегії активного набору, що зводиться до безумовної мінімізації відповідної функції Лагранжа L(ф,X,ф). Враховуючи, що матриця Гессе H_xx(ф?X,ф) функції Лагранжа задачі (21) є знаконевизначеною, пошук напряму спуску виконується в загальному випадку вздовж кривої:

C={X (a): X (a) =X₁+q₁ (a) s+q₂ (a) d, 0},

яка гарантує збіг послідовності X_i{a} до певної точки (X*, ф*), в якій фL(ф,X*,фф*) =0 і H_xx (f, X*,фф*) є додатно напіввизначеною.

Вектор s є розв'язком певної системи рівнянь B_ks_k=-g_k з додатно визначеною симетричною матрицею B_k. Вектор d являє собою напрям від'ємної кривини, g_k є градієнтом функції Лагранжа задачі (21).

У роботі використано факторизацію Холеського для обчислення напряму d і побудови додатно визначеної матриці, яка апроксимує невизначену матрицю H_xx(ф,X,ф).

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

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

Теорема 1. Матриця Гессе H_xx(ф, X, ф) функції Лагранжа L (ф,X,ф) задачі (21) має ранг не більш 2n, де n - кількість об'єктів, що розміщуються.

Іншими словами, пошук напряму руху p_k можна здійснювати у перерізі поверхні, що задається системою (14), площиною Оy₁ y₂... y_n.

Теорема 2. Для задачі (21) метод мінімізації за групами кутових параметрів розміщення і параметрів трансляції приводить до стаціонарної точки задачі.

У розділі розглянуто питання визначення оцінок і точних значень множників Лагранжа.

Зауваження 5. Якщо список активних обмежень містить (2n+1) рівностей, достатньо взяти вектор множників Лагранжа, що визначений для оптимальної точки задачі вигляду (13). При цьому компоненти вектора g^T_k за змінними трансляції дорівнюють нулю, тобто є необхідною мінімізація тільки за кутовими параметрами, що є ще одним підтвердженням основної ідеї алгоритму - вилучення двох груп змінних і оптимізації за групами змінних.

При визначенні величини крокуф_k враховується, що точки (X_k,ф_k) і (X_k+1,фф_k+1) належать межі області D.

Розглянемо деяку рівність системи обмежень (18) і припустимо, що пара “вершина - сторона“ (див. розд. 3), яка формує коефіцієнти обмежень системи, залишається незмінною. Тоді є вірною

Теорема 3. У задачі (21) визначення максимальної величини крокуф?_k за кутовими параметрами {ф_i}, i=1_, 2,..., n розміщення не залежить від значень параметрів трансляції (x₁, y₁, x₂, y₂,... , x_n, y_n).

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

Результатом дії засобу визначення величини f_k є певний проміжний вектор змінних задачі (X_k, ф_k+1), що визначає або внутрішню, або неприпустиму точку області D задачі (10-11).

Належність точки (X_k+1,ф_k+1) області D забезпечується припасуванням варіацій вектора незалежних змінних X. Для цього за новими значеннями ф_k+1 переобчислюються коефіцієнти обмежень системи (14) після чого значення кутових параметрів фіксуються. Система рівнянь із знов створеною матрицею коефіцієнтів (або ії лінійно-незалежна підсистема, якщо порядок системи (14) більше ніж 2n+1) розв'язується з метою визначення параметрів трансляції і z.

Відзначимо, що в загальному випадку процедура припасування є адаптивною підзадачею. Однак при розв'язанні практичних задач розміщення ця процедура складалась з одного кроку, незважаючи на те, що немає точного доведення, що матриця коефіцієнтів системи (14) (або її підматриця рангу 2n+1) завжди буде сумісною.

Необхідним етапом розв'язання задачі (21) є перевірка належності точки (X_k+1,ф_k+1) області D. Можливі наступні випадки.

1. (X_k+1,ф_k+1) D_nonlinear (X_k+1,ф_k+1) D.

2. (X_k+1,ф_k+1) D_nonlinear (X_k+1,ф_k+1) D.

3. (X_k+1,ф_k+1) D_nonlinear (X_k+1,ф_k+1) D.

Найбільш цікавим є другий випадок, коли є можливість спуску по внутрішньості області D.

На рис. 2 наведено приклад розв'язання задачі оптимального розміщення множини 16 багатокутників у півнескінченій смузі.

а)

б)

в)

Рис. 2. Приклад роботи алгоритму локальної мінімізації

а) - певне початкове розміщення;

б) - точка X₀ ;

в) - точка локального мінімуму задачі (19).

Розглянемо таку реалізацію основної задачі (1-3). Нехай є обмежені, замкнені, в загальному випадку неопуклі багатогранні об'єкти S_i, i=0,1, що мають задану просторову форму, причому метричні характеристики об'єкта S₁ також задані. Положення об'єктів у просторі R³ характеризується параметрами розміщення (x_i,y_i,z_i,ф_i), i=0,1. Над об'єктами припустимі афінні перетворення трансляції, повороту, а над об'єктом S₀ - і перетворення гомотетії, що задається коефіцієнтом гомотетії К.

Задача полягає в розміщенні об'єкта S₁ у багатограннику S₀ із метою мінімізації об'єму V₀(S₀) об'єкта S₀.

Використання властивостей афінних перетворень дозволяє зменшити розмірність задачі вдвічі фіксацією параметрів розміщення області S₀.

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

min К³ V₀, (22)

S₀ S₁ = S₁ (23)

де V₀* є початковим значенням об'єму об'єкта S₀.

Умова (22), що визначає область D припустимих розв'язків задачі (22-23), задається умовою Ф₀₁(x₁,y₁,z₁,ф₁,)0, поверхня 0-рівня якої описується набором нелінійних поверхонь вигляду (9).

Аналіз області D задачі (22-23) на основі визначення матриць Гессе функцій обмежень задачі показав, обмеження області D не є опуклими або увігнутими. Більш того, область припустимих розв'язків D задачі є у загальному випадку незв'язною. Тому дана задача є багатоекстремальною задачею з нелінійними неопуклими обмеженнями, що заважає безпосередньому застосуванню методів класичного опуклого нелінійного програмування.

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

1. Побудова початкового припустимого розміщення об'єктів, що задається вектором w₁=(x₁,y₁,z₁,ф₁,K), заснована на визначенні взаємної перспективної орієнтації об'єктів за допомогою оцінки їхніх моментів інерції та розрахунку еліпсоїдів інерції для кожного з об'єктів (рис.3.а).

Вектор w₁ задає точку області D, що належить певній неопуклій компоненті зв'язності D_p області D, у якій далі розглядається задача (22-23).

2. Визначення оптимального розміщення, тобто розв'язання такої підзадачи: знайти: min К³ V₀, (24)

G DR⁷

де підобласть G визначається системою рангу m{1,2,...,7} активних в поточній точці XD обмежень області D, тобто обмежень, що описують дотик об'єктів.

Пошук локального мінімуму задачі (24) являє собою монотонний ітераційний процес, у якому шляхом апроксимації знаконевизначеного гессіана деякою додатно визначеною матрицею на кожному кроці процесу розв'язання і вибору напряму спуску можна одержати послідовність X_j, j=1,2,..., що збігається, у загальному випадку, до стаціонарної точки X* (рис.3.б).

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



Рис. 3 -Розміщення неорієнтованих багатогранників

а) - початкове розміщення. Об'єкти перетинаються.

б) - результат роботи програми локальної оптимізації

У розділі розглядається ще одна реалізація задачі (1-3) у R². Є два неопуклих багатокутники S₀ і S₁, що характеризуються своєю площею s_i, і=0,1, (s₁=const). Афінні перетворення руху припустимі над об'єктами S₀ і S₁, над S₀ припустима також гомотетія. Необхідно визначити такі метричні характеристики об'єкта S₀ при зберіганні просторової форми об'єктів, щоб задовольнялися такі умови:

min s₀ (25)

S₁ S₀ = S₀,

Аналіз функції мети (25) дозволив записати модель задачі у вигляді

min K² s₀^* (26)

D R⁴

де s₀^* - початкове значення площі області S₀,

область D описується структурою нелінійних нерівностей вигляду (8).

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

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

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

Кожна крайня точка області D визначається системою чотирьох лінійних і нелінійних рівнянь. На основі істотного аналізу геометричних особливостей задачі оцінка М числа всіляких систем рівнянь складає М=О(N₀xN₁)².

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

Нехай є початкове розміщення (рис. 4.а) в ізотропній прямокутній області розміщення S₀, яке може бути одержано будь-яким методом геометричного проектування. Нехай також є набір об'єктів {S}, які є ще нерозміщеними. (рис. 4.б). Вважаємо, що набір {S} має нескінчену потужність.

Необхідно розмістити об'єкти з набору {S} у незайнятих частинах області розміщення S₀.

Методика розв'язання цієї задачі складається з двох етапів.

Етап 1. Вилучення так званих вільних областей (на рис. 4.в ці області пофарбовані сірим кольором).

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

Етап 2. Оптимальне розміщення у вільних областях об'єктів набору {S}, для чого реалізований засіб розв'язання задачі (35). При цьому з набору об'єктів {S} вибирається об'єкт з такими метричними характеристиками, який може бути розміщений у поточній вільній області.

а) б)

в)

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

Основні результати розділу опубліковані в роботах [2, 4, 5, 7, 8, 10-13, 16-18, 19, 21, 24, 29].

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

Розглянемо задачу розміщення набору S_i, i=1, 2,..., n, прямокутників з розмірами {a_i, b_i} і параметрами розміщення v_i={x_i,y_i} без взаємних перетинів у напівнескінченій смузі S₀={(x, y): 0xz, 0yW, W=const} з метою мінімізації довжини z зайнятої частини смуги.

Математична модель задачі має вигляд

, (27)

де область припустимих розв'язків D описується структурою

. (28)

де набір F_i0(v_i,z) містить нерівності вигляду {x_i0; y_i0; z-x_i - a_i 0; W - y_i - b_i 0},

набір F(v_i,v_j) містить нерівності вигляду {x_i - x_j - a_j0; x_j - x_i - a_i0; y_i - y_j - b_j0;

y_j - y_i - b_i0}, i,j=1,2,...,n, ij.

В загальному випадку область D є незв'язною багатогранною множиною, завдяки чому та лінійності функції мети глобальний мінімум задачі досягається у певній вершині X^* області D. Вершина X^* визначається однією або кількома системами рівнянь FX+C=0, що належать множині усіляких лінійно-незалежних систем рівнянь Q, побудованих з нерівностей наборів F_i0(v_i,z) i F(v_i,v_j) структури (28). Задача (27-28) є NP-повною оптимізаційною задачею, тому для її розв'язку застосований засіб дискретної оптимізації, який оснований на організації оптимізаційного процесу за деревом розв'язків А і полягає в усіченому переборі множини Q.

Побудована на останньому рівні дерева розв'язків А система рівнянь FX+C=0, якщо вона сумісна, описує: 1) вершини області D; 2) точки, що належать межі області D; 3) точки поза областю D, тобто точки, що визначають параметри розміщення, при яких деякі пари прямокутників перетинаються. Крім того, вершини дерева розв'язків можуть символізувати і 4) несумісні системи.

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

У розділі пропонується подальший розвиток методу розв'язання задачі (27-28) з метою усунення необхідності аналізу несумісних систем рівнянь.

Для цього дерево розв'язків А розбивається на два піддерева: А¹ і А². Піддерево А¹ містить усі вершини дерева А, на яких на кожному рівні дерева розв'язків при включенні в систему рівнянь чергового обмеження в список змінних додається тільки одна змінна, тобто, на кожному рівні піддерева А¹ побудована система рівнянь описує точку в просторі вимірності номера рівня дерева.

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

Зауваження 6. Усі несумісні системи рівнянь досягаються на вершинах дерева А².

Засіб аналізу вершин дерева А¹ забезпечує прямий порядок перегляду вершин і реалізує множину С правил відтинання кінцевих вершин дерева, у тому числі вершин дерева А¹, які визначають точку X_outD D (випадок 3), галуження з яких є недоцільним.

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

Застосування методу неперервної оптимізації, а саме, методики активного набору на певних кроках розв'язання комбінаторної задачі, який запропоновано у розділі, дозволяє використати систему рівнянь F_outX-B=0, що визначає точку (вектор параметрів розміщення) X_outD, у якій -функції деяких пар прямокутників приймають від'ємні значення. Іншими словами, у точці X_outD, здобутої на рівні 2k дерева розв'язків А¹ є множина F_broken={f_ik1, f_ik2, f_ik3, f _ik4}, i < k, i{1,2,...,k-1} порушених обмежень (чотири для кожної ?-функції, що приймає від'ємне значення).

Визначення 1. Назвемо найближчими граничні точки області D_2k, отримані з даної точки X_outD за алгоритмом, що реалізує стратегію активного набору.

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

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

Метод пошуку найближчої точки оснований на перегляді знаків компонентів вектора множників Лагранжа на кожній ітерації. В загальному випадку в залежності від вибраного на даній ітерації множника (напряму руху) результат оптимізації (припустима точка) може бути відмінним.

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

Теорема 6. Нехай система рівнянь FX+C=0, що визначає початкову неприпустиму точку X_outD, має таку властивість: кожній незалежній змінній задачі відповідає тільки одна рівність системи, яка містить цю змінну з коефіцієнтом 1.

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

Отже, для розв'язання задачі (27-28) необхідно побудувати всі системи рівнянь, що визначають вершини області припустимих розв'язків задачі. Частина таких систем рівнянь будується при перегляді вершин дерева розв'язків А¹, інша частина може бути отримана як розв'язок сукупності лінійних задач розв'язків множини найближчих точок з деякої точки Х_outD. Відзначимо таку важливу властивість

Властивість 1. Алгоритм визначення найближчої точки дозволяє знайти вершини (граничні точки) області D^k (k - номер рівня дерева розв'язків), що задаються системами рівнянь, які можна побудувати тільки при перегляді вершин дерева А².

Іншими словами, з точки Х_outD поза областю припустимих розв'язків, що знайдена при перегляді дерева А¹, будуються вершини (граничні точки) області припустимих розв'язків, що формуються, взагалі кажучи, на вершинах дерева А², причому даний процес скінчений і піддається упорядкуванню.

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

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

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

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

На рис. 5 наведений розв'язок задачі прямокутного розміщення 25 прямокутників. Час розв'язання склав 21 хвилину на PC AT 486.



Рис. 5 Розв'язок задачі прямокутного розміщення 25 прямокутників

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

Нехай є напівнескінчена область

S₀={(x₁, x₂,..., x_p) | x₁0, 0x_kA_k, k=2,...,p}.

Необхідно розмістити n прямокутних гіперпаралелепіпедів {S_i}_i=1,2,...,n з розмірами 2, k=1, 2,..., p вздовж відповідних осей координат в області S₀ так, щоб довжина зайнятої частини області вздовж координатної осі ОХ₁ була мінімальною.

Математична модель задачі має вигляд, аналогічний (27-28).

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

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

Основні результати розділу викладено у працях [1, 2, 10, 14, 18, 19, 22, 25, 29].

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

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

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

В процесі досліджень отримані такі нові результати.

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

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

4. Створено засіб аналітичного подання теоретико-множинного відношення включення для пари двовимірних неорієнтованих геометричних об'єктів, один з яких зізнає афінного перетворення подібності.

5. Апарат Ф-функцій застосовано для опису умов взаємного розміщення двох неорієнтованих багатогранників у R³.

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

7. Запропоновано методику побудови проекції 0-рівня ?-функції двох неорієнтованих багатокутників в анізотропній області.

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

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

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

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

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

13. Запропоновано алгоритмічні та програмні реалізації методів з оцінками обчислювальної складності алгоритмів.

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

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

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

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

ОСНОВНІ РЕЗУЛЬТАТИ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В НАСТУПНИХ НАУКОВИХ ПРАЦЯХ

оптимізаційний моделювання геометричний

1. Элементы теории геометрического проектирования / Гиль Н.И., Яковлев С.В., Новожилова М.В. и др.: Под ред. акад. НАН Украины Рвачева В.Л. - К.: Наук. думка, 1995. - 248с.

2. Новожилова М.В., Кожухов О.В. Система решения подкласса задач геометрического проектирования // Программное обеспечение технических систем, К.: Ин-т кибернетики АН УССР. - 1991. - С. 26-30.

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

4. Новожилова М.В. Метод решения задачи оптимизации линейной функции цели на структуре нелинейных неравенств // Математическое моделирование и оптимизация технических систем и процессов.-К.:Ин-т кибернетики НАН Украины. - 1993. - С.25-30.

5. Новожилова М.В. Моделирование и решение задачи размещения невыпуклых многоугольных объектов в ограниченной области // Автоматизация архитектурно-строительного проектирования.- Ростов- на-Дону: Ростовский гос. архитектурный ин-т. - 1994. - С.120-129.

6. Новожилова М.В., Карташов А.В. Выбор метода точного решения задачи размещения многоугольников в области с подвижными границами // Математическое и компъютерное моделирование в машиностроении.-К.:Ин-т кибернетики НАН Украины. - 1994. - С. 9-20.

7. Новожилова М.В. Операция теоретико-множественного вычитания на множестве произвольных многоугольников// Методы оптимизации технических и информационных систем.-К.: Ин-т кибернетики НАН Украины.-1995.-C.34-38.

8. Stoyan Yu.G., Novozhilova M.V., Kartashov A.V. Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem // European Journal of Operational Research.- 1996.- N 92, Р.193-210.

9. Стоян Ю.Г., Новожилова М.В., Пшеничная В.Д. Моделирование и метод решения задачи размещения неориентированного многогранника в многограннике с переменными метрическими характеристиками // Электронное моделирование.- 1998.-Т.20.- N 4.- С. 16-24.

10. Biro M., Stoyan Yu., Novozhilova M. et al. The State of Software Best Practice in Central and Eastern Europe // IEEE Software Process Newsletter.-1998, N 12.- P.19-21.

11. Стоян Ю.Г., Новожилова М.В. Условия локальной оптимальности в нерегулярных нелинейных задачах геометрического проектирования // Доклады НАН Украины.-1998.- N 12.-С.40-45.

12. Новожилова М.В. Моделирование и решение задачи размещения неориентированного объекта в области с переменными метрическими характеристиками // Проблемы бионики.- Харьков: ХГТУРЭ.- 1998.-Вып. 49. - С.95-98.

13. Новожилова М.В., Пандорiн О.К. Використання поняття ?-функцii в 2D задачах геометричного проектування // Вiсник ЖIТI; Фундаментальні науки. - 1998. - N 8. - С. 328-331.

14. Новожилова М. В., Лазарева И.Е. Применение методологии множителей Лагранжа в комбинаторной задаче размещения прямоугольников // Кибернетика и системный анализ.- 1999. - N 3. - С. 141-147.

15. Новожилова М. В. Методологiя розв'язання оптимiзацiйних нелiнiйних задач геометричного проектування // Вiсник Запорiзького державного унiверситету. - Запорiжжя: ЗДУ.-1999.- N 1. - С. 79-82.

16. Новожилова М. В. Моделювання основних обмежень в нелiнiйних задачах оптимiзацiйного геометричного проектування // Прикладна геометрiя i iнженерна графiка. - К.:КДТУБА. - 1999. - N 65. - С.82-86.

17. Пандорiн О.К., Панкратов О.В., Новожилова М. В. Аналiз i складнiсть алгоритму зображення однозвязного неопуклого многокутника у виглядi об'єднання опуклих многокутникiв // Вiсник Запорiзького державного унiверситету. - Запорiжжя: ЗДУ. -1999. - N 2. - С. 79-83.

18. Stoyan Yu.G., Novozhilova M.V. Nonguillotine placement of rectangles into a strip of given width // Pesquisa Operacional: Special Issue on Cutting and Packing problems.- 1999. - N 3. - P. 63-74.

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

20. Стоян Ю.Г., Новожилова М. В., Карташов А.В. Математическая модель и оптимизация линейных E_к(R²) задач размещения.-Харьков: 1991.-25 с. (Препр. / НАН Украины. Ин-т пробл. машиностроения; N 353).

21. Построение начального приближения для задачи размещения выпуклого многогранника в выпуклой многогранной области с переменными метрическими характеристиками // Новожилова М.В., Пшеничная В.Д.; Ин-т пробл. машиностр. АН Украины. М., 1996 - 18c. - Рус. - Деп. ВИНИТИ 16.08. 96, N 2694-В 96.

22. Применение методологии непрерывной оптимизации в одной комбинаторной задаче геометрического проектирования с линейными ограничениями и функцией цели // Новожилова М.В., Лазарева И.Е. ; Ин-т пробл.

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

...