Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях
Розглядається оптимiзацiйна задача розмiщення неорiєнтованих складених двовимiрних об’єктiв з нелiнiйною межею. Будується математична модель задачi. Пропонується стратегiя розв’язання. Наводяться результати чисельних експериментiв. The article considers an optimization packing problem for nonoriente...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/7730 |
| 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. — № 1. — С. 48-53. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860127952142860288 |
|---|---|
| author | Романова, Т.Е. Ступак, Е.А. Злотник, М.В. |
| author_facet | Романова, Т.Е. Ступак, Е.А. Злотник, М.В. |
| citation_txt | Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях / Т.Е. Романова, Е.А. Ступак, М.В. Злотник // Доп. НАН України. — 2009. — № 1. — С. 48-53. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| description | Розглядається оптимiзацiйна задача розмiщення неорiєнтованих складених двовимiрних об’єктiв з нелiнiйною межею. Будується математична модель задачi. Пропонується стратегiя розв’язання. Наводяться результати чисельних експериментiв.
The article considers an optimization packing problem for nonoriented compound two-dimensional objects with nonlinear frontiers. We provide a mathematical model of the problem based on the Ф-function technique. A solution strategy is introduced and illustrated with an example.
|
| first_indexed | 2025-12-07T17:43:03Z |
| format | Article |
| fulltext |
УДК 519.85
© 2009
Т.Е. Романова, Е.А. Ступак, М. В. Злотник
Математическая модель и метод решения задачи
оптимизации упаковки произвольных двумерных
объектов в прямоугольных областях
(Представлено членом-корреспондентом НАН Украины Ю.Г. Стояном)
Розглядається оптимiзацiйна задача розмiщення неорiєнтованих складених двовимiр-
них об’єктiв з нелiнiйною межею. Будується математична модель задачi. Пропону-
ється стратегiя розв’язання. Наводяться результати чисельних експериментiв.
Пусть имеется прямоугольная область P = {(x, y) ∈ R
2 | 0 6 x 6 l, 0 6 y 6 h} переменной
длины l и объекты Ti ⊂ R
2, i = 1, . . . , n, где R
2 — двумерное арифметическое эвклидово
пространство, Ti =
Si
⋃
si=1
Tisi
, Tisi
=
( Ξsi
⋃
℘si
=1
Tisi℘si
)
⋂
(Ksi
⋂
ksi
T ∗
isiksi
)
, T ∗
isiksi
=
Mksi
⋃
mksi
=1
T ∗
isiksi
mksi
,
Tisi℘si
∈ ℑ, T ∗
isiksi
mksi
∈ ℑ∗, frA
⋂
Bq1
= ∅, Bq1
⋂
Bq2
= ∅, где A =
Ξsi
⋃
℘si
=1
Tisi℘si
, и Bq = T ∗
isiksi
,
q = 1, . . . ,Ksi
, q1 < q2 = 2, . . . ,Ksi
, ℑ — множество односвязных, а ℑ∗ — множество дву-
связных базовых объектов [1], ℑ = {C,K,S}, ℑ∗ = {C∗,K∗, S∗}, где C, K, S — круг, мно-
гоугольник, круговой сегмент соответственно, T ∗ = cl(R2/T ). Геометрическая информация
о Ti задается кортежем вида
gi = (ci,mi, ui) =
({ Si
⋃
si=1
( Ξsi
⋃
℘si
=1
cisi℘si
)
⋂
( Ksi
⋂
ksi
=1
Mksi
⋃
mksi
=1
ciksi
mksi
)}
,
{(msi
, usi
), s = 1, . . . , ni}, (vi, θi)),
где ci — пространственная форма; mi — метрические характеристики; ui = (vi, θi) — па-
раметры размещения Ti; vi ∈ R
2 — вектор трансляции; θi — угол поворота объекта Ti
относительно центра собственной системы координат.
В дальнейшем Ti(ui) = T (vi, θi) ⊂ R
2 — объект, транслированный на вектор vi и по-
вернутый на угол θi.
Задача. Разместить объекты Ti, i = 1, . . . , n, в области P так, чтобы выполнялись
соотношения
int Ti(ui)
⋂
int P ∗ = ∅, intTi(ui)
⋂
intTj(uj) = ∅, i 6= j, i, j ∈ {1, . . . , n}, (1)
и переменная l принимала минимальное значение.
В терминах Φ-функций [2] соотношения (1) описываются неравенствами Φi(0, ui) > 0,
Φij(ui, uj) > 0, i 6= j, i, j ∈ {1, . . . , n}, где Φi(0, ui) — Φ-функция P ∗(0) и Ti(ui), Φij(ui, uj) —
Φ-функция Ti(ui) и Tj(uj).
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №1
Φ-функция Φi(0, ui) имеет вид
Φi(0, ui) = min
si=1,...,ni
max{ min
℘si
=1,...,Ξsi
Φ℘si
(0, ui + u℘si
),
max
ksi
=1,...,Ksi
min
mksi
=1,...,Mksi
Φmksi
(0, ui + umksi
)}, (2)
где Φ℘si
(0, ui + u℘si
) и Φmksi
(0, ui + umksi
) — Φ-функции для P ∗(0) и объектов Tisi℘si
∈
∈ ℑ и Tisiksi
mksi
∈ ℑ∗ соответственно. В [3, 4] приведены Φ-функции неориентированных
базовых объектов.
Φ-функция Φij(ui, uj) определяется следующим образом:
Φij(ui, uj) = min
si=1,...,ni
min
sj=1,...,nj
Φsisj
(ui + usi
, uj + usj
), (3)
где Φsisj
(ui + usi
, uj + usj
) — Φ-функция объектов Tisi
и Tjsj
,
Φsisj
(ui + usi
, uj + usj
) = max{ min
℘si
=1,...,Ξsi
min
℘sj
=1,...,Ξsj
Φ℘si
℘sj
(ui + u℘si
, uj + u℘sj
),
max
ksi
=1,...,Ksi
min
ksj
=1,...,Ksj
Φksi
ksj
(ui + uksi
, uj + uksj
)},
(4)
Φ℘si
℘sj
(ui + u℘si
, uj + u℘sj
) — Φ-функция объектов Tisi℘si
∈ ℑ и Tjsj℘sj
∈ ℑ, Φksi
ksj
(ui +
+ uksi
, uj + uksj
) — Φ-функция объектов Tisiksi
и Tjsjksj
,
Φksi
ksj
(ui+uksi
, uj +uksj
)= min
mksi
=1,...,Lsi
min
mksj
=1,...,Lsj
Φmksi
mksj
(ui+umksi
, uj +umksj
), (5)
Φmksi
mksj
(ui + umksi
, uj + umksj
) — Φ-функция объектов Tisiksi
mksi
, Tjsjksj
mksj
∈ ℑ∗.
Подставляя (4), (5) в (3), Φ-функцию объектов Ti(ui) и Tj(uj) запишем
Φij(ui, uj) = min
si=1,...,ni
min
sj=1,...,nj
max{ min
℘si
=1,...,Ξsi
min
℘sj
=1,...,Ξsj
Φ℘si
℘sj
(ui+u℘si
, uj +u℘sj
),
max
ksj
=1,...,Ksj
min
℘si
=1,...,Ξsi
min
mksj
=1,...,Mksj
Φ℘si
mksj
(ui + u℘si
, uj + umksj
),
max
ksi
=1,...,Ksi
min
mksi
=1,...,Mksi
min
℘sj
=1,...,Ξsj
Φmksi
℘sj
(ui + umksi
, uj + u℘sj
)}. (6)
Математическая модель поставленной задачи может быть представлена так:
min
X∈W⊂R3n+1
F (X), (7)
где X = (u1, u2, . . . , un, l), F (X) = l,
W = {X ∈ R
3n | ϕi(l, ui) > 0, i = 1, 2, . . . , n, Φij(ui, uj) > 0, i < j = 2, . . . , n},
Φi(0, ui)|l∈R1 = ϕi(l, ui),
где Φi(0, ui), Φij(ui, uj) определяются соответственно (2), (6).
Рассмотрим основные особенности математической модели (7).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №1 49
1. Задача (7) — нелинейная с линейной функцией цели.
2. Область допустимых решений W описывается n(n − 1)/2 неравенствами вида
Φij(ui, uj) > 0 и n неравенствами вида Φi(0, ui) > 0. Условие Φij(ui, uj) > 0 гарантирует
непересечение объектов Ti(ui) и Tj(uj), i < j = 2, . . . , n. Условие ϕi(l, ui) > 0 обеспечивает
принадлежность объекта Ti(ui) области P , i = 1, . . . , n.
3. Область W может быть представлена в виде объединения множеств Wτ , τ = 1, . . . , η:
W =
η
⋃
τ=1
Wτ ,
где
η < η∗ =
n−1
∏
i=1
n
∏
j=n+1
ni
∏
si=1
nj
∏
sj=1
( Ξsi
∏
℘si
=1
Ξsj
∏
℘sj
=1
ξ +
Ξsi
∏
℘si
=1
℘si
Ksj
+ Ksi
))
, ξ = ξ1 + ξ2,
здесь
ξ1 = 2
n1
j+n2
j
∏
k=n1
j+1
l
n1
j
k 4n1
i n3
j
n1
i +n2
i
∏
k=n1
i +1
l
n1
i
k
n1
i +n2
i
∏
k=n1
i +1
n1
j+n2
j
∏
m=n1
j+1
(lk + lm)
n1
i +n2
i
∏
k=n1
i +1
n1
j+n2
j
∏
m=n1
j+1
(lk + lm),
ξ2 = 4 · 4n3
i n1
j
n1
i +n2
i
∏
k=n1
i +1
nj
∏
m=n1
j+n2
j+1
Q
ni
∏
m=n1
i +n2
i +1
n1
j+n2
j
∏
k=n1
j+1
Q
ni
∏
k=n1
i +n2
i +1
nj
∏
m=n1
j+n2
j+1
(9 − i1km),
Q = 2(3 − i1km + lk),
где Wτ описывается системой нелинейных неравенств; l — число вершин K, K∗; i1 — число
характерстических вершин S, S∗; n1, n2, n3 — число базовых объектов C, K и S соответст-
венно.
4. Задача (7) может быть сведена к задаче
min{F (Xτ ), τ = 1, . . . , η},
где
F (Xτ ) = min F (X), X ∈ Wτ . (8)
Задача (8) в общем случае является нелинейной и многоэкстремальной.
5. Локальные минимумы задачи (7) в общем случае — нестрогие.
6. Для задачи (7) всегда можно построить дерево решений, концевым вершинам которого
соответствует система неравенств, описывающая множество Wτ , τ = 1, . . . , η.
Исходя из особенностей 1–6, можно сделать следующие выводы:
область допустимых решений W — несвязна с многосвязными компонентами связности;
задача (7) является многоэкстремальной и NP-сложной;
глобальный минимум задачи (7) может быть найден теоретически.
В силу этого для решения задачи (7) предлагается стратегия [5, 6], позволяющая полу-
чать приближения к глобальному экстремуму.
50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №1
Стратегия решения. Данная стратегия включает в себя: построение множества на-
чальных точек, принадлежащих области допустимых решений W ; поиск локальных мини-
мумов; перебор локальных минимумов, который гарантирует приближение к глобальному
минимуму.
Алгоритм, реализующий данную стратегию, состоит в следующем.
1. Аппроксимация области размещения P и составных объектов Ti, i = 1, 2, . . . , n, мно-
гоугольниками P ∗
i , i = 0, 1, . . . , n, где P ∗
i — объединение элементарных прямоугольников
одинаковой ширины, чьи стороны параллельны осям координат фиксированной системе
координат Oxy.
2. Поиск начальных точек X0 = (u0
1, . . . , u
0
n, l0) ∈ W методом оптимизации по груп-
пам переменных для P ∗
i , i = 1, . . . , n, и области P ∗
0 в соответствии с последовательностью
объектов (Ti1 , Ti2 , . . . , Tin), полученной методом сужающихся окрестностей [6].
3. Формирование множества Λ = {X0 ∈ W} [6].
4. Поиск точек локального минимума X0∗ = (u0∗
1 , . . . , u0∗
n , l0∗) ∈ W для каждой началь-
ной точки X0 ∈ Λ модифицированным методом Зонтендейка [7]. Формирование множества
Λ∗ = {X0∗}.
5. Поиск приближения к глобальному минимуму: X∗ = arg min
X∈Λ∗
X, X∗ = (u∗
1, . . . , u
∗
n, l∗).
П р и м е р . Пусть P = {(x, y) ∈ R
2 | 0 6 x 6 l, 0 6 y 6 15}, n = 17. Геометрическая информация
об объектах Ti, i = 1, . . . , n, задается следующим образом:
g1 = ({C1
⋃
C2}, {(1; (1; 1)), (1; (2; 1))}, (0; 0; 0)), n1 = 3,
g2 = ({(K
⋃
S1
⋃
S2)
⋂
(C∗
1
⋃
C∗
2
⋃
C∗
3 )}, {((3,5;−0,5), (3,5; 2), (2,5; 3), (−2; 3), (−3; 2), (−3; 1),
(2,5;−2)), (1; (3; 2), (2,5; 3), (0; 0; 0)), (1; (−2; 3), (−3; 2), (−2; 2; 0)), (0,5; (2,5; 0)),
(0,5; (2,5; 2)), (0,5, (−2; 2))}, (0; 0; 0)), n2 = 3,
g3 = ({(K
⋃
C)
⋂
C∗}, {((3;−1,5), (−1; 1,5), (−1;−1,5), (0; 0; 0)), (1,5; (−1; 0)), (0,5; (−2; 2))},
(0; 0; 0)), n3 = 2,
g4 = ({K, ((3;−0,5), (3; 0,5), (−1; 0,5), (−1;−0,5), (−0,5; 0), (−0,5; 2,5), (−2; 2,5), (−2; 0)),
(0; 0; 0)), n4 = 1,
g5 = ({K, ((3;−2), (1; 2), (−2; 2), (−4;−2), (0; 0; 0)), n5 = 1,
g6 = ({K
⋃
S}, {((1;−1), (−1;−1), (−1; 0), (1; 0), (0; 0; 0)), (1; (1; 0), (−1; 0), (0; 0; 0))}, (0; 0; 0)),
n6 = 3,
g7 = ({(
6
⋃
i=1
Ci)
⋂
(
6
⋃
j=1
C∗
j )}, {(5; (0; 0)), (2; (0; 5)), (2; (4, 75; 1,55)), (2; (2,95;−4,05)),
(2; (−2,95;−4,05)), (2; (−4,75; 1,55)), (3; (0; 0)), (1; (0; 5)), (1; (4,75; 1,55)), (1; (2,95;−4,05)),
(1; (−2,95;−4,05)), (1; (−4,75; 1,55))}, (0; 0; 0)), n7 = 1,
g8 = ({C
⋂
C∗}, {(2; (0; 0)), (1; (0; 0))}, (0; 0; 0)), n8 = 2,
g9 = ({C
⋂
C∗}, {(5; (0; 0)), (3; (0; 0))}, (0; 0; 0)), n9 = 1, n = n1 + n2 + · · · + n9.
Согласно предложенной стратегии, на рис. 1–3 приведены размещения объектов Ti,
i = 1, . . . , 17, соответствующие начальной точке, локальному экстремуму, приближению
к глобальному минимуму соответственно.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №1 51
Рис. 1
Рис. 2
Рис. 3
52 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №1
1. Stoyan Yu., Terno J., Scheithauer G. et al. Φ-function for 2D primary objects // Studia Informatica. –
2002. – 2, No 1. – P. 1–32.
2. Stoyan Yu. Φ-function and its basic properties // Доп. АН України. – 2001. – No 8. – С. 112–117.
3. Злотник М.В. Полный класс Φ-функций для кругов и прямоугольников с поворотами // Радиоэле-
ктроника и информатика. – 2006. – № 1. – С. 36–40.
4. Scheithauer G., Stoyan Yu., Romanova T. Mathematical modeling of interaction of a circular segment and
primary objects // Proc. of the Workshop on Cutting Stock Problems – Sapientia University of Miercurea-
Ciuc. – Romania, 2006. – P. 37–46.
5. Стоян Ю.Г., Злотник М.В. Размещение кругов и невыпуклых многоугольников с поворотами в
прямоугольнике минимальной длины // Доп. НАН України. – 2007. – № 2. – С. 37–42.
6. Стоян Ю.Г., Чугай А.М. Оптимизация упаковки одинаковых кругов в многосвязную область //
Там само. – 2004. – № 12. – С. 64–68.
7. Зонтендейк Г. Методы возможных направлений. – Москва: Изд-во иностр. лит., 1963. – 176 с.
Поступило в редакцию 02.07.2008Институт проблем машиностроения
им. А.Н. Подгорного НАН Украины, Харьков
Т. E. Romanova, E.A. Stupak, М. V. Zlotnik
A mathematical model and a method to solve the packing optimization
problem for arbitrary 2D objects in rectangular domains
The article considers an optimization packing problem for nonoriented compound two-dimensional
objects with nonlinear frontiers. We provide a mathematical model of the problem based on the
Φ-function technique. A solution strategy is introduced and illustrated with an example.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №1 53
|
| id | nasplib_isofts_kiev_ua-123456789-7730 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T17:43:03Z |
| publishDate | 2009 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Романова, Т.Е. Ступак, Е.А. Злотник, М.В. 2010-04-12T11:19:29Z 2010-04-12T11:19:29Z 2009 Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях / Т.Е. Романова, Е.А. Ступак, М.В. Злотник // Доп. НАН України. — 2009. — № 1. — С. 48-53. — Бібліогр.: 7 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/7730 519.85 Розглядається оптимiзацiйна задача розмiщення неорiєнтованих складених двовимiрних об’єктiв з нелiнiйною межею. Будується математична модель задачi. Пропонується стратегiя розв’язання. Наводяться результати чисельних експериментiв. The article considers an optimization packing problem for nonoriented compound two-dimensional objects with nonlinear frontiers. We provide a mathematical model of the problem based on the Ф-function technique. A solution strategy is introduced and illustrated with an example. ru Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях A mathematical model and a method to solve the packing optimization problem for arbitrary 2D objects in rectangular domains Article published earlier |
| spellingShingle | Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях Романова, Т.Е. Ступак, Е.А. Злотник, М.В. Інформатика та кібернетика |
| title | Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях |
| title_alt | A mathematical model and a method to solve the packing optimization problem for arbitrary 2D objects in rectangular domains |
| title_full | Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях |
| title_fullStr | Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях |
| title_full_unstemmed | Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях |
| title_short | Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях |
| title_sort | математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/7730 |
| work_keys_str_mv | AT romanovate matematičeskaâmodelʹimetodrešeniâzadačioptimizaciiupakovkiproizvolʹnyhdvumernyhobʺektovvprâmougolʹnyhoblastâh AT stupakea matematičeskaâmodelʹimetodrešeniâzadačioptimizaciiupakovkiproizvolʹnyhdvumernyhobʺektovvprâmougolʹnyhoblastâh AT zlotnikmv matematičeskaâmodelʹimetodrešeniâzadačioptimizaciiupakovkiproizvolʹnyhdvumernyhobʺektovvprâmougolʹnyhoblastâh AT romanovate amathematicalmodelandamethodtosolvethepackingoptimizationproblemforarbitrary2dobjectsinrectangulardomains AT stupakea amathematicalmodelandamethodtosolvethepackingoptimizationproblemforarbitrary2dobjectsinrectangulardomains AT zlotnikmv amathematicalmodelandamethodtosolvethepackingoptimizationproblemforarbitrary2dobjectsinrectangulardomains |