Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров

• Date: 2009
• Main Authors: Стоян, Ю.Г., Пацук, В.Н.
• Format: Article
• Language: Russian
• Published: Видавничий дім "Академперіодика" НАН України 2009
• Subjects: Математика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/8507
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров / Ю. Г. Стоян, В.Н. Пацук // Доп. НАН України. — 2009. — № 5. — С. 41-45. — Бібліогр.: 8 назв. — рос.

Задача зводиться до низки задач мiнiмiзацiї радiуса куль при фiксованiй їх кiлькостi. Функцiя мети являє собою мiнiмум скiнченної кiлькостi опуклих гладких функцiй. Показано, що екстремуми досягаються у вершинах багатогранникiв Вороного, побудованих для центрiв куль. Для знаходження екстремумiв застосовується метод можливих напрямкiв у комбiнацiї з випадковим пошуком. Наведено низку чисельних прикладiв. The problem is reduced to a sequence of sphere radius minimization problems when fixing the number of spheres. The objective function is the minimum of a finite number of convex smooth functions. It is shown that the extrema are reached at the vertices of the Voronoi polyhedra constructed for the centers of the spheres. The method of feasible directions in combination with a random search is applied for searching the extrema. A number of numerical examples is given.