Метод решения задачи размещения в анизотропной области
Исследованы некоторые свойства задачи размещения в анизотропной области в полярной системе координат. Построен и обоснован приближенный метод решения, основанный на идее размещения объектов с изменяемыми метрическими характеристиками в изотропной области. Досліджені деякі властивості задачі розміщен...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84672 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод решения задачи размещения в анизотропной области / И.А. Чуб, М.В. Новожилова // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 160-165. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860269827460956160 |
|---|---|
| author | Чуб, И.А. Новожилова, М.В. |
| author_facet | Чуб, И.А. Новожилова, М.В. |
| citation_txt | Метод решения задачи размещения в анизотропной области / И.А. Чуб, М.В. Новожилова // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 160-165. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Исследованы некоторые свойства задачи размещения в анизотропной области в полярной системе координат. Построен и обоснован приближенный метод решения, основанный на идее размещения объектов с изменяемыми метрическими характеристиками в изотропной области.
Досліджені деякі властивості задачі розміщення в анізотропній області в полярній системі координат. Запропоновано наближений метод розв’язання, що базується на можливості розміщення об’єктів з метричними характеристиками, що змінюються.
Properties of placement problems on anisotropic feasible region in polar coordinate system is investigated. An approximate method of solution, which is based on possibility to locate objects with varying metric characteristics, is constructed and justified.
|
| first_indexed | 2025-12-07T19:05:28Z |
| format | Article |
| fulltext |
160 Компьютерная математика. 2011, № 2
Исследованы некоторые свойства
задачи размещения в анизотроп-
ной области в полярной системе
координат. Построен и обоснован
приближенный метод решения,
основанный на идее размещения
объектов с изменяемыми метри-
ческими характеристиками в изо-
тропной области.
И.А. Чуб, М.В. Новожилова,
2011
Компьютерная математика. 2011, № 2 161
УДК 519.8
И.А. ЧУБ, М.В. НОВОЖИЛОВА
МЕТОД РЕШЕНИЯ
ЗАДАЧИ
РАЗМЕЩЕНИЯ
В АНИЗОТРОПНОЙ
ОБЛАСТИ
Введение. Множество прак-
тических задач оптимального
распределения ресурсов,
энергосбережения, планиро-
вания могут быть сформули-
рованы как задачи размеще-
ния
[1 – 3]. Поэтому данный
класс задач вызывает интерес
многих специалистов, в том
числе работающих в области
численных методов оптими-
зации [4]. Применение чис-
ленных методов позволяет
расширять спектр возможных
пространственных форм и
особенностей метрических характеристик
объек-тов и области размещения.
Среди задач размещения наименее изу-
ченным, несмотря на очевидное теоретиче-
ское и практическое значение, является класс
задач размещения геометрических объектов
в анизотропных областях [5], например, за-
дача раскроя кожи.
Цель работы – построение приближенного
метода решения задачи размещения выпуклых
многоугольников в анизотропной области в
полярной системе координат.
1. Постановка задачи. Есть прямоуголь-
ная область размещения 2
0R E⊂ , заданная в
полярной системе координат Оρ ϕ набором
координат вершин ( ){ }0 0, , 1,4k k kρ ϕ = :
( ) ( ){ ( )}2 20,0 , ,0 , , arctg , , / 2
W
Z Z W W
Z
+ π
,
const, varW Z= = . Область 0R обладает
свойством анизотропии вследствие наличия в
каждой точке ( ) 0, Rρ ϕ ∈ своего направления
наименьшей тягучести rs , задаваемого по
эллипсу напряжений. Пусть также имеется
МЕТОД РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ В АНИЗОТРОПНОЙ ОБЛАСТИ
Компьютерная математика. 2011, № 2 161
набор выпуклых многоугольных объектов размещения { }, 1,iR R i N= = . Разме-
щение iR в 0R задается параметрами ( ),i iρ ϕ , определяющими положение цен-
тра собственной полярной системы координат (ССК) i i iOρ ϕ (полюса объекта
iО ), inti iO R∈ .
Замечание 1. По постановке задачи 0 / 2i≤ ϕ ≤ π . Тогда каждой паре значе-
ний ( ),i iρ ϕ отвечает одна и только одна точка области 0R .
Замечание 2. Так как inti iO R∈ , следовательно 0, 0i iρ ≠ ϕ ≠ .
В ССК i i iOρ ϕ объект iR задается набором ( ){ },n n
i iρ ϕ координат его вершин
, 1,n
i iv n n= . Есть также набор ( ){ }, , 1,n n
i i ip n nα = расстояний n
ip и углов n
iα
между i iO ϕ и нормалью к i-й стороне объекта iR соответственно.
Анизотропия 0R означает, что в каждой точке ( ) 0, Rρ ϕ ∈ направление is
наименьшей тягучести объекта iR совпадает с направлением rs . Поэтому в за-
висимости от параметра iϕ объекта iR , изменяется ориентация его ССК i i iOρ ϕ .
Пусть направление is объекта iR совпадает с полярной осью i iO ϕ .
Задача: разместить набор объектов , 1,iR i N= без взаимных пересечений
в области 0R так, чтобы характеристика Z была минимальной.
Далее будем считать эквивалентными запись iR и ( ),i i iR ρ ϕ .
Математическая модель данной задачи имеет вид, найти:
* arg min
D
u Z= , (1)
где ( )1 1* , ,..., , ,N Nu Z= ρ ϕ ρ ϕ , 2 1ND E +⊂ – область допустимых решений, задан-
ная ограничениями
0 ,iR R⊂ (2)
int int , , 1,2,..., , .i jR R i j N i j∩ = ∅ = ≠ (3)
Свойство 1. Линейность функции цели Z означает, что точка * .u FrD∈
2. Аналитическое описание условий (1–2). В силу свойства 1 рассмотрим
аналитическое описание FrD . Прежде всего это аналитическое задание касания
пары объектов ( ),i jR R в виде набора ограничений ( ), 0k
n i jF u u = . Функции
( ) ( ){ } ( ), , , ,ki kj k
nj i j ni i j n i jf u u f u u F u u∈ ограничений, задающих касание I-го и II-го
типов [7], имеют вид соответственно:
( ) ( )cos cos cos 0,k k k n n k
j j i i i i i j j j i ipρ ϕ − ϕ − α − ρ α − − ρ ϕ + ϕ − ϕ − α = (4)
( ) ( ) ( )cos cos cos 0k k k n k
j j j i i j i i j ipρ ϕ − α − ρ ϕ − α − ϕ − α + ϕ = . (5)
И.А. ЧУБ, М.В. НОВОЖИЛОВА
Компьютерная математика. 2011, № 2 162
В 4-мерном пространстве параметров ( ), , ,i i j jρ ϕ ρ ϕ 0-уровень функции
( ),ki
nj i jf u u ( ( ),kj
ni i jf u u есть гладкое нелинейное многообразие ki
njγ ( ).kj
niγ
Свойство 2. В силу анизотропии области 0R касание І-го типа, задаваемое
ограничением (4), может иметь место в диапазоне * *
_ min _ max,k i k i
nj nj ϕ ϕ изменения
параметра jϕ , касание ІI-го типа (5) – в диапазоне * *
_ min _ max,k j k j
i ni ni ϕ ∈ ϕ ϕ .
Утверждение 1. Пусть определены функции ( ),ki
nj i jf u u , ( ),kj
ni i jf u u . Тогда
неравенство ( ), 0ki
nj i jf u u > ( ( ), 0kj
ni i jf u u > ) описывает условие (3), а ограничение
( ), 0ki
nj i jf u u < ( ( ), 0kj
ni i jf u u < ) определяет условие int inti jR R∩ ≠ ∅ в соответ-
ствующих диапазонах их изменения * *
_ min _ max,k i k i
nj nj ϕ ϕ , * *
_ min _ max,k j k j
ni ni ϕ ϕ .
Доказательство. Вид ограничения (4), описывающего поверхность ki
njγ
( kj
niγ ), получен при переходе от декартовой системы координат в 2E к полярной.
Такой переход не изменяет форму объектов и расстояния между ними, называе-
мые [1] отношениями взаимного непересечения вида (3). Поэтому в области
определения, заданной выделенными диапазонами изменения, утверждение 1
имеет место.
Аналитическое описание касания объекта iR границы ( 0FrR ) области 0R
задается набором уравнений ( ), 0, 1,4k
n i if kρ ϕ = = , где функция ( ),k
n i if ρ ϕ име-
ет, соответственно, вид:
( ){ ( )sin sin , sin sin ,n n n n
i i i i i i i i i iWρ ϕ + ρ α + ϕ − ρ ϕ − ρ α + ϕ
( ) ( )}cos cos , cos cosn n n n
i i i i i i i i i iZ − ρ ϕ − ρ α + ϕ ρ ϕ + ρ α + ϕ , 1, in n= . (6)
Свойство 3. Функции ( ),ki
nj i jf u u , ( ),kj
ni i jf u u , ( ),k
n i if ρ ϕ могут быть как вы-
пуклыми, так и вогнутыми.
3. Общая схема метода решения задачи (3). Легко показать, что задача
(1–3) – обобщение известной NP-трудной задачи о ранце и является NP-трудной.
Такие свойства задачи как многомерность, многоэкстремальность, наличие по-
грешностей в задании исходных данных, вычислительных погрешностей обу-
славливают использование приближенных алгоритмов решения.
Рассмотрим метод поиска некоторого приближения к глобальному экстре-
муму задачи, который включает следующие этапы.
Этап 1. Определение локального экстремума задачи на базе модифициро-
ванного метода оптимизации по группам переменных.
Этап 2. Перебор локальных экстремумов, основанный на переопределении
порядка размещения объектов.
МЕТОД РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ В АНИЗОТРОПНОЙ ОБЛАСТИ
Компьютерная математика. 2011, № 2 163
В данной работе предполагается, что способ задания последовательности
размещения объектов известен. Это может быть метод сужающихся окрестно-
стей или генетический алгоритм, или реализация датчика случайных чисел.
Общая схема метода оптимизации по группам переменных, на базе которо-
го определяются локальные экстремумы задачи (1–3), такова [1]:
а) объекты размещаются по одному по заданной последовательности
номеров;
б) ранее размещенные объекты считаются неподвижными;
в) размещение каждого объекта производится с учетом требования миними-
зации занятой части области размещения.
Таким образом, на каждой i-й итерации метода решается задача вида
( ),
min
i i i
i
D
Z
ρ ϕ ∈
, (7)
где iD − двумерное сечение подобласти 2iD E⊂% области D, , const,l lρ ϕ =
1, 1; , vari il i= − ρ ϕ = , область D% сформирована ограничениями на размещение
в полосе и условиями взаимного непересечения набора объектов { } 1,
,l l i
R = .
4. Модификация метода решения. Задача (7) вследствие учета анизотро-
пии области размещения имеет нетривиальную сложность. Поэтому в данной
работе предлагается методика ее решения с помощью вспомогательной задачи
размещения габаритных прямоугольников iΠ .
Габаритный прямоугольник iΠ объекта iR − прямоугольник минимальной
площади, содержащий iR . Параметры размещения ( )
_ _ _,
i i iΠ Π Πη = ρ ϕ iΠ , свя-
занные с его полюсом − , inti i iΡ Ρ ∈ Π , совпадают с параметрами ( ),i iρ ϕ объекта
iR . Итак, задача (8) разбивается на 3 подзадачи более простой структуры.
Задача i1. Определение габаритного прямоугольника iΠ для объекта iR .
Задача i2. Размещение прямоугольника iΠ в области rect
iD .
Задача i3. Сжатие полученного размещения (переход к исходным объектам).
Рассмотрим более подробно шаги модифицированного алгоритма.
i1. Метрические характеристики ( ) ( ), , i i i i i ia b a a b b= − − iΠ при _ 0iΠϕ =
таковы:
{ } { } { } { }i imin cos , max cos , b min sin ,b max sink k k k k k k k
i i i i i i i i i ik kk k
a a= ρ ϕ = ρ ϕ = ρ ϕ = ρ ϕ ,
1, .ik n= При этом, несмотря на то, что ориентация объекта iR при движении по
области 0R непрерывно меняется в соответствии с направлением sr, стороны iΠ
остаются, по определению, параллельными осям 0ϕ = и / 2ϕ = π .
Зафиксируем некоторое значение ( )_ i iΠϕ = ϕ . Пусть при этом _ mina ,
_ maxa , _ minb , _ maxb − номера габаритных вершин объекта iR .
Метрическая характеристика ia объекта iΠ – функция вида:
( ) ( ) ( )_ max _ max _ min _ min
_ _, cos cos .a a a a
i i i i i i i i i i ia a a a a Π Π= − = ρ ϕ + ϕ − ρ ϕ + ϕ (8)
И.А. ЧУБ, М.В. НОВОЖИЛОВА
Компьютерная математика. 2011, № 2 164
Аналогично, величина ib определяется как:
( ) ( ) ( )_ max _ max _ min _ min
_ _, sin sin .b b b b
i i i i i i i i i i ib b b b b Π Π= − = ρ ϕ + ϕ − ρ ϕ + ϕ 9)
Утверждение 2. Метрические характеристики ( , )a b прямоугольника iΠ –
кусочно-гладкие функции вида (8), (9) угла поворота _ iΠϕ .
Итак, размещение габаритных прямоугольников iΠ в анизотропной обла-
сти 0R эквивалентно размещению прямоугольников с изменяемыми по законам
(8), (9) метрическими характеристиками в изотропной области размещения.
i2. Область размещения
1
0
1
/
i
i
rect h
h
D R
−
=
= ∪ Π на каждой i -й итерации является
невыпуклой и имеет кусочно-постоянную границу 0
iFrR .
Из вышеизложенного следует, что справедливо
Утверждение 3. Задача (7) эквивалентна задаче вида *
_
0, 1
arg mini h
h i
Π
= −
η = Ψ ,
где
( ) ( )
_
_ 0 0min , 0
i
h h h i ia a a
Π
Πϕ
Ψ = ρ + + φ ρ = = (10)
при условии, что _
rect
i iDΠη ∈ .
i3. Точка *
_
rect
i iFrDΠη ∈ (или вершина области rect
iD ). Соответствующая
*
_ iΠη точка ( ),i iρ φ может быть: 1) вершиной; 2) граничной точкой;
3) ( ), inti i iDρ ϕ ∈ . При этом в силу свойства 2 и утверждения 1 во 2-м и 3-м слу-
чаях можно определить набор ограничений ( ), 0kh
ni h if u u > , ( ( ), 0ki
nh hi if u u > ),
{ } ( ), ; , 1,2,... 1h l t l t i∈ ∈ − , вида (4), (5), формирующих подобласть i iD℘ ⊂ .
Процедура сжатия состоит в решении задачи вида
( )* *
( , )
, arg min
i i i
i i i
Fr
Z
ρ ϕ ∈ ℘
ρ ϕ = . (11)
Замечание 3. В общем случае ( )* *, rect
i i iDρ ϕ ∉ .
На рисунке представлено решение модельной задачи размещения объектов
5-ти типов { }1 2 5, ,...,R R R , 4gR = , 1,5g = .
а
РИСУНОК. Решение задачи размещения 20-ти объектов в анизотропной области: а – разме-
щение габаритных прямоугольников; б – соответствующее решение задачи раз-
мещения исходных объектов
б
МЕТОД РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ В АНИЗОТРОПНОЙ ОБЛАСТИ
Компьютерная математика. 2011, № 2 165
Заключение. Исследованы свойства задачи размещения в анизотропной
области в полярной системе координат. Построен и обоснован новый приближен-
ный метод решения, основанный на идее размещения объектов с изменяемыми
метрическими характеристиками в изотропной области. Данный подход может
быть распространен на случай невыпуклых объектов и области размещения.
И.А.Чуб, М.В. Новожилова
МЕТОД РОЗВ’ЯЗАННЯ ЗАДАЧІ РОЗМІЩЕННЯ В АНІЗОТРОПНІЙ ОБЛАСТІ
Досліджені деякі властивості задачі розміщення в анізотропній області в полярній системі коор-
динат. Запропоновано наближений метод розв’язання, що базується на можливості розміщення
об’єктів з метричними характеристиками, що змінюються.
I.A. Chub, M.V. Novozhilova
METHOD OF SOLVING PLACEMENT PROBLEM ON ANISOTROPIC REGION
Properties of placement problems on anisotropic feasible region in polar coordinate system is
investigated. An approximate method of solution, which is based on possibility to locate objects with
varying metric characteristics, is constructed and justified.
1. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри-
ческого проектирования. – Киев: Наук. думка. – 1989. – 267 с.
2. Новожилова М.В., Чуб И.А. Оценка ресурсов инвестиционных проектов как составная
часть технологии банковского кредитования // Фінансово-кредитна діяльність: проблеми
теорії та практики. – Харків: ХІБС УБС НБУ, 2007. – № 4. – С. 35–39.
3. Чуб И.А., Новожилова М.В., Иванилов А.С. Решение задачи распределения ресурсов про-
екта как оптимизационной задачи размещения геометрических объектов с изменяемыми
метрическими характеристиками // Проблемы машиностроения. – 2010. – 4. – № 1–2. –
С. 79–87.
4. Ненахов Э.И., Соболенко Л.А. Метод линеаризации и негладкая оптимизация // System
Research & Information Technologies. – 2009. – № 3. – С. 90–104.
5. Чуб І.А., Новожилова М.В. Аналітичний опис геометричних обмежень задачі розміщення
багатокутних об'єктів в анізотропній області в полярній системі координат // Геометричне
та комп’ютерне моделювання. – Харків: ХДУХТ, 2010. – Вип. 26.
Получено 15.03.2011
Об авторах:
Чуб Игорь Андреевич,
докторант Национального университета гражданской защиты Украины,
e-mail: chubia@nuczu.edu.ua
Новожилова Марина Владимировна,
доктор физико-математических наук, профессор, зав. кафедрой
Харьковского государственного технического университета строительства и архитектуры.
e-mail: novozhilova@kstuca.kharkov.ua
|
| id | nasplib_isofts_kiev_ua-123456789-84672 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T19:05:28Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Чуб, И.А. Новожилова, М.В. 2015-07-11T21:03:02Z 2015-07-11T21:03:02Z 2011 Метод решения задачи размещения в анизотропной области / И.А. Чуб, М.В. Новожилова // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 160-165. — Бібліогр.: 5 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84672 519.8 Исследованы некоторые свойства задачи размещения в анизотропной области в полярной системе координат. Построен и обоснован приближенный метод решения, основанный на идее размещения объектов с изменяемыми метрическими характеристиками в изотропной области. Досліджені деякі властивості задачі розміщення в анізотропній області в полярній системі координат. Запропоновано наближений метод розв’язання, що базується на можливості розміщення об’єктів з метричними характеристиками, що змінюються. Properties of placement problems on anisotropic feasible region in polar coordinate system is investigated. An approximate method of solution, which is based on possibility to locate objects with varying metric characteristics, is constructed and justified. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Метод решения задачи размещения в анизотропной области Метод розв’язання задачі розміщення в анізотропній області Method of solving placement problem on anisotropic region Article published earlier |
| spellingShingle | Метод решения задачи размещения в анизотропной области Чуб, И.А. Новожилова, М.В. Теория и методы оптимизации |
| title | Метод решения задачи размещения в анизотропной области |
| title_alt | Метод розв’язання задачі розміщення в анізотропній області Method of solving placement problem on anisotropic region |
| title_full | Метод решения задачи размещения в анизотропной области |
| title_fullStr | Метод решения задачи размещения в анизотропной области |
| title_full_unstemmed | Метод решения задачи размещения в анизотропной области |
| title_short | Метод решения задачи размещения в анизотропной области |
| title_sort | метод решения задачи размещения в анизотропной области |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84672 |
| work_keys_str_mv | AT čubia metodrešeniâzadačirazmeŝeniâvanizotropnoioblasti AT novožilovamv metodrešeniâzadačirazmeŝeniâvanizotropnoioblasti AT čubia metodrozvâzannâzadačírozmíŝennâvanízotropníioblastí AT novožilovamv metodrozvâzannâzadačírozmíŝennâvanízotropníioblastí AT čubia methodofsolvingplacementproblemonanisotropicregion AT novožilovamv methodofsolvingplacementproblemonanisotropicregion |