Функція Мінковського в задачах пакування
The problem of packing, which consists in the most rational placement of group of given objects, is considered. Since in modeling of the placement of goods, cutout of material and similar processes a question arises about non-intersection of objects so a new approach to construction of non-intersect...
Gespeichert in:
| Datum: | 2010 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2010
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/106953 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1867334293489975296 |
|---|---|
| author | Ostapenko, V. V. Iakunina, I. L. |
| author_facet | Ostapenko, V. V. Iakunina, I. L. |
| author_institution_txt_mv | [
{
"author": "V. V. Ostapenko",
"institution": null
},
{
"author": "I. L. Iakunina",
"institution": null
}
] |
| author_sort | Ostapenko, V. V. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-06T12:28:40Z |
| description | The problem of packing, which consists in the most rational placement of group of given objects, is considered. Since in modeling of the placement of goods, cutout of material and similar processes a question arises about non-intersection of objects so a new approach to construction of non-intersection conditions is offered through an inequality specified by the Minkowski function. Analytical formulas that describe the Minkowski functions from the difference/sum of various objects are constructed. |
| first_indexed | 2025-07-17T10:21:50Z |
| format | Article |
| fulltext |
© В.В. Остапенко, И.Л. Якунина, 2010
Системні дослідження та інформаційні технології, 2010, № 3 115
TIДC
НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ,
ІНФОРМАТИЦІ ТА ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ
УДК 519.8
ФУНКЦИЯ МИНКОВСКОГО В ЗАДАЧАХ УПАКОВКИ
В.В. ОСТАПЕНКО, И.Л. ЯКУНИНА
Рассмотрена задача упаковки, которая состоит в наиболее рациональном раз-
мещении группы заданных предметов. Поскольку при моделировании разме-
щения грузов, раскрое материала и подобных процессов возникает вопрос о
непересечении предметов, предложен новый подход к построению условий
непересечения при помощи неравенств, которые задаются функцией Минков-
ского. Построены аналитические формулы, описывающие функции Минков-
ского от разности (суммы) различных тел.
При размещении или упаковке предметов возникает вопрос об оптимальном
их расположении. То есть, задача упаковки заключается в моделировании
наиболее рационального размещения группы определенных предметов
[1–3]. Сюда же относятся задачи раскроя, в которых требуется так рас-
кроить кусок материала, чтобы получить максимальное число заготовок
[4–9]. При перевозке грузов (контейнеров) требуется упаковать как можно
больше предметов в заданном пространстве. Рассмотрим, к примеру, пере-
возку грузов в транспортном самолете. Грузы в контейнере самолета разме-
щаются в несколько рядов. Причем, центр тяжести всей совокупности гру-
зов должен находиться как можно ближе к центру тяжести самолета.
Поиск оптимального расположения груза, раскроя материала и модели-
рования подобных процессов приводит к вопросу о непересечении предме-
тов или заготовок. Этот вопрос является одним из центральных. В данной
работе грузы или заготовки описываются выпуклыми компактными множе-
ствами (телами).
В представленной работе предложен новый подход к построению усло-
вий непересечения. Два тела не пересекаются, если разность их «центров»
не принадлежит разности двух выпуклых множеств, которые описывают
размещение предметов. Этот факт выражается с помощью неравенства, ко-
торое задается функцией Минковского [10]. В работе построены аналитиче-
ские формулы, описывающие функции Минковского от разности (суммы)
различных тел.
1. УСЛОВИЕ НЕПЕРЕСЕЧЕНИЯ
Под телом будем понимать выпуклое компактное множество с непустой
внутренностью.
В.В. Остапенко, И.Л. Якунина
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 116
Будем считать, что два тела M и N не пересекаются, тогда и только
тогда, когда пересечением их внутренностей является пустое множество, т.е.
0intint /=NM ∩ . Нетрудно доказать, что это эквивалентно тому, что
NM intint0 −∉ . (1)
Представим ,)(,)( ByyNAxxM +=+= где BARyx n ,,, ∈ — вы-
пуклые компактные множества из nR .
Множества не пересекаются, т.е. 0int)(int /=NxM ∩ , тогда и только
тогда, когда, согласно (1),
CyxBAyxByAx int)(int)int()int(0 +−=−+−=+−+∉ , где BAC −= ,
или
Cxy int∉− . (2)
Для дальнейшей работы с выпуклыми множествами будем использо-
вать функцию Минковского [10]: { }CzzC λλµ ∈>= :0inf)( . Эта функция
интересна сама по себе как пример выпуклой функции [11].
Известно, что z является внутренней точкой множества C , т.е.
Cz int∈ тогда и только тогда, когда 1)( <zµ ; z является граничной точкой
множества C , т.е.
Cz ∂∈ тогда и только тогда, когда 1)( =zµ ; (3)
z не принадлежит замыканию множества C , т.е.
Cz∉ тогда и только тогда, когда 1)( >zµ . (4)
Поэтому, согласно (3), (4), условие не пересечения Mint и Nint , или
условие (2), можно записать в виде 1)( ≥− xyCµ .
2. ПОСТАНОВКА ЗАДАЧИ
Рассмотрим множества вида miAx ii ,,1, …=+ , где i
n
i ARx ,∈ — замкну-
тые выпуклые множества в nR , такие, что iAint0∈ .
Рассмотрим задачу упаковки множества тел miAi ,,1, …= , в выпуклое
множество nRN ⊂ . Это означает, что тела не должны попарно пересекать-
ся и должны содержаться в N . Аналогично предположим iAint0∈ ,
mi ,,1…= . Под векторами ix понимаем смещение этих тел относительно
точки 0 (начало координат).
Таким образом, на переменные ix наложим условия
( ) ( ) mjiAxAx jjii ,,1,,0 …∩ =∀/=++ , (5)
miNAx ii ,,1, …=∀⊂+ . (6)
Функция Минковского в задачах упаковки
Системні дослідження та інформаційні технології, 2010, № 3 117
Ограничение (5) — условие непересечения тел, ограничение (6) — ус-
ловие содержания тел во множестве N . Ограничение (6) можно записать в
виде
miANx ii ,,1,* …=∀∈ . (7)
Символ * обозначает геометрическую разность множеств. Понятие
геометрической разности впервые введено Г. Минковским [10], в дальней-
шем изучено и описано в работах Л.С. Понтрягина [12] и М.С. Ни-
кольского [13].
Определение. Пусть BA, — непустые множества в nR . Геометриче-
ской разностью BA * называется множество { }ABcRcC n ⊂+∈= : .
Отметим, что BA * может оказаться пустым множеством.
Обозначим
ijµ — функция Минковского множества ji AA − , mji ,,1, …=∀ ,
iν — функция Минковского множества miAN i ,,1,* …=∀ .
Из п. 1. следует, что условия (5), (7) можно переписать в виде
ijmiyx jiij ,,1,,,1,1)( …… ==≥−µ , mixii ,,1,1)( …=≤ν .
Включение множеств iA в N является упаковкой этих множеств, ко-
торая может не быть оптимальной по разным критериям.
Рассмотрим функционал min),,( 1 →nxxf … .
Под функционалом можно понимать, например, периметр, объем,
центр тяжести.
3. ПРИМЕРЫ ФУНКЦИЙ МИНКОВСКОГО ДЛЯ НЕКОТОРЫХ КЛАССОВ
МНОЖЕСТВ
1. Декартово произведение множеств. Пусть множество M пред-
ставимо в виде декартова произведения множеств, а именно
kMMM ××= …1 , где kn
k
n EMEM ⊂⊂ ,,1
1 … , nnn k =++…1 .
Тогда )(max)( i
M
i
M xx
i
µµ = .
Действительно, Mx λ∈ тогда и только тогда, когда ii
i Mx λ∈ ,
ni ,,1…=∀ .
2. Выпуклое центральносимметричное множество. Пусть C — вы-
пуклое, уравновешенное (центральносимметричное) множество, и Cint0∈ .
)(xCµ является нормой вектора x в пространстве nR .
Пусть CrA ii = . Если CbBCaA == , , то CbaBA )( +=± , 0, >ba .
В.В. Остапенко, И.Л. Якунина
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 118
Тогда )(1)( x
ba
x CBA µµ
+
=± .
3. Отрезок. Пусть ]1,1[−=C (рис. 1).
Тогда ||)( 11 xxC =µ
Пусть ]1,1[111 −== aCaC . Тогда ||1)( 1
1
11
x
a
xC =µ .
4. Параллелограмм. Пусть CaCaM n××= …1 . Тогда
⎭
⎬
⎫
⎩
⎨
⎧
= ||1max)( i
i
M x
a
xµ .
5. Шар. Пусть { }0,:),,( 222
11 >≤++∈= rrxxRxxM n
n
n …… . Тогда
=)(xMµ
r
x
= или
r
xx
x n
M
22
1)(
++
=µ .
6. Эллипсоид. Пусть D — положительно-определенная симметричная
матрица размерности nn× .
Под эллипсом будем понимать множество вида { :nRxM ∈=
}2, aDxDx ≤ . Тогда
a
xD
xM =)(µ .
Если ),,(diag 1 nddD …= , то
a
xdxd
x nn
M
222
1
2
1)(
++
=µ .
Последнее выражение можно переписать
2
2
2
1
2
1
222
1
2
1)(
n
nnn
M
a
x
a
x
a
xdxd
x ++=
++
=µ , где ni
d
aa
i
i ,,1, …== .
7. Цилиндр. На основании примера 1 разобьем цилиндр (рис. 2) на де-
картово произведение множеств: отрезка и шара. Т.е. приведем к виду
21 MMM ×= ,
где
}0,:),{( 22
2
2
1
2
21
1 >≤+∈= rrxxRxxM ,
{ }0,: 33
2 >≤≤−∈= ccxcRxM .
Воспользуемся тем, что в силу примера 1 для функции Минковского
справедливо:
{ } { })(),(max,:0inf 2
2
1
1
2211 xxMxMx µµλλλµ =∈∈>=
Рис. 1. Отрезок
Функция Минковского в задачах упаковки
Системні дослідження та інформаційні технології, 2010, № 3 119
Тогда
⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧ +
=
c
x
r
xx
M
3
2
2
2
1 ,maxµ .
8. Сумма прямоугольника и круга. Пусть имеется прямоугольник со
сторонами 12a и 22a , и окружность радиуса r (рис. 3).
Найдем функцию Минковского в первой четверти. В остальных четвер-
тях руководствуемся аналогичными рассуждениями.
Для точек, лежащих в области между осью 1OX и прямой 1l ,
ra
x
x
+
=
1
1)(µ . Для точек, лежащих в области между прямой 2l и осью 2OX
ra
x
x
+
=
2
2)(µ .
Осталось найти функцию Минковского для точек, лежащих в области
между прямыми 1l и 2l . Для начала введем обозначение λ
λ
=
1 . Тогда
( ) ( ) 22
22
2
11 raxax =−+− λλ .
Рис. 3. Сумма прямоугольника и круга
Рис. 2. Цилиндр
В.В. Остапенко, И.Л. Якунина
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 120
Решением данного квадратного уравнения будут
( ) ( )
2
2
2
1
2
2112
2
2
2
1
2
2211
xx
xaxaxxrxaxa
+
−−+±+
=λ . (8)
Определим знак. Для этого воспользуемся вспомогательной точкой с
координатами ),( 21 aa . Для нее точно известно, что 1=λ . Подставим 1=λ
и координаты точки в (8):
( ) ( )( ) ( )( )
( )
=
++
+−−++±++
= 2
2
2
1
2
2121
2
2
2
1
2
22
2
11
raa
raaaaraarraaa
( ) ( )
( )22
2
1
222
2
1
raa
rarraaa
++
+±++
= .
Для получения единицы следует взять знак « + ».
Таким образом, для точек, лежащих в области между прямыми 1l и 2l ,
функция Минковского имеет вид
( ) ( )22112
2
2
2
1
2
2211
2
2
2
1)(
xaxaxxrxaxa
xxx
−−+++
+
=µ .
Функция Минковского в остальных четвертях находится аналогично.
Таким образом, представленные примеры иллюстрируют использова-
ние функции Минковского для описания условия непересечения различных
множеств.
Необходимость задания условий непересечения множеств возникает
при формулировании различных задач, в том числе задач оптимизации.
Примером использования функции Минковского для описания условий не-
пересечения при формулировке одной оптимизационной задачи является
работа [14].
ВЫВОДЫ
Построены аналитические формулы функции Минковского для разности
(суммы) различных выпуклых множеств таких как параллелепипеды, элип-
соиды, круги и прямоугольники. Разработанный метод позволит строить
приближенные функции Минковского для разности различных тел.
Предложенный подход применяется для решения задач оптимального
размещения грузов.
ЛИТЕРАТУРА
1. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. — М.: Мир, 1990.
— 413 с.
2. Пшеничный Б.Н., Соболенко Л.А. Метод линеаризации для обратно-выпуклого
программирования // Кибернетика и системный анализ. — 1995. — № 6. —
С. 86–97.
Функция Минковского в задачах упаковки
Системні дослідження та інформаційні технології, 2010, № 3 121
3. Пшеничный Б.Н., Соболенко Л.А. Метод обратно-выпуклого программирова-
ния и укладка параллелепипедов // Кибернетика и системный анализ. —
1996. — № 3. — С. 16–26.
4. Рвачев В.Л., Стоян Ю.Г. Алгоритм решения задачи оптимального раскроя с
круговыми выкройками при наличии ограничений на расстояния между
парами выкроек // Кибернетика. — 1965. — № 3. — С. 73–83.
5. Рвачев В.Л., Стоян Ю.Г. К задаче об оптимальном размещении круговых
выкроек // Кибернетика. — 1965. — № 4. — С. 70–75.
6. Stoyan Y.G., Yaskov G.N. Mathematical model and solution method of optimization
problem of placement of rectangles and circles taking into account special con-
straints // Intertional Transaction Operation Research. — 1998. — 43 (1). —
P. 45–57.
7. Rebennack S., Kallrath J., Panos M. Pardalos. Column enumiration based decompo-
sition techniques for a class of non-convex MINLP problems // Journal of Global
Optimization. — 2009. — 43. — P. 277–297.
8. Kallrath J. Cutting circles and polygons from area-minimizing rectangles // Journal
of Global Optimization. — 2009. — 43. — P. 299–328.
9. Stoyan Y.G., Yaskov G.N. A mathematical model and solution method For the prob-
lem of placing various-sized circles into a strip // European Journal of Operation
Research. — 2004. — 156. — P. 590–600.
10. Minkowski H. Verhandlungen des III internationalen Mathematiker-Kongresses in
Heidelberg. — Berlin, 1904. — P. 164–173.
11. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука.
Главная редакция физико-математической литературы, 1980. — 320 с.
12. Понтрягин Л.С. О линейных дифференциальных играх I // ДАН СССР. —
1967. — 174, № 6. — С. 1278–1280.
13. Никольский М.С. Первый прямой метод Л.С.Понтрягина в дифференциальных
играх. — М.: МГУ, 1984. — 64 с.
14. Остапенко В.В., Соболенко Л.А. Упаковка различных эллипсоидов в паралле-
лепипед с минимальной суммой сторон // Матеріали ХІ міжнар. наук.-техн.
конф. «Системний аналіз та інформаційні технології» 26–30 травня 2009 р.
— Киев: ННК «ІПСА» НТУУ «КПІ», 2009. — С. 168.
Поступила 03.12.2009
|
| id | journaliasakpiua-article-106953 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:21:50Z |
| publishDate | 2010 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/63/91cd11aa464b6a6891156768a7dc6563.pdf |
| spelling | journaliasakpiua-article-1069532018-04-06T12:28:40Z Minkowski function in packing problems Функция Минковского в задачах упаковки Функція Мінковського в задачах пакування Ostapenko, V. V. Iakunina, I. L. The problem of packing, which consists in the most rational placement of group of given objects, is considered. Since in modeling of the placement of goods, cutout of material and similar processes a question arises about non-intersection of objects so a new approach to construction of non-intersection conditions is offered through an inequality specified by the Minkowski function. Analytical formulas that describe the Minkowski functions from the difference/sum of various objects are constructed. Рассмотрена задача упаковки, которая состоит в наиболее рациональном размещении группы заданных предметов. Поскольку при моделировании размещения грузов, раскрое материала и подобных процессов возникает вопрос о непересечении предметов, предложен новый подход к построению условий непересечения при помощи неравенств, которые задаются функцией Минковского. Построены аналитические формулы, описывающие функции Минковского от разности (суммы) различных тел. Розглянуто задачу пакування, яка полягає в найбільш раціональному розміщенні групи заданих предметів. Оскільки при моделюванні розміщення вантажів, розкрою матеріалу та подібних процесів виникає питання про неперетин предметів, запропоновано новий підхід до побудови умов неперетину за допомогою нерівності, яка задається функцією Мінковського. Побудовано аналітичні формули, які описують функції Мінковського від різниці (суми) різних тіл. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2010-09-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/106953 System research and information technologies; No. 3 (2010); 115-121 Системные исследования и информационные технологии; № 3 (2010); 115-121 Системні дослідження та інформаційні технології; № 3 (2010); 115-121 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/106953/101952 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Ostapenko, V. V. Iakunina, I. L. Функція Мінковського в задачах пакування |
| title | Функція Мінковського в задачах пакування |
| title_alt | Minkowski function in packing problems Функция Минковского в задачах упаковки |
| title_full | Функція Мінковського в задачах пакування |
| title_fullStr | Функція Мінковського в задачах пакування |
| title_full_unstemmed | Функція Мінковського в задачах пакування |
| title_short | Функція Мінковського в задачах пакування |
| title_sort | функція мінковського в задачах пакування |
| url | https://journal.iasa.kpi.ua/article/view/106953 |
| work_keys_str_mv | AT ostapenkovv minkowskifunctioninpackingproblems AT iakuninail minkowskifunctioninpackingproblems AT ostapenkovv funkciâminkovskogovzadačahupakovki AT iakuninail funkciâminkovskogovzadačahupakovki AT ostapenkovv funkcíâmínkovsʹkogovzadačahpakuvannâ AT iakuninail funkcíâmínkovsʹkogovzadačahpakuvannâ |