Cluster packing of concave non-oriented polyhedra in a cuboid
Вантажиться...
Дата
2018
Автори
ORCID
DOI
10.20998/2522-9052.2018.1.03
Науковий ступінь
Рівень дисертації
Шифр та назва спеціальності
Рада захисту
Установа захисту
Науковий керівник
Члени комітету
Видавець
НТУ "ХПІ"
Анотація
The subject matter of the article is the solution of the problem of optimal packing of concave polyhedra in a cuboid of minimal volume. The goalis to construct a mathematical model of the problem under consideration and to develop a solution method. The task to be solved are: to develop tools for mathematical modeling of the interaction of two concave non-oriented polyhedra; to construct a mathematical model of the problem of packing concave non-oriented polyhedra in a cuboid of minimal volume; to investigate the peculiarities of the mathematical model; to develop an effective method of solution and implement its software. The methods used are: the phi-function technique, the internal point method. The following results are obtained. Using the phi-function for two convexnon-oriented polyhedra, a phi-function for two concave non-oriented polyhedra is constructed. On the basis of the phi-function, an exact mathematical model of the packing problem for concave polyhedra that allow simultaneous continuous translations and rotations is constructed. The mathematical model is represented as a non-linear programming problem. The properties of the constructed mathematical model are analyzed and a multi-stage approach based on them is proposed, which makes it possible to obtain a good locally optimal solution of the problem posed. Since working with polyhedra is an important to determine the optimal clustering of two objects, one of the stages of the proposed approach is to solve the problem of pairwise clustering of polyhedra. A numerical example demonstrating the effectiveness of the proposed approach is given. The scientific novelty of the obtained results consists in the following: an exact mathematical model of the packing problem of concavenon-oriented polyhedra is constructed in the form of a nonlinear optimization problem and a multi-stage approach is proposed that allows obtain a good locally optimal solution of the problem.
Предметом вивчення у статті є розв’язання задачі оптимальної упаковки неопуклих багатогранників у прямий паралелепіпед мінімального об’єму. Метоює побудова математичної моделі даної задачі і розробка методу розв’язання. Задачі: розробити засоби математичного моделювання взаємодії двох неопуклих неорієнтованих багатогранників; побудувати математичну модель задачі упакування неопуклих неорієнтованих багатогранників в кубоід мінімального об’єму; дослідити особливості математичної моделі; розробити ефективний метод розв’язання і виконати його програмну реалізацію. Використовуваними методами є: метод phi-функцій, метод внутрішньої точки. Отримані наступні результати. Використовуючи phi-функцію для двох опуклих неорієнтованих багатогранників, побудована phi-функція для двох неопуклих неорієнтованих багатогранників. На основі цієї phi-функції побудована точна математична модель задачі упаковки неопуклих багатогранників, що допускають одночасно безперервні трансляції та повороти. Математична модель представлена у вигляді задачі нелінійного програмування. Проаналізовано властивості побудованої математичної моделі і на їх основі запропонований багатоетапний підхід, що дозволяє отримати гарний локально оптимальний розв’язок поставленої задачі. Оскільки при роботі з багатогранниками важливою задачею є визначення оптимальної кластеризації двох об'єктів, то одним з етапів запропонованого підходу є розв’язання задачі попарної кластеризації багатогранників. Наводиться чисельний приклад, який демонструє ефективність запропонованого підходу. Наукова новизна отриманих результатів полягає в наступному: побудована точна математична модель задачі упаковки неопуклих неорієнтованих багатогранників у вигляді задачі нелінійної оптимізації та запропонований багатоетапний підхід, що дозволяє отримати гарне локально оптимальний розв’язок поставленої задачі.
Предметом вивчення у статті є розв’язання задачі оптимальної упаковки неопуклих багатогранників у прямий паралелепіпед мінімального об’єму. Метоює побудова математичної моделі даної задачі і розробка методу розв’язання. Задачі: розробити засоби математичного моделювання взаємодії двох неопуклих неорієнтованих багатогранників; побудувати математичну модель задачі упакування неопуклих неорієнтованих багатогранників в кубоід мінімального об’єму; дослідити особливості математичної моделі; розробити ефективний метод розв’язання і виконати його програмну реалізацію. Використовуваними методами є: метод phi-функцій, метод внутрішньої точки. Отримані наступні результати. Використовуючи phi-функцію для двох опуклих неорієнтованих багатогранників, побудована phi-функція для двох неопуклих неорієнтованих багатогранників. На основі цієї phi-функції побудована точна математична модель задачі упаковки неопуклих багатогранників, що допускають одночасно безперервні трансляції та повороти. Математична модель представлена у вигляді задачі нелінійного програмування. Проаналізовано властивості побудованої математичної моделі і на їх основі запропонований багатоетапний підхід, що дозволяє отримати гарний локально оптимальний розв’язок поставленої задачі. Оскільки при роботі з багатогранниками важливою задачею є визначення оптимальної кластеризації двох об'єктів, то одним з етапів запропонованого підходу є розв’язання задачі попарної кластеризації багатогранників. Наводиться чисельний приклад, який демонструє ефективність запропонованого підходу. Наукова новизна отриманих результатів полягає в наступному: побудована точна математична модель задачі упаковки неопуклих неорієнтованих багатогранників у вигляді задачі нелінійної оптимізації та запропонований багатоетапний підхід, що дозволяє отримати гарне локально оптимальний розв’язок поставленої задачі.
Опис
Ключові слова
cluster packing, concave polyhedra, continuous rotation, nonlinear optimization, безперервне обертання, нелінійна оптимізація
Бібліографічний опис
Chugay A. Cluster packing of concave non-oriented polyhedra in a cuboid / A. Chugay, Ye. Stoian // Сучасні інформаційні системи = Advanced Information Systems. – 2018. – Т. 2, № 1. – С. 16-21.