Please download to get full document.

View again

of 7
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

АДАПТИВНЫЕ Ф-ФУНКЦИИ ДЛЯ ДВУМЕРНЫХ ОБЪЕКТОВ

Category:

Business & Finance

Publish on:

Views: 9 | Pages: 7

Extension: PDF | Download: 0

Share
Related documents
Description
УДК Член-корреспондент НАН Украины Ю.Г.Стоян, Т.Е.Романова, Н.И.Чернов АДАПТИВНЫЕ Ф-ФУНКЦИИ ДЛЯ ДВУМЕРНЫХ ОБЪЕКТОВ При построении математических моделей оптимизационных задач упаковки и раскроя
Transcript
УДК Член-корреспондент НАН Украины Ю.Г.Стоян, Т.Е.Романова, Н.И.Чернов АДАПТИВНЫЕ Ф-ФУНКЦИИ ДЛЯ ДВУМЕРНЫХ ОБЪЕКТОВ При построении математических моделей оптимизационных задач упаковки и раскроя [] возникает необходимость в формализации ограничений на допустимые расстояния между геометрическими объектами. Применение нормализованных Ф- функций [] иногда приводит к сложным вычислительным процедурам. Цель данной работы построение Ф-функций, свободных от радикалов, учитывающих допустимые расстояния между двумерными объектами. Имеются замкнутые ограниченные ϕ -объекты A, B R [3]. Полагаем, что граница объекта A (или B ) задана последовательностью дуг окружностей и отрезков прямых, здесь R двумерное арифметическое евклидовое пространство. Допускаются аффинные отображения трансляции и поворота A и B. Положение A (или В) в пространстве R определяет вектор u = ( x, y, θ ), а координаты точек ( x, y) A (или ( x, y) B) определяются по формуле x= x0 cosθ + y0 snθ +x t, y x y = 0 snθ + 0 cosθ +y t, где ( x0, 0 t t y ) произвольная точка объекта A (или В) в собственной системе координат объекта A (или В), θ угол поворота, (x t, y t ) вектор трансляции объекта A (или В) в пространстве R. Пусть задано ограничение на минимально допустимое расстояние ρ между объектами A и B, т.е. dst(a,b) ρ, где dst(a,b)= mn (, ) dab a Ab, B, dab (, ) евклидово расстояние в R. В терминах Ф-функций это ограничение можно описать в виде Φ ρ, где Φ нормализованная Ф-функция объектов A и B [4]. Заметим, что Ф-функция объектов A и B зависит от векторов u A = ( x, y, θ ) и B u = ( x, y, θ ). B B B A A A Определим, так называемую, адаптивную Ф-функцию Φ, такую, что Φ = влечет Φ = 0. ρ Тогда справедливо соотношение dst(a,b) Φ 0. () ρ Рассмотрим множество A= A C( ρ ), где C( ρ ) круг радиуса ρ с центром в начале собственной системы координат множества A, символ операции суммы Минковского [5]. Тогда, полагаем Φ = Φ, где Φ Ф- функция объектов A и B. В [3] показано, что всегда существует свободная от радикалов Ф-функция для двух произвольных ϕ -объектов, граница которых описывается последовательностью отрезков прямых и дуг окружностей, в частности, для A и B, которая может быть определена как где Φ, =,, n, n Φ = mn{ Φ, Φ,..., Φ }, () n число пар базовых объектов [3], полученных в результате декомпозиции объектов A и В. В этом случае для определения Ф- функции () необходимо построение множества A в явном виде. Один из очевидных методов формирования множества A есть построение эквидистанты для границы множества А, используя, например, алгоритмы [6, 7]. В пределах данного исследования предлагается также иной подход, учитывающий особенности построения Ф-функций для ϕ -объектов, границы которых описываются дугами окружностей и отрезками прямых. В [3] приведено утверждение о том, что объект A всегда может быть представлен в виде где nt A nt A j =,, j Ip = {,,..., p}, j, A, A = A A p, (3) Aj I ={K, D, H, V}, nt( ) внутренность множества ( ), K выпуклый многоугольник, заданный вершинами p = (x, y ), =,,m; D = C T круговой сегмент, Т=conv{ p, p, p 3}, C круг радиуса r с центром (x c, y c ), pи p концевые точки хорды сегмента D; H=T C *, * C = R \ntc, Т=conv{H}, заданный вершинами p = (x, y ), =,,3; V = T C * C, где C круг радиуса r r, при этом * C C Φ = 0, * C C Φ Ф-функция C * и C [8]. Из этого утверждения следует, что множество A всегда может быть задано так: A= A A p, (4) где A I= { K, D, H, V }, A = A C( ρ ). где Учитывая (4), определим Ф-функцию для A и B в виде Φ j Ф-функция для множеств Φ = mn{ Φ j, A I, B j I. Ip, j Iq }, (5) Из (4) следует необходимость построения полного класса адаптивных Ф- функций Φ для множеств A и B из семейства базовых объектов I, что эквивалентно построению класса Ф-функций Φ для всех пар множеств A I и В I. Осуществим декомпозицию каждого объекта A I, используя алгоритм [9]. Заметим, что результат декомпозиции объектов K и D может быть однозначно m определен так (рис. ): K = D K, где K =conv{ p,, p m }; 3 D = D K, где = = K=conv{ p,, p 4 }. Рис.. Декомпозиция объектов K и D В случае декомпозиции объектов A { H, V } на базовые объекты из множества I, в зависимости от соотношений ρ и r, а также размерности угла α, имеем: H = 3 D K, где K=conv{ p,, p 5 }, (рис. а), если r = H = 5 D K K = ρ, α 90, где K =conv{ p,, p 4 }, K =conv{ p,, p 5 }, (рис.б), если ρ = r, α 90 ; H = 5 D H K K, где K =conv{ p,, p 6 }, K =conv{ p,, p 5 }, (рис. в), если ρ r для любого α ; H = 5 D K, где K=conv{ p,, p 7 }, (рис. г), если r = = ρ, α 90 ; a б в г Рис.. Декомпозиция объектов H 6 V = D H K K =, где K =conv{ p,, p 6 }, K =conv{ p,, p 5 }, (рис.3а.), если ρ r, 6 V = D K, где K =conv{ p,, p 7 }, (рис.3б.), если ρ r. = а б Тогда для В I, имеем Рис.3. Декомпозиция объектов V KB Φ =mn { Φ KB DB, Φ, =,,m}; (6) DB Φ =mn { Φ KB DB, Φ, =,,3}; (7) HB Φ =mn { Φ K DB, Φ, =,,3}, если ρ r, α 90, (8) HB K j DB = Φ =mn { Φ, j=,, Φ, =,,5}, если ρ r, α 90 HB Φ =mn { Φ HB, K jb DB Φ, j=,, Φ, =,,5}, если ρ r для любого α, HB Φ =mn { Φ K DB, Φ, =,,5}, если ρ r, α 90 ; VB Φ =mn { Φ KB DB, Φ, =,,6}, если ρ r, (9) VB Φ =mn { Φ HB, K jb DB Φ, j=,, Φ, =,,6}, если ρ r. (0), функций Таким образом, формулы (6)-(0) описывают полный класс адаптивных Ф- Φ для базовых объектов A, B I. Из ()-(0) следует справедливость следующего утверждения. Теорема. Для ϕ -объектов A и B, границы которых формируются последовательностью дуг окружностей и отрезков прямых всегда существует свободная от радикалов адаптивная Ф-функция допустимые расстояния между объектами A и B. Таким образом, Ф-функция определена как Ф-функция A I, B j I, I j I p, q Φ Φ для множеств, вида Φ Φ = mn{ Φ, Φ,..., Φ },, учитывающая минимально (5) для множеств A и B может быть A= A A p, B=B B q, n где Φ Φ = { Φ, Φ, Φ, Φ, Φ, Φ, Φ, Φ, Φ, Φ }, I KK DK HK VK DH HH VH DD DV VV p n q n =, = n число базовых объектов Al I, формирующих декомпозицию объектов A I, n A = Al. l= Замечание. Для формирования Ф-функций бесконечно дифференцируемые функции. Φ используются только Если для пары ограниченных ϕ -объектов A, B R, задано ограничение на максимально допустимое расстояние ρ + между ними, т.е. dst(a,b) ρ + + Φ ρ + Φ 0, то адаптивная Ф-функция Φ +, учитывающая максимально допустимые расстояния строится аналогично предложенному выше подходу. Теорема. Для ϕ -объектов A и B, границы которых формируются последовательностью дуг окружностей и отрезков прямых всегда существует свободная от радикалов адаптивная Ф-функция допустимые расстояния между объектами A и B. Φ +, учитывающая максимально Ограничение ρ dst(a,b) ρ + может быть задано системой неравенств вида { Φ 0, Φ 0. + Литература. Wäscher, G., Haußner, H. and Schumann, H., An mproved typology of cuttng and packng problems, European Journal of Operatonal Research, Volume 83, Issue 3, 6, 007, pp Stoyan, YG, Chugay, A., (008), Packng cylnders and rectangular paralleleppeds wth dstances between them, European J. Oper. Res., 97, N. Chernov, Y. Stoyan, T. Romanova, Mathematcal model and effcent algorthms for object packng problem/ Computatonal Geometry: Theory and Applcatons, vol. 43:5 (00), pp 4. J. Bennell, G. Schethauer, Yu. Stoyan, and T. Romanova, Tools of mathematcal modellng of arbtrary object packng problems, J. Annals of Operatons Research, Publsher Sprnger Netherlands, do:0.007/s Mnkovsk H. Dchteste gtterformge. Lagerung, n Nachr. Ges. Wss. - Gottngen, Построение эквидистанты Rus 7. Построение эквидистанты Eng 8. Stoyan, Y., Terno, J., Schethauer, G., Gl, N. and Romanova, T.,(00), Phfunctons for prmary D-objects, Studa Informatca Unversals, Н.И. Гиль, Т.Е. Романова, М.В. Злотник, Декомпозиция двумерных геометрических объектов. Доп. НАН України
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks