Розв’язання задачі оптимальної упаковки гомотетичних еліпсоїдів в контейнері мінімального об’єму

DOI https://doi.org/10.15407/pmach2016.02.044
Журнал Проблеми машинобудування
Видавець Інститут проблем машинобудування ім. А. М. Підгорного Національної академії наук України
ISSN 0131-2928 (print), 2411-0779 (online)
Випуск Том 19, № 2, 2016 (червень)
Сторінки 44–49

 

Автори

О. М. Хлуд, Інститут проблем машинобудування ім. А. М. Підгорного НАН України (61046, Україна, м. Харків, вул. Пожарського, 2/10), e-mail: hlud.olga@mail.ru

 

Анотація

Розглядається задача оптимізації упаковки гомотетичних однаково орієнтованих еліпсоїдів. Будується математична модель у вигляді задачі нелінійного програмування. Пропонується алгоритм пошуку локально оптимальних розв’язків з використанням гомотетичних перетворень еліпсоїдів та оптимізаційної процедури, що дозволяє звести задачу з великою кількістю нерівностей до послідовності задач з меншим числом нерівностей. Наводяться результати чисельних експериментів.

 

Ключові слова: оптимальна упаковка, гомотетичні еліпсоїди, phi-функції, нелінійне програмування, процедура LOFRT

 

Література

  1. Wright, S. J. Packing Ellipsoids with Overlap / S. J. Wright // SIAM – 2013. Vol. 55 (4). – P. 671–706. https://doi.org/10.1137/120872309
  2. Kallrath, J. Packing ellipsoids into volume-minimizing rectangular boxes / J. Kallrath // Global Optimization. – 2015. – P. 1–32. https://doi.org/10.1007/s10898-015-0348-6
  3. Pankratov, A. Quasi-phi-functions in packing of ellipsoids / A. Pankratov, T. Romanova, O. Khlud // Radioelectronics & Informatics. – 2015. – Vol. 68. – P. 37–42.
  4. Lubachevsky, B. D. Geometric properties of random disk packings / B. D. Lubachevsky, F. H Stillinger // Statistical Physics. – 1990. – Vol. 60. – P. 561–583. https://doi.org/10.1007/BF01025983
  5. Bennell, J. A. A tutorial in irregular shape packing problem / J. A. Bennell, J. F. Oliveira // Oper. Research Soc. ­ 2009. –Vol. 60. P. 93 – 105. https://doi.org/10.1057/jors.2008.169
  6. Chernov, N.  Mathematical model and efficient algorithms for object packing problem / N. Chernov, Yu. Stoyan, T. Romanova // Computational Geometry: Theory and Appl. – 2010. – Vol. 43, № 5. – P. 533–553. https://doi.org/10.1016/j.comgeo.2009.12.003
  7. Стецюк, П. І. NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер / П. І. Стецюк, Т. Є. Романова, І. О. Субота // Теорія оптимальних рішень: зб. наук. пр. – Київ: Ін-т кібернетики ім. В. М. Глушкова НАН України. – С. 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 Operational Research. – 2004. – Vol. 156. – P. 590–600. https://doi.org/10.1016/S0377-2217(03)00137-1
  9. Stoyan, Y. Quasi-phi-functions and optimal packing of ellipses / Y. Stoyan, A. Pankratov, T. Romanova // Global Optimization. – 2015. – Vol. 65. – P. 283–307. https://doi.org/10.1007/s10898-015-0331-2

 

Надійшла до редакції 03 квітня 2016 р.