Метод решения линеаризованной задачи размещения неориентированных геометрических объектов
Исследована оптимизационная задача размещения многоугольных неориентированных объектов в полосе, рассматриваемой в линеаризованной постановке. Описаны дополнительные свойства области допустимых решений и схема метода поиска локального минимума функции цели. Рассмотрена методика определения допустимо...
Saved in:
| Date: | 2011 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Series: | Управляющие системы и машины |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/82963 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Метод решения линеаризованной задачи размещения неориентированных геометрических объектов / И.А. Чуб, М.В. Новожилова // Управляющие системы и машины. — 2011. — № 5. — С. 47-52. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-82963 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-829632025-02-23T17:18:08Z Метод решения линеаризованной задачи размещения неориентированных геометрических объектов Solution Method for Linearized Problem of Non-Oriented Polygonal Placement Метод розв’язання лінеарізованої задачі розміщення неорієнтованих геометричних об’єктів Чуб, И.А. Новожилова, М.В. Новые методы в информатике Исследована оптимизационная задача размещения многоугольных неориентированных объектов в полосе, рассматриваемой в линеаризованной постановке. Описаны дополнительные свойства области допустимых решений и схема метода поиска локального минимума функции цели. Рассмотрена методика определения допустимого шага вдоль направления движения по границе компоненты связности линеаризованной области допустимых решений. The non-oriented polygonal placement optimization problem is considered in the linearized formulation. The additional properties of the problem linearized feasible region have been studied. The method of searching for a problem local minimum based on the active set idea is proposed. The scheme for determining step value among the descent direction wia to the frontier of the connected component of the linearized problem feasible region has been developed. Досліджено оптимізаційну задачу розміщення багатокутних неорієнтованих об'єктів у смузі, розглядуваної в лінеаризованій постановці. Описано додаткові властивості області припустимих рішень та схему методу пошуку локального мінімуму функції мети. Розглянуто схему визначення припустимого кроку за напрямом руху по межі компоненти зв’язності лінеаризованої області припустимих рішень. 2011 Article Метод решения линеаризованной задачи размещения неориентированных геометрических объектов / И.А. Чуб, М.В. Новожилова // Управляющие системы и машины. — 2011. — № 5. — С. 47-52. — Бібліогр.: 7 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82963 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 |
2011 |
| topic_facet |
Новые методы в информатике |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/82963 |
| citation_txt |
Метод решения линеаризованной задачи размещения неориентированных геометрических объектов / И.А. Чуб, М.В. Новожилова // Управляющие системы и машины. — 2011. — № 5. — С. 47-52. — Бібліогр.: 7 назв. — рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT čubia metodrešeniâlinearizovannojzadačirazmeŝeniâneorientirovannyhgeometričeskihobʺektov AT novožilovamv metodrešeniâlinearizovannojzadačirazmeŝeniâneorientirovannyhgeometričeskihobʺektov AT čubia solutionmethodforlinearizedproblemofnonorientedpolygonalplacement AT novožilovamv solutionmethodforlinearizedproblemofnonorientedpolygonalplacement AT čubia metodrozvâzannâlínearízovanoízadačírozmíŝennâneoríêntovanihgeometričnihobêktív AT novožilovamv metodrozvâzannâlínearízovanoízadačírozmíŝennâneoríêntovanihgeometričnihobêktív |
| first_indexed |
2025-11-24T03:47:50Z |
| last_indexed |
2025-11-24T03:47:50Z |
| _version_ |
1849642000634085376 |
| fulltext |
УСиМ, 2011, № 5 47
УДК 519.85
И.А. Чуб, М.В. Новожилова
Метод решения линеаризованной задачи размещения
неориентированных геометрических объектов
Исследована оптимизационная задача размещения многоугольных неориентированных объектов в полосе, рассматриваемой в
линеаризованной постановке. Описаны дополнительные свойства области допустимых решений и схема метода поиска ло-
кального минимума функции цели. Рассмотрена методика определения допустимого шага вдоль направления движения по
границе компоненты связности линеаризованной области допустимых решений.
The non-oriented polygonal placement optimization problem is considered in the linearized formulation. The additional properties of
the problem linearized feasible region have been studied. The method of searching for a problem local minimum based on the active set
idea is proposed. The scheme for determining step value among the descent direction wia to the frontier of the connected component of
the linearized problem feasible region has been developed.
Досліджено оптимізаційну задачу розміщення багатокутних неорієнтованих об'єктів у смузі, розглядуваної в лінеаризованій
постановці. Описано додаткові властивості області припустимих рішень та схему методу пошуку локального мінімуму функ-
ції мети. Розглянуто схему визначення припустимого кроку за напрямом руху по межі компоненти зв’язності лінеаризованої
області припустимих рішень.
Введение. Задача нерегулярного размещения
набора неориентированных многоугольных гео-
метрических объектов в некоторой многоуголь-
ной области принадлежит к классу задач опти-
мизационного геометрического проектирования
[1] и представляет как теоретический, так и
практический интерес. К таким задачам отно-
сятся, например, задачи раскроя изотропного
материала (металлопрокат, ткань, стекло и др.)
на многоугольные заготовки. При этом, если
над геометрическим объектом допустимо аф-
финное преобразование поворота, то такой
объект называют неориентированным.
Обзор предыдущих исследований
Рассматриваемый класс задач наименее изу-
чен среди задач размещения [2, 3]. В работе [4]
проведено исследование рассматриваемой за-
дачи размещения в полосе, выделены допол-
нительные свойства области допустимых ре-
шений, на основе которых предложена линеа-
ризация функций основных ограничений зада-
чи, позволяющая с заданной точностью свести
исходную нелинейную задачу размещения к на-
бору задач линейного программирования. В ра-
боте [5] рассмотрена схема определения на-
правления движения по границе компоненты
связности линеаризованной области допусти-
мых решений, основанная на использовании
идеи активного набора [6]. В схеме активного
набора (h + 1)-я итерация имеет вид [9] 1hu
h h hu p , где hu – значения независимых
переменных на предыдущей итерации; h –
шаг, ph – направление спуска.
Цель настоящей статьи – обоснование мето-
да определения длины шага при поиске локаль-
ного минимума функции цели задачи разме-
щения неориентированных многоугольников в
линеаризованной постановке.
Постановка задачи
Имеется набор 1,i i N
R R
выпуклых неори-
ентированных многоугольников и область раз-
мещения 2
0 , 0, , 0, ,R x y E x z y W
const,W z = var} (рис. 1). Объект Ri задается
набором {( , )}, 1,n n
i i ix y n n координат его вер-
шин в собственной системе координат XiOiYi,
1,i N . Положение Ri определяется параметра-
ми размещения ui = (vi, i) = (xi, yi, i), задающим
начало Oi системы координат XiOiYi, Oi int Rt.
О
Оj
Y
Ri
Rj
Rm
R0
Xj
Yj
j (xi,yi,0)
(xm,ym,0)
xj
yj
W
z
X
Рис. 1. Область R0 и объекты размещения Ri, Rj, Rm
48 УСиМ, 2011, № 5
Необходимо разместить набор , 1,iR i N
объектов без взаимных наложений в области
R0 так, чтобы длина занятой части полосы z
была минимальной:
найти:
3 1
* arg min
Nu D Е
u cu
, (1)
где 1 2( , ,..., , )Nu u u u z ; с = (0, 0, ..., 0, 1); D =
1 2D D область допустимых решений; под-
область 1
3 1ND Е определяется ограничения-
ми на размещение объектов Ri в полосе R0:
0 , 1,iR R i N ; (2)
2
3 1ND Е задается условиями взаимного по-
парного непересечения объектов (Ri, Rj):
int int , , 1, , .i jR R i j N i j (3)
Аналитическое описание условия (2) опреде-
ляется системой 1( ) 0: { ( ) 0,hn
i iF u f u 1, ;in n
1, 4; 1,h i N нелинейных неравенств, при-
чем функции ( )hn
i if u имеют вид
( ) { ; ; ;hn n n n
i i i i i i i if u x y y W
}n
i iz x , (4)
cos sin ;
cos sin .
nn n
i i i ii
nn n
i i i ii
x y
y x
(5)
Условие (3) задается системой 2 ( ) 0F u на-
боров ( , ) 0h
ij i jF u u нелинейных неравенств:
( , ) 0ij i jF u u := ( , ) 0, 1, , 1,hl
ij i j i jf u u h n l n ,
, 1, , .i j N i j
При этом функции hl
ijf в зависимости от
типа касания [3] пары ( , )i jR R имеют вид
( cos sin )( )
( cos sin )( )
( ) cos( )
( )sin( ) ( )
i i j i
i i j i
k k
j j i j
k k l l
j j i j i i
A B x x
B A y y
Ax By
Bx Ay By Ax
(6)
или
( cos sin )( )
( cos sin )( )
j j j i
j j j i
A B x x
B A y y
( ) cos( )
( )sin( ) ( ),
l l
i i j i
l l k k
i i j i j j
Ax By
Bx Ay By Ax
(7)
где , , ,l l k k
i i j jx y x y – координаты вершин объектов
,i jR R ; A, B – функции координат их вершин.
Линеаризованная постановка задачи
Для построения многогранного множества
D
L, аппроксимирующего область D (2), (3) в
диапазоне изменения углового параметра i
[ 0,36;0,36] с заданной погрешностью в [4]
обосновано представление: sin , cosi i i
( ) ( ), 1, ( )L
k i k i kg a b k K . При этом ве-
личины , n n
i i из (5) принимают вид
| ( ) |; Ln n n Ln
i i k i k i i ix a b y
| ( ) |n n
i k i k i iy a b x , k = 1, ( )K .
Тогда многогранное множество 1
LD , аппрок-
симирующее область D1, задается системой
1 ( ) 0 : { ( ) 0,L hn
i iF u u
1, ; 1, 4; 1,in n h i N (8)
наборов ( ) 0hn
i iu линейных неравенств, функ-
ции которых имеют вид [4]
{ ( )n n n
i i k i i i kx x a y x b ,
( ) n n n
i i k i i i ky y a x y b ,
( ) ( ),n n n
i i k i i i ky y a x W y b
( ) ,n n n
i i k i i i kz x x a y x b k = 1, ( )K }.
Многогранное множество 2
LD задается сис-
темой 2 ( ) 0LF u наборов ( , ) 0L
ij i jF u u линей-
ных неравенств:
( , ) 0L
ij i jF u u := ( , ) 0, 1, , 1,hl
ij i j i ju u h n l n ,
, 1, ,i j N i j . (9)
При этом набор ( , ) 0 ( , ) 0hl hl
ij i j ij i ju u u u
есть линейная аппроксимация функций 1hl
ijf (6),
(7). Процесс построения линейной аппрокси-
мации функций 1hl
ijf предусматривает переход
с учетом применения функции ( )L
k ig к виду
1 1 2 2 1
i i i i j
k i j k i i k i j k i i i jC x C x C y C y C
УСиМ, 2011, № 5 49
1 2
1 2 1
( ) ( )
( ) ( 1) ,
i j i j
k j i j i i k
j j j j i j k
j h k h i
b Ax Ax By By C a C
C a C C b b C
(10)
где
1 2 1
2
; ;
; ( ); ( ).
i i i i j l
k k k k j
l j l l k k k
j j j i i i
C B Aa C Ba A C Ax
By C Bx Ay C By Ax
Кусочно-линейная аппроксимация L
функ-
ций ,i { , , , , }j i j i jx x y y , 1,5 в
заданных диапазонах изменения параметров
осуществляется с помощью набора T линей-
ных функций , 1,t v t i tA B D t T . Тогда
функция 1hl
ijf имеет следующий вид:
1 1 1 2
2 3 2 4
1 5 1 2 1 1 1 2
2 3 2 4 1 5 1 2
( ) ( )
( ) ( )
( ) (
) ,
i i i i
k t k j k t k i
i i i i
k t k j k t k i
j j j j i i
t h j k t k t
i i j j i j
k t k t t k i
C A b A x C A b A x
C A b B y C A b B y
C B C a C C B C B
C B C B C A C a C D
(11)
где
1 1 1 2 2 3 2 4
1 5 1 ( 1) .
i i i i
k t k t k t k t
j j i j k
t k h i
D C D C D C D C D
C D C b b C
Утверждение 1. Кусочно-линейная аппрок-
симация t v t i tA B D поверхности v i
при v {xi, xj, yi, yj} не зависит от знака при-
ращения параметров {xi, xj, yi, yj}.
Доказательство. Утверждение 1 означает,
что одноименные по t уравнения набора ап-
проксимирующих плоскостей поверхностей
v i и (–v)i имеют идентичный набор коэф-
фициентов , , , 1,t t tA B D t T . Этот факт сле-
дует из симметричности поверхности v i от-
носительно координатной оси Оv.
Замечание 1. Возможны различные варианты
аппроксимации поверхностей v = iv 1,5 .
В данной статье используется триангуляция,
фрагмент которой представлен в табл. 1.
Т а б л и ц а 1
Плоскость v v A B D
0,01 0,12 0,0012
1,01 0,01 0,01011
0 0,00 0
0,00991 0,00915 0
0 0,12 0
1,01 0,12 0,12122
1,01 0,00 0
0,12 1,01 –0,1212
... ... ... ... ... ... ...
Таким образом, линеаризованная постанов-
ка исходной задачи размещения такова:
3 1
* arg min
L Nu D Е
u cu
, (12)
где область LD определяется ограничениями
(8), (9).
Конструктивные свойства задачи (10)
Для упорядочения схемы определения на-
правления движения отметим следующий факт.
Утверждение 2. При выборе направления
движения функция 1hl
ijf выглядит так:
1 5 1 2
1 5 1 2 1 5 1
( ) ( ) ( )
( ) .
L L j j j j
j i j i t h j
j j i j j j k
t k i t i
A x x B y y C B C a C
C A C a C C D C C
(13)
Доказательство. Положим i [0,]. Без по-
тери общности можно считать, что вектор зна-
чений независимых переменных uh на (h + 1)-й
итерации имеет вид uh
= (x1, y1, 0, x2, y2, 0, xN,
yN, 0). Тогда аппроксимирующие плоскости
(13) поверхностей v i на основе Утвержде-
ния 1 имеют одинаковые одноименные коэф-
фициенты, т.е.
1 2 3 4t t t tA A A A , 1 2 3 4t t t tB B B B ,
1 2 3 4t t t tD D D D .
Следовательно,
1 1 1 2
i i i i
k t k k t kC A b A C A b A ,
2 3 2 4
i i i i
k t k k t kC A b B C A b B .
1 1 1 2
2 3 2 4
1 5 1 2
1 5 1 2
1 5 1
( ) ( )
( ) ( )
( )
( ) ,
где ( 1) .
i i i i
k t k j k t k i
i i i i
k t k j k t k i
j j j j
t h j
j j i j
t k i
j j i j k
t k h i
C A b A x C A b A x
C A b B y C A b B y
C B C a C
C A C a C D
D C D C b b C
Более того, полагая 1, 1i j
k hb b , получаем,
что коэффициент при переменной i 1 1
i
k tC B
1 2 2 3 2 4 1 5 1 2
i i i j j i j
k t k t k t t kC B C B C B C A C a C ста-
новится равным 1 5 1 2
j j i j
t kC A C a C .
Отметим, что по постановке задачи 0,ix
0, 1,iy i N , тогда как угол поворота i
[, ]. Таким образом, на i не наложены
ограничения по знаку (отрицательный угол оз-
начает поворот против часовой стрелки). По-
50 УСиМ, 2011, № 5
этому постановку задачи необходимо несколь-
ко изменить в рамках стратегии активного на-
бора. Модификация заключается в замене пе-
ременных i разностью двух переменных: i =
= (i – wi), где i 0 и wi 0.
При этом оптимальное решение будет иметь
значения i = 0 (тогда i = wi) или w1 = 0 (то-
гда i = i ).
В общем случае направление спуска рh –
столбец матрицы
1
A
активных (обращающих-
ся в ноль на h-й итерации) ограничений задачи,
номер столбца соответствует отрицательной
компоненте вектора множителей Лагранжа.
Утверждение 3. Для задачи (12) вектор
множителей Лагранжа – g-я строка матрицы
1
A
, где g – номер столбца матрицы коэффи-
циентов А при переменной z.
Доказательство. Вектор множителей
Лагранжа есть решение системы уравнений
TA c . При этом вектор с содержит только
одну ненулевую компоненту – в строке, номер
которой совпадает с номером столбца матрицы
А при переменной z. Следовательно, вектор
представляет собой g-й столбец матрицы (AT)–1,
очевидно, это также g-я строка матрицы А–1.
Пример 1. Пусть задана полоса W = 7 и
объект R: {(–4,1), (1,–3), (3,2)}. Координаты
полюса (x, y, ) = (4,3,0) (рис. 2) определяются
системой:
1 1
13
2 2
23
3 3
33
( , ) 4
( , ) 3
( , ) 3
0
x a x y
y a x y
x a x y z
. (14)
0.0 2.0 4.0 6.0
6.0
4.0
2.0
R
Рис. 2. Начальное положение объекта R
Введем в рассмотрение угол = ( – w).
Тогда матрица А активного набора имеет вид:
А =
1 0 0,24 0,76 0
0 1 -0,82 1,18 0
-1 0 -1,82 2,18 1
0 0 1 0 0
0 0 0 1 0
x y u w z
,
A–1:
1 0 0 -1,24 0,76
0 1 0 0,82 -1,18
0 0 0 1 0
0 0 0 0 -1
1 0 1 0,58 -1,42
.
Вектор – пятая строка матрицы А–1 – со-
держит только одну отрицательную компонен-
ту 5. Следовательно, уравнение 5 системы (14)
выводится из рабочего списка, параметр по-
лучает отрицательное приращение. Вектор спус-
ка р – пятый столбец матрицы A–1: рT = (0,76;
–1,18; 0; –1).
Пример 2. Рассмотрим размещение объектов
{R1, R2, R3}. Ширина полосы W = 10 (рис. 3).
Начальное размещение u0 = (5; 3; 0; 6,5; 8;0; 7,34;
6,62; 0) задается системой уравнений Au = B
(рабочий список в терминах [7]). Матрица А с
учетом ввода в рассмотрение параметров i
объектов размещения (но без учета отрицатель-
ной составляющей w1, w2, w3) имеет вид:
A=
1 1 1 2 2 2 3 3 3
-2,1 7 -13,7 2,1 7 16,4 0 0 0 0
0 0 0 -4,9 6,1 -12,5 4,9 -6,1 13,5 0
-2,1 7 -12,5 0 0 0 2,1 7 14,5 0
1 0 3,3 0 0 0 0 0 0 0
0 1 3,18 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 -1 0 -1,8 0 0 0 1
0 0 0 0 -1 3,1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 -1 0 1,63 1
x y x y x y z
.
Вектор множителей Лагранжа – девятая стро-
ка А–1 содержит два отрицательных элемента:
0,483 0 –0 1 3,373 –7,436 1 3,373 –20,259 0,3E–16
Другими словами, можно исключить из ра-
бочего списка шестое ограничение: = 0,
причем = u1, т.е. угол может увеличи-
УСиМ, 2011, № 5 51
ваться (соответственно объект R1 – поворачи-
ваться по часовой стрелке), вектор р направле-
ния движения имеет вид:
(–3,3; –3,18; 1; –7,436; –3E–16; –1,5E–16;
–7,5251; –0,0726; 0; –7,4363).
0.0 2.0 4.0 6.0
R2
R3
R1
10.0
8.0
6.0
4.0
2.0
Рис. 3. Начальное положение объектов размещения (Пример 2)
Если принять исключаемым девятое огра-
ничение 3 = 0, и снова 3 = u3, т.е. угол 3 мо-
жет увеличиваться, и вектор р направления
движения становится равным
(1,7E–15; 1,05E–15; –2,01E–16; –18,43;
3,12; 1; –16,4095; 2,707; 0; –20,259).
Определение длины шага
В соответствии с идеологией активного на-
бора (линейного программирования) процеду-
ра определения длины шага осуществляется на
выпуклой области допустимых решений. В об-
щем случае область D
L E
3N+1 несвязная не-
выпуклая многогранная область. Поэтому в
дальнейшем понадобятся следующие свойства
области D
L.
Свойство 1.
1
Q
L L
qq
D D
, где L
qD компо-
нента связности области D
L.
Свойство 2. Неравенства систем (8) и (9),
становясь активными ограничениями, опреде-
ляют условия касания объекта границы R0 или
касания пары размещаемых объектов.
Свойство 3. Каждая компонента связности
L
qD области D
L может быть представлена в виде
объединения конечного числа Gq выпуклых
многогранных подобластей
g
L
qD :
1
q
g
G
L L
q q
g
D D
.
При этом границу области
g
L
qD задает на-
бор уравнений, содержащий, по крайней ме-
ре, по одному из ограничений каждого набо-
ра вида (8), (9).
Свойство 4. Для точки uh, включая u, спра-
ведливо соотношение
1 r
h L
q
r
u D
, где
r
L
qD –
выпуклая подобласть области D
L.
Общая схема метода поиска локального ми-
нимума на компоненте связности имеет вид:
1. Определение начального размещения u0.
2. Определение некоторой выпуклой подоб-
ласти
r
L
qD , u0
r
L
qD .
3. Решение задачи * arg min
r L
qr
q
u D
u cu
. Опреде-
ление некоторой выпуклой подобласти
1r
L
qD
такой, что
1
*
r r
L
q qu D
,
1
* arg min
r L
qr
q
Du
u cu
. Если та-
ковая найдется, положить r = r + 1 и перейти к
Шагу 3. Если нет – точка есть локальный ми-
нимум задачи.
Замечание 3. В качестве начального разме-
щения может быть использовано решение за-
дачи размещения ориентированных много-
угольных объектов в полосе [7].
Рассмотрим Задачу Этапа 3. Текущее при-
ближение uh, как и оптимальная точка *
rqu за-
дачи, описывается системой * 0F u I = 3N + 1
активных в точке u ограничений из систем
{ 1 ( ) 0,LF u 2 ( ) 0LF u } наборов линейных не-
равенств.
3.1. Определение направления движения (ал-
горитм решения рассмотрен ранее).
3.2. Определение величины шага [6] по
формуле
min , если 0 для некоторого ,
, если 0 для всех ,
T h
i ii
T h
i
a p i I
a p i I
где γ и 0
T h
T hi i
iT h
i
b a u
i I a p
a p
. (15)
Замечание 4. Список неактивных ограниче-
ний, которые необходимо проверять на воз-
можность включения в рабочий список на сле-
дующей итерации, можно существенно огра-
ничить, принимая во внимание свойство вы-
пуклости объектов размещения.
Продолжим Пример 2. В табл. 2 даны ре-
зультаты вычисления длины шага до неактив-
52 УСиМ, 2011, № 5
ных ограничений линеаризованной задачи (12)
с использованием подхода (15) (представлены
только те ограничения, для которых 0T h
ia p ).
Анализ данных (см. табл. 2) показывает, что
минимальный неотрицательный допустимый
шаг равен 0,12 (ограничение по ). Следо-
вательно, активным на следующем шаге алго-
ритма становится ограничение = 0,12.
Т а б л и ц а 2
Функция огра-
ничения T
ia
С
то
ро
на
по
ло
сы
В
ер
ш
ин
а
i
об
ъе
кт
а
R
xi yi
x1 y1 1 z
T h
ia p bi
T h
ia u
T h
i i
T h
i
b a u
a p
левая 2 1 –3 1 0 –3,06 0 –4,3 –1 4 1,16289
нижняя 3 3 2 0 1 –3,12 0 –2,3 –2 3 2,17391
верхняя 1 –4 1 0 –1 –3,94 0 –4,76 –6 –3 0,63025
Ограничение по 0 –1 0 –1 –0,12 0 –0,12 0,12
0,12
0.0 2.0 4.0 6.0
R2
R3
R1
10.0
8.0
6.0
4.0
2.0
Рис. 4. Приближение к локальному минимуму задачи Примера 2
Отметим, что на направление движения та-
кая замена не повлияет, так как матрица огра-
ничений А, и соответственно обратная матрица
А–1 не изменится. Другими словами, пересчи-
тывать при такой замене матрицу А–1 нет необ-
ходимости.
Введем следующие правила априорного вы-
бора подмножества неактивных ограничений,
возможных для включения в рабочий список
на следующей итерации решения.
Правило 1. Среди неактивных ограничений,
описывающих условия (3), для проверки вы-
бираются «смежные» по диапазону изменения
углов поворота.
Легко показать, что такая редукция множе-
ства неактивных ограничений возможна бла-
годаря выпуклости объектов размещения.
Правило 2. Если компонента вектора направ-
ления рh, соответствующая параметру i, равна
нулю (или «почти» ноль), то объект Ri считает-
ся ориентированным на этой итерации алгоритма.
Заключение. На базе исследования оптими-
зационной задачи размещения многоугольных
неориентированных объектов в полосе, рас-
сматриваемой в линеаризованной постановке,
и выделенных дополнительных свойствах ли-
неаризованной области допустимых решений за-
дачи разработан метод поиска локального ми-
нимума функции цели, основанный на исполь-
зовании идеи активного набора. Предложенный
подход легко адаптируется для решения задач
размещения неориентированных невыпуклых
геометрических объектов в полосе и представ-
ляет собой теоретический базис при разработ-
ке программного обеспечения решения прак-
тических задач оптимизации размещения не-
ориентированных многоугольных объектов.
1. Стоян Ю.Г., Яковлев С.В. Математические модели
и оптимизационные методы геометрического про-
ектирования. – К.: Наук. думка, 1986. – 268 с.
2. Гиренко К.А. Математична модель та метод розв’я-
зання задачі розміщення неорієнтованих складених
геометричних об’єктів: Автореф. дис. канд. техн.
наук. – Харків, 2009. – 18 с.
3. Новожилова М.В. Методологiя розв’язання опти-
мізацiйних нелiнiйних задач геометричного проек-
тування // Вiсн. ЗДУ. – 1999. – № 1. – С. 65–69.
4. Чуб И.А., Новожилова М.В. Построение линейной
аппроксимации области допустимых решений за-
дачи размещения неориентированных геометриче-
ских объектов // Математичні машини і системи. –
2010. – № 2. – С. 99–107.
5. Чуб И.А., Новожилова М.В. Определение направ-
ления спуска в линеаризованной задаче размеще-
ния неориентированных геометрических объектов
// Радіоелектроніка. Інформатика. Управління. –
2010. – № 2 (23). – С. 94–100.
6. Гилл Ф., Мюррей У., Райт М. Практическая опти-
мизация. – М.: Мир, 1985. – 509 с.
7. Stoyan Yu.G., Novozhilova M.V., Kartashov A.V. Mathe-
matical model and method of searching for a local ex-
tremum for the non convex oriented polygons alloca-
tion problem // Europ. J. of Operational Res. – 1996. –
№ 92. – Р. 193–210.
Поступила 16.03.2011
Тел. для справок: (057) 707-3490; 706-2049 (Харьков)
E-mail: chubia@nuczu.edu.ua
© И.А. Чуб, М.В. Новожилова, 2011
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|