Список выпусков > Серия «Математика». 2020. Том 31
Постановка задачи выпуклой оптимизации как общей
задачи упаковки сфер
Р. ЭнхбатРассмотрена общая задача упаковки сфер, которая заключается в упаковке непересекающихся сфер (шаров) с максимальным объемом в выпуклое множество. Эта проблема имеет важные приложения в науке и технике. Доказано, что эта задача эквивалентна выпуклой задаче максимизации, которая принадлежит классу глобальной оптимизации. Получены необходимые и достаточные условия для вписывания конечного числа шаров в выпуклый компакт. В двумерном случае задача упаковки сфер является классической задачей упаковки кругов. Показано, что 200-летняя задача Мальфатти [11] является частным случаем задачи упаковки кругов. Также рассмотрены существующие алгоритмы для решения задач упаковки кругов и их промышленное применение.
Энхбат Рэнцэн, д-р физ.-мат. наук, проф., Национальный университет Монголии, Монголия, Улан-Батор, ул. Бага Тойру, 4; тел.: 976-99278403, e-mail: renkhbat46@yahoo.com
Enkhbat R. Convex Maximization Formulation of General Sphere Packing Problem // Известия Иркутского государственного университета. Серия Математика. 2020. Т. 31. С. 142-149. https://doi.org/10.26516/1997-7670.2020.31.142
1. Dowsland K.A. Optimising the palletisation of cylinders in cases. OR Spectrum, 1991, vol. 13, pp. 204-212.
2. Drezner Z., Erkut E. Solving the continuous p-dispersionproblem using non-linear programming. Journal of the Operational Research Society, 1995, vol. 46, pp. 516-520.
3. Drezner Z. Discon: A new method for the layout problem. Operations Research, 1980, vol. 28, pp. 1375-1384.
4. Enhbat R. Global Optimization Approach to Malfatti’s Problem. Journal of Global Optimization, 2016, vol. 65, pp. 33-39.
5. Enkhbat R., Barkova M. Global Search Method for Solving Malfatti’s four-Circle Problem. The Bulletin of Irkutsk State University. Series Mathematics, 2016, vol.15, pp. 38-49.
6. Enkhbat R., Barkova M., Strekalovsky A. Solving Malfatti’s High Dimensional Problem by Global Optimization. Numerical Algebra, Control and Optimization, 2016, vol. 6, no. 2, pp. 153-160.
7. Erkut E. The discrete p-dispersion problem. European Journal of Operational Research, 1990, vol. 46, pp. 48-60.
8. Equation 5.19.4, NIST Digital Library of Mathematical Functions. 2013. Available at: http://dlmf.nist.gov/5.19E4.
9. Fraser H.J., George J.A. Integrated container loading software for pulp and paper industry. European Journal of Operational Research, 1994, vol. 77, pp. 466-474.
10. Hifi M., MHallah R. Approximate algorithms for constrained circular cutting problems. Computers and Operations Research, 2004, vol. 31, pp. 675-694.
11. Malfatti G. Memoria sopra una problema stereotomico. Memoria di Matematica e di Fisica della Societa italiana della Scienze, 1803, vol. 10, no. 1, pp. 235-244.
12. Martin C. How many robots can talk at the same time? Department of Mathematics, The Royal Institute of Technology, Stockholm, 2004. Available at: http://www.math.kth.se/optsyst/seminar/martinIII.html
13. Nguyen V.H., Strodiot J.J. Computing a Global Optimal Solution to a Design Centering Problem. Mathematical Programming, 1992, vol. 53, pp. 111-123.
14. Paris R.B., Kaminski D. Asymptotics and Mellin-Barnes Integrals. Cambridge University Press, 2001.
15. Strekalovsky A.S. On the global extrema problem. Soviet Math. Dokl., 1987, vol. 292, no. 5, pp. 1062-1066.
16. Strekalovsky A.S. On local search in d.c. optimization problems. Applied Mathematics and Computation, 2015, vol. 255, pp.73-83.
17. Vidigal L.M., Director S.W. A Design Centering Algorithm for Nonconvex Regions of Acceptability. IEEE Transactions on Computer-Aided-Design of Integrated Circuits and Systems, 1982, vol. CAD-1, pp. 13-24.
18. Wu Q.J., Bourland J.D. Morphology-Guided Radiosurgery Treatment Planning and Optimization for Multiple Isocenters. Medical Physics, 1992, vol. 26, pp. 2151-2160.
19. Wu A. Physics and Dosimetry of the Gamma Knife. Neurosurgery Clinics of North America, 1992, vol. 3, pp. 35-50.