Search academic texts

Registration Number

0419U000607, Candidate dissertation

Title

Optimal ellipsoid packing problem: mathematical models and solution methods.

Author

Khlud Olha М.,

popup.head Romanova Tetiana E.
popup.opponent Zholtkevych Grygoriy M.
popup.opponent Komiak Valentyna M.

Status

Кандидат технічних наук, 01.05.02, Математичне моделювання та обчислювальні методи

Date

28-02-2019

Description

У роботі досліджено задачу оптимальної упаковки заданого набору еліпсоїдів у опуклому контейнері мінімальних розмірів (відповідних метричних характеристик). Еліпсоїди допускають неперервні трансляції та обертання. Як контейнер розглянуто довільну опуклу область, границя якої формується сферичними, циліндричними, еліптичними поверхнями та площинами. Сформульовано базову задачу оптимальної упаковки еліпсоїдів (3DBEP). Залежно від виду цільової функції (об’єм, коефіцієнт гомотетії, одна з метричних характеристик контейнера), форми контейнера (прямокутний паралелепіпед, циліндр, куля, еліпсоїд або опуклий багатогранник), особливостей метричних характеристик еліпсоїдів (гомотетичні, еліпсоїд обертання, довільні), обмежень на орієнтацію еліпсоїдів (однаково орієнтовані, допускаються неперервні обертання) та мінімально допустимі відстані, виділено три реалізації базової задачі оптимальної упаковки еліпсоїдів: 3DHEP (Homothetic Ellipsoid Packing) – упаковка однаково орієнтованих гомотетичних еліпсоїдів в контейнер (прямокутний паралелепіпед, еліпсоїд); 3DEP (Ellipsoid Packing) – упаковка неорієнтованих еліпсоїдів обертання (сфероїдів) в контейнер (прямокутний паралелепіпед, циліндр); 3DAEP (Approximated Ellipsoid Packing) – упаковка неорієнтованих еліпсоїдів у довільний опуклий контейнер із урахуванням мінімально допустимих відстаней. Для аналітичного опису відношень неперетину, включення та мінімально допустимих відстаней побудовано phi-функції, квазі phi-функції, псевдонормалізовані phi-функції та псевдонормалізовані квазі phi-функції. Використовуючи відповідні засоби моделювання, побудовано математичні моделі базової задачі та її реалізацій у вигляді задач нелінійного програмування. Розроблено стратегію розв’язання базової задачі 3DBEP та її основних реалізацій, в основі якої лежить метод мультистарту. Для кожної реалізації запропоновано методи побудови стартових точок з області допустимих розв’язків та методи пошуку локальних екстремумів, які зводять задачу великої розмірності з великою кількістю нелінійних нерівностей до послідовності підзадач нелінійного програмування з меншою розмірністю та меншою кількістю нелінійних нерівностей. Наведено результати обчислювальних експериментів для основних реалізацій базової задачі упаковки еліпсоїдів у різних контейнерах. Проведено аналіз результатів, що підтверджує ефективність розроблених методів та алгоритмів. Отримані результати можуть бути застосовані при комп’ютерному моделюванні структури рідин, кристалів і скла, руху і пресування сипучих 23 речовин, у термодинаміці, в сучасній біології, у ядерній медицині, в адитивних технологіях (3D printing), у робототехніці. Ключові слова: упаковка, еліпсоїди, опуклий контейнер, метод phi- функцій, математична модель, нелінійна оптимізація.