Компонування м’яких багатогранників у опуклому контейнері мінімального об’єму

Abstract

Запропоновано доцільні засоби математичного моделювання умов розміщення (неперетин та включення) м’яких багатогранників із застосуванням методу phi-функцій. Побудовано відповідні математичні моделі як задачі нелінійного програмування. Розроблено метод розв’язання із застосуванням алгоритму генерації допустимих стартових розміщень та методу декомпозиції, який дозволяє звести задачу великої розмірності до послідовності задач меншої розмірності, лінійної до числа багатогранників.Appropriate tools of mathematical modeling of the placement conditions (non-overlapping and containment constraints) for soft polyhedra are proposed using the phi-function technique. The corresponding mathematical models are constructed as nonlinear programming problems. A solution method is developed using an algorithm for generating feasible starting points and a decomposition algorithm, which allows reducing a large-scale problem to a sequence of the smaller nonlinear programming problems, linear to the number of polyhedra.