Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2016.05.003

Данилин А.Н., Комяк В.В., Комяк В.М., Панкратов А.В. Упаковка эллипсов в прямоугольник минимальных размеров.  Управляющие системы и машины. 2016. № 5. С. 3–9.

Abstract on English.

УДК 616.12-07

Данілін О.М. – ад’юнкт, Нац. ун-т цивільного захисту України (Харків)

Комяк В.В. – к.т.н., Нац. ун-т цивільного захисту України (Харків)

Комяк В.М. – д.т.н., Нац. ун-т цивільного захисту України (Харків)

Панкратов О.В. – д.т.н., Ін-т проблем машинобудування ім. А.М. Підгорного НАН України (Харків)

Упаковка еліпсів  в прямокутник мінімальних розмірів 

Розглянуто задачу упаковки набору еліпсів у прямокутник мінімальних розмірів. Для моделювання відносин неперетинання еліпсів і його належності контейнеру використано phi-функції і квазі-phi-функції. Побудовано математичну модель у вигляді задачі нелінійної оптимізації. Запропоновано ефективний алгоритм пошуку локально-оптимальних рішень.

 Загрузить полный текст в PDF (на русском).

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

СПИСОК ПОСИЛАНЬ

1. Toth L.F. Packing of ellipses with continuously distributed area. J. of Discrete Mathematics. 1986. 60. P. 263–267. doi:10.1016/0012-365X(86)90018-X.
2. An ellipse-based discrete element model for granular materials / J.M. Ting, M. Khwaja, L.R. Meachum et al. Numerical and Analytical Methods in Geomechanics. 1993. 17 (9). P. 603–623. doi:10.1002/nag. 1610170902.
3. Feng Y., Han K., Owen D. An Advancing Front Packing of Polygons, Ellipses and Spheres. Discrete Element Methods. 2002. P. 93–98. doi:10.1061/40647(259)17.
4. Vickers G.T. Nested Ellipses. Appl. Probab. Trust. 2009. 41 (3). P. 131–137.
5. Xu W.X., Chen H.S., Lv Z. An overlapping detection algorithm for random sequential packing of elliptical particles. Physica. 2011. 390. P. 2452–2467. doi:10.1016/j.physa.2011.02.048.
6. Kallrath J., Rebennack S. Cutting Ellipses from Area-Minimizing Rectangles. J. of Global Optimization. 2013. – 59 (2–3). P. 405–437. doi:10.1007/s10898-013-0125-3.
7. Kallrath J. Cutting Circles and Polygons from Area-Minimizing Rectangles. Ibid. 2008. 43 (2–3). P. 299–328.  doi:10.1007/s10898-007-9274-6.
8. Панкратов А.В., Романова Т.Е., Суббота И.А. Оптимальная упаковка эллипсов с учетом допустимых расстояний. Журнал обчислювальної математики. 2014. T. 1. C. 27–42.
9. Stoyan Yu., Pankratov A.,  Romanova T. Quasi-phi-functions and optimal packing of ellipses. J. of Glob. Optim. 2015. P. 283–307. DOI: 10.1007/s10898-015-0331-2.
10. Квази-phi-функции для математического моделирования отношений геометрических / Ю.Г. Стоян, А.В. Панкратов, Т.Е. Романова и др. Доп. Нац. акад. наук України. 2014. T. 9. C. 49–54.
11. Optimized Object Packings Using Quasi-Phi-Functions / Yu. Stoyan, T. Romanova, A. Pankratov et al. Vol. 105 of the series Springer Optimization and Its Applications. 2015. P. 265–293.
12. Birgin E.G., Lobato R., Martínez J.M. Packing Ellipsoids by Nonlinear Optimization. J. of Global Optim. 2016. 65. P. 709–743.
13. Packing circles within ellipses / E.G. Birgin, L.H. Bustamante, H.F. Callisaya et al. Int. transactions in operational res. 2013. 20 (3). P. 365–389. doi:10.1111/ itor.12006.
14. Birgin E.G.,  Martinez J.M. Practical Augmented Lagrangian Methods for Constrained Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014.

15. General Ellipse Packings in an Optimized Circle Using Embedded Lagrange Multipliers (Submitted for publication January 2016) / Frank J. Kampas, János D. Pintér, Ignacio Castillo et al. Global Optimization Submissions. 2016. http://www.optimization-online.org/ DB_FILE/2016/01/5293.pdf.
16. Kampas Frank J., Castillo Ignacio,  Pintér János D. General Ellipse Packings in Optimized Regular Polygons, (Submitted for publication Feb. 2016). Global Optimization Submissions. 2016. http://www.optimization-online.org/DB_FILE/ 2016/03/5348.pdf.
17. Wachter A., Biegler L.T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming. 2006. 106 (1). P. 25–57. doi:10.1007/s10107-004-0559-y.
18. Математическая модель индивидуально-поточного движения людских и транспортных потоков / А.Н. Данилин, В.В. Комяк, В.М. Комяк и др. Вестн. Херсон. нац. техн. ун-та. Херсон: ХНТУ, 2016. № 3(58). С. 501–505.

Надійшла 06.09.2016