Математическая модель и метод решения задачи упаковки интервальных параллелепипедов
A mathematical interval model of the problem of optimization of a packing of interval parallelepipeds is developed. The transition to a two-criterion problem in the Euclid space is realized. A strategy of the solution based on the use of both the optimization with respect to the groups of variables...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/4116 |
| 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: | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов / Л. Г. Евсеева // Доп. НАН України. — 2008. — № 2. — С. 48-53. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859615607171842048 |
|---|---|
| author | Евсеева, Л. Г. |
| author_facet | Евсеева, Л. Г. |
| citation_txt | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов / Л. Г. Евсеева // Доп. НАН України. — 2008. — № 2. — С. 48-53. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| description | A mathematical interval model of the problem of optimization of a packing of interval parallelepipeds is developed. The transition to a two-criterion problem in the Euclid space is realized. A strategy of the solution based on the use of both the optimization with respect to the groups
of variables and the modified method of reducing neighborhoods is proposed.
|
| first_indexed | 2025-11-28T19:08:36Z |
| format | Article |
| fulltext |
УДК 519.859
© 2008
Л.Г. Евсеева
Математическая модель и метод решения задачи
упаковки интервальных параллелепипедов
(Представлено членом-корреспондентом НАН Украины Ю.Г. Стояном)
A mathematical interval model of the problem of optimization of a packing of interval parallelepi-
peds is developed. The transition to a two-criterion problem in the Euclid space is realized.
A strategy of the solution based on the use of both the optimization with respect to the groups
of variables and the modified method of reducing neighborhoods is proposed.
Многие прикладные и практические задачи размещения, упаковки, раскроя и покрытия
относятся к классу задач геометрического проектирования [1]. Задачи упаковки паралле-
лепипедов 3DBP (3D Bin Packing) занимают особое место в классе задач Cutting & Packing
(3D C&P) [2], что обусловлено их актуальностью и широким спектром приложений.
В основе предлагаемых исследователями [2, 3] методов решения задач трехмерной упа-
ковки — генетический алгоритм (genetic algorithm), алгоритм “имитационного отжига” (si-
mulated annealing algorithm), эвристические алгоритмы, методы динамического программи-
рования. Например, для решения задачи погрузки контейнеров (container loading problem)
предлагаются конструктивные эвристики, учитывающие практическое содержание задачи,
tabu поиск, методы линейного программирования.
Эффективные методы решения оптимизационных задач размещения разработаны в на-
учной школе Ю.Г. Стояна [1, 4]: модификации методов локальной и глобальной оптими-
зации. Однако, как правило, математическое моделирование и решение задач размещения
осуществлялось без учета погрешностей исходных данных, т. е. в идеализированной форме.
Развитие геометрического проектирования как научного направления предоставило воз-
можность учета погрешности метрических характеристик и параметров размещения гео-
метрических объектов в математических моделях задач и методах их решения на основе
использования приложения интервального анализа [5] в геометрическом проектировании,
интервальной геометрии [6]. Однако основное внимание уделялось двумерным задачам (см.,
например, [7]).
Целью настоящей работы является построение математической модели и разработка
метода решения задачи упаковки параллелепипедов с учетом погрешностей метрических
характеристик и параметров размещения объектов на основе применения таких понятий
интервальной геометрии, как интервальный параллелепипед, интервальное касание выпук-
лых интервальных многогранников, а также понятий элементарного интервального отобра-
жения и интервального направленного множества [8].
Рассмотрим оптимизационную задачу геометрического проектирования [1] в следующей
постановке. Пусть в евклидовом пространстве R3 имеется конечный набор параллелепипе-
дов Pi ∈ R3 с метрическими характеристиками
mν
i = (ai
1 ± νai
1
, ai
2 ± νai
2
, ai
3 ± νai
3
), (1)
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №2
где
ai
k ∈ R+, νai
k
∈ R+,
νai
k
< εai
k, ε ∈ (0, 1) ⊂ R1, k ∈ J3, i ∈ {0}
⋃
Jn, Jn = {1, 2, . . . , n}.
(2)
Значение ε зависит от конкретной прикладной или научной задачи и характеризует
точность задания исходных данных.
Пусть высота a0
3 параллелепипеда P0 является достаточно большой для того, чтобы
объекты Pi, i ∈ Jn, были гарантированно упакованы в область P0.
Обозначим через Pi(u
ν
i ) параллелепипед Pi с параметрами размещения
uν
i = (xi
1 ± νxi
1
, xi
2 ± νxi
2
, xi
3 ± νxi
3
) ∈ R3, νxi
k
∈ R1, k ∈ J3, i ∈ {0}
⋃
Jn. (3)
Задача. Найти вектор uν = (uν
1 , uν
2 , . . . , uν
n) ∈ R3n, такой, что параллелепипеды Pi(u
ν
i ) ⊂
⊂ P0(u
ν
0), i ∈ Jn, без взаимных пересечений и высота h∗ занятой части P0(u
ν
0) и ее погреш-
ность ν∗
h достигали минимума.
Представим метрические характеристики (2) и параметры размещения (3) в виде пары
(α, να) ∈ R2, где να ∈ R1 — погрешность задания величины α ∈ R1.
На основании гомеоморфизма [6] пространств IsR и R2 зададим биекцию
R2 ∋ (ai
k, νai
k
) ↔ 〈ai
k, νai
k
〉 = 〈Ai
k〉 ∈ IsR,
R2 ∋ (xi
k, νxi
k
) ↔ 〈xi
k, νxi
k
〉 = 〈Xi
k〉 ∈ IsR, k ∈ J3, i ∈ {0}
⋃
Jn.
(4)
В качестве математических моделей параллелепипедов Pi(u
ν
i ), i ∈ {0}
⋃
Jn, c метричес-
кими характеристиками mν
i и параметрами размещения uν
i в рамках данного исследования
рассматриваются точечные множества трехмерного интервального пространства:
Pi(Ui) ⊂ I
3
sR = IsR× IsR× IsR,
Pi(Ui) = intPi(Ui)
⋃
frPi(Ui), i ∈ {0}
⋃
Jn,
с интервальными метрическими характеристиками mi = {2〈Ai
1〉, 2〈A
i
2〉, 2〈A
i
3〉} и параметра-
ми размещения Ui = (〈Xi
1〉, 〈X
i
2〉, 〈X
i
3〉) ∈ I
3
sR, 〈Xi
k〉 = 〈xi
k, νxi
k
〉 ∈ IsR, k ∈ J3, i ∈ {0}
⋃
Jn,
которые являются интервальными направленными множествами [8]. При этом интерваль-
ное уравнение [6] интервальной границы frPi(Ui) [9] можно представить в виде
f(Ui) = 0, (5)
где
f(Ui) = max{f t
i (Ui), t = 1, 2, 3, 4, 5, 6}, ∀i ∈ {0}
⋃
Jn, 0 = 〈0, 0〉,
f
k
i (Ui) = (〈Xk〉 − 〈Xi
k〉) − 〈Ai
k〉, f
k+3
i (Ui) = −(〈Xk〉 − 〈Xi
k〉) − 〈Ai
k〉, ∀k ∈ J3,
〈X〉 = 〈x, νx〉 = 〈x,−νx〉 ∈ IsR − элемент, сопряженный элементу 〈X〉 = 〈x, νx〉 ∈ IsR.
Тогда задача может быть представлена как оптимизационная задача упаковки интер-
вальных параллелепипедов Pi(Ui) ⊂ I
3
sR, i ∈ Jn, в интервальной области P0(U0) ⊂ I
3
sR.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №2 49
Для аналитического описания взаимодействия объектов трехмерного интервального
пространства, следуя работе [10], введено понятие интервального Φ-отображения.
Отображение Φ : I
6
sR → IsR называется интервальным Φ-отображением для объектов
Ti(Ui) ⊂ I
3
sR, i = 1, 2, если оно удовлетворяет следующим свойствам:
1) Φ(U1, U2) > 0, если T1(U1)
⋂
T2(U2) = ∅;
2) Φ(U1, U2) = 0, если
{
intT1(U1)
⋂
intT2(U2) = ∅,
frT1(U1)
⋂
frT2(U2) 6= ∅;
3) Φ(U1, U2) < 0, если intT1(U1)
⋂
intT2(U2) 6= ∅.
На основании Ф-функции параллелепипедов идеализированного случая [10], а также
условия интервального касания точек интервального пространства I
3
sR [11], интервальное
Φ-отображение примет вид:
1) для интервального параллелепипеда Pi(Ui) и интервального объекта P
∗
0(U0) =
= I
3
sR \ clP0(U0)
⋃
frP0(U0)
Φ0i(U0, Ui) = max{f t
0i(U0, Ui), t = 1, 2, 3, 4, 5, 6},
f
k
0i(U0, Ui) = 〈Xi
k〉 − 〈X0
k
〉 + 〈−νa0
k
− νai
k
, νa0
k
− νai
k
〉,
f
k+3
0i (U0, Ui) = −〈Xi
k〉 − 〈X0
k〉 + 〈A0
k〉 − 〈Ai
k〉 − 〈νa0
k
+ νai
k
, 0〉, ∀k ∈ J3, i ∈ Jn;
(6)
2) для интервальных параллелепипедов Pi(Ui) и Pj(Uj), i, j ∈ Jn, i < j
Φij(Ui, Uj) = max{f t
ij(Ui, Uj), t = 1, 2, 3, 4, 5, 6},
f
k
ij(Ui, Uj) = 〈Xj
k〉 − 〈Xi
k〉 − 〈Ai
k〉 − 〈νai
k
+ ν
a
j
k
, ν
a
j
k
〉,
f
k+3
ij (Ui, Uj) = −〈Xj
k
〉 − 〈Xi
k
〉 − 〈Ai
k
〉 − 〈νai
k
+ ν
a
j
k
, ν
a
j
k
〉, ∀k ∈ J3,
(7)
где 〈Xi
k〉 − 〈X0
k 〉, 〈X
j
k〉 − 〈Xi
k〉, ∀k ∈ J3, — интервальные координаты параметров размеще-
ния U0i, Uij соответственно.
На основании гомеоморфизма пространств IsR и R2 [6], в качестве интервального ото-
бражения цели принимаем “интервальную высоту” 〈H〉 занятой части интервального па-
раллелепипеда P0(U0) как результат размещения в нем интервальных параллелепипедов
Pi(Ui), i ∈ Jn, где
〈H〉 = max
j∈Jn
ρ(Π0,Πj).
Здесь ρ(Π0,Πj) — интервальное расстояние [12] между интервальной гиперплоскостью
Π0 : f
6
0 (U0) = 0, участвующей в формировании frP0(U0), и интервальными гиперплоскос-
тями Πj : f
5
j (Uj) = 0, j ∈ Jn, участвующими в формировании frPj(Uj), и интервально па-
раллельными интервальной координатной плоскости 〈X〉O〈Y 〉. Здесь максимум понимаем
в соответствии с отношением линейного порядка в пространстве IsR.
На основании (6), (7) интервальную математическую модель задачи представим в виде
inf
(U,〈H〉)∈D⊂I
3n+1
s R
〈H〉, (8)
50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №2
где
D :
{
Φ0i(U0, Ui) > 0, i ∈ Jn,
Φij(Ui, Uj) > 0, i ∈ Jn, j ∈ Jn, i < j,
U = (U1, U2, . . . , Un) ∈ I
3n
s R, Ui = (〈Xi
1〉, 〈X
i
2〉, 〈X
i
3〉) ∈ I
3
sR, i ∈ Jn,
(9)
а Φ0i(U0, Ui) и Φij(Ui, Uj) определяются соотношениями (6) и (7).
Осуществим погружение математической модели (8), (9) в евклидово пространство
R6n+2, изометричное интервальному пространству I
3n+1
s R.
На основании определения интервального неравенства [6] и соотношений (6), (7), нера-
венствам из системы (9) в пространстве R6n+2 соответствуют наборы линейных уравнений
и неравенств вида
χk
ij :
−(xj
k − xi
k) − (aj
k + ν
a
j
k
+ νai
k
) > 0,
{
−(xj
k − xi
k) − (aj
k + ν
a
j
k
+ νai
k
) = 0,
−(ν
x
j
k
− νxi
k
) − (ν
a
j
k
+ νai
k
) > 0,
χk+3
ij :
(xj
k − xi
k) − (ai
k + νai
k
+ ν
a
j
k
) > 0,
{
(xj
k
− xi
k) − (ai
k + νai
k
+ ν
a
j
k
) = 0,
(ν
x
j
k
− νxi
k
) − (νai
k
+ ν
a
j
k
) > 0,
χk
0i :
xi
k − νa0
k
− νai
k
> 0,
{
xi
k − νa0
k
− νai
k
= 0,
νxi
k
+ νa0
k
− νai
k
> 0,
χk+3
0i :
−xi
k + (a0
k − ai
k) − (νa0
k
+ νai
k
) > 0,
{
−xi
k + (a0
k − ai
k) − (νa0
k
+ νai
k
) = 0,
−νxi
k
+ (νa0
k
− νai
k
) > 0,
∀k ∈ J3, i, j ∈ Jn.
(10)
Тогда математическую модель, полученную при погружении интервальной математи-
ческой модели (8), (9) в евклидово пространство, представим в виде
inf
(Un,h,νh)∈D⊂R6n+2
(h, νh), (11)
D =
6
⋂
t=1
((
n
⋂
i=1
χt
0i
)
⋂
(
n
⋂
i,j=1
i<j
χt
ij
))
, (12)
Un = (x1
1, νx1
1
, x1
2, νx1
2
, x1
3, νx1
3
, x2
1, νx2
1
, . . . , xn
1 , νxn
1
, xn
2 , νxn
2
, xn
3 , νxn
3
) ∈ R6n,
(h, νh) = H(〈H〉), H — гомеоморфизм [6], H3n+1(D) = D, D ⊂ I
3n+1
s R, D ⊂ R6n+2.
На основании особенностей области допустимых решений [7, 13] осуществим переход
от задачи (11), (12) c векторной функцией цели к последовательности однокритериальных
задач вида
h1 = min
(Un,h,νh)∈D⊂R6n+2
h, (13)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №2 51
ν
(1)
h
= min
(Un,h,νh)∈D⊂R6n+2
νh. (14)
h2 = min
(Un,h,νh)∈D∗⊂R6n+2
h, (15)
D∗ =
{
(Un, h, νh) ∈ D | νh = ν
(1)
h
}
.
Как известно [14], точка множества D тогда и только тогда является решением двух-
критериальной задачи (11), (12), когда она является единственным с точностью до эквива-
лентности [13] решением следующей задачи:
min
(Un,h,νh)∈D′⊂R6n+2
νh, (16)
где
D′ = {(Un, h, νh) ∈ D | h 6 h′}, h′ ∈ [h1, h2].
Каждое решение задачи (16) единственно с точностью до эквивалентности.
Общая стратегия решения задачи (16) может быть представлена следующим образом.
1. Решаем задачу (13):
1) генерируем последовательности размещаемых объектов модифицированным методом
сужающихся окрестностей [4, 14];
2) строим начальные точки методом оптимизации по группам переменных [1, 15] со-
гласно сгенерированным последовательностям;
3) осуществляем поиск точек локального минимума методом возможных направле-
ний [14].
2. Решаем задачу (14) аналогично (13).
3. Находим множество Парето [13] методом прямоугольников.
4. Находим решение задачи (16) методом последовательной оптимизации.
Разработано программное обеспечение “Packing interval parallelepipeds” INTPAR, реали-
зующее данную стратегию упаковки интервальных параллелепипедов.
Проведены численные эксперименты, по результатам которых можно сделать следую-
щие выводы.
Для произвольных ai
k и νai
k
= 0,01ai
k справедливо неравенство
h− < h + νh < h+,
[h∗ − νh∗ , h∗ + νh∗ ] ⊂ [h−, h+],
где h−, h+ — результаты приближенного решения задачи [13] в случае, когда параллелепи-
педы P−
i упаковываются в P+
0 , а P+
i , i ∈ Jn, — в P−
0 соответственно, где
P−
i (ui) = {(x1, x2, x3) ∈ R3 | xi = ai
k + νai
k
, k ∈ J3},
P+
i (ui) = {(x1, x2, x3) ∈ R3 | xi = ai
k + νai
k
, k ∈ J3}, i ∈ {0}
⋃
Jn.
Примененный в данной работе подход позволяет вычислить границы выходных данных
задачи и сузить полученный интервал при заданных границах входных параметров, таким
52 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №2
образом строго определяя интервал, в котором с неизбежностью будет лежать решение,
если значения входных параметров принадлежат заданным интервалам.
Программное обеспечение INTPAR может быть использовано при проектировании карт
трехмерного раскроя промышленных материалов, при создании малоотходных технологий,
в задачах минимизации транспортных расходов и других задач, которые моделируются
как 3DBP задачи с учетом погрешностей метрических характеристик и параметров разме-
щения.
1. Стоян Ю.Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического
проектирования. – Киев: Наук. думка, 1986. – 267 с.
2. Terno J., Lindemann R., Scheithauer G. Cutting Problems and Their Practical Solution. – Thun and
Frankfurt/Main: Verlag Harri Deutsch, 1987.
3. 3
rd ESICUP Meeting Euro Special Interest Group on Cutting and Packing. – Instituto Superior de
Engerharla do Porto. ISEP Portugal. – 2006. – March. – 16/18.
4. Стоян Ю.Г., Соколовский В. З. Решение некоторых многоэкстремальных задач методом сужающих-
ся окрестностей. – Киев: Наук. думка, 1980. – 208 с.
5. Kaucher E. Interval analysis in the extended interval space IR // Comp. Suppl. – 1980. – P. 33–49.
6. Стоян Ю.Г. Введення в iнтервальну геометрiю: Навч. пос. – Харкiв: ХНУРЕ, 2006. – 98 с.
7. Стоян Ю.Г., Романова Т. Е., Сысоева Ю.А. Оптимизационная задача размещения правильных ин-
тервальных многоугольников // Доп. НАН України. – 1998. – № 9. – С. 114–120.
8. Евсеева Л. Г., Романова Т. Е, Шеховцов С.Б. Интервальные направленные множества в многомерных
интервальных пространствах // Искусств. интеллект. – 2005. – № 4. – С. 169–176.
9. Стоян Ю.Г. Выпуклые интервальные многоугольники // Доп. НАН України. – 2000. – № 5. – С. 33–
39.
10. Stoyan Yu.G. Φ-function and its basic properties // Там само. – 2001. – No 8. – С. 112–117.
11. Романова Т. Е., Рудой Д.С. Интервальное касание точек интервального пространства I
3
sR // Ради-
оэлектроника и информатика. – 2000. – № 2. – С. 53–57.
12. Евсеева Л.Г. Интервальная метрика на n-мерном множестве центрированных интервалов // АСУ и
приборы автоматики. – 2006. – Вып. 136. – С. 50–56.
13. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – Москва:
Наука, 1982. – 256 с.
14. Чугай А.М. Решение задачи упаковки кругов в выпуклый многоугольник с помощью модифициро-
ванного метода сужающихся окрестностей // Радиоэлектроника и информатика. – 2005. – № 1. –
С. 58–63.
15. Стоян Ю.Г., Пономаренко Л.Д., Панкратов А.В., Лойко А.Ф. Программная система КТС автома-
тической компоновки бокса сложной технической системы блочной конструкции. – Харьков, 1987. –
37 с. – (Препринт / НАН Украины. ИПМаш; 264).
Поступило в редакцию 20.08.2007Полтавский университет потребительской
кооперации Украины
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №2 53
|
| id | nasplib_isofts_kiev_ua-123456789-4116 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-11-28T19:08:36Z |
| publishDate | 2008 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Евсеева, Л. Г. 2009-07-15T13:55:20Z 2009-07-15T13:55:20Z 2008 Математическая модель и метод решения задачи упаковки интервальных параллелепипедов / Л. Г. Евсеева // Доп. НАН України. — 2008. — № 2. — С. 48-53. — Бібліогр.: 15 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/4116 519.859 A mathematical interval model of the problem of optimization of a packing of interval parallelepipeds is developed. The transition to a two-criterion problem in the Euclid space is realized. A strategy of the solution based on the use of both the optimization with respect to the groups of variables and the modified method of reducing neighborhoods is proposed. ru Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Математическая модель и метод решения задачи упаковки интервальных параллелепипедов Article published earlier |
| spellingShingle | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов Евсеева, Л. Г. Інформатика та кібернетика |
| title | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов |
| title_full | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов |
| title_fullStr | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов |
| title_full_unstemmed | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов |
| title_short | Математическая модель и метод решения задачи упаковки интервальных параллелепипедов |
| title_sort | математическая модель и метод решения задачи упаковки интервальных параллелепипедов |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/4116 |
| work_keys_str_mv | AT evseevalg matematičeskaâmodelʹimetodrešeniâzadačiupakovkiintervalʹnyhparallelepipedov |