Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины

A mathematical model of the optimization placement problem of circles and non-convex polygons with rotations into a rectangle of minimal length is built, and its peculiarities are investigated. An algorithm of solving the problem is developed. This algorithm allows one to get an approximation to the...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2007
Автори:	Злотник, М.В., Стоян, Ю.Г.
Формат:	Стаття
Мова:	Russian
Опубліковано:	"Доповіді НАН України" 2007
Теми:	Інформатика та кібернетика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/1604
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины / Ю.Г. Стоян, М.В. Злотник // Доп. НАН України. — 2007. — N 2. — С. 37-42. — Библиогр.: 12 назв. — рус.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-1604
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-16042025-02-10T01:00:24Z Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины Злотник, М.В. Стоян, Ю.Г. Інформатика та кібернетика A mathematical model of the optimization placement problem of circles and non-convex polygons with rotations into a rectangle of minimal length is built, and its peculiarities are investigated. An algorithm of solving the problem is developed. This algorithm allows one to get an approximation to the global minimum of the problem. A numerical example is given. 2007 Article Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины / Ю.Г. Стоян, М.В. Злотник // Доп. НАН України. — 2007. — N 2. — С. 37-42. — Библиогр.: 12 назв. — рус. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/1604 519.85 ru application/pdf "Доповіді НАН України"
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Інформатика та кібернетика Інформатика та кібернетика
spellingShingle	Інформатика та кібернетика Інформатика та кібернетика Злотник, М.В. Стоян, Ю.Г. Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины
description	A mathematical model of the optimization placement problem of circles and non-convex polygons with rotations into a rectangle of minimal length is built, and its peculiarities are investigated. An algorithm of solving the problem is developed. This algorithm allows one to get an approximation to the global minimum of the problem. A numerical example is given.
format	Article
author	Злотник, М.В. Стоян, Ю.Г.
author_facet	Злотник, М.В. Стоян, Ю.Г.
author_sort	Злотник, М.В.
title	Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины
title_short	Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины
title_full	Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины
title_fullStr	Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины
title_full_unstemmed	Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины
title_sort	размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины
publisher	"Доповіді НАН України"
publishDate	2007
topic_facet	Інформатика та кібернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/1604
citation_txt	Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины / Ю.Г. Стоян, М.В. Злотник // Доп. НАН України. — 2007. — N 2. — С. 37-42. — Библиогр.: 12 назв. — рус.
work_keys_str_mv	AT zlotnikmv razmeŝeniekrugovinevypuklyhmnogougolʹnikovspovorotamivprâmougolʹnikeminimalʹnoidliny AT stoânûg razmeŝeniekrugovinevypuklyhmnogougolʹnikovspovorotamivprâmougolʹnikeminimalʹnoidliny
first_indexed	2025-12-02T09:09:13Z
last_indexed	2025-12-02T09:09:13Z
_version_	1850386995689291776
fulltext	оповiдi НАЦIОНАЛЬНОЇ АКАДЕМIЇ НАУК УКРАЇНИ 2 • 2007 IНФОРМАТИКА ТА КIБЕРНЕТИКА УДК 519.85 © 2007 Член-корреспондент НАН Украины Ю.Г. Стоян, М. В. Злотник Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины A mathematical model of the optimization placement problem of circles and non-convex polygons with rotations into a rectangle of minimal length is built, and its peculiarities are investigated. An algorithm of solving the problem is developed. This algorithm allows one to get an approxi- mation to the global minimum of the problem. A numerical example is given. Задачи размещения многоугольников с поворотами рассматривались в [1, 2]. Однако в этих работах осуществляется поиск решений, которые не всегда соответствуют стационарным точкам (локальному минимуму или седловой точке). Кроме того, из-за отсутствия стро- гой математической модели задачи для ее решения не всегда используются современные эффективные методы локальной и глобальной оптимизации. Рассматриваемая в данной работе задача имеет следующую постановку. Даны круги Ci радиусом ri, i = 1, 2, . . . ,m1, невыпуклые многоугольники Pi, заданные координатами своих вершин, i = m1 + 1, . . . ,m1 +m2 = m, и прямоугольник S = {(x, y) ∈ R2, 0 6 y 6 w, 0 6 x 6 6 l}, где l является переменной. Обозначим параметры размещения через ui = (vi, θi) = = (xi, yi, θi), где xi, yi — координаты центра собственной системы координат объекта Ti, а θi — угол поворота собственной системы координат объекта относительно неподвижной системы координат. Множество Ti, для которого задан вектор движения ui = (vi, θi), обо- значим через Ti(ui), T ∈ {C,P}, вектор переменных задачи — через X = (u, l) ∈ Rq+1, где u = {u1, u2, . . . , um}, u ∈ Rq, q = 2m1 + 3m2. Задача. Необходимо определить вектор X∗, при котором круги Ci, i = 1, 2, . . . ,m1, и многоугольники Pi, i = m1 + 1, . . . ,m, размещаются в прямоугольнике S и его длина l принимает минимальное значение. Построим математическую модель этой задачи, воспользовавшись Ф-функциями для пары кругов [3], круга и невыпуклого многоугольника, пары невыпуклых многоугольни- ков [4]. Тогда математическая модель задачи имеет вид: min u∈D F (u, l) = l∗, (1) ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №2 37 область допустимых решений D поставленной задачи описывается следующей системой: D :                        ΦC i (ui) > 0, i = 1, . . . ,m1, ΦP i (ui) > 0, i = m1 + 1, . . . ,m, ΦCC ij (ui, uj) > 0, i < j = 2, . . . m1, ΦCP ij (ui, uj) > 0, i = 1, . . . ,m1, j = m1 + 1, . . . ,m, ΦPP ij (ui, uj) > 0, i < j = m1 + 2, . . . ,m, (2) где ΦC i (ui) = min{xi − ri, yi − ri, w − yi − ri, l − xi − ri}, ΦP i (ui) = min v=1,...,ni min ϑ=1,...,4 fϑiv(ui), f1iv = xi + xiv\| cos θi\| + yiv\| sin θi\|, f2iv = yi − xiv\| sin θi\| + yiv\| cos θi\|, f3iv = l − (xi + xiv\| cos θi\| + yiv\| sin θi\|), f4iv = w − (yi − xiv\| sin θi\| + yiv\| cos θi\|), ΦCC ij (ui, uj) = √ (xi − xj)2 + (yi − yj)2 − ri − rj , ΦCP ij (ui, uj) = min t=1,...,nj ΦCK ijt (ui, uj), ΦCK ijt (ui, uj) = max k=1,...,njt max{minψk{(ui, uj), ωk(ui, uj)}, χ ∗ k(ui, uj)}, ψk(ui, uj) = A′ k(x ′ j) −B′ k(y ′ j) +C ′ k, C ′ k = −A′ k(xjtk + x∗k−1) +B′ k(yjtk + y∗k−1), A′ k = y∗k − y∗k−1, B′ k = x∗k − x∗k−1, v∗k = (x∗k, y ∗ k) = r √ A2 k +B2 k ( Ak −Bk ) , Ak = yjtk+1 − yjtk, Bk = xjtk+1 − xjtk, v∗0 = v∗njt , Ck = −Akxjtk +Bkyjtk, ωk(ui, uj) = (x′j − xjtk) 2 + (y′j − yjtk) 2 − r2i , χ∗ k(ui, uj) = Ak(x ′ j) −Bk(y ′ j) + C∗ k , C∗ k = Ck −Akx ∗ k +Bky ∗ k, x′j = (xi − xj) cos θj − (yi − yj) sin θj, y′j = (xi − xj) sin θj + (yi − yj) cos θj, ΦPP ij (ui, uj) = min k=1,...,ni min t=1,...,nj ΦKK ikjt (ui, uj), ΦKK ikjt (ui, uj) = max{Ψ1(ui, uj),Ψ2(ui, uj), . . . ,Ψη(ui, uj)}, Ψν(ui, uj) = max{ων1 ikjt (ui, uj), ω ν2 ikjt (ui, uj), . . . , ω νdν ikjt (ui, uj), Ων1 ikjt (ui, uj),Ω ν2 ikjt (ui, uj), . . . ,Ω νιν ikjt (ui, uj)}Kν(θi, θj) + Hν(θi, θj), 38 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №2 Kν(θi, θj) = { 1, если Hν(θi, θj) = 0, 0, если Hν(θi, θj) 6= 0, Hν(θi, θj) = { 0, если βν−1 ikjt 6 \|θj − θi\| 6 βν ikjt , ω, если βν ikjt < \|θj − θi\| или \|θj − θi\| < βν−1 ikjt , ωνr ikjt (u1, u2) = (Xij(θi) − xikr + x′jtν(θi, θj))a νr ikjt − (Yij(θi) − yikr + y′jtν(θi, θj))b νr ikjt , Ωνr ikjt (u1, u2) = (Xji(θj) − x′′ikr(θi, θj) + xjtν)Aνr ikjt − (Yji(θj) − y′′ir(θi, θj) + yjν)B νr ij , Xij(θi) = (xj − xi) cos(θi) − (yj − yi) sin(θi), Yij(θi) = (xj − xi) sin(θi) + (yj − yi) cos(θi), x′jtν (θi, θj) = xjtν cos(θj − θi) + yjtν sin(θj − θi), y′jtν(θi, θj) = −xjtν sin(θj − θi) + yjtν cos(θj − θi), Xji(θj) = (xj − xi) cos(θj) − (yj − yi) sin(θj), Yji(θj) = (xj − xi) sin(θj) + (yj − yi) cos(θj), x′′ikr(θi, θj) = xikr cos(θj − θi) − yikr sin(θj − θi), y′′ikr(θi, θj) = xikr sin(θj − θi) − yikr cos(θj − θi), aνr ikjt = yikr+1 − yikr, bνr ikjt = xikr+1 − xikr, Aνr ikjt = yjtv+1 − yjtv, Bνr ikjt = xjtv+1 − xjtv, ΦC i (ui) — Φ-функция круга Ci и множества S∗ = cl(R2 \ S) [5]; clT — операция замыка- ния [6]; ΦP i (ui) — Ф-функция Pi и S∗; ΦCC ij (ui, uj) — Ф-функция Ci и Cj; ΦCP ij (ui, uj) — Ф-функция Ci и Pj ; ΦCK ijt (ui, uj) — Ф-функция Ci и Kjt; ΦPP ij (ui, uj) — Ф-функция Pi и Pj ; ΦKK ikjt (ui, uj) — Ф-функция Kik и Kjt ; Ph = nh ⋃ t=1 Kht [7], Kht — выпуклый многоугольник; nh — количество выпуклых многоугольников; xhtr, yhtr — координаты вершин многоуголь- ника Kht , r = 1, . . . , nht , nht — количество вершин Kht , h ∈ {i, j}. Особенности задачи (1)–(2). 1. D ⊂ Rq+1, D определяется системой линейных и нелинейных неравенств, а также яв- ляется ограниченной, в общем случае несвязной, и каждая компонента связности является многосвязной [6]. Кроме того, D — область овражного типа. 2. Задача является многоэкстремальной и NP трудной. 3. Локальные минимумы могут быть нестрогими. 4. Для выполнения ΦCK it (ui, uj) > 0, ΦPP it (ui, uj) > 0 достаточно выполнения одной из систем неравенств, которая входит в соответствующий набор систем неравенств. Стратегия решения. 1. В соответствии с модифицированным методом сужающихся окрестностей [8] генери- руются последовательности Ωj = (Ωj 1,Ω j 2, . . . ,Ω j m) номеров размещаемых объектов. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №2 39 2. Для быстрого получения начальных точек X используется представление геометри- ческих объектов в виде объединения элементарных прямоугольников, а также метод опти- мизации по группам переменных [9]. 3. Каждая точка X берется в качестве начальной для поиска локального минимума F (X∗). 4. Специальным образом формируется множество Γ∗ точек локальных минимумов. 5. В качестве приближения к глобальному минимуму принимается X0 = arg min X∈Γ∗ F (X), где Γ∗ — множество точек X∗. Для реализации модифицированного метода сужающихся окрестностей каждому кру- гу Ci и многоугольнику Pi ставятся в соответствие пары чисел ci = (ri, ri), i = 1, . . . ,m1, и pi = (ai, bi), i = m1 + 1, . . . ,m, где ai, bi — соответственно длина и ширина прямоу- гольника, описанного вокруг многоугольника Pi. Затем каждой последовательности Ωj = = (Ωj 1,Ω j 2, . . . ,Ω j m), состоящей из кругов Ci и многоугольников Pi, ставится в соответствие вектор vj = {vj 1, v j 2, . . . , v j m} ∈ R2m, где vj k может соответствовать ck или pk. Если ci 6= ct, pi 6= pt, ci 6= pt для i 6= t, то количество различных векторов vj равно m! Пусть V ⊂ R2m — множество всех векторов vj. Оптимизация в соответствии с модифицированным методом сужающихся окрестностей производится на множестве V в несколько этапов, на каждом из которых формируются окрестности и выбираются их центры [10]. Из всех полученных начальных точек специальным образом формируется множество Γ ⊂ D. Каждая точка X ∈ Γ берется в качестве начальной для решения задачи пои- ска локального минимума. Для поиска локального минимума используется модификация метода возможных направлений [11]. Для того чтобы определить вектор спуска Zk = = (zk 1 , z k 2 , . . . , z k m+1), из точки Xk на k-м этапе итеративного процесса Xk+1 = Xk + hZk, k = 0, 1, 2, . . . , η, поиска локального минимума первоначально выделяются ε-активные не- равенства 0 6 Ψkj (uk) 6 ε в точке Xk из системы (2). При этом в процессе решения задачи значение ε уменьшается. Для поиска вектора Zk решается следующая задача линейного программирования: max Zk∈Gk λ, где Gk определяется системой                        (−∇F (X), Zk) > λ, (∇Ψk1 (uk), Zk) > λ, (∇Ψk2 (uk), Zk) > λ, . . . (∇Ψkµ (uk), Zk) > λ, −1 6 zk i 6 1, i = 1, . . . ,m+ 1. (3) Поскольку ΦKK ikjt (ui, uj) является кусочно-гладкой, то при формировании системы (3) для точек, в которых не существует градиент, необходимо определять субградиент [12] ∇pΦ KK ikjt (ui, uj) этой функции. Множество таких точек определяется следующим условием: ω ν,r ikjt (u1, u2) = ω ν+1,r ikjt (u1, u2) = Ων,r ikjt (u1, u2) = Ων,r+1 ikjt (u1, u2). 40 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №2 В этом случае при формировании системы (3) участвуют четыре неравенства ων,r ikjt (u1, u2) > > 0, ων+1,r ikjt (u1, u2) > 0, Ων,r ikjt (u1, u2) > 0, Ων,r+1 ikjt (u1, u2) > 0. Аналогичным образом для ΦP i (ui) множество таких точек определяется следующими равенствами: fϑiv1 (ui) = fϑiv2 (ui) = . . . = fϑivς (ui), где vξ ∈ {1, . . . , ni}, ξ = 1, . . . , ς, ϑ = = 1, . . . , 4. Однако, при этом, из этих равенств необходимо выбрать только две функции, которые определяют ∇pΦ P i (ui), т. е. в формировании системы (3) в этом случае участвуют неравенства fϑivρ1 > 0 и fϑivρ2 > 0, такие что: если ϑ ∈ {1, 3}, то f2ivρ1 = max ξ=1,...,ς (f2ivξ ), f2ivρ2 = min ξ=1,...,ς (f2ivξ ); если ϑ ∈ {2, 4}, то f1ivρ1 = max ξ=1,...,ς (f1ivξ ), f1ivρ2 = min ξ=1,...,ς (f1ivξ ). П р и м е р . Имеются круги Ci, i = 1, . . . , 10, радиусом r1 = 2, r2 = 1,9, r3 = 1,8, r4 = 1,7, r5 = 1,6, r6 = 1,5, r7 = 1,4, r8 = 1,3, r9 = 1,2, r10 = 1,1 и многоугольники Pi, i = 11, . . . , 20, координаты вершин, заданные в собственной системе координат, приведены в табл. 1. Таблица 1. Координаты вершин многоугольников i 1 2 3 4 5 6 7 8 9 10 11 12 11 xi 0,5 0,5 1,5 1,5 0,5 0,5 −0,5 −0,5 −1,5 −1,5 −0,5 −0,5 yi 1,5 0,5 0,5 −0,5 −0,5 −1,5 −1,5 −0,5 0,5 0,5 0,5 1,5 12 xi 0 2 0 −2 — — — — — — — — yi 1,5 0,5 −3,5 1,5 — — — — — — — — 13 xi 0,75 2,75 0,75 −4,25 — — — — — — — — yi 0,75 −0,25 −1,25 0,75 — — — — — — — — 14 xi 0,75 2,75 0,75 −4,25 — — — — — — — — yi 4 −2 −3 1 — — — — — — — — 15 xi 2,417 3,583 2,583 0,583 −1,42 −2,92 — — — — — — yi 2,667 2,667 −2,33 −0,33 −0,33 −2,33 — — — — — — 16 xi −2,25 2,75 2,75 0,75 −1,25 −2,75 — — — — — — yi 2,667 2,667 −2,33 −0,33 −0,33 −2,33 — — — — — — 17 xi 1,5 0,5 0 −2 — — — — — — — — yi 1,063 −1,94 −0,19 1,063 — — — — — — — — 18 xi 0,75 0,75 0,25 −1,75 — — — — — — — — yi 1,063 −1,94 −0,19 1,063 — — — — — — — — 19 xi 2 0 −2 — — — — — — — — — yi 0,333 −0,67 0,333 — — — — — — — — — 20 xi 2 0 −2 — — — — — — — — — yi −0,67 −1,67 2,33 — — — — — — — — — Таблица 2. Параметры размещения кругов i 1 2 3 4 5 6 7 8 9 10 xi 6,644 13,90 16,83 13,33 11,93 15,07 17,07 10,36 17,43 17,53 yi 2,000 4,063 1,800 9,941 6,954 7,256 4,993 9,488 8,573 10,87 Таблица 3. Параметры размещения многоугольников i 11 12 13 14 15 16 17 18 19 20 xi 1,574 3,302 12,476 3,044 6,048 8,656 15,246 8,2940 10,99 1,661 yi 10,39 1,565 1,1709 6,440 8,429 3,591 10,937 10,927 11,49 2,679 θi 1,346 1,107 −0,449 −1,03 0,862 0,960 −0,000 −0,014 0,089 1,654 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №2 41 Рис. 1. Результат решения задачи Требуется разместить эти круги и многоугольники в прямоугольнике шириной 12 и минималь- ной длиной l0. Результат решения приведен на рис. 1, а значения параметров размещения кругов и многоу- гольников, соответствующие этому размещению, — в табл. 2 и 3. При этом l0 = 18,629. 1. Новожилова М.В. Методологiя розв’язку оптимiзацiйних нелiнiйних задач геометричного проекту- вання // Вiсн. Запорiзьк. держ. ун-ту. – 1999. – № 1. – С. 79–83. 2. Milencovich V. Rotational polygon overlap minimization and compaction // Computat. Geometry. – 1998. – No 10. – С. 305–318. 3. Stoyan Yu., Terno J., Scheithaue G. et al. Φ-functions for primary 2D-objects: Prepr. / Technische Uni- versität Dresden; MATH-NM – 15–2001. – Dresden. – 2001. – 28 p. 4. Stoyan Y.G. Φ-function of non-convex polygons with rotations // Пробл. машиностроения. – 2003. – Вып. 6. – No 1. – С. 74–86. 5. Stoyan Y., Gil M., Terno J., Scheithauer G. Ф-function for complex 2D objects // 4OR Quarterly J. of the Belgian, French and Italian Operations Research Societies. – 2004. – 2, No 1. – P. 69–84. 6. Александрян Р.А., Мирзаханян Э.А. Общая топология. – Москва: Высш. шк., 1979. – 336 с. 7. Пандорин О.К., Панкратов О.В., Новожилова М.В. Аналiз i складнiсть алгоритму зображення однозв’язного не опуклого многокутника у виглядi об’єднання опуклих многокутникiв // Вiсн. Запо- рiзьк. держ. ун-ту. – 1999. – № 2. – С. 79–83. 8. Стоян Ю.Г., Соколовский В. З. Решение некоторых многоэкстремальных задач методом сужающих- ся окрестностей. – Киев: Наук. думка, 1980. – 208 с. 9. Stoyan Yu., Gil’ N., Pankratov A., Scheithauer G. Packing of non-convex polytopes into a parallelepiped: Preprint / Technische Universität Dresden; MATH-NM – 06–2004. – Dresden, 2004. – 27 p. 10. Чугай А.М. Решение задачи упаковки кругов в выпуклый многоугольник с помощью модифициро- ванного метода сужающихся окрестностей // Радиоэлектроника и информатика. – 2005. – № 1. – С. 58–63. 11. Зонтендейк Г. Методы возможных направлений. – Москва: Изд-во иностр. лит., 1963. – 176 с. 12. Сухарев А.Г., Тимохов А.В., Федоров В. В. Курс методов оптимизации. – Москва: Наука, 1986. – 328 с. Поступило в редакцию 10.07.2006Институт проблем машиностроения им. А.Н. Подгорного НАН Украины, Харьков 42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №2

Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины

Репозитарії

Схожі ресурси