Задача упаковки шаров имеет множество приложений в различных областях науки и техники. Мы рассматриваем задачу максимизации суммы радиусов непересекающихся шаров, вписанных в многогранное множество в гильбертовом пространстве. Такая задача часто формулируется как задача упаковки. Рассматривая задачу в гильбертовом пространстве, мы формулируем ее как задачу оптимального управления с терминальным функционалом и терминальными ограничениями на конечный момент времени. Эта задача принадлежит к классу невыпуклых задач оптимального управления, поэтому применение градиентного метода не всегда гарантирует нахождения глобального решения для данной задачи. В работе показано, что задача для трех кругов в конечномерном пространстве является хорошо известной задачей Мальфатти [16]. Дополнительно доказано, что максимизация суммы радиусов кругов, вписанных в треугольник, эквивалентна задаче Мальфатти. Обобщенная задача Мальфатти рассматривалась как задача выпуклой максимизации в работах [6;7] с применением условия глобальной оптимальности А. С. Стрекаловского [17].

Энхбат Рэнцэн, д-р физ.-мат. наук, профессор, Национальный университет Монголии, Монголия, Улан-Батор, ул. Бага Тойру, 4; тел.: 976-99278403, e-mail: renkhbat46@yahoo.com

Даваадулам Жамсранжав, Ph. D., профессор, Национальный университет Монголии, Монголия, Улан-Батор, ул. Бага Тойру, 4; тел.: 976-99278403, e-mail: jdavaadulam@yahoo.com

Enkhbat R., Davaadulam J. Maximizing the Sum of Radii of Balls Inscribed in a Polyhedral Set // Известия Иркутского государственного университета. Серия Математика. 2019. Т. 28. С.138-145. https://doi.org/10.26516/1997-7670.2019.28.138

1. Birgin E.G., Gentil J.M. New and improved results for packing identical unitary radius circles within triangles, rectangles and strips.Computer and Operations Research, 2010, vol. 37, pp. 1318-1327. https://doi.org/10.1016/j.cor.2009.09.017
2. Birgin E.G., Martinez J.M., Ronconi D.P. Optimizing the packing of cylinders into a rectangular container: a nonlinear approach. European Journal of Operational Research, 2005, vol. 160, pp. 19-33. https://doi.org/10.1016/j.ejor.2003.06.018
3. Castillo I., Kampas F.J., Pinter J.D. Solving circle packing problems by global optimization: numerical results and industrial applications. European Journal of Operational Research, 2008, vol. 191, pp. 786-802. https://doi.org/10.1016/j.ejor.2007.01.054
4. Cui Y., Xu D. Strips minimization in two-dimensional cutting stock of circular items. Computers and Operations Research, 2010, vol. 37, pp. 621-629. https://doi.org/10.1016/j.cor.2009.06.005
5. Enkhbat R. Global optimization approach to Malfatti’s problem. Journal of Global Optimization, 2016, vol. 65, pp. 33-39. https://doi.org/10.1007/s10898-015-0372-6
6. 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.
7. Enkhbat R., Barkova M., Strekalovsky A.S. Solving Malfatti’s High Dimensional Problem by Global Optimization. Numerical Algebra, Control and Optimization, 2016, vol. 6, no. 2, pp. 153-160.
8. Fejos Toth L. Lagerungen in der Ebene auf der Kugel und im Raum. Zweite Auflage. Grundl Math. Springer-Verlag, Wiss, 1958.
9. Folkman J.H., Graham R.L. A packing inequality for compact subsets of the plane. Canadian Mathematical Bulletin, 1969, vol. 12, pp. 745-752.
10. Goldberg M. On the original Malfatti problem. Mathematics Magazine, 1967, vol. 40, no. 5, pp. 241-247. https://doi.org/10.1080/0025570X.1967.11975806
11. Grosso A.R., Jamali M.J.U., Locatelli M., Schoen F. Solving the problem of packing equal and unequal circles in a circular container. Journal of Global Optimization, 2010, vol. 47, no. 1, pp. 63-81. https://doi.org/10.1007/s10898-009-9458-3
12. Hamacher H.W., Drezner Z. Facility Location: Application and Theory. 2nd ed. Springer-Verlag, New York, 2004.
13. Hifi M., M’Hallah R. A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies. Advances in Operations Research, 2009, vol. 22. https://doi.org/10.1155/2009/150624.
14. Huang W., Ye T. Global optimization method for finding dense packings of equal circles in a circle. European Journal of Operational Research, 2011, vol. 210, pp. 516–524. https://doi.org/10.1016/j.ejor.2010.11.020
15. Lob H., Richmond H.W. On the solutions of the Malfatti problem for a triangle. Proc. London Math. Soc., 1930, vol. 2, no. 30, pp. 287–301. https://doi.org/10.1112/plms/s2-30.1.287
16. Malfatti C. Memoria sopra una problema stereotomico. Memoria di Matematica e di Fisica della Societa italiana della Scienze, 1803, vol. 10, no. 1, pp. 235–244.
17. Strekalovsky A.S. On the global extrema problem. Soviet Math. Doklad, 1987, vol. 292, no. 5, pp. 1062–1066.
18. Zalgaller V.A. An inequality for acute triangles. Ukrainskii Geometricheskii Sbornik,1991 , vol. 35, pp. 11–14.