Упаковка большого числа конгруэнтных шаров в цилиндре
Розглядається задача пакування максимальної кiлькостi конгруентних куль одиничного радiуса в прямому круговому цилiндрi заданих розмiрiв. Запропоновано математичну модель задачi. Вважається, що радiуси куль є змiнними. Глобальний максимум задачi забезпечує пакування всiх куль. Алгоритм побудови поча...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/19138 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Упаковка большого числа конгруэнтных шаров в цилиндре / Г.Н. Яськов // Доп. НАН України. — 2009. — № 12. — С. 45-49. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-19138 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-191382011-04-21T12:05:23Z Упаковка большого числа конгруэнтных шаров в цилиндре Яськов, Г.Н. Інформатика та кібернетика Розглядається задача пакування максимальної кiлькостi конгруентних куль одиничного радiуса в прямому круговому цилiндрi заданих розмiрiв. Запропоновано математичну модель задачi. Вважається, що радiуси куль є змiнними. Глобальний максимум задачi забезпечує пакування всiх куль. Алгоритм побудови початкового пакунку грунтується на гратчастому пакуваннi куль. Результати порiвнюються з кращими вiдомими результатами. Наведено чисельнi приклади. The paper considers the problem of packing a maximal number of congruent spheres of the unit radius into a straight circular cylinder of given sizes. A mathematical model of the problem is suggested. Radii of all spheres are supposed to be variable A global maximum of the problem ensures the packing of all spheres. An algorithm of constructing a starting package is based on a lattice packing of spheres. Results are compared with the best known ones. A number of numerical examples are given. 2009 Article Упаковка большого числа конгруэнтных шаров в цилиндре / Г.Н. Яськов // Доп. НАН України. — 2009. — № 12. — С. 45-49. — Бібліогр.: 10 назв. — рос. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/19138 519.85 ru Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Яськов, Г.Н. Упаковка большого числа конгруэнтных шаров в цилиндре |
| description |
Розглядається задача пакування максимальної кiлькостi конгруентних куль одиничного радiуса в прямому круговому цилiндрi заданих розмiрiв. Запропоновано математичну модель задачi. Вважається, що радiуси куль є змiнними. Глобальний максимум задачi забезпечує пакування всiх куль. Алгоритм побудови початкового пакунку грунтується на гратчастому пакуваннi куль. Результати порiвнюються з кращими вiдомими результатами. Наведено чисельнi приклади. |
| format |
Article |
| author |
Яськов, Г.Н. |
| author_facet |
Яськов, Г.Н. |
| author_sort |
Яськов, Г.Н. |
| title |
Упаковка большого числа конгруэнтных шаров в цилиндре |
| title_short |
Упаковка большого числа конгруэнтных шаров в цилиндре |
| title_full |
Упаковка большого числа конгруэнтных шаров в цилиндре |
| title_fullStr |
Упаковка большого числа конгруэнтных шаров в цилиндре |
| title_full_unstemmed |
Упаковка большого числа конгруэнтных шаров в цилиндре |
| title_sort |
упаковка большого числа конгруэнтных шаров в цилиндре |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2009 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/19138 |
| citation_txt |
Упаковка большого числа конгруэнтных шаров в цилиндре / Г.Н. Яськов // Доп. НАН України. — 2009. — № 12. — С. 45-49. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT âsʹkovgn upakovkabolʹšogočislakongruéntnyhšarovvcilindre |
| first_indexed |
2025-07-02T20:03:54Z |
| last_indexed |
2025-07-02T20:03:54Z |
| _version_ |
1836566848928219136 |
| fulltext |
УДК 519.85
© 2009
Г.Н. Яськов
Упаковка большого числа конгруэнтных шаров
в цилиндре
(Представлено членом-корреспондентом НАН Украины Ю.Г. Стояном)
Розглядається задача пакування максимальної кiлькостi конгруентних куль одинично-
го радiуса в прямому круговому цилiндрi заданих розмiрiв. Запропоновано математичну
модель задачi. Вважається, що радiуси куль є змiнними. Глобальний максимум задачi
забезпечує пакування всiх куль. Алгоритм побудови початкового пакунку грунтується
на гратчастому пакуваннi куль. Результати порiвнюються з кращими вiдомими ре-
зультатами. Наведено чисельнi приклади.
Задачи упаковки шаров возникают в различных сферах деятельности человека. Такие зада-
чи актуальны при анализе структуры нефтеносных пород, моделировании пористых сред,
структуры гранулированных материалов, полидисперсных слоистых систем, структуры на-
нопленок, при изучении структуры белка в биологии, жидкостей и газов в химии и физи-
ке [1–5]. Среди них наиболее распространенной является задача плотной упаковки большо-
го числа шаров одинакового размера [1], которая возникает, например, при моделировании
процессов в активной зоне ядерного реактора.
Предметом исследования данной работы является задача упаковки большого числа кон-
груэнтных шаров в цилиндрическом контейнере.
При решении задач упаковки большого числа шаров в контейнеры (цилиндр, паралле-
лепипед) используются либо случайные упаковки, полученные методом Монте–Карло (см.,
например, [4, 5]), либо алгоритмы оптимизации по группам переменных [1].
Ниже предлагается метод упаковки большого числа конгруэнтных шаров (больше 200)
на основе оригинальной математической модели задачи. Новизна предложенного метода
состоит в том, что радиусы шаров рассматриваются как переменные.
Рассмотрим конгруэнтные шары Si радиусов ri = r, i ∈ I = {1, 2, . . . , n}, и цилиндр
C = {(x, y, z) ∈ R3 : x2 + y2 − ρ2 6 0, 0 6 z 6 h}.
Местоположение шара Si в пространстве R3 определяется координатами его центра ui =
= (xi, yi), i ∈ I.
Задача. Найти вектор u = (u1, u2, . . . , un) ∈ R3n, который обеспечивает упаковку ма-
ксимального числа λ∗ шаров Si, i ∈ I, в цилиндре C.
Для получения верхней оценки Λ+ максимального количества шаров используется ко-
эффициент заполнения π/
√
18 ≈ 0,74 гексагональной решетчатой упаковки шаров. Тогда
Λ+ =
[
π(ρ/r)2h√
18
]
,
где [•] — целая часть от •. В качестве нижней оценки Λ− может быть выбрано количество
узлов в решетчатой упаковке шаров, попадающих в цилиндр. Таким образом, Λ−
6 λ∗
6
6 Λ+.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №12 45
Полагаем, что радиусы ri шаров Si, i ∈ I, являются переменными. Обозначим vn =
= (r1, r2, . . . , rn) ∈ Rn.
Рассмотрим последовательность задач:
Fλ(X
λ∗) = max
Xλ∈Dλ
Fλ(X
λ), λ = Λ−,Λ− + 1, . . . ,Λ∗ < Λ+, (1)
где
Fλ(X
λ) =
λ
∑
i=1
ri, Xλ = (vλ, uλ), vλ = (r1, r2, . . . , rλ), uλ = (u1, u2, . . . , uλ), (2)
Dλ =
{
Xλ ∈ R4n : Φij(ri, rj , ui, uj) > 0, 0 < i < j = 1, 2, . . . , λ,Φi(ri, ui) > 0,
r − ri > 0, ri > 0, i = 1, 2, . . . , λ,
}
, (3)
Φij(ri, rj , ui, uj) = (xi − xj)
2 + (yi − yj)
2 + (zi − zj)
2 − (ri + rj)
2, (4)
Φi(ri, ui) = x2i + y2i − (ρ− ri)
2. (5)
Отметим некоторые особенности математической модели (1)–(5):
1) область допустимых решений Dλ описывается линейными и квадратичными нера-
венствами;
2) вследствие линейности функции Fλ(X
λ) локальные максимумы задачи (1)–(5) дости-
гаются в крайних точках области Dλ;
3) задача (1)–(5) является NP -трудной [6];
4) если Fλ+1(X
(λ+1)∗) < (λ+1)r и Fλ(X
λ∗) = λr, где Xλ∗ и X(λ+1)∗ — точки глобальных
максимумов, то точке Xλ∗ соответствует упаковка λ∗ = λ шаров.
Выбор слишком малого λ0, близкого к Λ−, приведет к длительной процедуре решения
задач вида (1)–(5) для последовательно возрастающих значений λ. С другой стороны, если
сразу выбрать большое значение λ0, близкое к Λ+, то придется тратить еще больше времени
для решения задач вида (1)–(5) для последовательно убывающих значений λ.
Гексагональная решетка дает хорошую упаковку шаров в случае, если ρ/r > 10. По мере
уменьшения соотношения ρ/r возрастают так называемые стеновые эффекты [5]. В этом
случае плотность упаковки у стенок цилиндра уменьшается. Для уменьшения “стеновых
эффектов” можно произвести сдвиг решетки относительно оси цилиндра или использовать
в качестве начальной случайную упаковку шаров с радиусом, меньшим r.
Если ρ/r 6 10, то полученную методом Монте–Карло [4, 5] упаковку выбираем в ка-
честве начального размещения. Если же ρ/r > 10, начальную точку строим на основании
решетчатой упаковки шаров. Радиус шаров в решетке подбирается так, чтобы количество
размещенных шаров было λ = λ0.
Координаты центров шаров радиуса, которые образуют гексагональную решетку при
упаковке в цилиндр, можно найти по формулам:
(x0k, y
0
l , z
0
m) =
(
±2(k − 1)τ,±
√
3(2l − 2)τ,
(
1 + 4(m− 1)
√
2
3
)
τ
)
,
(x0k, y
0
l , z
0
m) =
(
±2(k − 1)τ + τ,±
√
3(2l − 1)τ,
(
1 + 4(m− 1)
√
2
3
)
τ
)
,
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №12
(x0k, y
0
l , z
0
m) =
(
±2(k − 1)τ − τ,±
√
3(2l − 2)τ − τ
√
3,
(
1 + 4(m− 1)
√
2
3
)
τ
)
, (6)
(x0k, y
0
l , z
0
m) =
(
±2(k − 1)τ,±
√
3(2l − 1)τ − τ
√
3,
(
1 + 4(m− 1)
√
2
3
)
τ
)
,
k, l,m = 1, 2, . . . ,K,
(x0k)
2 + (y0l )
2
6 (ρ− τ)2, τ 6 z0m 6 h− τ.
Решетка может быть сформирована последовательным повторением двух слоев, сме-
щенных один относительно другого на τ в направлении оси OX, на τ
√
3 — в направлении
оси OY и на
√
2/3τ — в направлении оси OZ. В свою очередь, каждый из этих слоев мо-
жет быть сформирован последовательным повторением двух рядов шаров, находящихся на
одной высоте. Один ряд шаров смещен относительно другого в направлении оси OY на
√
3τ .
Используя формулы (6), выбираем начальное количество и начальную упаковку шаров.
Для решения задачи (1)–(5) применяем модификацию метода возможных направлений Зой-
тендейка и концепцию ε-активных неравенств [7–9].
Пусть Γ = λ(λ − 1)/2, g1(X) = Φ12(X), g2(X) = Φ13(X), . . ., g(λ−1)(X) = Φ1,(λ−1)(X),
gλ(X) = Φ23(X), . . ., gΓ(X) = Φ(λ−1),λ(X), gΓ+1(X) = Φ1(X), . . ., gΓ+λ(X) = Φλ(X),
gΓ+λ+1(X) = r1, . . ., gΓ+2λ(X) = rλ, gΓ+2λ+1(X) = r − r1, . . ., gΓ+3λ(X) = r − rλ, I1 =
= {1, 2, . . . ,Γ+λ}, I2 = {Γ+λ+1,Γ+λ+2, . . . ,Γ+2λ}, I2 = {Γ+2λ+1,Γ+2λ+2, . . . ,Γ+3λ},
т. е. для удобства переиндексируем все неравенства в (3)–(5) для данного λ.
Решение задачи (1)–(5) вычисляется по итерационной формуле X(l+1) = X l + tlZ l, l =
= 0, 1, . . ., где X0 = Xλ0, tk > 0, вектор Zk является решением следующей задачи линейного
программирования:
max
(κ,Zk)∈Gk⊂R3λ+1
κ, (7)
Gk =
{
(κ,Zk) ∈ R3λ+1 : (Fλ(X
k), Zk) > κ, (gi(X
k), Zk) > κ, i ∈ T k
1 ,
(gi(X
k), Zk) > 0, i ∈ T k
2
⋃
T k
3
}
,
T k
1 = {i ∈ I1 : gi(X
k) > ε}, T k
2 = {i ∈ I2 : gi(X
k) > ε},
T k
3 =
{
i ∈ I3 : gi(X
k) >
ε
10
}
.
(8)
Для решения задачи линейного программирования (7), (8) используется пакет HOPDM
(версия 2.13), реализующий прямодвойственный алгоритм высокого порядка, разработан-
ный J. Gondzio [10]. Процесс локальной оптимизации прекращается, если для некоторого k
выполняются условия Fλ(X
k)− Fλ(X
(k−1)) < 10−4, r − rki < 10−5, i = 1, 2, . . . , λ.
Если окажется, что для некоторого λ имеем Fλ(X
λ∗) = λr, то глобальный максимум
задачи
Fλ(X
λ∗) = max
Xλ∈Dλ
Fλ(X
λ) (9)
достигнут, λ увеличивается на единицу и задача (1)–(5) решается снова.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №12 47
Таблица 1. Результаты вычислений
n ρ h nbest nadd
201 5,5 15,6142 200 1
353 3,96 52,1 339 14
1514 5,6 108,8 1479 35
1692 5,96 106,4 1652 40
Если для некоторого λ имеем Fλ(X
λ∗) < λr, то достигнут локальный или глобальный
максимум задачи (9). λ уменьшается на единицу и задача (1)–(5) решается снова.
Если Fλ(X
λ∗) = λr и Fλ+1(X
(λ+1)∗) < (λ+1)r, то точка Xλ∗ берется в качестве прибли-
жения к глобальному максимуму задачи (1)–(5).
Все численные примеры посчитаны с применением процессора AMD Athlon 64 X2 6000+
+ (3.1Ghz). Исходные коды программ написаны в Delphi. Во всех примерах r = 1.
Результаты вычислений и сравнение с известными результатами приведены в табл. 1.
Здесь n — количество шаров; ρ и h — радиус основания и высота цилиндра C соответст-
венно; nbest — лучшее, известное на сегодняшний день количество шаров; nadd — количе-
ство дополнительных шаров, упакованных с помощью алгоритма, предложенного в данной
работе.
Предложенный подход дает возможность использовать многопроцессорные компьютеры.
Математическая модель, в которой радиусы всех шаров являются переменными, позво-
ляет значительно улучшить качество получаемых решений.
Этот метод может быть применен для решения задачи упаковки шаров разных радиусов.
1. Mueller G. E. Numerically packing spheres in cylinders // Powder Technology. – 2005. – 159. – P. 105–110.
2. Birgin E.G., Sobral F.N. C. Minimizing the object dimensions in circle and sphere packing problems //
Computers & Operations Research. – 2008. – 35. – P. 2357–2375.
3. Sutou A., Dai Y. Global optimization approach to unequal sphere packing problems in 3D // J. of Opti-
mization Theory and Applications. – 2002. – 114, No 3. – P. 671–694.
4. Abreu C.R.A., Tavares M. Influence of particle shape on the packing and on the segregation of spherocyli-
nders via Monte Carlo simulations // Powder Technol. – 2003. – 134. – P. 167–180.
5. Abreu C.R.A., Macias-Salinas R., Tavares F.W., Castier M. A Monte-Carlo simulation of the packing
and segregation of spheres in cylinders // Braz. J. Chem. Eng. – 1999. – 16, No 4. – P. 395–405.
6. Lenstra J. K., Rinnooy Kan A.H.G. Complexity of packing, covering, and partitioning problems // Packing
and Covering in Combinatorics. – Amsterdam: Mathematische Centrum, 1979. – P. 275–291.
7. Zoutendijk G. Nonlinear programming, computational methods, integer and nonlinear programming / Ed.
J. Abadie. – Amsterdam: North Holland, 1970.
8. Stoyan Y., Yaskov G. Packing identical spheres into a rectangular parallelepiped / Eds. A. Bortfeldt,
J. Homberger, H. Kopfer, G. Pankratz, R. Strangmeier / Intelligent Decision Support. Current Challenges
and Approaches. – Wiesbaden: Betriebswirtschaftlicher Verlag Dr. Th. Gabler / GWV Fachverlage GmbH,
2008. – P. 46–67.
9. Stoyan Y., Chugay A. Packing cylinders and rectangular parallelepipeds with distances between them into
a given region // European J. of Operational Research. – 2009. – 197, No 2. – P. 446–455.
10. Gondzio J. HOPDM (version 2.12) – A fast LP solver based on a primal-dual interior point method //
Ibid. – 1995. – 85, No 1. – P. 221–225.
Поступило в редакцию 01.06.2009Институт проблем машиностроения
им. А.Н. Подгорного НАН Украины, Харьков
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №12
G.N. Yaskov
Packing a large number of congruent spheres into a cylinder
The paper considers the problem of packing a maximal number of congruent spheres of the unit
radius into a straight circular cylinder of given sizes. A mathematical model of the problem is
suggested. Radii of all spheres are supposed to be variable A global maximum of the problem ensures
the packing of all spheres. An algorithm of constructing a starting package is based on a lattice
packing of spheres. Results are compared with the best known ones. A number of numerical examples
are given.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №12 49
|