Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов
Проведено исследование оптимизационной задачи размещения многоугольных неориентированных объектов в полосе, выделены дополнительные свойства области допустимых решений задачи, на основе которых предложена линеаризация функций основных ограничений области допустимых решений, позволяющая с наперед зад...
Gespeichert in:
| Datum: | 2010 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2010
|
| Schriftenreihe: | Математичні машини і системи |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/51603 |
| 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: | Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов / И.А. Чуб, М.В. Новожилова // Мат. машини і системи. — 2010. — № 2. — С. 99-107. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-51603 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-516032025-02-09T17:51:17Z Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов Побудова лінійної апроксимації області припустимих рішень задачі розміщення неорієнтованих геометричних об'єктів Construction of lineаr approximation of region of admissible decisions of placement problem of non-oriented geometrical objects Чуб, И.А. Новожилова, М.В. Моделювання і управління великими системами Проведено исследование оптимизационной задачи размещения многоугольных неориентированных объектов в полосе, выделены дополнительные свойства области допустимых решений задачи, на основе которых предложена линеаризация функций основных ограничений области допустимых решений, позволяющая с наперед заданной точностью свести рассматриваемую нелинейную оптимизационную задачу к набору задач линейного программирования. Проведено дослідження оптимізаційної задачі розміщення багатокутних неорієнтованих об'єктів у смузі, виділені додаткові властивості області припустимих рішень задачі, на основі яких запропонована лінеаризація функцій основних обмежень області припустимих рішень, що дозволяє з наперед заданою точністю звести розглянуту нелінійну оптимізаційну задачу до набору задач лінійного програмування. An optimization placement problem of non-oriented polygons on a strip is considered. A linearization of approximation procedure for restriction functions is proposed on the base of studying additional peculiarities of the problem. As a result, we can present the placement problem of non-oriented objects as a set of linear programming problems with a prescribed accuracy. 2010 Article Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов / И.А. Чуб, М.В. Новожилова // Мат. машини і системи. — 2010. — № 2. — С. 99-107. — Бібліогр.: 5 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/51603 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 |
Проведено исследование оптимизационной задачи размещения многоугольных неориентированных объектов в полосе, выделены дополнительные свойства области допустимых решений задачи, на основе которых предложена линеаризация функций основных ограничений области допустимых решений, позволяющая с наперед заданной точностью свести рассматриваемую нелинейную оптимизационную задачу к набору задач линейного программирования. |
| format |
Article |
| author |
Чуб, И.А. Новожилова, М.В. |
| author_facet |
Чуб, И.А. Новожилова, М.В. |
| author_sort |
Чуб, И.А. |
| title |
Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов |
| title_short |
Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов |
| title_full |
Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов |
| title_fullStr |
Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов |
| title_full_unstemmed |
Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов |
| title_sort |
построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2010 |
| topic_facet |
Моделювання і управління великими системами |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/51603 |
| citation_txt |
Построение линейной аппроксимации области допустимых решений задачи размещения неориентированных геометрических объектов / И.А. Чуб, М.В. Новожилова // Мат. машини і системи. — 2010. — № 2. — С. 99-107. — Бібліогр.: 5 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT čubia postroenielinejnojapproksimaciioblastidopustimyhrešenijzadačirazmeŝeniâneorientirovannyhgeometričeskihobʺektov AT novožilovamv postroenielinejnojapproksimaciioblastidopustimyhrešenijzadačirazmeŝeniâneorientirovannyhgeometričeskihobʺektov AT čubia pobudovalíníjnoíaproksimacííoblastípripustimihríšenʹzadačírozmíŝennâneoríêntovanihgeometričnihobêktív AT novožilovamv pobudovalíníjnoíaproksimacííoblastípripustimihríšenʹzadačírozmíŝennâneoríêntovanihgeometričnihobêktív AT čubia constructionoflinearapproximationofregionofadmissibledecisionsofplacementproblemofnonorientedgeometricalobjects AT novožilovamv constructionoflinearapproximationofregionofadmissibledecisionsofplacementproblemofnonorientedgeometricalobjects |
| first_indexed |
2025-11-29T02:50:35Z |
| last_indexed |
2025-11-29T02:50:35Z |
| _version_ |
1850091426923151360 |
| fulltext |
© Чуб И.А., Новожилова М.В., 2010 99
ISSN 1028-9763. Математичні машини і системи, 2010, № 2
МОДЕЛЮВАННЯ І УПРАВЛІННЯ ВЕЛИКИМИ СИСТЕМАМИ
УДК 519.85
И.А. ЧУБ, М.В. НОВОЖИЛОВА
ПОСТРОЕНИЕ ЛИНЕЙНОЙ АППРОКСИМАЦИИ ОБЛАСТИ ДОПУСТИМЫХ
РЕШЕНИЙ ЗАДАЧИ РАЗМЕЩЕНИЯ НЕОРИЕНТИРОВАННЫХ
ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ
Abstract. An optimization placement problem of non-oriented polygons on a strip is considered. A linearization of
approximation procedure for restriction functions is proposed on the base of studying additional peculiarities of the
problem. As a result, we can present the placement problem of non-oriented objects as a set of linear programming
problems with a prescribed accuracy.
Key words: placement of non-oriented objects, linear approximation, region of admissible decisions.
Анотація. Проведено дослідження оптимізаційної задачі розміщення багатокутних неорієнтованих об'єктів
у смузі, виділені додаткові властивості області припустимих рішень задачі, на основі яких запропонована
лінеаризація функцій основних обмежень області припустимих рішень, що дозволяє з наперед заданою
точністю звести розглянуту нелінійну оптимізаційну задачу до набору задач лінійного програмування.
Ключові слова: розміщення багатокутних неорієнтованих об'єктів, лінійна апроксимація, область
припустимих рішень.
Аннотация. Проведено исследование оптимизационной задачи размещения многоугольных
неориентированных объектов в полосе, выделены дополнительные свойства области допустимых
решений задачи, на основе которых предложена линеаризация функций основных ограничений области
допустимых решений, позволяющая с наперед заданной точностью свести рассматриваемую нелинейную
оптимизационную задачу к набору задач линейного программирования.
Ключевые слова: размещение многоугольных неориентированных объектов, линейная аппроксимация,
область допустимых решений.
1. Введение
Задача оптимального размещения конечного набора неориентированных многоугольных
геометрических объектов в заданной многосвязной многоугольной области относится к классу
задач оптимизационного геометрического проектирования [1] и является объектом пристального
внимания исследователей, о чем свидетельствует постоянно растущее число публикаций [1–4] как
в нашей стране, так и за рубежом. К задачам такого рода относятся, например, задачи раскроя
изотропного материала (металлопрокат, ткань с соответствующими характеристиками, стекло,
пластмасса и.т.д.) на многоугольные заготовки. При этом, если над многоугольником допустимо
аффинное преобразование поворота, такой геометрический объект называют неориентированным.
Данная задача является многомерной многоэкстремальной задачей нелинейного
невыпуклого программирования с весьма специфичной областью допустимых решений, что
затрудняет или делает невозможным применение классических методов условной оптимизации [5].
Эффективные точные методы решения задач практической размерности отсутствуют.
Актуальность рассматриваемого класса задач обуславливает необходимость создания
программного обеспечения процесса решения, основанного на современном математическом
инструментарии.
Целью настоящей статьи является выделение новых свойств области допустимых решений
математической модели задачи и построение линейной аппроксимации основных ограничений
области допустимых решений, причем точность аппроксимации является экзогенным параметром.
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 100
2. Постановка задачи
Пусть есть набор { } NiRR i ,1, == выпуклых неориентированных многоугольников, заданных в
арифметическом евклидовом пространстве 2E , и область размещения 0R вида
c
C
c
SR Ω∪=
=100 / , (1)
где ( ){ [ ) [ ] var},,,0,,0, 2
0 ==∈∈∈= zconstWWyzxEyxS – полубесконечная полоса,
),b,(a cccΩ C 1,2,...c = – множество выпуклых областей запрета, )b,(a cc – фиксированные
параметры.
Объект iR задается упорядоченным против часовой стрелки набором i
n
i
n
i nnyx ,1)},,{( =
координат его вершин в собственной системе координат iii YOX , Ni ,1= .
Положение iR в общей системе координат XOY , связанной с областью 0R , задается
вектором параметров размещения
( ) ( )iiiiii yxvu ϕϕ ,,, == , который опре-
деляет начало его собственной системы
координат iii YOX . При этом компонента
( )iii yxv ,= задает трансляцию iO , а
угловой параметр jϕ − поворот системы
координат iii YOX относительно iO
(рис. 1).
Задача размещения такова:
необходимо разместить набор NiRi ,1, =
объектов без взаимных наложений в области
0R так, чтобы длина занятой части полосы z была минимальной.
Математическая модель оптимизационной задачи размещения имеет вид:
13
minarg*
+⊂∈
=
NЕDu
zu , (2)
где ),,,,...,,,,,,(),,...,,( 22211121 zyxyxyxzuuuu NNNN ϕϕϕ== , 321 DDDD I∩= − область
допустимых решений задачи; 1D – подобласть пространства 13 +NЕ , выделяемая ограничениями
на размещение в полосе 0S ; 2D – подобласть 13 +NЕ , задаваемая условиями попарного взаимного
непересечения ),( ciR Ω , Ni ,1= , Сс ,1= ; 3D – подобласть 13 +NЕ , выделяемая условиями
попарного взаимного непересечения объектов размещения ),( ji RR , jiNji ≠= ,,1, .
Приведем основные свойства области D , необходимые для дальнейших построений.
z
( )ii y,x
iR
W
jx
jR
1Ω
Рис. 1. Область размещения с размещаемыми
объектами и неподвижной областью запрета
X
Y
O
jX
jY
jO jy
jϕ
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 101
Свойство 1. Область D − невыпуклое несвязное ограниченное точечное множество,
имеющее кусочно-гладкую границу FrD=Ψ , NE3⊂Ψ . Каждая компонента связности области D
является многосвязной. Гиперповерхность Ψ состоит из гладких участков, которые описываются
линейными и нелинейными ограничениями.
Свойство 2. Число ограничений Ι, описывающих область D задачи (2), квадратично
зависит от числа размещаемых объектов и равно
)()4(321 i
N1,i
2
i
N1,i
i
N1,i
nmaxO(N)nmaxCNOnmaxNOIIII
===
++=++= , (3)
где I ,I ,І 321 – число ограничений, описывающих подобласти 1D , 2D , 3D соответственно.
Целью данной статьи является построение преобразования ),( εDℑ : LDD
ℑ
→ , такого, что
его применение к функциям ограничений задачи, определяющих исходную нелинейную область
D , продуцирует аппроксимационное множество LD с кусочно-линейной границей.
3. Построение кусочно-линейной аппроксимации области D
Замечание 1. Преобразование ℑ осуществляется для дальнейшего построения итерационного
алгоритма решения исходной задачи как набора задач линейного программирования. При этом
( )1+h -я итерация алгоритма имеет вид [5]
pX XX h1h •Δ+=+ ,
где Xh – значение переменной на предыдущей итерации, XΔ – шаг, p – направление движения.
Замечание 2. Кусочно-линейная аппроксимация области D , реализуемая преобразованием
ℑ , проводится в диапазоне u Δ изменения параметров размещения объектов iR , определяемом
заданной точноcтью вычислений ε . На основании изучения особенностей области D сделан
вывод о возможности выбора диапазонов вида Niyx ii ,1],5;0[,],3,0;3,0[ =∈ΔΔ−∈Δϕ .
Далее будем использовать обозначение ϕ вместо ϕΔ .
4. Линеаризация условий размещения объектов в области – подобласть 1D
Подобласть 1D описывается системой NihnjufuF ii
hj
i ,1;4,1;,1,0)({:0)( 00 ===≤=≤
нелинейных неравенств, таких, что функции неравенств 0)(0 ≤i
hj
i uf имеют вид
; sinx+ cos yWy sinxcos y+y ; siny cos xxf i
j
i i
j
i i i
j
i i
j
i i i
j
i i
j
i i
hj
i ϕϕϕϕϕϕ −−−−++−∈ ;{0
} i
j
i i
j
i i siny cos xzx ϕϕ −−− .
Замечание 3. В данном случае реализовано касание типа «вершина )y, (x j
i
j
i объекта iR −
сторона 0S ». Назовем это касание касанием I-го типа [4].
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 102
Каждая из функций h
if0 представляет собой сумму трех слагаемых, первое из них является
линейным, а два других − тригонометрические функции параметра iϕ . Для линеаризации функций
h
if0 разложим тригонометрические слагаемые в ряд Маклорена, что позволяет приближенно
представить функцию ϕsin ее аргументом ϕ ϕϕ ≅sin: , а функцию ϕсos − выражением
25,01cos ϕϕ −≅ . При этом, если в качестве экзогенного параметра задана погрешность
вычислений 0sin >ε , то можно определить диапазон измененияϕ , в котором sinsin εϕϕ <− . Так,
если 015,0sin =ε , то ]2,0;2,0[−∈ϕ .
Тогда функции h
if0 , 4,1=h в соответствующих диапазонах изменения углового параметра
ϕ могут быть представлены следующим образом:
i
j
i
2
j
i i
1
0 y )
2
(1 xx ϕϕ
+−+−≈ i
if , i
j
i
2
j
i i
2
0 x)
2
(1y+y ϕϕ
−−−≈ i
if , (4)
i
j
i
2
ij
i i x+ )
2
(1 yWy ϕϕ
−−−≈3
i0f , i
j
i
2
j
i i
4
0 y )
2
(1 xx ϕϕ
−−−−≈ i
i zf . (5)
Кусочно-линейная аппроксимация )(g i
L ϕ функции )
2
(1 )g(
2
i
iϕϕ −= в диапазоне
изменения углового параметра ]36,0;0[∈iϕ с заданной погрешностью cosε [4] имеет вид
kiki
L
1-k ba)(g +ϕ=ϕ , )( cosεfk = , 4,2=k ,
где )/()(
11 −−
−−=
kkkk AAAAk xxyya ,
11 −−
−=
kk AkAk xayb . Точки ( )1;01 =A , ( )99,0;12,02 =A ,
( )97,0;24,03 =A , ( )93,0;36,04 =A – равномерно отстоящие по оси ϕ узлы аппроксимации
)(g i
L ϕ .
Тогда функция 1
0if представляется набором функций
, y )(g xx y )(g xx i
j
i i
L
1-k
j
i i i
j
i i
Lj
i i
1
0 ϕϕϕϕ ++−=++−≈if ];[ 1 kki AA −∈ϕ , )( cos_ linfk ε= . (6)
Аналогично записываются аппроксимации функций 4,2,0 =hf h
i .
Пример 1. Пусть положение объекта ),,( 1111 ϕyxR в полосе 0S (рис. 2а) задается системой
уравнений вида
⎪
⎩
⎪
⎨
⎧
=
=
=
,
,0
,0
_fixed 11
22
01
11
01
ϕϕ
f
f
⇔
⎪
⎩
⎪
⎨
⎧
=
=−+−
=++−
.
,0sin x cos yy
,0sin y cos xx
_fixed 1 1
1
2
1 i
2
11
1
1
1 1
1
11
ϕϕ
ϕϕ
ϕϕ
(7)
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 103
Реализация алгоритма линейной аппроксимации функций ограничений 11
01f , 22
01f при
максимальном шаге изменения углового параметра 2,0=iϕ проиллюстрирована на рис. 2б. Так,
на рисунке отмечен след полюса объекта при решении системы (7) и ее аппроксимированного
аналога. Расчетное и аппроксимированное значения координат полюса практически совпадают.
а) объект ),,( 1111 ϕyxR б) результат аппроксимации
Рис. 2. Реализация алгоритма линейной аппроксимации функций системы (7)
Замечание 4. Предложенная методика линеаризации условий размещения объектов iR в
области 0S практически без изменений применима в случае, если объекты iR − невыпуклые.
5. Линеаризация условий взаимного непересечения объектов и зон запрета – подобласть 2D
Подобласть 2D описывается системой 0)( ≤uF наборов 0),( ≤icic uuF , Ni ,1= , Сс ,1=
нелинейных неравенств, где набор 0),( ≤icic uuF задает условия попарного взаимного
непересечения объекта iR и зоны запрета cΩ :
0),( ≤icic uuF icic
hj
ic njnhuuf ,1,,1,0),(: ==≤= , (8)
где cn – количество вершин зоны запрета cΩ .
Другими словами, для обеспечения условия непересечения или касания объекта iR и зоны
запрета cΩ необходимо выполнение только одного неравенства из набора (8).
Вид функции ),( ic
hj
ic uuf неравенств системы (8) зависит от типа касания пары ),( ciR Ω .
Здесь реализуется как касание I-го типа «вершина ),( k
i
k
i yx − сторона ),[( l
c
l
c yx , )],( 11 ++ l
с
l
с yx »
(рис. 3а), так и касание II-го типа «сторона ),,[( k
i
k
i yx )],( k
i
k
i yx − вершина ),( l
c
l
c yx » (рис. 3б).
Касание I-го типа (в системе координат ccc YOX ) описывается следующим образом:
,0sin)(cos)()()(: 10
1 =−−−++−+− СAyBxByAxbyBaxAf i
k
i
k
ii
k
i
k
icici
hj
i ϕϕ
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 104
где =−= 21 YYA −l
cy 1l
cy + , 21 XXB −= −= +1l
сx l
сx , )(1 ByАxС l
c
l
с += .
а) касание I-го типа б) касание II-го типа
Рис. 3. Условия касания объектов и зон запрета
Применяя подход, изложенный в п.5, получаем следующее приближение функции 1
0
hj
if :
0)()()(: 10
1 ≤−−−−−+−+ CBbAaAyBxgByAxByAxf icj
k
j
k
ji
k
j
k
jjj
hj
i ϕϕ .
Использование функции )(g i
L ϕ завершает линеаризацию функции 1
0
hj
if .
Касание II-го типа (рис. 3б) описывается следующим образом:
0)(sin)(cos))(())((: 11
0
1 =++−++−−+− ++ ByАxBxAyByАxbyBaxAf k
i
k
i
l
c
l
ci
l
c
l
ciciicii
hj
i ϕϕϕϕ ,
где iii B ϕϕϕ sinAcos)A( += , ii A ϕϕϕ sinBcos)B( −= , +−= +1k
iyA k
iy , +−= k
ixB 1+k
ix ,
i
h
ii yyy Δ+= , i
h
ii xxx Δ+= .
На первом шаге линеаризации заменим
ϕϕϕϕϕ BAB i
iii +−≈+= )
2
1(sinAcos)A(
2
, ϕϕϕϕϕ ABA i
ii −−≈−= )
2
1(sinBcos)B(
2
.
Функция 1
0
hj
if ограничения примет вид
),,(1
0 iii
hj
i yxf ϕΔΔ )(),,( 321 iiii QyxQQ ϕϕ +ΔΔ+= 54 ),,( QyxQ iii +ΔΔ+ ϕ ( iii yx ϕ,,ΔΔ ).
где ByАxBbAa k
i
k
icc
11
1 Q ++ ++−−= – константная часть функции 1
0
hj
if ;
=ΔΔ ),,(2 iii yxQ ϕ )()(( c
h
ic
h
iiii axBbxAyBxA −+−−+Δ+Δ ϕ )BxAy l
c
l
c −+ –линеаризованная часть;
))()((,)
2
1()( 22
2
3
l
c
l
cc
h
ic
h
i
i
i ByАxaxAbyBCСQ −−−+−=−=
ϕϕ – квадратичная часть;
iiiiiii yAxByxQ Δ−Δ=ΔΔ ϕϕϕ ),,(4 – гиперболическая часть;
i
i
i
i
iii yBxAyxQ Δ−Δ−=ΔΔ
22
),,(
22
5
ϕϕϕ – составляющая третьего порядка.
Линеаризация )(3 iQ ϕ осуществляется на основе построения функции )(g i
L ϕ и имеет вид
)(3 i
LQ ϕ =≈ 2 i
L )(g Cϕ 2 i
L
1-k )(g Cϕ , )(],;[ cos1 εϕ fkAA kki =∈ − . (9)
xc
l yc
l
xj
k yj
k
Ri Ωc
xc
l+1 yc
l+1
(ac be)
(xj yj ϕi)
(X2 Y2)
(X1 Y1)
xc
l yc
l
xj
k yj
k
Ri
Ωc
X1= xc
l - xj
k+1, Y1= yc
l- yj
k+1
(ac bc)
(xj yj ϕi)
xj
k+1 yj
k+1
X2= xc
l - xi
k,
Y2= yc
l- yi
k
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 105
Функция 4Q содержит произведения ii xΔϕ , ii yΔϕ . В рассматриваемых диапазонах
[ ]3,0;0∈iϕ , [ ]5;0∈ix поверхность iiii xx Δ=ΔΓ ϕϕ ),( имеет вид, показанный на рис. 4а.
.
а) iiii xx Δ=ΔΓ ϕϕ ),( б) проекция кусочно-линейной аппроксимации
поверхности ),( ii xΔΓ ϕ
Рис. 4. Поверхность iiii xx Δ=ΔΓ ϕϕ ),(
Кусочно-линейная аппроксимация )x,( ii
L ΔϕΓ функции iiii x)x,( Δϕ=ΔϕΓ в диапазонах
изменения параметров [ ]3,0;0∈iϕ , [ ]5;0∈Δ ix может быть построена с помощью плоскостей вида
≈Δ ),(4 iixG ϕ 6,1,/)x A(),x( ik ii
L
k =++Δ=ΔΓ kCDB kkikϕϕ .
Проекция поверхности ),( ii
L xΔΓ ϕ на плоскость ii xОΔϕ представлена на рис. 4б.
Пример 2. Пусть положение объекта ),,( 1111 ϕyxR в полосе 0S (рис. 2а) задается системой
уравнений вида
⎪
⎩
⎪
⎨
⎧
=
=+−−
=++−++−−+− ++
.
,0sin x cos yy
,0)(sin)(cos))(())((
_fixed 1 1
1
2
1 i
2
11
11
ϕϕ
ϕϕ
ϕϕϕϕ
W
ByАxBxAyByАxbyBaxA k
i
k
i
l
c
l
ci
l
c
l
ciciicii
(10)
Реализация алгоритма линейной аппроксимации функций ограничений при максимальном
шаге изменения углового параметра 2,0=iϕ проиллюстрирована на рис. 5, где отмечен след
полюса объекта ),,( 1111 ϕyxR при решении системы (10) и ее аппроксимированного аналога, а
также промежуточные положения объекта ),,( 1111 ϕyxR . Точный результат (сплошная линия) и
аппроксимированный результат (прерывистая линия) практически совпадают.
1 4 7 10 13
Р1Р2Р3Р4Р5Р6
0
0,2
0,4
0,6
0,8
1
1,2
1,4
1,6
1,8
2
угловой параметр
координата х
1,8-2
1,6-1,8
1,4-1,6
1,2-1,4
1-1,2
0,8-1
0,6-0,8
0,4-0,6
0,2-0,4
0-0,2
0
0,03
0,06
0,09
0,12
0,15
0,18
0,21
0,24
0,27
0,3
0,33
0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 5,5
координата х
уг
ло
во
й
па
ра
м
ет
р
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 106
6. Линеаризация условий взаимного
непересечения объектов – подобласть 3D
Подобласть 3D сформирована условиями взаимного
попарного непересечения объектов размещения.
Рассмотрим пару объектов jiNjiRR ji ≠∈ ,,1,),,( .
В данном случае как параметры размещения
),,( iii yx ϕΔΔ объекта iR , так и параметры
размещения ),,( jjj yx ϕΔΔ объекта jR , являются
переменными величинами. При этом реализуется как
касание I-го типа «сторона ),[( k
i
k
i yx )],( k
i
k
i yx объекта iR − вершина ),( l
c
l
c yx объекта jR », так и
касание II-го типа «вершина ),( k
i
k
i yx объекта iR − сторона [ )y,x( l
c
l
c , )y,x( 1l
с
1l
с
++ ] объекта jR ».
Область 3D описывается системой 0)(3 ≤uF наборов 0),( ≤ji
h
ij uuF нелинейных
неравенств, задающих условие непересечения пары объектов jiNjiRR ji ≠∈ ,,1,),,( вида
=≤ :0),( jiij uuF jiic
hl
ij nlnhuuF ,1,,1,0),( ==≤ ,
причем вид функции 0),( ≤ji
hl
ij uuF 1hl
ijf зависит от типа касания пары ),( ji RR .
В случае реализации касания I-го типа функция 1hl
ijf имеет вид
).()sin()(
)cos()())(sincos())(sincos(
l
i
l
iji
k
j
k
j
ji
k
j
k
jijiiijii
AxByAyBx
ByAxyyABxxBA
+−−−−
−++−++−−
φφ
φφφφφφ
(11)
В случае реализации касания II -го типа функция 1hl
ijf имеет вид
).()sin()(
)cos()())(sincos())(sincos(:1
k
j
k
jij
l
i
l
g
ij
l
g
l
iijjjijjj
hl
ij
AxByAyBx
ByAxyyABxxBAf
++−−+
−+−−++−−
φφ
φφφφφφ
(12)
Структура функций (11–12) аналогична структуре функций набора (8), подробно
рассмотренной ранее. Следовательно, для линеаризации функций (11–12) в качестве базовой
применима процедура линеаризации функций ограничений II-го типа из набора условий взаимного
непересечения объектов размещения и зон запрета.
Отличие состоит в том, что
1. Тригонометрические функции разности угловых параметров объектов размещения,
входящие в состав функций (11) и (12), аппроксимируются следующим образом:
ji
jiji
ji ϕϕ
ϕϕϕϕ
ϕϕ +−−=
−
−≈−
22
1
2
)(
1)cos(
222
, jiji ϕϕϕϕ −≈− )sin( .
Рис. 5. Реализация алгоритма линейной
аппроксимации ограничений
области 2D
ISSN 1028-9763. Математичні машини і системи, 2010, № 2 107
2. В силу переменности параметров размещения ),,,,,( jjjiii yxyx ϕϕ ΔΔΔΔ объектов
),( ji RR функции 1hl
ijf ),,,,,( jjjiii yxyx ϕϕ ΔΔΔΔ представляются в виде
=1
0
hj
if −ΔΔ+ΔΔ++ΔΔ+ ∑
∈
), ,x(Q), ,x(Q)(Q), ,x([Q s5s43
},{,
s21 msmsmms
jims
yyyQ ϕϕϕϕ
ij
l
g
l
i ByAx φφ)( +− ,
где 54321 ,,,, QQQQQ – константная, линеаризованная, квадратичная, гиперболическая часть,
составляющая третьего порядка функции 1hl
ijf соответственно.
7. Выводы
Таким образом, построена линейная аппроксимация области допустимых решений задачи
размещения неориентированных геометрических объектов, позволяющая с заданной точностью
свести рассматриваемую нелинейную оптимизационную задачу к набору оптимизационных задач
линейного программирования. При этом размерность пространства параметров размещения, в
котором рассматривается область допустимых решений задачи, остается неизменной, а точность
аппроксимации является экзогенным параметром.
Проведенная линеаризация дает возможность получить удовлетворительное решение
многих задач практической размерности с использованием хорошо разработанного
математического аппарата.
Данный подход является основой для построения алгоритмического и программного
обеспечения процесса решения указанных оптимизационных задач, основанного на современном
математическом инструментарии.
СПИСОК ЛИТЕРАТУРЫ
1. Стоян Ю.Г. Математические модели и оптимизационные методы геометрического проектирования /
Ю.Г. Стоян, С.В. Яковлев. – К.: Наукова думка, 1986. – 268 с.
2. Гиренко К.А. Математична модель та метод розв’язання задачі розміщення неорієнтованих складених
геометричних об’єктів: автореф. дис. на здобуття наук. ступеня канд. техн. наук. – Харків, 2009. – 18 с.
3. Чуб И.А. Линеаризация оптимизационной задачи размещения неориентированных объектов в
промышленных системах раскроя изотропных материалов / И.А. Чуб // Тез. докл. IV междунар. научн.-практ.
конф. “Математическое и имитационное моделирование систем” (Киев, 22–26 июня 2009 г.). – Киев: ИПММС,
2009. – С. 165 – 168.
4. Новожилова М.В. Методологiя розв’язання оптимiзацiйних нелiнiйних задач геометричного проектування /
М.В. Новожилова // Вiсник Запорiзького державного унiверситету. – Запоріжжя: ЗДУ, 1999. – № 1. – С. 75 – 81.
5. Гилл Ф. Практическая оптимизация / Гилл Ф., Мюррей У., Райт М. – М.: Мир, 1985. – 509 с.
Стаття надійшла до редакції 11.09.2009
|