Список выпусков > Серия «Математика». 2016. Том 15
Метод глобального поиска для задачи Мальфатти: случай четырёх кругов
Рассматривается задача Мальфатти, сформулированная 200 лет назад. Изначально, решение этой задачи предполагалось геометрическим методом. В 1994 году Залгаллер и Лос предложили для решения так называемый жадный алгоритм. Однако до сих пор не известна оптимальность этого алгоритма для задачи с n ≥ 4 кругами. В статье обобщается задача Мальфатти, сформулированная для трёх кругов, на случай четырёх кругов. Были исследованы шесть возможных вариантов вписания кругов в треугольник. Исследуемая задача формулируется как задача максимизации выпуклой функции на невыпуклом множестве, для решения которой используются условия глобальной оптимальности А. С. Стрекаловского. Предложен алгоритм для численного решения задачи Мальфатти, который сходится к глобальному решению. Вспомогательными задачами предложенного алгоритма являются задачи квадратичного программирования с квадратичными ограничениями. Эти задачи могут быть решены методом Лагранжа. Для проведения вычислительного эксперимента был рассмотрен треугольник с заданными вершинами. В работе приводятся численные результаты для заданного треугольника.
MSC
90C26
1. Enkhbat R. An algorithm for maximizing a convex function over a simple set. Journal of Global Optimization, 1996, vol.8, pp. 379-391.
2. Marco Andreatta, Andrs Bezdek and Jan P. Boroski, The Problem of Malfatti: Two Centuries of Debate. The Mathematical Intelligencer, 2011, vol. 33, issue 1, pp. 72-76.
3. V.N. Nefedov, Finding the Global Maximum of a Function of Several Variables on a Set Given by Inequality Constraints. Journal of Numerical Mathematics and Mathematical Physics, 1987, vol. 27(1), pp. 35-51.
4. Strekalovsky A.S. On the global extrema problem. Soviet Math. Doklad, 1987, vol. 292(5), pp. 1062-1066.
5. V.A. Zalgaller, An inequality for acute triangles. Ukr. Geom. Sb., 1991, vol. 34, pp. 10-25.
6. V.A. Zalgaller, The solution of Malfatti’s problem. Journal of Mathematical Sciences, 1994, vol.72, no 4, pp. 3163-3177.
7. G.A. Los, Malfatti’s Optimization Problem. [in Russian]. Dep. Ukr. NIINTI, July 5, 1988.
8. Saaty T. Integer Optimization Methods and Related Extremal Problems [Russian translation]. Moscow, Nauka, 1973.
9. Gabai H., Liban E. On Goldberg’s inequality associated with the Malfatti problem. Math. Mag., 1967, vol. 41, no 5, pp. 251-252.
10. Goldberg M. On the original Malfatti problem. Math. Mag., 1967, vol. 40, no 5, pp. 241-247.
11. H. Lob and H. W. Richmond, On the solutions of the Malfatti problem for a triangle. Proc. London Math. Soc., 1930, vol. 2, no 30, pp. 287-301.
12. C. Malfatti, Memoria sopra una problema stereotomico. Memoria di Matematica e di Fisica della Societa italiana della Scienze, 1803, vol. 10, no 1, pp. 235-244.