Решение задачи оптимальной упаковки гомотетических эллипсоидов в контейнере минимального объема
Ключевые слова:
оптимальная упаковка, гомотетичные эллипсоиды, phi-функции, стартове точки, непересечение, включение, нелинейное программирование, итерационная процедура, процедура LOFRTАннотация
Рассматривается задача оптимизации упаковки гомотетичных одинаково ориентированных эллипсоидов в контейнере минимального объема. Строится математическая модель в виде задачи нелинейного программирования. Ограничения непересечения эллипсоидов и их включения в контейнер построены с использованием метода phi-функций В качестве контейнера рассматривается либо прямоугольный параллелепипед переменной длины, ширины и высоты, либо эллипсоид с переменным коэффициентом гомотетии. Предлагается алгоритм поиска локально оптимальных решений. с использованием гомотетических преобразований эллипсоидов и оптимизационной процедуры, позволяющей свести задачу с большим числом неравенств к последовательности задач с меньшим числом неравенств. Для поиска локальных минимумов задачи используется подход, в основе которого лежит метод мультистарта и оптимизационная процедура, включающая поиск допустимых стартовых точек и локальную оптимизацию. В качестве локально-оптимального решения выбирается наилучший из полученных локальных экстремумов. С целью минимизации числа нелинейных неравенств, формирующих область допустимых решений, предложена процедура LOFRT, которая позволяет значительно сократить вычислительные ресурсы. Приводятся результаты численных экспериментовБиблиографические ссылки
1. Wright S. J. Packing Ellipsoids with Overlap. SIAM Review, 55(4):671-706. 2013.
2. Kallrath J. Packing ellipsoids into volume-minimizing rectangular boxes. Journal of Global Optimization. DOI:10.1007/s10898-015-0348-6.
3. Pankratov A., Romanova T., Khlud O. Quasi-phi-functions in packing of ellipsoids. Radioelectronics & Informatics, 68:37–42. 2015.
4. Lubachevsky B. D., Stillinger F. H. Geometric properties of random disk packings. Journal of Statistical Physics, 60 (5–6):561-583. 1990.
5. Bennell J. A., Oliveira J. F. A tutorial in irregular shape packing problem.Journal of the Operational Research Society. 2009. 60:93–105.
6. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications. 2010. Vol. 43, № 5. P. 533-553.
7. Stetsuk P. I., Romanova T. E., Subota I. O. NLP-zadacha upakovky homotetychnyh elipsiv u priamokutnyi konteiner. Teoriya optymalnyh rishen: zb. nauk. pr. – Kiev: In. kibernetyky im. V. M. Hkushkova NAN Ukrainy. 2014. S. 139-146.
8. Stoyan Yu. G. A mathematical model and a solution method for the problem of placing various-sized circles into a strip / Yu. G. Stoyan, G. N. Yaskov. European Journal of Operational Research. 2004. Vol. 156. P. 590–600.
9. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization. 2015. DOI:10.1007/s10898-015-0331-2.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2016 О. М. Хлуд
Это произведение доступно по лицензии Creative Commons «Attribution-NoDerivatives» («Атрибуция — Без производных произведений») 4.0 Всемирная.
Авторы, публикующиеся в этом журнале, соглашаются со следующими условиями:
- Авторы оставляют за собой право на авторство своей работы и передают журналу право первой публикации этой работы на условиях лицензионного договора (соглашения).
- Авторы имеют право заключать самостоятельно дополнительные договора (соглашения) о неэксклюзивном распространении работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном хранилище учреждения или публиковать в составе монографии), при условии сохранения ссылки на первую публикацию работы в этом журнале.
- Политика журнала позволяет размещение авторами в сети Интернет (например, в хранилищах учреждения или на персональных веб-сайтах) рукописи работы, как до подачи этой рукописи в редакцию, так и во время ее редакционной обработки, поскольку это способствует возникновению продуктивной научной дискуссии и позитивно отражается на оперативности и динамике цитирования опубликованной работы (см. The Effect of Open Access).
