Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов
На основе квази Ф-функций построена математическая модель задачи плотной упаковки неориентированных выпуклых многогранников в параллелепипеде минимальной высоты. На основе особенностей построенной модели предложен метод получения различных начальных размещений многогранников. Метод состоит из трех о...
Збережено в:
| Опубліковано в: : | Проблемы машиностроения |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/80994 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов / А.М. Чугай // Проблемы машиностроения. — 2014. — Т. 17, № 2. — С. 40-45. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860095448971214848 |
|---|---|
| author | Чугай, А.М. |
| author_facet | Чугай, А.М. |
| citation_txt | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов / А.М. Чугай // Проблемы машиностроения. — 2014. — Т. 17, № 2. — С. 40-45. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы машиностроения |
| description | На основе квази Ф-функций построена математическая модель задачи плотной упаковки неориентированных выпуклых многогранников в параллелепипеде минимальной высоты. На основе особенностей построенной модели предложен метод получения различных начальных размещений многогранников. Метод состоит из трех основных этапов. На первых двух решаются вспомогательные задачи нелинейного программирования, которые позволяют получить начальное размещение многогранников. На последнем этапе определяются параметры разделяющих плоскостей для квази Ф-функций.
На основі квазі Ф-функцій побудовано математичну модель задачі щільного пакування неорієнтованих опуклих багатогранників у паралелепіпеді мінімальної висоти. На основі властивостей побудованої моделі запропоновано метод отримання різноманітних початкових розміщень багатогранників. Метод складається з трьох основних етапів. На перших двох вирішуються допоміжні задачі нелінійного програмування, які дозволяють отримати початкове розміщення багатогранників. На останньому етапі визначаються параметри відокремлюваних площин для квазі Ф-функцій.
In this paper a mathematical model of a dense packing problem of non-oriented convex polytopes into a cuboid of minimum height is constructed by using the quasi Ф-function. An application of quasi Ф-functions allows to formulate mutual non-intersections conditions for a pair of objects as a set of inequalities systems left sides of which are infinitely differentiable functions. Owing to this fact a mathematical model of the problem is presented as a classical non-linear programming problem. For construction of different starting points a special method is proposed. The method includes three stages. On the first and second stages helper problems are solved. The first helper problem allows us to find a covering of polytopes by spheres of minimal radius. The second one allows us to find a dense packing of spheres in an arrangement region. At the third stage parameters of separating planes between the dense packing spheres are calculated.
|
| first_indexed | 2025-12-07T17:25:55Z |
| format | Article |
| fulltext |
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 40
А. М. Чугай,
канд. техн. наук
Институт проблем
машиностроения
им. А. Н. Подгорного
НАН Украины, Харьков,
e-mail:
chugay@ipmach.kharkov.ua
Ключові слова: математичне
моделювання, квазі Φ-функція,
неорієнтовані опуклі багато-
гранники, щільне пакування
об’єктів.
УДК 519.859
МЕТОД ПОЛУЧЕНИЯ НАЧАЛЬНЫХ
РАЗМЕЩЕНИЙ В ЗАДАЧЕ МОДЕЛИРОВАНИЯ
СТРУКТУРЫ СИСТЕМ ПЛОТНОУПАКОВАННЫХ
ОБЪЕКТОВ
На основі квазі Ф-функцій побудовано математичну модель задачі щільно-
го пакування неорієнтованих опуклих багатогранників у паралелепіпеді мі-
німальної висоти. На основі властивостей побудованої моделі запропоно-
вано метод отримання різноманітних початкових розміщень багатогран-
ників. Метод складається з трьох основних етапів. На перших двох вирі-
шуються допоміжні задачі нелінійного програмування, які дозволяють
отримати початкове розміщення багатогранників. На останньому етапі
визначаються параметри відокремлюваних площин для квазі Ф-функцій.
Введение
Решение задач плотной упаковки трехмерных геометрических объектов востребовано во мно-
гих областях человеческой деятельности. Так, например, плотные упаковки однородных твердых
частиц представляют большой интерес, поскольку могут быть представлены в виде моделей физиче-
ских систем, таких, как жидкости, стекла и аморфные материалы. Кроме этого, системы плотноупа-
кованных твердых тел используются при проведении исследований в области гранулированных по-
рошков и пористых материалов [1–3]. Для трехмерного моделирования, визуального и количествен-
ного анализа структурных особенностей различных твердых структур, а также для моделирования
структуры материалов, используемых в нанотехнологиях, могут быть использованы математические
модели и методы теории оптимизационного геометрического проектирования.
Анализ литературных данных и постановка проблемы
Обзор работ, посвященных плотной упаковке трехмерных геометрических объектов, позволя-
ет сделать вывод, что сложность решения таких задач обусловлена отсутствием эффективных алго-
ритмов её решения. Большинство работ сводится к размещению простых геометрических фигур (па-
раллелепипеды, цилиндры, сферы), в то время как большинство практических задач требует разме-
щения объектов произвольной формы. Поэтому поиск новых подходов и алгоритмов для решения
задачи плотного размещения трехмерных геометрических объектов остается актуальным. Вычисли-
тельная сложность решения задач трехмерной упаковки вынуждает многих исследователей вводить
упрощения, которые достаточно сильно урезают область допустимых решений, но то же время по-
зволяют находить рациональные решения задач с приемлемыми затратами вычислительных ресурсов
[4–6].
На сегодняшний день в классе задач размещения трехмерных геометрических объектов наи-
менее изученными являются задачи, в которых допускаются аффинные преобразования не только
трансляции, но и произвольного поворота объектов. Вместе с тем эти задачи имеют важное как тео-
ретическое, так и практическое значение. По своей постановке задачи размещения трехмерных гео-
метрических объектов является оптимизационными. Однако в настоящее время существует проблема
применения методов локальной и глобальной оптимизации для решения задач размещения неориен-
тированных (т.е. допускающих произвольные повороты) трехмерных объектов. Это обусловлено от-
сутствием конструктивных средств математического моделирования отношений между этими объек-
тами. В статье [7] приводится обзор современных подходов к решению задач размещения и говорит-
ся, что одним из перспективных подходов для построения адекватных математических моделей ука-
занных задач является метод Φ-функций. В настоящее время построению Φ-функций для трехмерных
объектов посвящён ряд работ, в частности [8, 9].
© А. М. Чугай, 2014
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 41
Целью данной работы является математическое моделирование плотного размещения неори-
ентированных выпуклых многогранников и разработка метода получения их начальных размещений.
Рассматриваемая задача имеет следующую постановку. Пусть даны выпуклые многогранники
Pi, i ∈ I = {1, 2, …, n}, заданные вершинами pit = (x'it, y'it, xzit) t ∈ T. Размещение многогранника Pi в
пространстве R3 определяется вектором vi = (xi, yi, zi) трансляции собственной системы координат Pi и
тремя углами поворота θ = (φi, ψi, ωi), i ∈ I.
Представим оператор поворота в следующем виде:
.==
321
321
321
iii
iii
iii
i
i
i
i
qqq
ooo
mmm
q
o
m
R
где iiiiiiiii mm ωφ+ωψφωψ sincoscossinsin=,coscos= 21 , ,sinsincossincos=3 iiiiiim ωφ+ωψφ−
iiiiiiiii oo ωφ+ωψφ−ωψ− coscossinsinsin=,sincos= 21 , iiiiiio ωφ+ωψφ cossinsinsincos=3 ,
.coscos=,cossin=,sin= 321 iiiiiiii qqq ψφψφ−ψ
Тогда pij(ui) = (mi
Tpij + xi, oi
Tpij + yi, qi
Tpij + z), j ∈ T, i ∈ I.
Вектор движения многогранника Pi обозначим через ui = (vi, θi) ∈ R6.
В качестве контейнера размещения рассматривается параллелепипед P = {X = (x, y, z) ∈ R3 :
0 ≤ x ≤ w, 0 ≤ y ≤ l, η1 ≤ z ≤ η2, η1 > 0}. Обозначим через P(η) контейнер высотой H(η) = η2 – η1.
Вектор u = (u1, u2, …, un) ∈ Rω, ω = 6n, будет определять размещение многогранников Pi, i ∈ I,
в пространстве R3.
Задача. Необходимо найти вектор u, который обеспечивает размещение Pi, i ∈ I, в P(η) без
взаимных пересечений таким образом, чтобы высота H(η) = η2 – η1 была минимальной.
Математическое моделирование взаимодействия геометрических объектов
Для моделирования взаимодействия выпуклых многогранников в [8] была построена
Φ-функция. Чтобы уменьшить вычислительную сложность описания в аналитическом виде условий
непересечения пары объектов, может быть использовано понятие квази Φ-функции. Эта функция за-
висит не только от параметров размещения объектов, но и от некоторых дополнительных перемен-
ных Y, количество k которых зависит от размерности пространства, в котором заданы геометрические
объекты.
Всюду определенная и непрерывная функция Qij(ui, uj, Yij) : Rk → R1, где (ui, uj) ∈ Rμ и k > μ,
называется квази Φ-функцией для геометрических объектов Oi(ui) и Oj(uj), если ),,(max ijjiij
RY
YuuQ
k
ij
μ−∈
является Φ-функцией Φij(ui, uj) для этих объектов.
Следует отметить важное свойство квази Φ-функции: если Qij(ui, uj, Yij) то Oi(ui) и Oj(uj) либо
касаются, либо не имеют общих точек.
Идея квази Φ-функции основывается на построении разделяющей плоскости пары объектов
Pi(ui) и Pj(uj).
Перед построением квази Φ-функции для Pi и Pj построим Φ-функцию для Pi и
полупространства Hl
Hl = {(x, y, z) ∈ R3 : fl(X, Yl) = al(αl)x + bl(αl, βl)y + cl(αl, βl)z + dl ≤ 0}, (1)
где al(αl) = sinαl, bl(αl, βl) = sinβlcosαl, cl(αl, βl) = cosβlcosαl, Yl = (αl, βl, dl).
Легко проверить, что ||Nl|| = ||al(αl), bl(αl, βl),cj(αl, βl)|| = 1. Следовательно, плоскость ϒl = frHl
(1) определяется нормальным уравнением
fl(X, Yl) = al(αl)x + bl(αl, βl)y + cl(αl, βl)z + dl = 0 (2)
Поскольку ||Nl|| = 1, то коєффициенты al(αl), bl(αl, βl) и cl(αl, βl) не могут быть одновременно
равны нулю, т. е. мы всегда имеем дело с полупространством.
Тогда, используя выражение (2) построим Φ-функцию для Pi и Hl
Φij(ui, Yl) = min{fl(pit(ui), Yl), t ∈ T}. (3)
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 42
Φ-функция для Pi и cl(R3\P(η))будет иметь вид
}.,,,
,,,min{=),(
21 Ttzpqzpqypol
xpmwypoxpmu
iit
T
iiit
T
iiit
T
i
iit
T
iiit
T
iiit
T
iii
∈−−η++η−−−
−−++ηΦ
(4)
Для дальнейшего удобства введем переименование ϒl (2)
ϒij = {(x, y, z) ∈ R3 : fij(X, Yij) = aij(αij)x + bij(αij, βij)y + cij(αij, βij)z + dij = 0}. (5)
Плоскость ϒij делит пространство R3 на 2 полупространства
},0),(),()(=),(:),,{(=
,}0),(),()(=),(:),,{(=
3
3
≤−βα−βα−α−∈
≤+βα+βα+α∈
+
−
ijijijijijijijijijijijl
ijijijijijijijijijijijl
dzcybxaYXfRzyxH
dzcybxaYXfRzyxH
(6)
где .),,(=
_
ijijijij dY −βα+π Тогда на основании (6) Φ-функции для Pi и Hl
– (Hl
+) будут иметь вид
( ) ( ) ( ){ }
( ) ( ) ( ){ }. ,),)((min),(
, ,=),)((min=),(
2
1
TtdczpqbypoaxpmYupfYu
TtdczpqbypoaxpmYupfYu
ijijiit
T
iijiit
T
iijiit
T
iijjjtijijjij
ijijiit
T
iijiit
T
iijiit
T
iijiitijijiij
∈++++++==Φ
∈++++++Φ
(7)
Тогда на основании выражений (7) квази Φ-функция многогранников Pi и Pj может быть
записана как
.)},(,),(min{=),,( 21
ijiijijiijijjiij YuYuYuuQ ΦΦ (8)
На основе Φ-функции (4) и квази Φ-функции (8) математическая модель поставленной задачи
может быть построена в виде
2),,(
)(min=)(
+ε+ω⊂Λ∈η
∗ ηη
RYu
HH , (9)
где
{ }.00,),(,0,),(,<00,),,(:),,(=
,
2
1)(3=,),...,,...,,,,...,,(=
221
2
1)(2242311312
≥η≥ηη∈≥ηΦ∈<≥∈ηΛ
−
ε∈
+ε+ω
ε
−
HIiuIjiYuuQRYu
nnRYYYYYYYY
iiijjiij
nnnn (10)
Таким образом, выполнение Qij(ui, uj, Yij) ≥ 0 обеспечивает непересечение Pi(ui) и Pj(uj), а
выполнение Φi(ui, η) ≥ 0 – размещение Pi(ui) внутри P(η).
Метод получения начальных размещений
Поскольку математическая модель (9)–(10) поставленной задачи построена в виде
классической задачи нелинейного программирования, то для ее решения могут быть применены
различные модификации методов нелинейной оптимизации. Однако для применения численных
методов нелинейной оптимизации необходимо иметь допустимую начальную точку. Среди методов,
которые применяются для построения начальных точек, в задачах размещения объектов в основном
используются различные модификации «жадных» алгоритмов. Применение «жадных» алгоритмов в
рассматриваемой задаче представляет большую сложность. Кроме того, одним из недостатков
применения таких алгоритмов является невозможность получения разнообразных начальных
размещений объектов. Поскольку задачи размещения геометрических объектов являются
NP-трудными, то применение «жадных» алгоритмов существенно ограничивает возможности
перебора огромного количества локальных экстремумов (количество которых превышает n!).
В связи с вышеуказанными фактами в работе предлагается метод, который позволяет
генерировать любые начальные точки задачи (9)–(10), т. е. определять начальные размещения
объектов в области размещения. Предлагаемый метод можно разбить на три основных этапа.
На первом этапе каждый многогранник Pi покрывается сферой Si минимального радиуса Ri
0,
i ∈ I. Для этого мы решаем следующую вспомогательную задачу нелинейного программирования:
,min=
4),(=
*
RDRvX
ii
iiii
RR
⊂∈
(11)
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 43
где
Di = {Xi = (vi, Ri) ∈ R4 : Ψij(Xi) = Ri
2 – (x'ij – xi)2 – (y'ij – yi)2 – (z'ij – zi)2 ≥ 0, j ∈ Ti}. (12)
На втором этапе будем полагать, что Ri, i ∈ I, являются переменными, а все переменные
радиусы формируют вектор R = (R1, R2, …, Rn). Кроме того, перенесем собственную систему
координат Pi в центр найденной на первом этапе сферы Si, i ∈ I.
Установим высоту H(η0) = η2
0– η1
0 области размещения P(η0) таким образом, что будет
гарантировано размещение всех Si, i ∈ I внутри P(η0) без пересечений. Предположив Ri
• = 0, i ∈ I,
случайным образом сгенерируем вектор v• таким образом, что vi
• ∈ P(η0), i ∈ I. В результате получим
вектор X• = (v•, 0). Взяв точку X• = (v•, 0), решим следующую вспомогательную задачу:
,max=)(max=)(
1=
44 i
n
iRGXRGX
RRR
nn ∑
⊂∈⊂∈
∗ ΩΩ (13)
где
}.0,0,=)(0,),(,<<00,),(:{= 004 IiRRRRXIjiXXRXG iiiiiiijiij
n ∈≥≥−ϕ≥ηΦ∈≥Φ∈ (14)
Очевидно, что X• ∈ G. Задача (13)–(14) имеет следующие свойства. Если в точке )
ˆ
,ˆ(=ˆ RuX
))
локального максимума dRR i
n
i
==)ˆ( 0
1=
∑Ω , то Λ∈η ),ˆ( 0u , т. е. многогранники ,)ˆ( ii uP i ∈ I, размещены
в P(η0). В таком случае точка X̂ является глобальным максимумом задачи (13)–(14). Если же
глобальный максимум )ˆ,ˆ(=ˆ RuX такой, что dh <)ˆ(Ω , то многогранники ,)ˆ( ii uP i ∈ I, не размещены
в P(η0). Поскольку выбор η0 обеспечивает размещение сфер Si, i ∈ I, в P(η0), т.е.. dR =)ˆ(Ω , то в
результате решения задачи (13)–(14) мы получим точку глобального экстремума (v•, R•) = (v•, R0) ∈ G.
На последнем третьем этапе для построения начальной точки (u•, Y•, η0) ∈ Λ задачи (9)–(10)
определим параметры разделяющих плоскостей для квази Φ-функций Qij(ui, uj, Yij), 0 < i < j ∈ I. Для
этого случайным образом выберем значения φi
•, ψi
•, ωi
• ∈ [0, 2π], i ∈ I, и определим вектор Y•.
Построим канонические уравнения прямых ϒij, проходящих через точки vi
• и vj
•
••
•
••
•
••
•
−
−
−
−
−
−
ij
i
ij
i
ij
i
zz
zz
yy
yy
xx
xx == .
Далее построим точки ),,(),,,( 232221131211
ijijijijijij NNNNNN , 0 < i < j ∈ I, где
( ) ( ) ( ) .
,
)(
,
)(
,
)(
,
)(
,
)(
,
)(
222
0
23
0
22
0
21
0
13
0
12
0
11
••••••
••••••
••••••
−+−+−=ς
ς
−
−=
ς
−
−=
ς
−
−=
ς
−
+=
ς
−
+=
ς
−
+=
ijijijij
ij
ijj
jij
ij
ijj
jij
ij
ijj
jij
ij
iji
iij
ij
iji
iij
ij
iji
iij
zzyyxx
zzR
zN
yyR
yN
xxR
xN
zzR
zN
yyR
yN
xxR
xN
После этого построим плоскости Nij, проходящие через точки
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +++
2
,
2
,
2
231322122111
ijijijijijij NNNNNN
перпендикулярно к ϒij
( ) ( ) ( ) Ijizz
NN
zyy
NN
yxx
NN
x ij
ijij
ij
ijij
ij
ijij ∈<<−⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +
−+−⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +
−+−⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +
− •••••• 0,0=
222
231322122111
.
Из построения Nij следует, что данная плоскость является разделяющей плоскостью сфер
Si(vi
•) и Sj(vj
•).
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 44
Взяв
( ) ( ) ( ),
222
,=,=,=
231322122111
•••••••
••
•
••
•
••
•
−
ς
+
+−
ς
+
+−
ς
+
=
ς
−
ς
−
ς
−
ij
ij
ijij
ij
ij
ijij
ij
ij
ijij
ij
ij
ij
ij
ij
ij
ij
ij
ij
ij
zz
NN
yy
NN
xx
NN
d
zz
c
yy
b
xx
a
получим нормальное уравнение
0=
222
231322122111
•••• +⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +
−+⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +
−+⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +
− ijij
ijij
ij
ijij
ij
ijij dc
NN
zb
NN
ya
NN
x ,
разделяющей плоскоти Nij для сфер Si(vi
•) и Sj(vj
•). Поскольку сферы Si(vi
•) и Sj(vj
•)покрывают
мнгогранники Pi(vi
•) и Pj(vj
•), то плоскости Nij являются разделяющими плоскостями для этих
многогранников. Следовательно, мы можем взять вектор
),...,,,...,,...,,,,...,,(= )1(2)1(1)1(2222111211
•
−
•
−
•
−
•••••••
nnnnnn YYYYYYYYYY ,
где ),,( •••• βα= ijijijij dY , •• =α ijij aarcsin ,
•
•
•
α−
=β
ij
ij
ij
b
2cos1
arcsin .
Сформируем вектор (v•, θ•, Y•, η0) = (u•, Y•, η0). Поскольку сферы Si(vi
•) содержат
многогранники Pi(vi
•), i ∈ I, то (u•, Y•, η0) ∈ Λ. Следовательно, точка (u•, Y•, η0) ∈ Λ может быть взята
в качестве начальной точки для поиска точки локального максимума (u*, Y*, η0) задачи (9)–(10).
Для поиска локальных экстремумов задачи (11)–(12) и (13)–(14) использовалась библиотека
IPOPT [10]. В данной библиотеке реализованы алгоритмы метода внутренней точки, которые для по-
иска вектора движения используют матрицу Гессе левой части системы ограничений, описывающей
область допустимых решений.
Выводы
Для трехмерного моделирования структурных особенностей различных материалов предло-
жено использовать задачу плотной упаковки неориентированных выпуклых многогранников в парал-
лелепипеде.
Для построения математической модели поставленной задачи использован аппарат квази
Φ-функций. Благодаря этому математическая модель поставленной задачи построена в виде класси-
ческой задачи нелинейного программирования.
Предложен специальный метод получения разнообразных начальных размещений неориенти-
рованных выпуклых многогранников. Метод условно разбивается на три этапа, предполагающих ре-
шение вспомогательных задач нелинейного программирования и определение параметров разделяю-
щих плоскостей для квази Φ-функций неориентированных выпуклых многогранников.
Литература
1. Williams, S. R. Random Packings of Spheres and Spherocylinders Simulated by Mechanical Contraction / S. R. Wil-
liams, A. P. Philipse // Phys. Rev. E. – 2003. – Vol. 67. – P. 051301-1–051301-9.
2. Torquato, S. Modeling of Physical Properties of Composite Materials / S. Torquato // Int. J. Solids Struct. – 2000. –
Vol. 37. – P. 411–422.
3. Yi, Y. B. Compression of Packed Particulate Systems: Simulations and Experiments in Graphitic Li-ion Anodes /
Y. B. Yi, C. W. Wang, A. M. Sastry // J. Eng. Materials and Techn. – 2006. – Vol. 128. – P. 73–80.
4. Li, S. X. Sphere assembly model and relaxation algorithm for packing of non-spherical particles / S. X. Li, J. Zhao //
Chin. J. Comput. Phys. – 2009. – Vol. 26(3), P. 167–173.
5. Korte, A. C. J. Random packing of digitized particles / A. C. J Korte, H. J. H. Brouwers // Powder Techn. – 2013. –
Vol. 233. – P. 319–324.
6. Jia, X. Validation of a digital packing algorithm in predicting powder packing densities / X. Jia, M. Gan, R. A. Wil-
liams, D. Rhodes // Powder Techn. – 2007. – Vol. 174. – P. 10–13.
7. Bennell, . The geometry of nesting problems: A tutorial / J. ennell, J. Oliveira // European J. Oper. Res. – 2008. –
Vol. 184. – P. 397–415.
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 45
8. Stoyan, Yu. G. Mathematical modeling of the interaction of non-oriented convex polytopes / Yu. G. Stoyan,
А. М. Chugay // Cybernetics and Systems Analysis. – 2012. – Vol. 48(6). – P. 837–845.
9. Scheithauer, G. Mathematical modeling of interactions of primary 3D geometric objects / G. Scheithauer,
Y. Stoyan, T. Romanova // Cybernetics and System Analysis. – 2005. – Vol. 41(3). – P. 332–342.
10. Wachter, A. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlin-
ear programming / A. Wachter, L. T. Biegler // Math. Programming. – 2006. – Vol. 106(1). – Р. 25–57.
Поступила в редакцию 12.05.14
|
| id | nasplib_isofts_kiev_ua-123456789-80994 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0131-2928 |
| language | Russian |
| last_indexed | 2025-12-07T17:25:55Z |
| publishDate | 2014 |
| publisher | Інстиут проблем машинобудування ім. А.М. Підгорного НАН України |
| record_format | dspace |
| spelling | Чугай, А.М. 2015-04-29T19:52:54Z 2015-04-29T19:52:54Z 2014 Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов / А.М. Чугай // Проблемы машиностроения. — 2014. — Т. 17, № 2. — С. 40-45. — Бібліогр.: 10 назв. — рос. 0131-2928 https://nasplib.isofts.kiev.ua/handle/123456789/80994 519.859 На основе квази Ф-функций построена математическая модель задачи плотной упаковки неориентированных выпуклых многогранников в параллелепипеде минимальной высоты. На основе особенностей построенной модели предложен метод получения различных начальных размещений многогранников. Метод состоит из трех основных этапов. На первых двух решаются вспомогательные задачи нелинейного программирования, которые позволяют получить начальное размещение многогранников. На последнем этапе определяются параметры разделяющих плоскостей для квази Ф-функций. На основі квазі Ф-функцій побудовано математичну модель задачі щільного пакування неорієнтованих опуклих багатогранників у паралелепіпеді мінімальної висоти. На основі властивостей побудованої моделі запропоновано метод отримання різноманітних початкових розміщень багатогранників. Метод складається з трьох основних етапів. На перших двох вирішуються допоміжні задачі нелінійного програмування, які дозволяють отримати початкове розміщення багатогранників. На останньому етапі визначаються параметри відокремлюваних площин для квазі Ф-функцій. In this paper a mathematical model of a dense packing problem of non-oriented convex polytopes into a cuboid of minimum height is constructed by using the quasi Ф-function. An application of quasi Ф-functions allows to formulate mutual non-intersections conditions for a pair of objects as a set of inequalities systems left sides of which are infinitely differentiable functions. Owing to this fact a mathematical model of the problem is presented as a classical non-linear programming problem. For construction of different starting points a special method is proposed. The method includes three stages. On the first and second stages helper problems are solved. The first helper problem allows us to find a covering of polytopes by spheres of minimal radius. The second one allows us to find a dense packing of spheres in an arrangement region. At the third stage parameters of separating planes between the dense packing spheres are calculated. ru Інстиут проблем машинобудування ім. А.М. Підгорного НАН України Проблемы машиностроения Прикладная математика Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов A method of generation of starting arrangements in a problem of structure modelling of systems of densely packed objects Article published earlier |
| spellingShingle | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов Чугай, А.М. Прикладная математика |
| title | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов |
| title_alt | A method of generation of starting arrangements in a problem of structure modelling of systems of densely packed objects |
| title_full | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов |
| title_fullStr | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов |
| title_full_unstemmed | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов |
| title_short | Метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов |
| title_sort | метод получения начальных размещений в задаче моделирования структуры систем плотноупакованных объектов |
| topic | Прикладная математика |
| topic_facet | Прикладная математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/80994 |
| work_keys_str_mv | AT čugaiam metodpolučeniânačalʹnyhrazmeŝeniivzadačemodelirovaniâstrukturysistemplotnoupakovannyhobʺektov AT čugaiam amethodofgenerationofstartingarrangementsinaproblemofstructuremodellingofsystemsofdenselypackedobjects |