Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
Розглянуто математичні моделі та алгоритми оптимальної збалансованої розрідженої упаковки куль та кубів у сферичний та кубічний контейнери. Збалансованою розрідженою (задаються допустимі відстані між обʼєктами)упаковкою об’єктів у зовнішній контейнер є така їх упаковка, коли центр ваги сімейства об’...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2022 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2022
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/210890 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери / П.I. Стецюк, О.А. Березовський, О.П. Лиховид, М.Г. Стецюк // Проблеми керування та інформатики. — 2022. — № 3. — С. 87-100. — Бібліогр.: 11 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859676678703284224 |
|---|---|
| author | Стецюк, П.I. Березовський, О.А. Лиховид, О.П. Стецюк, М.Г. |
| author_facet | Стецюк, П.I. Березовський, О.А. Лиховид, О.П. Стецюк, М.Г. |
| citation_txt | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери / П.I. Стецюк, О.А. Березовський, О.П. Лиховид, М.Г. Стецюк // Проблеми керування та інформатики. — 2022. — № 3. — С. 87-100. — Бібліогр.: 11 назв. — укр. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розглянуто математичні моделі та алгоритми оптимальної збалансованої розрідженої упаковки куль та кубів у сферичний та кубічний контейнери. Збалансованою розрідженою (задаються допустимі відстані між обʼєктами)упаковкою об’єктів у зовнішній контейнер є така їх упаковка, коли центр ваги сімейства об’єктів збігається з центром зовнішнього контейнера, а відстані між об’єктами та відстані від них до зовнішнього контейнера булине менші за наперед задані величини. Наведено математичні моделі, послідовні та паралельні алгоритми розв’язання задач знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичний та кубічний контейнери. Наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у куб мінімального обʼєму за умови, що сторони всіх кубів паралельні осям координат, та опис негладкої штрафної функції для пошуку локальних мінімумів задачі. Досліджувані задач і відносяться до класу NP-важких задач. Математичні моделі представлені багатоекстремальними задачами нелінійного програмування. Для пошуку найкращого допустимого розвʼязку застосовується метод мультистарту у сполученні з r-алгоритмом Шора. Для цього задача зводиться до задачі безумовної оптимізації за допомогою штрафних функцій у вигляді функцій максимуму, а для пошуку локальних мінімумів із набору стартових точок застосовуються методи мінімізації негладких функцій, що базуються на використанні програмних реалізацій r-алгоритму. Математичні моделі та послідовні і паралельні алгоритми, що розглядаються, можна використати для розробки програмних засобів розв’язування задач знаходження збалансованої розрідженої упаковки сферичних та кубічних обʼєктів у сферичні та кубічні контейнери. Матеріал представлено в трьох розділах. У розд. 1 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичний контейнер. Описано послідовний та паралельний алгоритми знаходження найкращого допустимого розв’язку задач. У розд. 2 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженої упаковки куль різних радіусів у кубічний контейнер. Описано послідовний та паралельний алгоритми знаходження найкращого допустимого розв’язку задач. У розд. 3 наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у кубічний контейнер. Наведено опис негладкої штрафної функції для пошуку локальних мінімумів задачі.
Mathematical models and algorithms for optimal balanced sparse packing of spheres and cubes in spherical and cubic containers are considered. The balanced sparse packing (where permissible distances between objects are specified) is such that the center of gravity of the object family coincides with the center of the external container, and the distances between the objects and from them to the external container are no less than predefined values. Mathematical models are presented, along with sequential and parallel algorithms for solving the tasks of finding balanced sparse packing of spheres of different radii in spherical and cubic containers. A mathematical model of the task of finding balanced sparse packing of cubes in a cube of minimal volume is provided, under the condition that the sides of all cubes are parallel to the coordinate axes, along with the description of a non-smooth penalty function for searching local minima of the problem.
|
| first_indexed | 2026-03-14T22:04:45Z |
| format | Article |
| fulltext |
© П.І. СТЕЦЮК, О.А. БЕРЕЗОВСЬКИЙ, О.П. ЛИХОВИД, М.Г. СТЕЦЮК, 2022
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 87
ЧИСЕЛЬНІ МЕТОДИ В ЕКСТРЕМАЛЬНИХ ЗАДАЧАХ,
МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ
УДК 519.85
П.І. Стецюк, О.А. Березовський, О.П. Лиховид, М.Г. Стецюк
МАТЕМАТИЧНІ МОДЕЛІ ТА АЛГОРИТМИ
ОПТИМАЛЬНОЇ УПАКОВКИ КУЛЬ ТА КУБІВ
У СФЕРИЧНИЙ ТА КУБІЧНИЙ КОНТЕЙНЕРИ
Стецюк Петро Іванович
Інститут кібернетики ім. В.М. Глушкова НАН України, м. Київ,
stetsyukp@gmail.com
Березовський Олег Анатолійович
Інститут кібернетики ім. В.М. Глушкова НАН України, м. Київ,
o.a.berezovskyi@gmail.com
Лиховид Олексій Петрович
Інститут кібернетики ім. В.М. Глушкова НАН України, м. Київ,
o.lykhovyd@gmail.com
Стецюк Марія Григорівна
Інститут кібернетики ім. В.М. Глушкова НАН України, м. Київ,
danilyukm5@gmail.com
Розглянуто математичні моделі та алгоритми оптимальної збалансованої
розрідженої упаковки куль та кубів у сферичний та кубічний контейнери.
Збалансованою розрідженою (задаються допустимі відстані між обʼєктами)
упаковкою об’єктів у зовнішній контейнер є така їх упаковка, коли центр
ваги сімейства об’єктів збігається з центром зовнішнього контейнера, а
відстані між об’єктами та відстані від них до зовнішнього контейнера були
не менші за наперед задані величини. Наведено математичні моделі, послі-
довні та паралельні алгоритми розв’язання задач знаходження збалансова-
ної розрідженої упаковки куль різних радіусів у сферичний та кубічний
контейнери. Наведено математичну модель задачі знаходження збалансо-
ваної розрідженої упаковки кубів у куб мінімального обʼєму за умови, що
сторони всіх кубів паралельні осям координат, та опис негладкої штрафної
функції для пошуку локальних мінімумів задачі. Досліджувані задачі
відносяться до класу NP-важких задач. Математичні моделі представлені
багатоекстремальними задачами нелінійного програмування. Для пошуку
найкращого допустимого розвʼязку застосовується метод мультистарту у
сполученні з r-алгоритмом Шора. Для цього задача зводиться до задачі
безумовної оптимізації за допомогою штрафних функцій у вигляді функцій
максимуму, а для пошуку локальних мінімумів із набору стартових точок
застосовуються методи мінімізації негладких функцій, що базуються на
використанні програмних реалізацій r-алгоритму. Математичні моделі та
послідовні і паралельні алгоритми, що розглядаються, можна використати
для розробки програмних засобів розв’язування задач знаходження збалан-
mailto:stetsyukp@gmail.com
mailto:o.lykhovyd@gmail.com
88 ISSN 2786-6491
сованої розрідженої упаковки сферичних та кубічних обʼєктів у сферичні
та кубічні контейнери. Матеріал представлено в трьох розділах. У розд. 1
наведено математичну модель та алгоритми розв’язання задачі знаходжен-
ня збалансованої розрідженої упаковки куль різних радіусів у сферичний
контейнер. Описано послідовний та паралельний алгоритми знаходження
найкращого допустимого розв’язку задач. У розд. 2 наведено математичну мо-
дель та алгоритми розв’язання задачі знаходження збалансованої розрідженої
упаковки куль різних радіусів у кубічний контейнер. Описано послідовний та
паралельний алгоритми знаходження найкращого допустимого розв’язку
задач. У розд. 3 наведено математичну модель задачі знаходження збалансова-
ної розрідженої упаковки кубів у кубічний контейнер. Наведено опис
негладкої штрафної функції для пошуку локальних мінімумів задачі.
Ключові слова: задачі упаковки, розрідженість упаковки, негладка оп-
тимізація, квадратичні екстремальні задачі, паралельні алгоритми, висо-
копродуктивні обчислення.
Вступ
Задачі упаковки сфер та кубів у контейнери різноманітних форм нині актуа-
льні [1–4]. Вони мають важливе прикладне значення у космічній інженерії та ра-
кетобудуванні, в адитивному виробництві (3D-друк), при формуванні завадостій-
ких кодів, при дослідженні кристалічних структур, при проєктуванні та компоно-
вці різноманітних технологічних обʼєктів і систем, при оптимізації зберігання,
захисту та транспортування товарів і т.д. Підвищення конкурентноздатності алго-
ритмів розвʼязання подібних задач повʼязано як з новими теоретичними результа-
тами, так і з використанням нових (суперкомпʼютерних, грід- і хмарних) техноло-
гій. Зокрема, в роботі [1] запропоновано загальну методологію розвʼязання опти-
мізаційної задачі упаковки багатовимірних гіперсфер; у роботі [2] запропоновано
підхід для розвʼязання задачі заповнення прямокутного 3D-обʼєму нерівними
сферами, яка виникає в адитивному виробництві. Робота [3] присвячена застосу-
ванню технологій паралельних обчислень [5, 6] у системах зі спільною памʼяттю та
розподіленою памʼяттю для розвʼязання оптимізаційних задач геометричного проєк-
тування. Перша технологія ґрунтується на властивостях максимінних phi-функцій
для складених геометричних обʼєктів, а в другій технології використано стратегію
мультистарту та методи мінімізації негладких функцій [7]. Це дало змогу в декілька
разів зменшити витрати часу під час пошуку локально оптимальних розміщень
2D- та 3D-обʼєктів та отримати кращі результати за значенням цільової функції.
У даній роботі розглянуто математичні моделі, послідовні та паралельні ал-
горитми, що базуються на застосуванні методу мультистарту та програмних реа-
лізацій r-алгоритмів Шора [8, 9], для задач знаходження збалансованої розрідже-
ної упаковки сферичних обʼєктів у сферичний та кубічний контейнери. Також роз-
глянуто математичну модель задачі знаходження збалансованої розрідженої
упаковки кубів у куб мінімального обʼєму.
Математична модель та алгоритми знаходження
збалансованої розрідженої упаковки куль у сферичний контейнер
Нехай задано сімейство куль iS з радіусами ir й вагами ,iw = 1, , .i m
Будемо вважати, що центр ваги кулі iS знаходиться в її центрі. Збалансованою
упаковкою сімейства куль ,iS = 1, , ,i m у кулю S з обмеженнями на відстань
назвемо таку їх упаковку, щоб радіус кулі S був мінімальним, центр ваги
сімейства куль ,iS = 1, , ,i m збігався з центром зовнішньої кулі ,S а відстані
між кулями iS та відстані від них до зовнішньої кулі S були не менші за наперед
задані величини.
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 89
Не обмежуючи загальності, будемо вважати, що центр кулі S знаходиться на
початку системи координат. Нехай ( , , )i i ix y z — невідомий центр кулі ,S r —
невідомий радіус кулі .S Позначимо відстань між двома кулями: iS та ,jS
= 1, , ,i m = 1, , ,j m i j як ,ijd а відстані від куль ,iS = 1, , ,i m до
зовнішньої кулі S — як .id Позначимо відомі величини
=1
= ,/
m
i i j
j
w w
= 1, , ,i m і очевидну нижню границю на шуканий радіус
=1, ,
= max ( ).low i i
i m
r r d+
Тоді знаходженню збалансованої упаковки сімейства куль ,iS = 1, , ,i m із
заданими допустимими відстанями між ними відповідає багатоекстремальна
задача нелінійного програмування:
*
, , ,
= min
r x y z
r r (1)
з обмеженнями:
2 2 2 2( ) , =1, , ,i i i i ix y z r r d i m+ + − − (2)
2 2 2 2( ) ( ) ( ) ( ) , 1 < ,i j i j i j i j ijx x y y z z r r d i j m− + − + − + + (3)
=1 =1 =1
= 0, = 0, = 0,
m m m
i i i i i i
i i i
x y z (4)
.lowr r (5)
Цільова функція (1) є лінійною функцією i повʼязана з мінімізацією r -радіуса
кулі .S Квадратичні обмеження (2) означають, що кожна куля ,iS = 1, , ,i m
знаходиться усередині кулі ,S а відстань між нею і зовнішньою кулею S не
менша за наперед задану величину .id Квадратичні обмеження (3) гарантують,
що ніякі дві кулі із сімейства ,iS = 1, , ,i m не перетинаються (не мають
загальних внутрішніх точок), а відстань між ними не менша за наперед задану
величину. Лінійні обмеження (4) означають, що центр ваги сімейства куль ,iS
= 1, , ,i m локалізований на початку координат. Обмеження (5) забезпечує
додатнє значення параметру ,r потрібне для коректності обмежень (2).
Два альтернативних формулювання задачі рівноважної упаковки неоднако-
вих куль з обмеженнями на відстань наведені нижче. Вони вільні від обмежен-
ня (5), оскільки повʼязані з заміною обмежень (2) на наступні обмеження:
2 2 2 , = 1, , ,i i i i ix y z r r d i m+ + − − (6)
які автоматично враховують додатність змінної .r Перше формулювання є
задачею обернено-опуклого програмування. Вона повʼязана з мінімізацією ці-
льової функції (1) при обмеженнях (6), (3) і (4). Друге формулювання повʼязане з
мінімізацією негладкої опуклої функції й полягає в знаходженні
* 2 2 2
, 1, ,
min max { }i i i i i
x y i m
r x y z r d
=
= + + + − (7)
при обмеженнях (3), (4). Тут змінна r не використовується. Її оптимальне
значення *r визначається з мінімального значення негладкої цільової функції.
За допомогою негладких штрафів задача (1)–(5) зводиться до задачі безумов-
ної мінімізації негладкої функції
90 ISSN 2786-6491
1
, , ,
min { ( , , , ) ( , , , )},P
r x y z
f r x y z r r x y z= + (8)
де штрафна функція ( , , , )P r x y z має вигляд
1 1 2 2 3( , , , ) ( , , , ) ( , , ) max{0, }.P lowr x y z PF r x y z P F x y z P r r = + + − + (9)
Тут 1 2 3{ , , },P P P P= де ,kP =1, 2, 3,k — додатні штрафні коефіцієнти, а функції
1( , , , )F r x y z й 2( , , )F x y z визначаються так:
2 2 2 2
1
1
( , , , ) max{0, ( ) }
m
i i i i i
i
F r x y z x y z r r d
=
= + + − − − +
2 2 2 2
1 1
max{0, ( ) ( ) ( ) ( ) },
m m
i j i j i j i j ij
i j i
x x y y z z r r d
= = +
+ − − − − − − + + + (10)
2
=1 =1
( , , ) max 0, ,
m m
i i i i
i i
F x y z x x x x
= − − − +
=1 =1
max 0, ,
m m
i i i i
i i
y y y y
+ − − − +
=1 =1
max 0, , ,
m m
i i i i
i i
z z z z
+ − − −
(11)
де ,x y й z — задані допуски на відхилення координат центру ваги сімей-
ства куль від початку координат. Це означає, що обмеження (4) задачі замінюють-
ся на наступні :
=1
=1
=1
,
,
.
m
i i
i
m
i i
i
m
i i
i
x x x
y y y
z z z
−
−
−
Знаходження локального мінімуму задачі (1)–(5) можна замінити на пошук
локального мінімуму задачі (8)–(11), яка є задачею безумовної мінімізації
багатоекстремальної негладкої функції 1( , , , ).f r x y z Якщо при деяких додатніх
значеннях штрафних коефіцієнтів 1 2 3{ , , }P P P P= локальному мінімуму функції
1( , , , )f r x y z відповідає рівне нулю значення штрафної функції ( , , , ),P r x y z то
він буде локальним мінімумом задачі (1)–(5). Вибір штрафних коефіцієнтів 1,P
2P і 3P дозволяє враховувати точність виконання обмежень (2)–(5). Коефіцієнт 1P
відповідає за «сумарне порушення» квадратичних обмежень (2), (3), коефіцієнт 2P —
за «сумарне порушення» лінійних обмежень (4), а коефіцієнт 3P — за «порушення»
обмеження (5).
Послідовний алгоритм пошуку найкращого розвʼязку задачі (1)–(5) базується
на методі мультистарту з випадковим вибором стартових точок і модифікації
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 91
r-алгоритму Шора [8, 9] для пошуку локальних мінімумів функції 1( , , , ).f r x y z
Алгоритм не вимагає, щоб стартові точки були допустимими для задачі (1)–(5).
Його можна використовувати й за відсутності обмежень на центр ваги системи
кіл. Для цього досить покласти 2 0,P = що рівносильно тому, що із задачі (1)–(5)
виключаються обмеження (4).
Алгоритм полягає в наступному. Нехай ntest — кількість стартових точок,
які будуть генеруватися за допомогою датчика рівномірного розподілу в кулі
радіуса upr (найкраща верхня оцінка радіуса зовнішньої кулі). На початку
процесу найкраща верхня оцінка радіуса встановлюється рівною
1
( ),
m
up i
i
r r
=
= +
=1, , 1
max{ max , max },i ij
i m i j m
d d
= й послідовно уточнюється для кожної чергової
стартової точки в міру знаходження локального мінімуму з меншим значенням
цільової функції. Пошук локального мінімуму функції 1( , , , )f r x y z здійснюється
за допомогою модифікації r-алгоритму з постійним коефіцієнтом розтягу
простору й адаптивним регулюванням кроку [9, с. 384–385]. Найкращий
локальний мінімум функції 1( , , , ),f r x y z у якому реалізується близьке до нуля
значення штрафної функції ( , , , ),P r x y z приймаємо за розвʼязок задачі (1)–(5).
Йому відповідає найкраще значення радіуса upr і відповідні йому координати
центрів куль ( , , ),up up upx y z що розміщуються.
Паралельний алгоритм пошуку найкращого розвʼязку задачі (1)–(5) запускає
множинний пошук локальних розвʼязків за допомогою модифікації r-алгоритму.
Реалізація паралельного алгоритму використовує процедуру «Master-Slave» на
( 1)k + процесорах. Один з них вибирається «провідним» (Master), а інші k —
«підпорядкованими» (Slave). Ця процедура апробована в [10].
На початку обчислень в Master-процесорі випадковим чином генеруються k
стартових точок у кулі з радіусом
=1, , 11
( ), max{ max , max },
m
up i i ij
i m i j mi
r r d d
=
= + =
і пересилаються в Slave-процесори. Slave-процесор займається пошуком локаль-
ного мінімуму функції 1( , , , )f r x y z для отриманої ним стартової точки. Як тільки
r-алгоритм закінчує роботу на будь-якому Slave-процесорі, результат пошуку пе-
редається в Master-процесор. Якщо при цьому знайдено локальний мінімум
задачі (1)–(5), то значення радіуса зовнішньої кулі порівнюється з найкращим
зі знайдених до цього моменту значенням .upr Якщо радіус менше ,upr то він
стає новим значенням upr і далі запамʼятовуються відповідні йому значення
координат центрів куль, що розміщуються ( , , ).up up upx y z Потім Master-процесор
генерує нову стартову точку, яка передається для чергового пошуку локально-
го мінімуму в той Slave-процесор, для якого r-алгоритм закінчив роботу. Про-
цес завершується, якщо перевищено задану кількість стартових точок або за-
мовлений час.
Частковим випадком є програмна реалізація паралельного алгоритму для
кругів, виконана мовою програмування С++ у середовищі паралельного програ-
мування MPI. Вона оформлена як програма за назвою «Збалансована упаковка
кругів з заданими допустимими відстанями між ними» і докладно описана в [11],
92 ISSN 2786-6491
де наведено код програми, приклад протоколу її роботи й інтерфейс користувача
для роботи з програмою. У якості генератора псевдовипадкових чисел програма
використовує стандартну функцію rand з бібліотеки С++. Пошук локальних міні-
мумів здійснюється модулем ralgb5, який відповідає octave-коду модифікації
r-алгоритму з [9]. Програма призначена для роботи на кластері із середовищем
MPI під керуванням операційної системи Linux. Вона може працювати як на од-
ному процесорі, так і на багатьох паралельних процесорах.
Математична модель та алгоритми знаходження
збалансованої розрідженої упаковки куль у кубічний контейнер
Нехай задано сімейство куль iS з радіусами ir й вагами ,iw = 1, , .i m
Будемо вважати, що центр ваги кулі iS знаходиться в її центрі. Збалансованою
упаковкою сімейства куль ,iS = 1, , ,i m у куб C з обмеженнями на відстань
назвемо таку їх упаковку, щоб довжина сторони куба C була мінімальною, центр
ваги сімейства куль ,iS = 1, , ,i m збігався з центром куба ,C а відстані між ку-
лями iS та відстані від них до зовнішнього куба C були не менші за наперед
задані величини.
Не обмежуючи загальності, вважатимемо, що центр куба C знаходиться на
початку системи координат. Нехай ( , , )i i ix y z — невідомий центр кулі ,iS L —
половина невідомої довжини сторони куба .C Позначимо відстань між двома ку-
лями iS та ,jS = 1, , ,i m = 1, , ,j m ,i j як ,ijd а відстані від куль ,iS
= 1, , ,j m до зовнішнього куба C — як .id Позначимо відомі величини
=1
= ,/
m
i i j
j
w w = 1, , .i m Тоді знаходженню збалансованої упаковки сімейства
куль ,iS = 1, , ,i m із заданими допустимими відстанями між ними відповідає
багатоекстремальна задача нелінійного програмування
*
, , ,
= min 2
L x y z
L L (12)
з обмеженнями
( ) ( ), =1, , ,i i i i iL r d x L r d i m− + + − − (13)
( ) ( ), =1, , ,i i i i iL r d y L r d i m− + + − − (14)
( ) ( ), =1, , ,i i i i iL r d z L r d i m− + + − − (15)
2 2 2 2( ) ( ) ( ) ( ) ,1 < ,i j i j i j i j ijx x y y z z r r d i j m− + − + − + + (16)
=1
=1
=1
,
,
,
m
i i
i
m
i i
i
m
i i
i
x x x
y y y
z z z
−
−
−
(17)
де ,x y й z — задані допуски на відхилення координат центру ваги
сімейства куль від початку координат.
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 93
Цільова функція (12) є лінійною функцією i повʼязана з мінімізацією L —
половина довжини сторони куба .C Лінійні обмеження (13)–(15) означають, що
кожна куля ,iS = 1, , ,i m знаходиться усередині куба ,C а відстань між нею і
зовнішним кубом C не менша за наперед задану величину .id Квадратичні
обмеження (16) гарантують, що ніякі дві кулі із сімейства ,iS = 1, , ,i m не
перетинаються (не мають загальних внутрішніх точок), а відстань між ними не
менша за наперед задану величину. Лінійні обмеження (17) означають, що центр
ваги сімейства куль ,iS = 1, , ,i m локалізований на початку координат.
За допомогою негладких штрафів задача (12)–(17) зводиться до задачі безу-
мовної мінімізації негладкої функції
2
, , ,
min { ( , , , ) ( , , , )},P
L x y z
f L x y z L L x y z= + (18)
де штрафна функція ( , , , )P L x y z має вигляд
1 1 2 2 3 3( , , , ) ( , , , ) ( , , ) ( , , ).P L x y z PF L x y z P F x y z P F x y z = + + (19)
Тут 1 2 3{ , , },P P P P= де ,kP 1, 2, 3,k = — додатні штрафні коефіцієнти, а функції
1( , , , ),F L x y z 2( , , )F x y z й 3( , , )F x y z визначаються так:
1
1
( , , , ) max{0, ( ) , ( )}
m
i i i i i i
i
F L x y z L r d x x L r d
=
= − + + − − − − +
1
max{0, ( ) , ( )}
m
i i i i i i
i
L r d y y L r d
=
+ − + + − − − − +
1
max{0, ( ) , ( )},
m
i i i i i i
i
L r d z z L r d
=
+ − + + − − − − (20)
2( , , )F x y z =
2 2 2 2
1 1
max{0, ( ) ( ) ( ) ( ) },
m m
i j i j i j i j ij
i j i
x x y y z z r r d
= = +
= − − − − − − + + + (21)
3
=1 =1
( , , ) max 0, ,
m m
i i i i
i i
F x y z x x x x
= − − − +
=1 =1
max 0, ,
m m
i i i i
i i
y y y y
+ − − − +
=1 =1
max 0, ,
m m
i i i i
i i
z z z z
+ − − −
. (22)
Знаходження локального мінімуму задачі (12)–(17) можна замінити на пошук
локального мінімуму задачі (18)–(22), яка є задачею безумовної мінімізації
багатоекстремальної негладкої функції 2( , , , ).f L x y z Якщо при деяких додатніх
значеннях штрафних коефіцієнтів 1 2 3{ , , }P P P P= локальному мінімуму функції
2( , , , )f L x y z відповідає рівне нулю значення штрафної функції ( , , , ),P L x y z то
він буде локальним мінімумом задачі (12)–(17). Вибір штрафних коефіцієнтів 1,P
94 ISSN 2786-6491
2P і 3P дозволяє враховувати точність виконання обмежень (13)–(17). Коефіцієнт
1P відповідає за «сумарне порушення» лінійних обмежень (13)–(15), коефіцієнт
2P — за «сумарне порушення» квадратичних обмежень (16), а коефіцієнт 3P —
за «сумарне порушення» лінійних обмежень (17).
Послідовний алгоритм пошуку найкращого розвʼязку задачі (12)–(17)
базується на методі мультистарту з випадковим вибором стартових точок і моди-
фікації r-алгоритму Шора [9] для пошуку локальних мінімумів функції
2( , , , ).f L x y z Алгоритм не вимагає, щоб стартові точки були допустимими для
задачі (12)–(17). Його можна використовувати й за відсутності обмежень на центр
ваги системи кіл. Для цього досить покласти 2 0,P = що рівносильно тому, що із
задачі (12)–(17) виключаються обмеження (17).
Алгоритм полягає в наступному. Нехай ntest — кількість стартових точок, які
будуть генеруватися за допомогою датчика рівномірного розподілу в кубі з
довжиною сторони upL (найкраща верхня оцінка довжини сторони зовнішньої
кулі). На початку процесу найкраща верхня оцінка довжини сторони встанов-
люється рівною
=1, , 11
( ), max{ max , max }
m
up i i ij
i m i j mi
L r d d
=
= + = й послідовно уточ-
нюється для кожної чергової стартової точки в міру знаходження локального
мінімуму з меншим значенням цільової функції. Пошук локального мінімуму
функції 2( , , , )f L x y z здійснюється за допомогою модифікації r-алгоритму з
постійним коефіцієнтом розтягу простору й адаптивним регулюванням кроку [9].
Найкращий локальний мінімум функції 2( , , , ),f L x y z в якому реалізується
близьке до нуля значення штрафної функції ( , , , ),P L x y z приймаємо за роз-
вʼязок задачі (12)–(17). Йому відповідає найкраще значення довжини сторони upL
і відповідні йому координати центрів куль ( , , ),up up upx y z що розміщуються.
Паралельний алгоритм пошуку найкращого розвʼязку задачі (12)–(17) запус-
кає множинний пошук локальних розвʼязків за допомогою модифікації r-ал-
горитму. Реалізація паралельного алгоритму використовує процедуру «Master-
Slave» на ( 1)k + процесорах. Один з них вибирається «провідним» (Master), а інші
k — «підпорядкованими» (Slave). Ця процедура апробована в [10].
На початку обчислень в Master-процесорі випадковим чином генерується k
стартових точок у кубі з довжиною сторони
=1, ,1
( ), max{ max ,
m
up i i
i mi
L r d
=
= + =
1
max },ij
i j m
d
і пересилаються в Slave-процесори. Slave-процесор займається
пошуком локального мінімуму функції 2( , , , )f L x y z для отриманої ним старто-
вої точки. Як тільки r-алгоритм закінчує роботу на будь-якому Slave-процесорі,
то результат пошуку передається в Master-процесор. Якщо при цьому знайдений
локальний мінімум задачі (12)–(17), то значення довжини сторони зовнішнього
куба порівнюється з найкращим із знайдених до цього моменту значенням .upL
Якщо довжина сторони зовнішнього куба менша ,upL то вона стає новим зна-
ченням ,upL і далі запамʼятовуються відповідні їй значення координат центрів
куль, що розміщуються ( , , ).up up upx y z Потім Master-процесор генерує нову
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 95
стартову точку, яка передається для чергового пошуку локального мінімуму
в той Slave-процесор, для якого r-алгоритм закінчив роботу. Процес завершу-
ється, якщо перевищено задану кількість стартових точок або замовлений час.
Математична модель задачі збалансованої
розрідженої упаковки кубів у кубічний контейнер
У даному розділі описано математичну модель задачі знаходження
оптимальної збалансованої розрідженої упаковки кубів у кубічний контейнер за
умови, що сторони всіх кубів паралельні осям координат.
Нехай задано сімейство кубів iC зі сторонами ia й вагами ,iw = 1, , .i m
Будемо вважати, що центр ваги куба iC знаходиться в його центрі. Збалансова-
ною упаковкою сімейства кубів ,iC = 1, , ,i m у куб 0C з обмеженнями на
відстань назвемо таку їх упаковку, щоб довжина сторони куба 0C була міні-
мальною, центр ваги сімейства кубів ,iC = 1, , ,i m збігався з центром куба 0 ,C
а відстані між кубами iC та відстані від них до зовнішнього куба 0C були не
менші за наперед задані величини.
Крім цього, вважатимемо, що центр куба 0C знаходиться на початку системи
координат. Нехай ( , , )i i ix y z — невідомий центр куба ,iC 0a — невідома довжина
сторони куба 0.C Позначимо відстань між двома кубами iS та ,jS = 1, , ,i m
= 1, , ,j m i j як ,ijd а відстані від кубів ,iS = 1, , ,i m до зовнішнього куба
C — як .id Позначимо відомі величини
=1
= ,/
m
i i j
j
w w =i 1, , .m= Тоді
знаходженню збалансованої упаковки сімейства кубів ,iC = 1, , ,i m із
заданими допустимими відстанями між ними відповідає багатоекстремальна
задача нелінійного програмування:
0
*
0
, , , ,
min ,
a x y z t
f a= (23)
0 0
0 0
0 0
, = 1, , ,
2 2 2 2
, = 1, , ,
2 2 2 2
, = 1, , ;
2 2 2 2
i i
i i i
i i
i i i
i i
i i i
a a a a
d x d i m
a a a a
d y d i m
a a a a
d z d i m
− + − + −
− + − + −
− + − + −
(24)
(1 ), = 1, , , = 1, , , ,
2 2
(1 ), = 1, , , = 1, , , ,
2 2
(1 ), = 1, , , = 1, , , ;
2 2
j xi
i j ij ij
j yi
i j ij ij
j zi
i j ij ij
aa
x x d S t i m j m i j
aa
y y d S t i m j m i j
aa
z z d S t i m j m i j
− + + + −
− + + + −
− + + + −
(25)
96 ISSN 2786-6491
1, 1 ;
y yx z x z
ij ij ji jiij jit t t t t t i j m+ + + + + = (26)
2
2
2
( ) 0, = 1, , , = 1, , , ,
( ) 0, = 1, , , = 1, , , ,
( ) 0, = 1, , , = 1, , , ;
x x
ij ij
y y
ij ij
z z
ij ij
t t i m j m i j
t t i m j m i j
t t i m j m i j
− =
− =
− =
(27)
=1
=1
=1
,
,
,
m
i i
i
m
i i
i
m
i i
i
x x x
y y y
z z z
−
−
−
(28)
де ,x y й z — задані допуски на відхилення координат центру ваги сімейст-
ва кубів від початку координат.
Цільова функція (23) повʼязана з мінімізацією 0a — довжини сторони ку-
ба 0.C Лінійні обмеження (24) означають, що кожний куб ,iC = 1, , ,i m
знаходиться усередині куба 0 ,C а відстань між ним і зовнішним кубом 0C не
менша за наперед задану величину .id Обмеження (25)–(27) гарантують, що ніякі
два куба із сімейства ,iC = 1, , ,i m не перетинаються (не мають загальних
внутрішніх точок), а відстань між ними не менша за наперед задану величину. Їх-
ній зміст полягає в наступному. Для кожної пари кубів ( , )i j має виконуватися
одна з нерівностей:
0,
2 2
ji
i j ij
aa
x x d− + + +
0,
2 2
ji
j i ij
aa
x x d− + + +
0,
2 2
ji
i j ij
aa
y y d− + + +
0,
2 2
ji
j i ij
aa
y y d− + + +
0,
2 2
ji
i j ij
aa
z z d− + + +
0
2 2
ji
j i ij
aa
z z d− + + +
(наприклад, якщо справедлива перша нерівність, то куб i лежить лівіше ку-
ба j по координатній осі ,x а якщо справедлива друга нерівність — правіше).
Для врахування умови «або» (тобто, коли достатньо виконання хоча б одно -
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 97
го з обмежень) до нерівностей додано члени (1 ),x
ijS t− (1 ),
y
ijS t− (1 ),z
ijS t−
де S — достатньо великий штрафний множник (наприклад,
1
( ),
m
i
i
S a
=
= + =
=1, , 1
max{ max , max }).i ij
i m i j m
d d
= Обмеження (26) відповідає за те, щоб хоча б по
одній з координат один з будь-яких двох кубів, що розміщуються, лежав лівіше за
інший. Лінійні обмеження (28) означають, що центр ваги сімейства кубів ,iC
= 1, , ,i m локалізований на початку координат.
За допомогою негладких штрафів задача (23)–(28) зводиться до задачі безу-
мовної мінімізації негладкої функції
0
3 0 0 0
, , , ,
min { ( , , , , ) ( , , , , )},P
a x y z t
f a x y z t a a x y z t= + (29)
де штрафна функція 0( , , , , )P a x y z t має вигляд
0( , , , , )P a x y z t =
1 1 0 2 2 3 3 4 4 5 5( , , , ) ( , , , ) ( ) ( ) ( , , ).PF a x y z P F x y z t P F t P F t P F x y z= + + + + (30)
Тут 1 2 3 4 5{ , , , , },P P P P P P= де ,kP 1, 2, 3, 4, 5,k = — додатні штрафні коефіцієнти,
а функції 1 0( , , , ),F a x y z 2( , , , ),F x y z t 3( ),F t 4 ( ),F t 5( , , )F x y z визначаються так:
1 0( , , , )F a x y z =
0 0
1
0 0
1
max 0, ,
2 2 2 2
max 0, ,
2 2 2 2
m
i i
i i i i
i
m
i i
i i i i
i
a a a a
d x x d
a a a a
d y y d
=
=
= − + − − − + − +
+ − + − − − + − +
0 0
1
max 0, ,
2 2 2 2
m
i i
i i i i
i
a a a a
d z z d
=
+ − + − − − + −
, (31)
2( , , , )F x y z t =
1 1
max 0, (1 ), (1 )
2 2 2 2
m m
j jx xi i
i j ij ij j i ij ji
i j i
a aa a
x x d S t x x d S t
= = +
= − + + + − − − + + + − − +
1 1
max 0, (1 ), (1 )
2 2 2 2
m m
j jy yi i
i j ij j i ijij ji
i j i
a aa a
y y d S t y y d S t
= = +
+ − + + + − − − + + + − − +
1 1
max 0, (1 ), (1 ) ,
2 2 2 2
m m
j jz zi i
i j ij ij j i ij ji
i j i
a aa a
z z d S t z z d S t
= = +
+ − + + + − − − + + + − −
(32)
3( )F t =
1 1
max{( ) 1,1 ( )},
m m
y y y yx z x z x z x z
ij ij ji ij ij ij ji jiij ji ij ji
i j i
t t t t t t t t t t t t
= = +
= + + + + + − − + + + + + (33)
98 ISSN 2786-6491
2 2
4
1 1
( ) max{( ) , ( ) }
m m
x x x x
ij ij ij ij
i j
i j
F t t t t t
= =
= − − + +
2 2 2 2
1 1 1 1
max{( ) , ( ) } max{( ) , ( ) },
m m m m
y y y y z z z z
ij ij ij ijij ij ij ij
i j i j
i j i j
t t t t t t t t
= = = =
+ − − + + − − + (34)
5
=1 =1
( , , ) max 0, ,
m m
i i i i
i i
F x y z x x x x
= − − − +
=1 =1
max 0, ,
m m
i i i i
i i
y y y y
+ − − − +
=1 =1
max 0, , .
m m
i i i i
i i
z z z z
+ − − −
(35)
Знаходження локального мінімуму задачі (23)–(28) можна замінити на пошук
локального мінімуму задачі (29)–(35), яка є задачею безумовної мінімізації
багатоекстремальної негладкої функції 3 0( , , , , ).f a x y z t Для пошуку найкращого
допустимого розвʼязку задачі (23)–(28) можна застосувати, наприклад, метод
мультистарту, як описано в розд. 1, 2.
Враховуючи складність задачі, цікаво вивчити можливість отримання нижніх
оцінок
*,f щоб оцінювати якість локальних мінімумів. Для знаходження таких
оцінок у квадратичних оптимізаційних задачах загального вигляду
* *
0 0( ) inf ( ),
nx T R
f f x f x
= = { : ( ) 0, , ( ) 0, },LQ EQ
i iT x f x i I f x i I= =
можна застосувати, зокрема, двоїстий підхід [7]:
* *
( , ) 0
0
sup ( ( , ) inf ( , , )) ,
xA u v
v
u v L x u v f
=
= =
де T T( , , ) ( , ) ( , ) ( , )L x u v x A u v x b u v x c u v= + + — функція Лагранжа, u — вектор
двоїстих змінних, що відповідають обмеженням рівностей, v — вектор двоїстих
змінних, що відповідають обмеженням нерівностей; 0A = позначає невідʼємно
визначену матрицю. Використання теорії лагранжових двоїстих оцінок є перспек-
тивним, оскільки наявність лінійних обмежень дозволяє просто будувати функ-
ціонально надлишкові обмеження для уточнення цих оцінок без збільшення
розмірності вихідної задачі [7]. До того ж результати цих досліджень можна
поширити і на інший тип оцінок, отриманих шляхом використання SDP-релак-
сацій квадратичних оптимізаційних задач.
Висновок
Розглядаються математичні моделі для знаходження збалансованої розрідже-
ної упаковки куль різних радіусів у сферичний та кубічний контейнери та упаков-
ки кубів у кубічний контейнер. Досліджувані задачі відносяться до класу NP-важ-
ких. Для пошуку найкращого допустимого розвʼязку пропонується застосувати
метод мультистарту. В рамках цього методу задача зводиться до задачі безумов-
ної оптимізації за допомогою штрафних функцій у вигляді функцій максимуму,
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 3 99
а для пошуку локальних мінімумів із набору початкових точок пропонується за-
стосовувати r -алгоритм [7].
Наведено послідовні та паралельні алгоритми (мультистарт у сполученні з
модифікацією r -алгоритму [9]) для знаходження найкращого допустимого
розвʼязку задач упаковки сферичних обʼєктів у сферичний та кубічний контейне-
ри. Для задачі упаковки кубів у кубічний контейнер наведено негладку штрафну
функцію у вигляді функцій максимуму.
Для задач, що розглядаються, перспективними є дослідження математичних
моделей на основі pL -норм, коли 1.p Тоді обмеження, які означають, що
кожний обʼєкт знаходиться усередині контейнера, можна представити, наприклад,
у вигляді
1/( ) , = 1, , ,
p p p p
i i i ix y z r r i m+ + −
а обмеження
1/( ) , 1 < ,
p p p p
i j i j i j i jx x y y z z r r i j m− + − + − +
гарантують, що ніякі два обʼєкти не перетинаються. Використовуючи pL -норму,
при 2p = можна отримати математичну модель упаковки куль у сферичний кон-
тейнер, а при p = — кубів у кубічний контейнер.
Математичні моделі та послідовні і паралельні алгоритми, що розглядаються,
можна використати для розробки програмних засобів розвʼязування задач знаход-
ження збалансованої розрідженої упаковки сферичних та кубічних обʼєктів у сфе-
ричні та кубічні контейнери.
P. Stetsyuk, O. Berezovskyi, O. Lykhovyd, M. Stetsyuk,
MATHEMATICAL MODELS AND ALGORITHMS
FOR OPTIMAL PACKING OF BALLS AND CUBES
INTO SPHERICAL AND CUBIC CONTAINERS
Petro Stetsyuk
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv,
stetsyukp@gmail.com
Oleg Berezovskyi
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv,
o.a.berezovskyi@gmail.com
Oleksii Lykhovyd
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv,
o.lykhovyd@gmail.com
Mariia Stetsyuk
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv,
danilyukm5@gmail.com
The article considers mathematical models and algorithms for optimal balanced
sparse packing of spheres and cubes into spherical and cubic containers. A bal-
anced sparse (allowable distances between objects are specified) packing of ob-
jects into an outer container is such a packing that the center of gravity of the
family of objects coincides with the center of the outer container, and the dis-
tances between the objects as well as the distances from them to the outer con-
mailto:stetsyukp@gmail.com
mailto:o.lykhovyd@gmail.com
100 ISSN 2786-6491
tainer are not less than the predetermined values. Mathematical models, sequen-
tial and parallel algorithms for solving problems of finding a balanced sparse
packing of balls of different radii into spherical and cubic containers are given.
A mathematical model of the problem of finding a balanced sparse packing of
cubes into a cube of minimum volume, provided that the sides of all cubes are
parallel to the coordinate axes, and a description of the non-smooth penalty
function for finding local minima of the problem are given. The investigated
problems belong to the class of NP-hard problems. Mathematical models are
represented by multi-extremal nonlinear programming problems. To find the
best feasible solution, the multistart method is used in combination with Shor's r-
algorithm. For this, the problem is reduced to the unconditional optimization
problem using penalty functions in the form of maximum functions, and non-
smooth optimization methods based on the use of software implementations of r-
algorithm are used to find local minima from a set of starting points. Mathemati-
cal models and sequential and parallel algorithms under consideration can be
used to develop software tools for solving problems of finding a balanced sparse
packing of spherical and cubic objects into spherical and cubic containers. The
material is presented in three sections. The first section presents a mathematical
model and algorithms for solving the problem of finding a balanced sparse pack-
ing of balls of different radii into a spherical container. The sequential and paral-
lel algorithms for finding the best feasible problem solution are described. Sec-
tion 2 provides a mathematical model and algorithms for solving the problem of
finding a balanced sparse packing of balls of different radii into a cubic contain-
er. The sequential and parallel algorithms for finding the best feasible problem
solution are described. Section 3 presents a mathematical model of the problem
of finding a balanced sparse packing of cubes into a cubic container. A description of
the non-smooth penalty function for finding local minima of the problem is given.
Keywords: packing problems, packing sparsity, non-smooth optimization,
quadratic extremal problems, parallel algorithms, high-performance computing.
REFERENCES
1. Stoyan Y., Yaskov G., Romanova T., Litvinchev I., Yakovlev S., Cant J.M.V. Optimized packing
multidimensional hyperspheres: a unified approach. Mathematical Biosciences and Engineering.
2020. 17, N 6. P. 6601–6630. http://doi.org/10.3934/mbe.2020344.
2. Duriagina Z., Lemishka I., Litvinchev I., Marmolejo J.A., Pankratov A., Romanova T., Yaskov G.
Optimized filling of a given cuboid with spherical powders for additive manufacturing. Journal of
the Operations Research Society of China. 2020. http://doi.org/10.1007/s40305-020-00314-9.
3. Романова Т.Є., Стецюк П.І., Чугай А.М., Шеховцов С.Б. Технології паралельних обчислень
для розвʼязання оптимізаційних задач геометричного проектування. Кибернетика и си-
стемный анализ. 2019. № 6. С. 17–29. http://www.kibernetika.org/volumes/2019/numbers/
06/articles/02/ArticleDetailsUA.htm.
4. Стецюк П.И., Романова Т.Е. Равновесная упаковка шаров в шар минимального радиуса.
Международная конференция «Дискретная оптимизация и исследование операций»
(DOOR-2013). (Новосибирск, 24-28 июня 2013 г.).
5. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт-Петербург: БХВ-
Петербург, 2002. 608 с.
6. Кластерний комплекс Інституту кібернетики. Кластерний комплекс СКІТ. URL:
http://icybcluster.org.ua/.
7. Shor N.Z. Nondifferentiable optimization and polynomial problems. Boston/Dordrecht/London,
Kluwer Academic Publishers, 1998. 412 p. https://doi.org/10.1007/978-1-4757-6015-6.
8. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и си-
стемный анализ. 2017. 53, № 5. С. 43–57.
9. Стецюк П.И. Методы эллипсоидов и r-алгоритмы. Эврика: Кишинэу, 2014. 488 с.
10. Лиховид А.П. О реализации параллельного алгоритма для решения задач равновесной упа-
ковки. Теорія оптимальних рішень. Київ : Інститут кібернетики ім. В.М. Глушкова НАН
України, 2015. С. 154–159. http://dspace.nbuv.gov.ua/handle/123456789/112413.
11. Лиховид О.П., Стецюк П.І. Компʼютерна програма «Паралельна програма «Збалансована
упаковка кругів з заданими допустимими відстанями між ними». Свідоцтво про реєстрацію
авторського права на твір № 109298. Україна. Національний орган інтелектуальної власно-
сті державне підприємство «Український інститут інтелектуальної власності» (Укрпатент).
Дата реєстрації 10.11.2021. 40 c.
Отримано 19.07.2022
http://doi.org/10.3934/mbe.2020344
http://doi.org/10.1007/s40305-020-00314-9
http://www.kibernetika.org/volumes/2019/numbers/06/articles/02/ArticleDetailsUA.html
http://www.kibernetika.org/volumes/2019/numbers/06/articles/02/ArticleDetailsUA.html
http://icybcluster.org.ua/
https://doi.org/10.1007/978-1-4757-6015-6
http://dspace.nbuv.gov.ua/handle/123456789/112413
|
| id | nasplib_isofts_kiev_ua-123456789-210890 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Ukrainian |
| last_indexed | 2026-03-14T22:04:45Z |
| publishDate | 2022 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.I. Березовський, О.А. Лиховид, О.П. Стецюк, М.Г. 2025-12-20T09:38:59Z 2022 Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери / П.I. Стецюк, О.А. Березовський, О.П. Лиховид, М.Г. Стецюк // Проблеми керування та інформатики. — 2022. — № 3. — С. 87-100. — Бібліогр.: 11 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210890 519.85 10.34229/2786-6505-2022-3-7 Розглянуто математичні моделі та алгоритми оптимальної збалансованої розрідженої упаковки куль та кубів у сферичний та кубічний контейнери. Збалансованою розрідженою (задаються допустимі відстані між обʼєктами)упаковкою об’єктів у зовнішній контейнер є така їх упаковка, коли центр ваги сімейства об’єктів збігається з центром зовнішнього контейнера, а відстані між об’єктами та відстані від них до зовнішнього контейнера булине менші за наперед задані величини. Наведено математичні моделі, послідовні та паралельні алгоритми розв’язання задач знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичний та кубічний контейнери. Наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у куб мінімального обʼєму за умови, що сторони всіх кубів паралельні осям координат, та опис негладкої штрафної функції для пошуку локальних мінімумів задачі. Досліджувані задач і відносяться до класу NP-важких задач. Математичні моделі представлені багатоекстремальними задачами нелінійного програмування. Для пошуку найкращого допустимого розвʼязку застосовується метод мультистарту у сполученні з r-алгоритмом Шора. Для цього задача зводиться до задачі безумовної оптимізації за допомогою штрафних функцій у вигляді функцій максимуму, а для пошуку локальних мінімумів із набору стартових точок застосовуються методи мінімізації негладких функцій, що базуються на використанні програмних реалізацій r-алгоритму. Математичні моделі та послідовні і паралельні алгоритми, що розглядаються, можна використати для розробки програмних засобів розв’язування задач знаходження збалансованої розрідженої упаковки сферичних та кубічних обʼєктів у сферичні та кубічні контейнери. Матеріал представлено в трьох розділах. У розд. 1 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичний контейнер. Описано послідовний та паралельний алгоритми знаходження найкращого допустимого розв’язку задач. У розд. 2 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженої упаковки куль різних радіусів у кубічний контейнер. Описано послідовний та паралельний алгоритми знаходження найкращого допустимого розв’язку задач. У розд. 3 наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у кубічний контейнер. Наведено опис негладкої штрафної функції для пошуку локальних мінімумів задачі. Mathematical models and algorithms for optimal balanced sparse packing of spheres and cubes in spherical and cubic containers are considered. The balanced sparse packing (where permissible distances between objects are specified) is such that the center of gravity of the object family coincides with the center of the external container, and the distances between the objects and from them to the external container are no less than predefined values. Mathematical models are presented, along with sequential and parallel algorithms for solving the tasks of finding balanced sparse packing of spheres of different radii in spherical and cubic containers. A mathematical model of the task of finding balanced sparse packing of cubes in a cube of minimal volume is provided, under the condition that the sides of all cubes are parallel to the coordinate axes, along with the description of a non-smooth penalty function for searching local minima of the problem. uk Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Чисельні методи в екстремальних задачах, методи наближення функцій Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери Mathematical models and algorithms for optimal packing of balls and cubes into spherical and cubic containers Article published earlier |
| spellingShingle | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери Стецюк, П.I. Березовський, О.А. Лиховид, О.П. Стецюк, М.Г. Чисельні методи в екстремальних задачах, методи наближення функцій |
| title | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери |
| title_alt | Mathematical models and algorithms for optimal packing of balls and cubes into spherical and cubic containers |
| title_full | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери |
| title_fullStr | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери |
| title_full_unstemmed | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери |
| title_short | Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери |
| title_sort | математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери |
| topic | Чисельні методи в екстремальних задачах, методи наближення функцій |
| topic_facet | Чисельні методи в екстремальних задачах, методи наближення функцій |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210890 |
| work_keys_str_mv | AT stecûkpi matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičniitakubíčniikonteineri AT berezovsʹkiioa matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičniitakubíčniikonteineri AT lihovidop matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičniitakubíčniikonteineri AT stecûkmg matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičniitakubíčniikonteineri AT stecûkpi mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers AT berezovsʹkiioa mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers AT lihovidop mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers AT stecûkmg mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers |