Сучасні інформаційні системи (May 2018)
Кластерна упаковка неопуклих неорієнтованих багатогранників у кубоід
Abstract
Предметом вивчення у статті є розв’язання задачі оптимальної упаковки неопуклих багатогранників у прямий паралелепіпед мінімального об’єму. Метою є побудова математичної моделі даної задачі і розробка методу розв’язання. Задачі: розробити засоби математичного моделювання взаємодії двох неопуклих неорієнтованих багатогранників; побудувати математичну модель задачі упакування неопуклих неорієнтованих багатогранників в кубоід мінімального об’єму; дослідити особливості математичної моделі; розробити ефективний метод розв’язання і виконати його програмну реалізацію. Використовуваними методами є: метод phi-функцій, метод внутрішньої точки. Отримані наступні результати. Використовуючи phi-функцію для двох опуклих неорієнтованих багатогранників, побудована phi-функція для двох неопуклих неорієнтованих багатогранників. На основі цієї phi-функції побудована точна математична модель задачі упаковки неопуклих багатогранників, що допускають одночасно безперервні трансляції та повороти. Математична модель представлена у вигляді задачі нелінійного програмування. Проаналізовано властивості побудованої математичної моделі і на їх основі запропонований багатоетапний підхід, що дозволяє отримати гарний локально оптимальний розв’язок поставленої задачі. Оскільки при роботі з багатогранниками важливою задачею є визначення оптимальної кластеризації двох об'єктів, то одним з етапів запропонованого підходу є розв’язання задачі попарної кластеризації багатогранників. Наводиться чисельний приклад, який демонструє ефективність запропонованого підходу. Висновки. Наукова новизна отриманих результатів полягає в наступному: побудована точна математична модель задачі упаковки неопуклих неорієнтованих багатогранників у вигляді задачі нелінійної оптимізації та запропонований багатоетапний підхід, що дозволяє отримати гарне локально оптимальний розв’язок поставленої задачі.
Keywords
