О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности
Для использования в постановках задач упаковки и покрытия формализовано взаимное расположение прямоугольников со стохастическими, интервальными или нечеткими параметрами. Предлагаемый подход основывается на установлении взаимного расположения отрезков, являющихся их проекциями на оси координат. Такж...
Saved in:
| Published in: | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
|---|---|
| Date: | 2015 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/133864 |
| 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: | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности / О.А. Емец, Т.Н. Барболина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2015. — Вип. 12. — С. 83-100. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860027889716559872 |
|---|---|
| author | Емец, О.А. Барболина, Т.Н. |
| author_facet | Емец, О.А. Барболина, Т.Н. |
| citation_txt | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности / О.А. Емец, Т.Н. Барболина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2015. — Вип. 12. — С. 83-100. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| description | Для использования в постановках задач упаковки и покрытия формализовано взаимное расположение прямоугольников со стохастическими, интервальными или нечеткими параметрами. Предлагаемый подход основывается на установлении взаимного расположения отрезков, являющихся их проекциями на оси координат. Также построены комбинаторные математические модели оптимальной упаковки прямоугольников и покрытия прямоугольниками для случая, когда входные данные являются дискретными случайными величинами.
Authors formalize mutual placement of rectangles with stochastic, interval or fuzzy parameters for use in packing and covering problem statements. The approach offered in the paper is based on determining of mutual placement of their projections on the coordinate axes. We also construct a combinatorial mathematical model of optimum rectangle packing when data are discrete random variables.
|
| first_indexed | 2025-12-07T16:50:45Z |
| format | Article |
| fulltext |
Серія: Фізико-математичні науки. Випуск 12
83
УДК 519.85
О. А. Емец*, д-р физ.-мат. наук, професор,
Т. Н. Барболина**, канд. физ.-мат. наук
*Полтавский университет экономики и торговли, г. Полтава,
**Полтавский национальный педагогический университет
имени В. Г. Короленко, г. Полтава
О ЗАДАЧАХ ОПТИМИЗАЦИИ ВЗАИМНОГО РАСПОЛОЖЕНИЯ
ПРЯМОУГОЛЬНИКОВ В УСЛОВИЯХ СТОХАСТИЧЕСКОЙ,
ИНТЕРВАЛЬНОЙ ИЛИ НЕЧЕТКОЙ НЕОПРЕДЕЛЕННОСТИ
Для использования в постановках задач упаковки и покры-
тия формализовано взаимное расположение прямоугольников
со стохастическими, интервальными или нечеткими парамет-
рами. Предлагаемый подход основывается на установлении
взаимного расположения отрезков, являющихся их проекция-
ми на оси координат. Также построены комбинаторные мате-
матические модели оптимальной упаковки прямоугольников и
покрытия прямоугольниками для случая, когда входные дан-
ные являются дискретными случайными величинами.
Ключевые слова: комбинаторная оптимизация, модели
упаковки, параметры с неопределенностью, упаковка прямо-
угольников.
Введение, постановка задачи. Применение аппарата комбина-
торной оптимизации (см., например [1–6]) позволяет адекватно фор-
мализовать целый ряд практически значимых задач. Одной из таких
задач евклидовой комбинаторной оптимизации является задача упа-
ковки прямоугольников, которая в одном из простейших случаев
формулируется следующим образом [2, с. 146]. Пусть есть полубес-
конечная полоса, разделенная на полоски одинаковой ширины H .
Заданы также t прямоугольников ширины H с длинами 1,..., ta a .
Задача состоит в расположении прямоугольников без наложений в
полосе таким образом, чтобы длина занятой части полосы была ми-
нимально возможной (под длиной занятой части полосы понимают
максимальную из длин занятых частей отдельных полосок).
Следует отметить, что в случае наличия той или иной неопреде-
ленности входных данных (см., например, [5; 7]) возникает вопрос о
формализации понятий взаимного расположения прямоугольников в
полосе. Одним из возможных подходов к решению данной проблемы
может быть использование введенного порядка на множестве соот-
ветствующих величин (нечетких чисел [8], центрированных интерва-
лов [7], случайных величин [9]). Например, в [8], это было подробно
© О. А. Емец, Т. Н. Барболина, 2015
Математичне та комп’ютерне моделювання
84
сделано для прямоугольников с нечеткими параметрами. В данной
статье предлагается подход, который идейно близок к жестким по-
становкам в задачах стохастического программирования [10; 11] и
закрывает имеющийся в этом смысле пробел для учета стохастиче-
ской неопределенности данных.
При этом для математической постановки задачи упаковки пря-
моугольников с неопределенными данными сначала необходимо оп-
ределить, что понимать под различными способами размещения пря-
моугольников: попаданием прямоугольника в полосу; взаимным пе-
ресечением прямоугольников, размещенных в полосе; взаимным не-
пересечением прямоугольников, размещенных в полосе; касанием
прямоугольников, размещенных в полосе.
Формализация понятия прямоугольника с неопределенны-
ми параметрами. В данной статье будем рассматривать прямоуголь-
ники, по крайне мере один из размеров которых является центриро-
ванным интервалом, нечетким числом с дискретным носителем ко-
нечной мощности или конечнозначной дискретной случайной вели-
чиной. Такие параметры прямоугольников с неопределенностью (ин-
тервальной, нечеткой, стохастической) будем обозначать буквами
полужирного начертания и называть ИНСН-параметрами. Для удоб-
ства изложения также будем говорить о возможных значениях
ИНСН-параметров, под которыми будем понимать следующее:
для центрированных интервалов — множество точек соответст-
вующего интервала, в том числе концы интервала;
для нечетких чисел — элементы носителя нечеткого числа;
для дискретных случайных величин — в соответствии с общепри-
нятым пониманием — множество тех значений, для которых со-
ответствующая вероятность положительна.
Возможные значения ИНСН-параметров будем обозначать соот-
ветствующими буквами обычного начертания. Также для ИНСН-
параметра r через minr будем обозначать наименьшее, а через maxr
наибольшее возможное значение (для рассматриваемых величин та-
кие значения, очевидно, существуют).
Замечание 1. Отметим, что действительное число a может
быть представлено как случайное с вероятностью 1, как нечеткое со
значением функции принадлежности 1 или как центрированный ин-
тервал ( ;0)a . При этом min maxa a a .
Прямоугольником , у которого хотя бы один из размеров за-
дан ИНСН-параметром, назовем множество реализаций прямоуголь-
ников, размеры которых принимают одно из возможных значений
Серія: Фізико-математичні науки. Випуск 12
85
соответствующих ИНСН-параметров. Например, если длина d и ши-
рина h — дискретные случайные величины с возможными реализа-
циями jd с вероятностью jp и jh с вероятностью jq соответствен-
но, то прямоугольник ' с размерами id и jh с вероятностью реали-
зации i jp q — один из заданного множества прямоугольников;
' . Определение прямоугольника с нечеткими параметрами
дано в [8, с. 61]. Если размеры прямоугольника заданы как цен-
трированные интервалы: длина ( ; )d , ширина ( ; )h , — то ' имеет
размеры ' [ ; ], [ ; ]d d d h h h и это — один из обычных
прямоугольников, которые образуют множество : ' .
Пусть на плоскости задана декартова система координат xOy .
Будем рассматривать расположения прямоугольников из , стороны
которых параллельны осям координат. Тогда расположение прямо-
угольника относительно системы координат может быть определено
такими ИНСН-параметрами:
(ζ, υ) — соответственно абсцисса и ордината левого нижнего угла
при каждой реализации прямоугольника из в системе коорди-
нат xOy ;
h и d — ширина (высота) и длина прямоугольника.
Прямоугольник с указанными ИНСН-параметрами будем обозна-
чать через (ζ, υ, h, d). Также через ( , ) будем обозначать отрезок
с координатами концов η и θ (ИНСН-параметрами или действительными
числами). Полагаем, что конец с координатой расположен левее (на-
чало отрезка), то есть для действительных чисел и min min ,
если η и θ — ИНСН-параметры. Будем говорить, что отрезок τ(η, θ)
( , ) удовлетворяет условию определенности концов отрезка, если для
ИНСН-параметров η и θ выполняется неравенство max min .
Введем проекции x (ζ, υ, h, d) и y (ζ, υ, h, d) прямоугольника
(ζ, υ, h, d) на оси Ox и Oy соответственно. Назовем проекциями
x (ζ, υ, h, d) = τ(ζ, ζ + d) и y (ζ, υ, h, d) = τ(υ, υ + h) . Операции
суммы для нахождения ζ + d, υ + h для нечетких чисел рассмотрены в
[8, с. 30], для центрированных интервалов — в [7, с. 44], а для слу-
чайных величин — классические. В дальнейшем будем полагать, что
для отрезков x (ζ, υ, h, d) и y (ζ, υ, h, d) выполняется условие оп-
ределенности концов отрезка.
Математичне та комп’ютерне моделювання
86
Формализация взаимного расположения прямоугольников в
описанном выше понимании может быть осуществлена на основе
установления взаимного расположения их проекций на оси коорди-
нат. Поэтому рассмотрим детальнее вопрос о взаимном расположе-
нии двух отрезков, лежащих на одной прямой, если координаты кон-
цов отрезка являются ИНСН-параметрами.
Формализация в условиях неопределенности взаимного рас-
положения отрезков. Рассмотрим отрезки τ(p, q) и τ(r, s), для кото-
рых min minp r (назовем это условие упорядочением начал отрез-
ков). Тогда при возможных значениях , , ,p q r s ИНСН-параметров
p, q, r, s отрезки ( , )p q и ( , )r s , очевидно, не имеют общих точек
тогда и только тогда, когда q r .
Определение 1. Отрезок τ(r, s) будем называть безусловно при-
надлежащим отрезку τ(p, q), если при любых возможных значениях
, , ,p q r s ИНСН-параметров p, q, r, s все точки отрезка ( , )r s при-
надлежат отрезку ( , )p q .
Пример 1. Рассмотрим отрезки τ(p, q) и τ(r, s), где , , ,p q r s яв-
ляются центрированными интервалами, которые будем обозначать
( , ) , понимая под этим интервал числовой оси ( ; )
( 1, R , 0 ). Пусть p (2;1) , q (9;0,5) , r (4;0,5) , s (7,5;1) .
Так как max min3 8,5p q и max min4,5 6,5r s , то для заданных
отрезков выполняется условие определенности концов. Также выполня-
ется условие упорядочения начал отрезков: min min1 3,5p r . Как
легко видеть из рис. 1, отрезок τ(r, s) является безусловно принадле-
жащим отрезку τ(p, q) (на рис. 1 заштрихованы те промежутки число-
вой прямой, которые принадлежат соответствующему отрезку при
любых возможных значениях интервальных параметров).
20 9
p q
sr
Рис. 1. Иллюстрация к примеру 1
Определение 2. Отрезок τ(r, s) будем называть возможно при-
надлежащим отрезку τ(p, q), если при отсутствии безусловной при-
надлежности существуют такие возможные значения , , ,p q r s ИНСН-
параметров p, q, r, s, при которых все точки отрезка ( , )r s принад-
лежат отрезку ( , )p q .
Серія: Фізико-математичні науки. Випуск 12
87
Определение 3. Отрезки τ(p, q) и τ(r, s) будем называть безус-
ловно непересекающимися, если при любых возможных значениях
, , ,p q r s ИНСН-параметров p, q, r, s отрезки ( , )p q и ( , )r s не
имеют общих точек.
Определение 4. Отрезки τ(p, q) и τ(r, s) будем называть возмож-
но непересекающимися, если выполняются следующие условия:
а) существуют возможные значения , , ,p q r s ИНСН-параметров
p, q, r, s, при которых отрезки ( , )p q и ( , )r s имеют больше од-
ной общей точки;
б) существует такое возможное значение r ИНСН-параметра r, что
при любых возможных значениях ИНСН-параметров p, q, s отрез-
ки ( , )p q и ( , )r s не имеют общих точек.
Определение 5. Отрезки τ(p, q) и τ(r, s) будем называть внешне
касающимися, если существует единственная пара возможных значе-
ний ,q r ИНСН-параметров q, r, при которых независимо от воз-
можных значений ,p s ИНСН-параметров p, s отрезки ( , )p q и
( , )r s имеют одну общую точку, а при всех остальных возможных
значениях ИНСН-параметров отрезки не имеют общих точек.
Определение 6. Отрезки τ(p, q) и τ(r, s) будем называть внутренне
касающимися, если для любых возможных значений , , ,p q r s ИНСН-
параметров p, q, r, s отрезки ( , )r s и ( , )p q имеют различные (необ-
щие) точки и при этом существует единственная пара возможных значе-
ний ,q r ИНСН-параметров q, r, такая, что независимо от возможных
значений ,p s ИНСН-параметров p, s отрезки ( , )p q и ( , )r s имеют
одну общую точку, а при всех остальных возможных значениях ИНСН-
параметров отрезки имеют больше одной общей точки.
Определение 7. Отрезки τ(p, q) и τ(r, s) будем называть безус-
ловно пересекающимися, если τ(r, s) не является безусловно или воз-
можно принадлежащим τ(p, q) и при любых возможных значениях
, , ,p q r s ИНСН-параметров p, q, r, s отрезки ( , )p q и ( , )r s имеют
больше одной общей точки.
Определение 8. Отрезки τ(p, q) и τ(r, s) будем называть возмож-
но пересекающимися, если выполняются следующие условия:
а) отрезок τ(r, s) не является возможно принадлежащим отрезку τ(p, q);
б) существуют возможные значения , , ,p q r s ИНСН-параметров p, q, r, s,
при которых отрезки ( , )p q и ( , )r s не имеют общих точек;
Математичне та комп’ютерне моделювання
88
в) существует такое возможное значение q ИНСН-параметра q, что
при любых возможных значениях ИНСН-параметров p, r, s отрез-
ки ( , )p q и ( , )r s имеют по крайней мере одну общую точку.
Справедливо следующее утверждение.
Утверждение 1 (о полноте введенной системы взаимного рас-
положения отрезков в условиях неопределенности). Для любых двух
отрезков τ(p, q) и τ(r, s), для которых выполнено условия определен-
ности концов max minp q и упорядочения начал min minp r , имеет
место одно из соотношений, введенных в определениях 1–8.
Замечание 2. В случае, когда неопределенность имеет вероят-
ностный характер, целесообразно также ставить вопрос о вероятно-
сти касания (пересечения, непересечения) отрезков.
Формализация взаимного расположения прямоугольников.
Определение 9. Прямоугольник (ζ, υ, h, d) будем называть
безусловно размещающимся в прямоугольнике (ζ', υ', h', d'), если
отрезки x (ζ, υ, h, d) и y (ζ, υ, h, d) безусловно принадлежат от-
резкам x (ζ', υ', h', d') и y (ζ', υ', h', d') соответственно.
Определение 10. Прямоугольник (ζ, υ, h, d) будем называть
возможно размещающимся в прямоугольнике (ζ', υ', h', d') если
выполняются следующие условия:
а) прямоугольник (ζ, υ, h, d) не является безусловно размещаю-
щимся в прямоугольнике (ζ', υ', h', d');
б) отрезки x (ζ, υ, h, d) и y (ζ, υ, h, d) возможно или безусловно
принадлежат отрезкам x (ζ', υ', h', d') и y (ζ', υ', h', d') соот-
ветственно.
Замечание 3. Если рассматривается размещение прямоугольни-
ка (ζ, υ, h, d) в полубесконечной полосе шириной H, левый ниж-
ний угол которой имеет действительные координаты 0;0 , причем
ось Ox направлена вдоль бесконечной стороны полосы, то в опреде-
лениях 9, 10 при использовании «безусловной принадлежности» по-
лагаем min max' ' 0, min max' ' 0, ,h H min' ,d max'd тако-
вы, что неравенства max max' ,d d min min'd d выполняются при
любых значениях maxd и mind .
Определение 11. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть безусловно непересекающимися, если безусловно не пе-
ресекаются отрезки по крайней мере одной из двух следующих пар:
x (ζ, υ, h, d), x (ζ', υ', h', d') или y (ζ, υ, h, d), y (ζ', υ', h', d').
Серія: Фізико-математичні науки. Випуск 12
89
Определение 12. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть возможно непересекающимися, если при отсутствии
безусловного непересечения возможно не пересекаются отрезки по
крайней мере одной из двух следующих пар: x (ζ, υ, h, d),
x (ζ', υ', h', d') или y (ζ, υ, h, d), y (ζ', υ', h', d').
Определение 13. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть безусловно пересекающимися, если выполнено одно
из двух условий:
а) отрезки (ζ, υ, h, d) и (ζ', υ', h', d') безусловно пересекаются и
при этом либо безусловно пересекаются отрезки y (ζ, υ, h, d) и
y (ζ', υ', h', d'), либо один из отрезков y (ζ, υ, h, d), и
y (ζ', υ', h', d') является безусловно или возможно принадлежа-
щим другому;
б) отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d') безусловно пересекаются
и при этом один из отрезков x (ζ, υ, h, d) и x (ζ', υ', h', d') явля-
ется безусловно или возможно принадлежащим другому.
Определение 14. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть возможно пересекающимися, если выполнено одно
из двух условий:
а) отрезки x (ζ, υ, h, d) и x (ζ', υ', h', d') возможно пересекаются и
при этом либо пересекаются (безусловно или возможно) отрезки
y (ζ, υ, h, d) и y (ζ', υ', h', d'), либо один из отрезков y (ζ, υ, h, d)
и y (ζ', υ', h', d') является безусловно или возможно принадле-
жащим другому;
б) отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d') возможно пересекаются и
при этом либо безусловно пересекаются отрезки x (ζ, υ, h, d) и
x (ζ', υ', h', d'), либо один из отрезков x (ζ, υ, h, d) и
x (ζ', υ', h', d') является безусловно или возможно принадлежа-
щим другому.
Определение 15. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть безусловно касающимися внешне (внутренне), если
выполнено одно из двух условий:
а) отрезки x (ζ, υ, h, d) и x (ζ', υ', h', d')
являются внешне (внутрен-
не) касающимися и при этом отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d')
Математичне та комп’ютерне моделювання
90
безусловно пересекаются либо один из отрезков y (ζ, υ, h, d) и
y (ζ', υ', h', d') является безусловно принадлежащим другому;
б) отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d')
являются внешне (внутрен-
не) касающимися и при этом отрезки x (ζ, υ, h, d) и x (ζ', υ', h', d')
безусловно пересекаются либо один из отрезков x (ζ, υ, h, d) и
x (ζ', υ', h', d') является безусловно принадлежащим другому.
Определение 16. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть возможно касающимися внешне (внутренне), если
выполнено одно из двух условий:
а) отрезки x (ζ, υ, h, d) и x (ζ', υ', h', d')
являются внешне (внутрен-
не) касающимися и при этом отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d')
возможно пересекаются либо один из отрезков y (ζ, υ, h, d),
y (ζ', υ', h', d')
является возможно принадлежащим другому;
б) отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d')
являются внешне (внутрен-
не) касающимися и при этом отрезки x (ζ, υ, h, d) и x (ζ', υ', h', d')
возможно пересекаются либо один из отрезков x (ζ, υ, h, d),
x (ζ', υ', h', d') является возможно принадлежащим другому.
Определение 17. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть внешне (внутренне) касающимися, если внешне
(внутренне) касающимися являются как отрезки x (ζ, υ, h, d) и
x (ζ', υ', h', d'), так и отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d')
.
Определение 18. Прямоугольники (ζ, υ, h, d) и (ζ', υ', h', d')
будем называть внешне-внутренне касающимися, если выполнено
одно из двух условий:
а) отрезки x (ζ, υ, h, d) и x (ζ', υ', h', d')
являются внешне касаю-
щимися, а отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d')
— внутренне
касающимися;
б) отрезки x (ζ, υ, h, d) и x (ζ', υ', h', d')
являются внутренне ка-
сающимися, а отрезки y (ζ, υ, h, d) и y (ζ', υ', h', d') — внешне
касающимися.
Пример 2. Рассмотрим прямоугольники (ζ1, υ1, h1, d1) и
(ζ2, υ2, h2, d2), параметры которых являются дискретными случай-
ными величинами, определенными рядами распределения в соответ-
ствии с табл. 1.
Серія: Фізико-математичні науки. Випуск 12
91
Таблица 1
Ряды распределения параметров прямоугольников
Параметры прямоугольников i = 1 i = 2
значения ζi 1 2 6 6,3 7
вероятности значений ζi 0,3 0,7 0,5 0,3 0,2
значения υi 2 2,5 3 0,5
вероятности значений υi 0,3 0,3 0,4 1
значения hi 3 2,5 3 4
вероятности значений hi 1 0,2 0,6 0,2
значения di 3 4 4
вероятности значений di 0,5 0,5 1
Проекциями рассматриваемых прямоугольников на оси коорди-
нат являются отрезки τ(p1, q1) = Πx(ζ1, υ1, h1, d1), τ(p2, q2) = Πx(ζ2, υ2, h2, d2),
τ(r1, s1) = Πy(ζ1, υ1, h1, d1), τ(r2, s2) = Πy(ζ2, υ2, h2, d2), где pi = ζi, ri = υi
( 1, 2i ), а ряды распределения случайных величин q1 = ζ1 + d1,
q2 = ζ2 + d2, s1 = υ1 + h1, s2 = υ2 + h2, представлены в табл. 2.
Таблица 2
Ряды распределения параметров отрезков
Параметры отрезков i = 1 i = 2
значения qi 4 5 6 10 10,3 11
вероятности значений qi 0,15 0,5 0,35 0,5 0,3 0,2
значения si 5 5,5 6 3 3,5 4,5
вероятности значений si 0,3 0,3 0,4 0,2 0,6 0,2
На рис. 2 каждая точка областей 1 и 2 принадлежит по
крайней мере одному прямоугольнику в обычном смысле
1 (ζ1, υ1, h1, d1) или 2 (ζ2, υ2, h2, d2) соответственно. За-
штрихованные области — это множества точек, принадлежащих лю-
бому прямоугольнику из множества Π(ζi, υi, hi, di) ( 1;2i ).
y
1 xO
Π1
Π2
p1 p2
6
q1 q2
r1
s1
s2
6
r2
Рис. 2. Иллюстрация к примеру 2
Математичне та комп’ютерне моделювання
92
Из рис. 2 видно, что отрезки τ(p1, q1) и τ(p2, q2) являются внешне
касающимися (значения ИНСН-параметров max min
1 1 2 2 6q q p p
удовлетворяют условиям определения 5), а отрезки τ(r2, s2) и
τ(r1, s1) — внутренне касающимися (условиям определения 6 удовле-
творяют значения max min
1 1 2 2 3r r s s ). Таким образом, в соответ-
ствии с условием а) определения 18 прямоугольники Π(ζ1, υ1, h1, d1) и
Π(ζ2, υ2, h2, d2) являются внешне-внутренне касающимися.
Возможные размещения прямоугольников систематизированы в
табл. 3, где использованы следующие обозначения, используемые
при описании расположения прямоугольников: Б — безусловно, В —
возможно, Пр — принадлежащие, П — пересекающиеся, НП — не-
пересекающиеся, Вш — внешне, Вт — внутренне, К — касающиеся,
Р — размещающиеся.
В табл.3 шапка и боковик определяют расположение отрезков
Πx(ζ, υ, h, d), Πx(ζ', υ', h', d') и отрезков Πy(ζ, υ, h, d), Πy(ζ', υ', h', d')
соответственно, а клетка на их пересечении — расположение прямо-
угольников Π(ζ, υ, h, d), Π(ζ', υ', h', d').
Таблица 3
Возможные размещения прямоугольников
x
y
БПр ВПр БНП ВНП БП ВП ВшК ВтК
БПр БР ВР БНП ВНП БП ВП БВшК БВтК
ВПр ВР ВР БНП ВНП БП ВП ВВшК ВВтК
БНП БНП БНП БНП БНП БНП БНП БНП БНП
ВНП ВНП ВНП БНП ВНП ВНП ВНП ВНП ВНП
БП БП БП БНП ВНП БП ВП БВшК БВтК
ВП ВП ВП БНП ВНП ВП ВП ВВшК ВВтК
ВшК БВшК ВВшК БНП ВНП БВшК ВВшК ВшК ВшВтК
ВтК БВтК ВВтК БНП ВНП БВтК ВВтК ВшВтК ВтК
Как следует из табл.3, справедливо следующее утверждение
Утверждение 2 (о полноте введенной системы взаимного рас-
положения прямоугольников в условиях неопределенности). Для лю-
бых двух прямоугольников Π(ζ, υ, h, d) и Π(ζ', υ', h', d'), для проекций
которых на оси координат выполняется условие определенности кон-
цов отрезка, имеет место одно из соотношений, введенных в опреде-
лениях 9–18.
Математические модели задач упаковки и покрытия прямо-
угольников со стохастическими параметрами. Используя введен-
ные понятия, построим одну математическую модель задачи упаков-
Серія: Фізико-математичні науки. Випуск 12
93
ки прямоугольников в случае, когда длины прямоугольников 1,..., ta a
являются конечнозначными дискретными случайными величинами.
Один из возможных подходов к формализации взаимного располо-
жения прямоугольников состоит в использовании отношения порядка
на множестве дискретных случайных величин [9]. Ниже предлагается
подход, который идейно близок к жестким постановкам задач стохас-
тической оптимизации.
Как известно [11, с. 8], при построении моделей выбора реше-
ний в условиях неполной информации в ряде случаев целесообразно
использовать так называемые жесткие постановки задач стохастиче-
ского программирования, в которых ограничения задачи должны
удовлетворяться при всех реализациях случайных параметров. В
применении к задаче упаковки прямоугольников это означает, что ни
при каких значения случайных величин не может произойти наложе-
ние прямоугольников, однако могут образовываться зазоры.
Пусть осуществляется упаковка прямоугольников, ширина H ко-
торых является действительным числом, в полубесконечную полосу
0 , левый нижний угол которой расположен в начале системы коор-
динат, причем ось Ox направлена вдоль бесконечной стороны полосы.
Полагаем, что данная полубесконечная полоса разделена на m поло-
сок ширины H . Тогда в оптимальном решении в каждой полоске сто-
ит от 1 до ( 1)t m прямоугольников. Обозначим 1n t m и вве-
дем в рассмотрение mn t прямоугольников с шириной H и длиной
0 0a (в замечании 1 отмечена возможность рассматривать действи-
тельные числа как ИНСН-параметр в предельных случаях). В каждой
полоске разместим столько прямоугольников длины 0a , чтобы их об-
щее количество в полоске равнялось n . Таким образом, можно счи-
тать, что в каждой полоске стоит ровно n прямоугольников.
Обозначим Π(ζij, υij, hij, xij) — прямоугольник, стоящий в i -й по-
лоске ( mi J ) на j -м ( nj J ) от начала полосы месте (тут и далее
sJ обозначено множество s первых натуральных чисел). Так как все
полоски и прямоугольники одинаковой ширины H , то при ij Hh ,
( 1)ij i H ν ,m ni J j J , очевидно, прямоугольники, стоящие в
разных полосках, являются либо безусловно непересекающимися,
либо касающимися (как внутренне, так и внешне).
Так как ни при каких возможных значениях дискретных случайных
величин 0 1, ,..., ta a a прямоугольники не могут накладываться, то в до-
пустимом решениии должно иметь место либо безусловное непересече-
Математичне та комп’ютерне моделювання
94
ние, либо внешнее касание (безусловное или возможное) соседних пря-
моугольников ненулевой длины. Очевидно, что в оптимальном решении
прямоугольники должны в полосках размещаться так, чтобы каждый
следующий внешне касался предыдущего. Так как , 1i j ij ν ν , то это
означает внешнее касание всех отрезков Πx(ζij, υij, hij, xij) = τ(ζij, ζij +xij) и
Πx(ζi,j + 1, υi,j + 1, hi,j + 1, xi,j + 1) = τ(ζi,j + 1, ζi,j + 1 +xi,j + 1), для которых ijx и
, 1i jx — дискретные случайные величины.
Необходимым и достаточным условием внешнего касания указан-
ных проекций является выполнение равенства max min
, 1ij ij i jx .
Действительно, в этом случае отрезки max
,ij ij ijx
и
min
, 1 , 1 , 1,i j i j i jx имеют единственную общую точку при любых
возможных значениях ИНСН-параметров ,ijξ ζi,j + 1 +xi,j + 1, причем вслед-
ствие неравенства , 1ij ij i jx отрезки не пересекаются для всех ос-
тальных возможных значений ИНСН-параметров. С другой стороны,
если max min
, 1ij ij i jx , то отрезки max
,ij ij ijx
и
min
, 1 , 1 , 1,i j i j i jx имеют больше одной общей точки, а при
max min
, 1ij ij i jx отрезки τ(ζi,j, ζi,j +xi,j) и τ(ζi,j + 1, ζi,j + 1 +xi,j + 1) не имеют
общих точек ни при каких возможных значениях ИНСН-параметров.
Будем размещать прямоугольники таким образом, чтобы
1
ij R mi J nj J . Тогда max
ij ij , min
, 1 , 1i j i j , значит,
maxmin max
, 1 , 1i j i j ij ij ij ijx x . При этом для отрезков нуле-
вой длины это равенство запишется как , 1i j ij , то есть добавле-
ние прямоугольников длины 0 0a
не влияет на длину занятой части
полосы. Таким образом, в оптимальном решении должны выполнять-
ся равенства max
, 1i j ij ijx 1,m ni J j J .
Первый в полоске прямоугольник, очевидно, следует размещать
так, чтобы его начало совпадало с началом полосы, то есть 1 0i .
Следовательно, длина занятой части i -й полоски равна
max max max
1 2 ...i i inx x x , а длина занятой части полосы в целом опреде-
ляется как max max max
1 2
1
max ...i i in
i m
x x x
.
Серія: Фізико-математичні науки. Випуск 12
95
Для формализации ограничений на возможные длины прямо-
угольников может быть использован аппарат евклидовой комбина-
торной оптимизации. Соответствующую терминологию будем ис-
пользовать преимущественно из [2]. В частности, под мультимноже-
ством G понимаем совокупность элементов, среди которых могут
быть и одинаковые. Множество, различными элементами которого
являются различные k -выборки из G вида
1 2
, ,..., ,
ki i ig g g (1)
jig G , j ji i ,j t ni i J , , kj t J называется евклидовым комби-
наторным множеством. Примерами евклидовых комбинаторных
множеств являются общее множество размещений kE G (множест-
во всех k -выборок вида (1) из мультимножества G ) и общее множе-
ство перестановок kE G (множество всех выборок вида (1) из муль-
тимножества G при условии k ).
Рассмотрим мультимножество 0 0 1{ ,..., , ,..., }t
mn t
G
a a a a и вектор
11 1 21 1,..., , ,..., ,..., .n m mnx x x x x x (2)
Тогда каждому расположению прямоугольников в полосе вза-
имно однозначно соответствует вектор x , который можно рассмат-
ривать как элемент множества перестановок kE G ( k mn ) из эле-
ментов мультимножества G , то есть kx E G .
Таким образом, математическую модель сформулированной за-
дачи упаковки прямоугольников, длины которых являются дискрет-
ными случайными величинами, можно записать так: найти пару
* *,F x x такую, что
* max * max
1 11 1
min max ; arg min max
k k
n n
ij ij
x E G i m i mx E Gj j
F x x x x
.
Замечание 4. Можно также рассматривать задачу упаковки
прямоугольников в случае, когда ширина прямоугольников H явля-
ется дискретной случайной величиной. Тогда из запрета наложений
следует, что ширина полосок, на которые разделяется заданная полу-
бесконечная полоса, равна maxH .
Приведем пример содержательной интерпретации задачи упа-
ковки прямоугольников, в котором целесообразным представляется
применение рассматриваемого в статье подхода. Пусть имеется неко-
Математичне та комп’ютерне моделювання
96
торая система обслуживания, содержащая m устройств. Каждое из
устройств в любой момент времени может осуществлять обслужива-
ние одного из t заказов, причем длительность исполнения заказов не
зависит от обслуживающего устройства. Будем считать, что в зада-
нии длительности обработки заказов имеет место стохастическая не-
определенность. Необходимо до начала обслуживания определить
для каждого заказа соответствующее устройство и момент (детерми-
нированный) начала его выполнения при таких условиях:
недопустимость задержки обслуживания заказов: в момент времени,
определенный как начало выполнения i -го заказа, выполнение пре-
дыдущих заказов на данном устройстве должно завершиться;
время выполнения всех заказов должно быть минимально воз-
можным.
Интерпретируя длительность обслуживания заказов как длины
прямоугольников со стохастическими параметрами, задачу распреде-
ления заказов можно сформулировать как задачу упаковки прямо-
угольников. При этом именно использование описанного выше под-
хода к формализации взаимного расположения прямоугольников по-
зволяет гарантировать отсутствие задержек (то есть пересечений
прямоугольников) при всех реализациях стохастических параметров.
Вместе с задачей упаковки прямоугольников практически зна-
чимой является задача покрытия прямоугольной области прямо-
угольниками. Некоторые математические модели такой задачи для
случаев, когда размеры прямоугольников являются действительными
или нечеткими числами, были предложены в [12; 13]. Рассмотрим
одну из возможных постановок, если длины прямоугольников явля-
ются конечнозначными дискретными случайными величинами.
Пусть задана прямоугольная полоса, разделенная на m полосок оди-
наковой ширины H и длины L (т.е. прямоугольников), где 1H R ,
L — конечнозначная дискретная случайная величина. Так же, как и
в задаче упаковки, заданы t m прямоугольников ширины H с
длинами 1,..., ta a (как и длина полосы, длины прямоугольников яв-
ляются конечнозначными дискретными случайными величинами).
Полагаем, что при любых возможных значениях стохастических па-
раметров 1,..., ta a суммарная площадь прямоугольников не меньше
площади полосы mHL (здесь под произведением mHL понимаем
случайную величину, возможные значения которой равны произве-
дению возможных значений величины L на константу mH , а веро-
ятности равны соответствующим вероятностям величины L ). Задача
состоит в том, чтобы выбрать такое размещение прямоугольников,
Серія: Фізико-математичні науки. Випуск 12
97
при котором каждая точка полосы принадлежала бы по крайней мере
одному из прямоугольников независимо от реализаций случайных
параметров и при этом математическое ожидание суммарной площа-
ди прямоугольников было минимально.
Будем рассматривать положение полосы, как в предыдущей за-
даче, и использовать аналогичные обозначения. Можно полагать, что
в каждой полоске стоит ровно n прямоугольников, из которых неко-
торые нулевой длины (вопрос об определении значения n будет рас-
смотрен ниже). Так как между прямоугольниками не должно быть
промежутков ни при каких возможных значениях стохастических
параметров, то соседние прямоугольники ненулевой длины должны
либо внутренне касаться (безусловно или возможно), либо безуслов-
но пересекаться. Очевидно, что для любого покрытия, в котором со-
седние прямоугольники безусловно пересекаются, существует по-
крытие без пересечения, которое будет по крайней мере не хуже с
точки зрения указанного критерия оптимальности.
Если для прямоугольника , , ,ij ij ij ijh x , как и выше, полага-
ем, что , ,ij ij ijh являются действительными числами, причем
1ij i H , ijh H , то между полосками, очевидно, промежутков
нет. При этом отрезки , , , ,x ij ij ij ij ij ij ijh x x и
, 1 , 1 , 1 , 1 , 1 , 1 , 1, , , ,x i j i j i j i j i j i j i jh x x должны внутрен-
не касаться. Достаточным условием этого является выполнение ра-
венства min max
, 1ij ij i jx (очевидно, отрезки имеют различные
точки, причем возможные значения min
ij ijq x и max
, 1i jr
удовлетворяют условиям определения 6).
Учитывая, что ij — действительное число, то есть min
ij ij ,
получаем min
, 1i j ij ijx
,m ni J j J . Кроме того, при любых
возможных значениях стохастических параметров правый конец по-
следнего прямоугольника должен располагаться правее конца поло-
сы, то есть должно выполняться неравенство
min max
1
.
n
ij
j
x L
(3)
Как и в задаче упаковки, каждому размещению прямоугольни-
ков в полосе взаимно однозначно соответствует вектор (2).
Математичне та комп’ютерне моделювання
98
Вернемся к вопросу о значении величины n . Пусть длины пря-
моугольников 1,..., ta a упорядочены по неубыванию значений min
ia :
min min
1i ia a 1ti J . Из рассмотренных принципов размещения пря-
моугольников в полоске следует, что их максимальное количество n
в полоске может быть определено из условий
1
min max min max
1 1
, .
n n
i i
i i
a L a L
Так как прямоугольников нулевой длины, очевидно, не больше
1m n (в каждой полоске размещается по крайней мере один пря-
моугольник), введем в рассмотрение мультимножество
0 0 1 1
1
{ ,..., , ,..., } ,..., 1t n
m n
G g g m n t
a a a a ). Тогда вектор (2)
является упорядоченной k -выборкой ( k mn ) из мультимноже-
ства G , то есть элементом общего множества размещений kE G .
Таким образом, математическую модель сформулированной выше
задачи покрытия прямоугольной полосы прямоугольниками можно
записать так: найти пару * *,F x x такую, что
* *
1 1 1 1
min , arg min
k
k
m n m n
ij ij
x E G x E Gi j i j
F x M H x M H
x x
при условии (3) (здесь через M (ζ) обозначено математическое ожи-
дание случайной величины ζ).
Замечание 5. Как и задачу упаковки, задачу покрытия прямо-
угольниками можно рассматривать в случае, когда H является дис-
кретной случайной величиной. Тогда ширина полосок, на которые
разделяется заданная полоса, равна minH .
Замечание 6. Если размеры прямоугольников являются действи-
тельными числами, то рассмотренная математическая модель задачи
покрытия эквивалентна модели 2 из [12], в которой минимизируемым
критерием оптимальности является сумма «выступов» (величин
1
n
ijj
x L
) при условии, что прямоугольники расположены не только
без промежутков, но и без наложений. Действительно, при таком допус-
тимом расположении прямоугольников величину минимизируемого при
(3) на kE G F x можно представить следующим образом:
Серія: Фізико-математичні науки. Випуск 12
99
1
.
n
ij
j
F x HL Hx L
Это означает, что задача минимизации функции F x эквива-
лентна задачи минимизации суммы «выступов». Однако такой крите-
рий оптимальности нецелесообразен для определенного в данной
статье взаимного расположения прямоугольников, так как невозмож-
но выбрать такое расположение прямоугольников, чтобы при всех
возможных значениях стохастических параметров между ними не
было расстояний и в то же время прямоугольники не накладывались.
Замечание 7. Изложенный подход к формализации взаимного
расположения прямоугольников является новым. Авторам не извест-
на рассматриваемая реализация прямоугольников со стохастически-
ми параметрами. Для параметров с центрированными интервалами
этот подход отличается от работ Ю. Г. Стояна и его учеников (см.,
например, [14]). Для параметров с нечеткими числами предложенный
подход отличен от работ, обобщенных в [8]).
Выводы. Таким образом, в статье предложен подход к форма-
лизации взаимного размещения прямоугольников, которые на плос-
кости задаются параметрами с интервальной, нечеткой или стохасти-
ческой неопределенностью. На основе введенных понятий взаимного
размещения прямоугольников построены математические модели
задач упаковки прямоугольников и покрытия полосы прямоугольни-
ками для случая, когда длины прямоугольников являются конечно-
значными дискретными случайными величинами. Как направление
дальнейших исследований можно наметить разработку методов ре-
шения сформулированной задачи.
Список использованной литературы:
1. Сергиенко И. В. Модели и методы решения на ЭВМ комбинаторных за-
дач оптимизации / И. В. Сергиенко, М. Ф. Каспшицкая. — К. : Наук. дум-
ка, 1981. —288 с.
2. Cтоян Ю. Г. Теорія і методи евклідової комбінаторної оптимізації /
Ю. Г. Стоян, О. О. Ємець. — К. : Інститут системних досліджень освіти,
1993. — 188 с.
3. Барболина Т. Н. Решение частично комбинаторных задач оптимизации на
размещениях методом построения лексикографической эквивалентности /
Т. Н. Барболина // Кибернетика и системный анализ. — 2013. — № 6. —
С. 137–149.
4. Емец О. А. Решение линейных условных полностью комбинаторных оп-
тимизационных задач на перестановках методом ветвей и границ /
О. А. Емец, Е. М. Емец, Т. А. Парфёнова, Т. В. Чиликина // Кибернетика и
системный анализ. — 2013. — № 2. — С. 121–128.
Математичне та комп’ютерне моделювання
100
5. Емец О. А. О комбинаторной оптимизации в условиях неопределенности
/ О. А. Емец, А. А. Роскладка // Кибернетика и системный анализ. —
2008. — № 5. — С. 35–44.
6. Емец О. А. Решение задач оптимизации с дробно-линейными целевыми
функциями и дополнительными ограничениями / О. А. Емец, Т. Н. Бар-
болина, О. А. Черненко // Кибернетика и системный анализ. — 2006. —
№ 5. —С. 79–85.
7. Сергиенко И. В. Задачи оптимизации с интервальной неопределенно-
стью: метод ветвей и границ / И. В. Сергиенко, О. А. Емец, А. О. Емец //
Кибернетика и системный анализ. — 2013. — № 5. — С. 38–50.
8. Ємець О.О. Розв'язування задач комбінаторної оптимізації на нечітких мно-
жинах / О. О. Ємець, Ол-ра О. Ємець. — Полтава : ПУЕТ, 2011. — 239 с.
9. Ємець О. О. Формалізація взаємного розташування прямокутників з ви-
падковими параметрами / О. О. Ємець, Т. М. Барболіна // Problems of de-
cision making under uncertainties (PDMU-2014) : abstracts of XXIV Interna-
tional Conference, September 1-5, 2014, Cesky Rudolec, Czech Republic / Ta-
ras Shevchenko National University of Kyiv, University of Defence, Brno
etc. — К. : ТВіМС, 2014. — С. 124–125.
10. Ермольев Ю. М. Стохастические модели и методы в экономическом плани-
ровании / Ю. М. Ермольев, А. И. Ястремский. — М. : Наука, 1979. — 256 с.
11. Юдин Д. Б. Математические методы управления в условиях неполной
информации / Д. Б. Юдин.— М. : Сов. радио, 1974. — 400 с.
12. Ємець О. О. Комбінаторна задача покриття прямокутника прямокутника-
ми / О. О. Ємець, О. Ю. Галюкова // Матеріали ІІ Всеукраїнської науково-
практичної конференції «Інформатика та системні науки» ІСН-2011, 17-
19 березня 2011р. / за ред. д.ф.-м.н., проф. О. О. Ємця. — Полтава : РВВ
ПУЕТ, 2011. — С. 102–104.
13. Ємець О. О. Нечіткі прямокутники в задачі покриття / О. О. Ємець,
О. Ю. Галюкова // Інформаційні технології, системний аналіз і моделю-
вання соціоекологічних систем / Кафедра економічної кібернетики ФЕП
ІЕМ НАУ. — К. : Допомога, 2011. — С. 97–103.
14. Стоян Ю. Г. Комбинаторная оптимизационная задача размещения прямо-
угольников с учетом погрешностей исходных данных / Ю. Г. Стоян,
Т. Е. Романова, Л. Г. Евсеева // Доповіді НАН України. — 1997. —
№ 7. — С. 56–60.
Authors formalize mutual placement of rectangles with stochastic, in-
terval or fuzzy parameters for use in packing and covering problem state-
ments. The approach offered in the paper is based on determining of mu-
tual placement of their projections on the coordinate axes. We also con-
struct a combinatorial mathematical model of optimum rectangle packing
when data are discrete random variables.
Key words: combinatorial optimization, models of packing, parame-
ters under uncertainty, packing of rectangles.
Отримано: 26.03.2015
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /All
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (Coated FOGRA27 \050ISO 12647-2:2004\051)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Warning
/CompatibilityLevel 1.3
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.1000
/ColorConversionStrategy /sRGB
/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 false
/PreserveFlatness false
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
/Arial-Black
/Arial-BlackItalic
/Arial-BoldItalicMT
/Arial-BoldMT
/Arial-ItalicMT
/ArialMT
/ArialNarrow
/ArialNarrow-Bold
/ArialNarrow-BoldItalic
/ArialNarrow-Italic
/ArialUnicodeMS
/CenturyGothic
/CenturyGothic-Bold
/CenturyGothic-BoldItalic
/CenturyGothic-Italic
/CourierNewPS-BoldItalicMT
/CourierNewPS-BoldMT
/CourierNewPS-ItalicMT
/CourierNewPSMT
/Georgia
/Georgia-Bold
/Georgia-BoldItalic
/Georgia-Italic
/Impact
/LucidaConsole
/Tahoma
/Tahoma-Bold
/TimesNewRomanMT-ExtraBold
/TimesNewRomanPS-BoldItalicMT
/TimesNewRomanPS-BoldMT
/TimesNewRomanPS-ItalicMT
/TimesNewRomanPSMT
/Trebuchet-BoldItalic
/TrebuchetMS
/TrebuchetMS-Bold
/TrebuchetMS-Italic
/Verdana
/Verdana-Bold
/Verdana-BoldItalic
/Verdana-Italic
]
/AntiAliasColorImages false
/CropColorImages false
/ColorImageMinResolution 150
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 150
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/ColorImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/AntiAliasGrayImages false
/CropGrayImages false
/GrayImageMinResolution 150
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 150
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/GrayImageDict <<
/QFactor 0.76
/HSamples [2 1 1 2] /VSamples [2 1 1 2]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 15
>>
/AntiAliasMonoImages false
/CropMonoImages false
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects true
/CheckCompliance [
/PDFX1a:2001
]
/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 (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064506390020064506420627064A064A0633002006390631063600200648063706280627063906290020062706440648062B0627062606420020062706440645062A062F062706480644062900200641064A00200645062C062706440627062A002006270644062306390645062706440020062706440645062E062A064406410629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043f043e04340445043e0434044f044904380020043704300020043d043004340435043604340435043d0020043f044004350433043b04350434002004380020043f04350447043004420020043d04300020043104380437043d0435044100200434043e043a0443043c0435043d04420438002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e55464e1a65876863768467e5770b548c62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc666e901a554652d965874ef6768467e5770b548c52175370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002000760068006f0064006e00fd00630068002000700072006f002000730070006f006c00650068006c0069007600e90020007a006f006200720061007a006f007600e1006e00ed002000610020007400690073006b0020006f006200630068006f0064006e00ed0063006800200064006f006b0075006d0065006e0074016f002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000650067006e006500720020007300690067002000740069006c00200064006500740061006c006a006500720065007400200073006b00e60072006d007600690073006e0069006e00670020006f00670020007500640073006b007200690076006e0069006e006700200061006600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200075006d002000650069006e00650020007a0075007600650072006c00e40073007300690067006500200041006e007a006500690067006500200075006e00640020004100750073006700610062006500200076006f006e00200047006500730063006800e40066007400730064006f006b0075006d0065006e00740065006e0020007a0075002000650072007a00690065006c0065006e002e00200044006900650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000520065006100640065007200200035002e003000200075006e00640020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ENU (Use these settings to create Adobe PDF documents suitable for reliable viewing and printing of business documents. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f00620065002000500044004600200061006400650063007500610064006f007300200070006100720061002000760069007300750061006c0069007a00610063006900f3006e0020006500200069006d0070007200650073006900f3006e00200064006500200063006f006e006600690061006e007a006100200064006500200064006f00630075006d0065006e0074006f007300200063006f006d00650072006300690061006c00650073002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e400740074006500690064002000e4007200690064006f006b0075006d0065006e00740069006400650020007500730061006c006400750073007600e400e4007200730065006b0073002000760061006100740061006d006900730065006b00730020006a00610020007000720069006e00740069006d006900730065006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f006200650020005000440046002000700072006f00660065007300730069006f006e006e0065006c007300200066006900610062006c0065007300200070006f007500720020006c0061002000760069007300750061006c00690073006100740069006f006e0020006500740020006c00270069006d007000720065007300730069006f006e002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003b103be03b903cc03c003b903c303c403b7002003c003c103bf03b203bf03bb03ae002003ba03b103b9002003b503ba03c403cd03c003c903c303b7002003b503c003b903c703b503b903c103b703bc03b103c403b903ba03ce03bd002003b503b303b303c103ac03c603c903bd002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05d405e905ea05de05e905d5002005d105d405d205d305e805d505ea002005d005dc05d4002005db05d305d9002005dc05d905e605d505e8002005de05e105de05db05d9002000410064006f006200650020005000440046002005e205d105d505e8002005d405e605d205d4002005d505d405d305e405e105d4002005d005de05d905e005d4002005e905dc002005de05e105de05db05d905dd002005e205e105e705d905d905dd002e002005de05e105de05db05d90020005000440046002005e905e005d505e605e805d5002005e005d905ea05e005d905dd002005dc05e405ea05d905d705d4002005d105d005de05e605e205d505ea0020004100630072006f006200610074002005d5002d00410064006f00620065002000520065006100640065007200200035002e0030002005d505d205e805e105d005d505ea002005de05ea05e705d305de05d505ea002005d905d505ea05e8002e>
/HRV (Za stvaranje Adobe PDF dokumenata pogodnih za pouzdani prikaz i ispis poslovnih dokumenata koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF00410020006800690076006100740061006c006f007300200064006f006b0075006d0065006e00740075006d006f006b0020006d00650067006200ed007a00680061007400f30020006d0065006700740065006b0069006e007400e9007300e900720065002000e900730020006e0079006f006d00740061007400e1007300e10072006100200073007a00e1006e0074002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c00200068006f007a006800610074006a00610020006c00e9007400720065002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA (Utilizzare queste impostazioni per creare documenti Adobe PDF adatti per visualizzare e stampare documenti aziendali in modo affidabile. I documenti PDF creati possono essere aperti con Acrobat e Adobe Reader 5.0 e versioni successive.)
/JPN <FEFF30d330b830cd30b9658766f8306e8868793a304a3088307353705237306b90693057305f002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a3067306f30d530a930f330c8306e57cb30818fbc307f3092884c3044307e30593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020be44c988b2c8c2a40020bb38c11cb97c0020c548c815c801c73cb85c0020bcf4ace00020c778c1c4d558b2940020b3700020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b0075007200690065002000740069006e006b006100200070006100740069006b0069006d006100690020007000650072017e0069016b007201170074006900200069007200200073007000610075007300640069006e0074006900200076006500720073006c006f00200064006f006b0075006d0065006e007400750073002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020007000690065006d01130072006f00740069002000640072006f016100610069002000620069007a006e00650073006100200064006f006b0075006d0065006e007400750020006100700073006b006100740065006900200075006e0020006400720075006b010101610061006e00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken waarmee zakelijke documenten betrouwbaar kunnen worden weergegeven en afgedrukt. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d002000650072002000650067006e0065007400200066006f00720020007000e5006c006900740065006c006900670020007600690073006e0069006e00670020006f00670020007500740073006b007200690066007400200061007600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f0020006e00690065007a00610077006f0064006e00650067006f002000770079015b0077006900650074006c0061006e00690061002000690020006400720075006b006f00770061006e0069006100200064006f006b0075006d0065006e007400f300770020006600690072006d006f0077007900630068002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f00620065002000500044004600200061006400650071007500610064006f00730020007000610072006100200061002000760069007300750061006c0069007a006100e700e3006f002000650020006100200069006d0070007200650073007300e3006f00200063006f006e0066006900e1007600650069007300200064006500200064006f00630075006d0065006e0074006f007300200063006f006d0065007200630069006100690073002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e007400720075002000760069007a00750061006c0069007a00610072006500610020015f006900200074006900700103007200690072006500610020006c0061002000630061006c006900740061007400650020007300750070006500720069006f0061007201030020006100200064006f00630075006d0065006e00740065006c006f007200200064006500200061006600610063006500720069002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002000760068006f0064006e00fd006300680020006e0061002000730070006f013e00610068006c0069007600e90020007a006f006200720061007a006f00760061006e006900650020006100200074006c0061010d0020006f006200630068006f0064006e00fd0063006800200064006f006b0075006d0065006e0074006f0076002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020007000720069006d00650072006e006900680020007a00610020007a0061006e00650073006c006a00690076006f0020006f0067006c00650064006f00760061006e006a006500200069006e0020007400690073006b0061006e006a006500200070006f0073006c006f0076006e0069006800200064006f006b0075006d0065006e0074006f0076002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002c0020006a006f0074006b006100200073006f0070006900760061007400200079007200690074007900730061007300690061006b00690072006a006f006a0065006e0020006c0075006f00740065007400740061007600610061006e0020006e00e400790074007400e4006d0069007300650065006e0020006a0061002000740075006c006f007300740061006d0069007300650065006e002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d00200070006100730073006100720020006600f60072002000740069006c006c006600f60072006c00690074006c006900670020007600690073006e0069006e00670020006f006300680020007500740073006b007200690066007400650072002000610076002000610066006600e4007200730064006f006b0075006d0065006e0074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005400690063006100720069002000620065006c00670065006c006500720069006e0020006700fc00760065006e0069006c0069007200200062006900720020015f0065006b0069006c006400650020006700f6007200fc006e007400fc006c0065006e006d006500730069002000760065002000790061007a0064013100720131006c006d006100730131006e006100200075007900670075006e002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043d0430043404560439043d043e0433043e0020043f0435044004350433043b044f043404430020044204300020043404400443043a0443002004340456043b043e04320438044500200434043e043a0443043c0435043d044204560432002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043f043e04340445043e0434044f04490438044500200434043b044f0020043d0430043404350436043d043e0433043e0020043f0440043e0441043c043e044204400430002004380020043f04350447043004420438002004340435043b043e0432044b044500200434043e043a0443043c0435043d0442043e0432002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
>>
/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
>>
<<
/AllowImageBreaks true
/AllowTableBreaks true
/ExpandPage false
/HonorBaseURL true
/HonorRolloverEffect false
/IgnoreHTMLPageBreaks false
/IncludeHeaderFooter false
/MarginOffset [
0
0
0
0
]
/MetadataAuthor ()
/MetadataKeywords ()
/MetadataSubject ()
/MetadataTitle ()
/MetricPageSize [
0
0
]
/MetricUnit /inch
/MobileCompatible 0
/Namespace [
(Adobe)
(GoLive)
(8.0)
]
/OpenZoomToHTMLFontSize false
/PageOrientation /Portrait
/RemoveBackground false
/ShrinkContent true
/TreatColorsAs /MainMonitorColors
/UseEmbeddedProfiles false
/UseHTMLTitleAsMetadata true
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/BleedOffset [
0
0
0
0
]
/ConvertColors /ConvertToRGB
/DestinationProfileName (sRGB IEC61966-2.1)
/DestinationProfileSelector /UseName
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements true
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles true
/MarksOffset 6
/MarksWeight 0.250000
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PageMarksFile /RomanDefault
/PreserveEditing true
/UntaggedCMYKHandling /UseDocumentProfile
/UntaggedRGBHandling /LeaveUntagged
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [600 600]
/PageSize [419.528 595.276]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-133864 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2308-5878 |
| language | Russian |
| last_indexed | 2025-12-07T16:50:45Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Барболина, Т.Н. 2018-06-08T17:11:34Z 2018-06-08T17:11:34Z 2015 О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности / О.А. Емец, Т.Н. Барболина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2015. — Вип. 12. — С. 83-100. — Бібліогр.: 14 назв. — рос. 2308-5878 https://nasplib.isofts.kiev.ua/handle/123456789/133864 519.85 Для использования в постановках задач упаковки и покрытия формализовано взаимное расположение прямоугольников со стохастическими, интервальными или нечеткими параметрами. Предлагаемый подход основывается на установлении взаимного расположения отрезков, являющихся их проекциями на оси координат. Также построены комбинаторные математические модели оптимальной упаковки прямоугольников и покрытия прямоугольниками для случая, когда входные данные являются дискретными случайными величинами. Authors formalize mutual placement of rectangles with stochastic, interval or fuzzy parameters for use in packing and covering problem statements. The approach offered in the paper is based on determining of mutual placement of their projections on the coordinate axes. We also construct a combinatorial mathematical model of optimum rectangle packing when data are discrete random variables. ru Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности Article published earlier |
| spellingShingle | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности Емец, О.А. Барболина, Т.Н. |
| title | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности |
| title_full | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности |
| title_fullStr | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности |
| title_full_unstemmed | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности |
| title_short | О задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности |
| title_sort | о задачах оптимизации взаимного расположения прямоугольников в условиях стохастической, интервальной или нечеткой неопределенности |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/133864 |
| work_keys_str_mv | AT emecoa ozadačahoptimizaciivzaimnogoraspoloženiâprâmougolʹnikovvusloviâhstohastičeskoiintervalʹnoiilinečetkoineopredelennosti AT barbolinatn ozadačahoptimizaciivzaimnogoraspoloženiâprâmougolʹnikovvusloviâhstohastičeskoiintervalʹnoiilinečetkoineopredelennosti |