The method of software building the thickest grid packing
The math model and the method of defining the thickest packing for two kinds of flat geometrical objects, which have any outside contours configuration, is proposed in this work. The criteria of defining the thickest packing for two kinds of flat geometrical objects is defined.Problems in programmin...
Gespeichert in:
| Datum: | 2026 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2026
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/963 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| _version_ | 1866844989476044800 |
|---|---|
| author | Chuprynka, V.I. Chebanyuk, O.V. |
| author_facet | Chuprynka, V.I. Chebanyuk, O.V. |
| author_institution_txt_mv | [
{
"author": "V.I. Chuprynka",
"institution": "Kyiv National University of Technologies and Design"
},
{
"author": "O.V. Chebanyuk",
"institution": "Kyiv National University of Technologies and Design"
}
] |
| author_sort | Chuprynka, V.I. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2026-06-01T06:02:58Z |
| description | The math model and the method of defining the thickest packing for two kinds of flat geometrical objects, which have any outside contours configuration, is proposed in this work. The criteria of defining the thickest packing for two kinds of flat geometrical objects is defined.Problems in programming 2010; 2-3: 629-635 |
| first_indexed | 2026-06-02T01:01:59Z |
| format | Article |
| fulltext |
Прикладне програмне забезпечення
© В.І. Чупринка, О.В. Чебанюк, 2010
ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск 629
УДК 685.3
МЕТОД ПРОГРАМНОГО ПРОЕКТУВАННЯ
НАЙЩІЛЬНІШИХ РЕШІТЧАСТИХ УКЛАДОК
В.І. Чупринка, О.В. Чебанюк
Київський національний університет технологій і дизайну,
01011, Київ-11, вул. Немировича-Данченка, 2, тел. (044) 256 84 65,
bagire@i.ua
Запропоновані математична модель та метод визначення найщільнішої укладки для двох видів плоских геометричних об’єктів, що
мають довільну конфігурацію зовнішніх контурів. Визначений критерій існування щільних решітчастих укладок для двох видів
плоских геометричних об’єктів.
The math model and the method of defining the thickest packing for two kinds of flat geometrical objects, which have any outside contours
configuration, is proposed in this work. The criteria of defining the thickest packing for two kinds of flat geometrical objects is defined.
Вступ
Ефективність спроектованої розкрійної схеми визначає відсоток використання матеріалу. Важливим
показником, який впливає на відсоток використання матеріалу, є величина міжшаблонних відходів. Це
величина, яка дозволяє оцінити відходи, що утворюються за рахунок того, що плоскі геометричні об’єкти,
розташовані на розкрійній схемі поряд, не завжди щільно прилягають один до одного у всіх границях контурів
об’єктів ( ділянки сірого кольору на рис. 1).
Для оцінки міжшаблонних відходів розкрійних схемах решітчастого розміщення плоских геометричних
об’єктів визначаються не заповнені ділянки схеми, у паралелограмах, які побудовані на векторах решітки.
Традиційно розкрійні схеми будуються для плоских геометричних об’єктів, що мають однакову
конфігурацію зовнішніх контурів. Але, сумістивши плоскі геометричні об’єкти, які мають різні конфігурації
зовнішніх контурів, можна визначити такі варіанти їх положення на матеріалі при яких відсоток укладки буде
вищий, ніж при суміщенні однотипних деталей.
Відомі методи, наприклад [1], визначають найщільнішу укладку шляхом перебору множини
допустимих решіток, та вибору серед них тієї, яка забезпечує мінімальну площу паралелограма, який
побудований на її векторах. Такі алгоритми мають велику обчислювальну складність та не дають гарантії, що
знайдений розв’язок є найкращим.
Тому розробка методу аналітичного визначення найщільнішої укладки для плоских геометричних
об’єктів, що мають різні конфігурації зовнішніх контурів є актуальною задачею. Практичний аспект – це вибір
схеми, яка дозволяє мінімізувати величину міжлекальних відходів при проектуванні нової моделі певного
виробу.
У роботі запропонований метод пошуку найщільнішої укладки для двох видів плоских геометричних
об’єктів, що мають довільну (однакову або різну) конфігурацію зовнішніх контурів. Представлений метод
базується на математичній моделі визначення взаємного положення плоских геометричних об’єктів на
площині.
Решітчасті укладки
Розглянемо на площині два типи об’єктів S1 та S2, що мають довільну (однакову або різну)
конфігурацію зовнішніх контурів (рис. 1).
Рис. 1. Щільна укладка для двох видів плоских геометричних об’єктів
Прикладне програмне забезпечення
630
Позначимо intS=S –S^, де S^ – границя об’єкта S. Якщо виконуються умови:
intS1 intS2=0 та S1 S2 0, (1)
то об’єкти S1 та S2 називаються щільно розміщеними.
Щільно розміщені об’єкти не мають спільних внутрішніх точок, але обов’язково мають спільні
граничні точки.
Система об’єктів Si, i=1,..., p, утворює на площині укладку, якщо для кожної пари об’єктів із цієї
системи виконуються умови їх взаємного неперетину:
int Sn intSm=0, n,m=1,..., p, (2)
та для будь-якої пари об’єктів Si та Sq , i=1,..., p знайдеться хоча б один об’єкт, де q, i є[1,..., p], p≠і, який
дотикається до об’єкта Si.
Позначимо S+a об’єкт, який можна отримати переміщенням кожної точки об’єкта S на вектор a та
назвемо його трансляцією об’єкта S.
Множину векторів вигляду
r=na1+ma2, де n,m=0, 1, 2, 3,…, k…, (3)
де a1 1 1( , )x ya a , a2 2 2( , )x ya a – лінійно-незалежні вектори, назвемо решіткою з базисом a1, a2 та позначимо
= (a1,a2).
Множину векторів виду r1=na1+ma2 та r2=na1+ma2+g, де n,m=0, 1, 2, 3,…, k …, (4)
де a1, a2 – лінійно-незалежні вектори, назвемо подвійною решіткою з базисом a1, a2 і вектором зсуву решітки g
та позначимо W=W(a1,a2,g). Абсолютна величина визначника, який складений із базових векторів подвійної
решітки, називається визначником решітки та позначається det W.
Розглянемо систему об’єктів 1
.
nm
n m
S та 2
.
nm
n m
S , де n,m=0, 1, 2, 3,…, k…, які складаються із
трансляції S1
nm
=S1+na1+ma2 та S2
nm
=S2+na1+ma2+g, об’єктів S1 та S2 на вектори подвійної решітки
W=W(a1,a2, g). Якщо ця система є укладкою, то така укладка називається укладкою об’єктів S1 та S2, виконаної
за подвійною решіткою W=W(a1, a2, g). Подвійна решітка W=W(a1, a2, g) у цьому випадку є допустимою для
укладки об’єктів S1 та S2. Вона представляє собою дві однакові одинарні решітки 1= (a1,a2) та 2= (a1+g , a2+
+g), які зміщені одна щодо іншої на вектор зсуву решітки g. У вузлах решітки 1 розміщаються об’єкти S1,
а у вузлах решітки 2 – об’єкти S2.
Абсолютна величина визначника, який складений із векторів решітки, називається визначником решітки
W та позначається det W, де
det W =|[ a1 х a2 ]|=
1 1
1 2 2 1
2 2
.
x y
x y x y
x y
a a
a a a a
a a
(5)
Щільність s(W) решітчастої укладки можна характеризувати за допомогою співвідношення:
s(W)=( S1 + S2 ) /det W , (6)
де S1 та S2 – відповідно площі плоского геометричного об’єкта S1 та S2, det W – визначник решітки W=W(a1,
a2, g), за якою виконана укладка. З наведеного співвідношення видно, що щільність s(W) решітчастої укладки
тим вища, чим менша площа паралелограма, сторонами якого є базові вектори решітки a1 та a2.
Постановка задачі аналітичного визначення найщільнішої укладки
Математична постановка задач.
Є два плоскі геометричні об’єкти та , які мають різну або однакову конфігурацію зовнішніх
контурів, що розташовані на схемі під кутами α та β. Позначимо таке розташування 1( )S і 2 ( )S .
Серед множини всіх можливих подвійних решітчастих укладок 1 2( , , )W W a a g для плоских
геометричних об’єктів 1( )S і 2 ( )S із щільністю укладки ( )S W знайти таку * * * *
1 2( , , )W W a a g , в якій
щільність *( )S W подвійної укладки многокутників 1( )S та 2 ( )S (рис. 2), виконаної за цією решіткою
задовольняла би співвідношенню:
1 2 1 2 1 2 1 2*
1 2 1 2 1 2
( ) max ( ) max max max max .
det
S S
W W W W W
ABCD x y y x
S S S S S S S S
W W
S W a a a a a a
(7)
У даному випадку 1 1 1{ , },x ya AD a a 2 2 2{ , },x ya AB a a { , }x yg AE g g , 1S та 2S – площі
плоских геометричних об’єктів.
Прикладне програмне забезпечення
631
1
a
2a
g
1
a
2a
g
Рис. 2. Приклади щільних укладок
Технологічна постановка задачі.
Серед множини щільних укладок для двох плоских геометричних об’єктів та , що мають довільну
конфігурацію зовнішніх контурів, обрати таку, яка задовольняє співвідношенню (7), врахувавши технологічні
вимоги та обмеження. Такі вимоги можуть накладатися головним напрямком анізотропії плоских геометричних
об’єктів чи матеріалу або необхідною величиною міжшаблонного містка. Тоді множина всіх можливих решіток
визначається з урахуванням тільки тих варіантів положень плоских геометричних об’єктів, які допускаються
технологічними обмеженнями.
Математична модель задачі проектування найщільнішої решітчастої укладки
У задачі побудови найщільнішої решітчастої укладки можна виділити наступні структурні компоненти:
аналітичне представлення інформації про зовнішні контури розміщуваних плоских геометричних об’єктів;
параметри, що визначають положення плоских геометричних об’єктів на площині;
аналітичний опис умов взаємного неперетину плоских геометричних об’єктів в укладці;
аналітичний опис системи суміщення плоских геометричних об’єктів в укладці;
математичний опис множини допустимих розв’язків задачі;
аналітичне представлення функції цілі.
Далі наведемо опис кожного з виділених компонентів.
Аналітичний опис зовнішнього контуру плоского геометричного об’єкта та його положення на площині.
Для представлення плоского геометричного об’єкта на площині слід обрати спосіб, який не накладає
обмежень на складність конфігурації зовнішнього контуру об’єкта та дозволяє однозначно відобразити його
положення на площині. Цим вимогам задовольняє метод кусково-лінійної апроксимації. Тоді плоский
геометричний об’єкт S представляється на площині, замкнений багатокутником Sm, вершини якого
сполучаються відрізками. Для однозначного визначення зовнішнього контуру багатокутника Sm достатньо
знати координати вершин Аі(Xi,Yi), де і = 1, 2,..., n та X1= Xn, Y1=Yn (рис. 3).
Тоді координати будь-якої точки Q(xq ,yq) на стороні Аі Аі+1 зовнішнього контуру апроксимуючого
багатокутника можна представити наступним чином [3]:
1
1
( )
( )
i i i i
i i i i
xq X X t X
yq Y Y t Y
, де і=1, 2,..., n – 1 та [0,1].it (8)
Рис. 3. Представлення деталі за допомогою кусково-лінійної апроксимації на площині
Прикладне програмне забезпечення
632
Параметри, які визначають положення плоских геометричних об’єктів на площині. Для одно-
значного відображення положення плоского геометричного об’єкта S на площині необхідно знати тип деталі,
координати полюсу плоского геометричного об’єкта (Xpk, Ypk) в системі координат XOY, що пов’язана з
площиною, та кут повороту плоского геометричного об’єкта щодо його вихідного положення θk (рис. 4).
Тоді координати будь-якої вершини Aik(і=1, 2,..., n) апроксимуючого багатокутника для плоского
геометричного об’єкта S в системі координат XOY, що пов’язана із площиною, визначатимуться таким чином :
cos sin ,
sin cos .
k k
i i k i k
k k
i i k i k
X X Y Xp
Y X Y Yp
(9)
Координати будь-якої точки Qk(xq
k
,yq
k
) на стороні АіАі+1 зовнішнього контуру апроксимуючого
багатокутника в системі координат XOY, що пов’язана із площиною XOY, можна представити таким чином:
1
1
( )
( )
k k k
i i i i
k k k
i i i i
xq X X t X
yq Y Y t Y
, де і = 1, 2,..., n–1 та [0,1]it . (10)
Тобто, за допомогою виразів (9 – 10), можна однозначно аналітично описати зовнішній контур плоского
геометричного об’єкта в щільній укладці на площині.
Аналітичний опис умов взаємного неперетину плоских геометричних об’єктів. Нехай S1 та S2 – два
об’єкти, які зберігають постійну взаємну орієнтацію. Позначимо О1 та О2 полюси об’єктів, які вибрані в
довільних точках даних об’єктів. Тоді X1O1Y1 та X2O2Y2 – системи координат, які жорстко зв’язані з об’єктами
S1 та S2 відповідно. Без обмеження відповідні координатні осі можна вважати направленими однаково.
Припустимо, що об’єкт S1 нерухомо закріплений на площині, а об’єкт S2 – рухомий. Розглянемо множину
можливих щільних положень об’єкта S2 щодо об’єкта S1. Кожне таке положення характеризується вектором r12
= О1О2. Вектор-функція, що ставить у відповідність щільному положенню об’єктів S1 та S2 значення вектора
r12 за умови, що об’єкт S1 нерухомий, називається годографом вектор-функції Г12 щільного розміщення (рис. 5)
об’єкта S2 щодо об’єкта S1 [2].
Нехай θ – кут, який утворює вектор r12 з віссю O1X1. Тоді вектор-функція щільного розміщення об’єкта
S2 щодо об’єкта S1 може бути задана у вигляді r= r12(θ), де 0≤ θ≤2π .
Позначимо Ф12 область, яка обмежена годографом Г12. Зазначимо найбільш важливі властивості
годографа Г12 вектор-функції щільного розміщення та області Ф12, яка обмежена ним (рис. 5):
- якщо полюс O2 об’єкта S2 розміщений на границі області Ф12, то об’єкти S1 та S2 мають спільні
граничні точки, тобто є щільно розміщеними (рис. 5, а);
- якщо полюс O2 об’єкта S2 розміщений зовні області Ф12, об’єкти S1 та S2 не мають спільних внутрішніх
точок, тобто не перетинаються (рис. 5, б);
- якщо полюс O2 об’єкта S2 розміщений всередині області Ф12, то об’єкти S1 та S2 мають спільні
внутрішні точки, тобто перетинаються (рис. 5, в).
Крім того, годограф вектор-функції щільного розміщення (ГВФЩР) об’єкта S2
щодо об’єкта S1
представляє собою замкнуту лінію та ГВФЩР для багатокутників є також багатокутник з числом вершин не
більшим, ніж сума кількості вершин багатокутників, для яких був побудований ГВФЩР.
),( k
i
k
i
k
i YXA
),( kkk YpXpO
X
Xk
О
Yk Y
k
Рис. 4. Параметри, що однозначно визначають положення
плоского геометричного об’єкта S на площині
S
Прикладне програмне забезпечення
633
Годограф Г12 двох однакових і однаково орієнтованих фігур має центральну симетрію.
Так як плоскі геометричні об’єкти S1 та S2 апроксимуються багатокутниками Sm1 та Sm2, то ГВФЩР для
плоских геометричних об’єктів буде багатокутник G з координатами вершин Gi(Xgi,Ygi), i = 1, 2,..., ng.
Тоді координати будь-якої точки на ГВФЩР можна представити наступним чином:
1
1
( )
( )
i i i i
i i i i
xg Xg Xg Xg
yg Yg Yg Yg
, де i = 1, 2,.., ng та [0,1]i . (11)
Тобто, використовуючи апарат ГВФЩР, є можливість контролювати взаємне розміщення плоских
геометричних об’єктів в укладці. Якщо полюси плоских геометричних об’єктів будуть знаходитися на
ГВФЩР, то плоскі геометричні об’єкти будуть дотикатись. Крім того апарат ГВФЩР дозволяє аналітично
представити умови взаємного неперетину плоских геометричних об’єктів, що розміщуються на площині.
Математичний опис множини допустимих розв’язків задачі проектування найщільнішої
решітчастої укладки. Розглянемо множини допустимих розв’язків для задачі побудови найщільнішої
решітчастої укладки плоских геометричних об’єктів виду S1 та S2 (плоскі геометричні об’єкти S1 повернуті до
рядка на кут α та плоскі геометричні об’єкти S2 повернуті до рядка на кут β щодо їх основного положення).
Сформуємо умову розв’язку задачі. Для цього побудуємо ГВФЩР r= r11(θ) для плоского геометричного
об’єкту S1 самого з собою та ГВФЩР r= r22(θ) для плоского геометричного об’єкта S2 самого з собою.
Знайдемо min_r11, min_r22, max_r11, max_r22 для яких виконуються наступні нерівності [4]:
min_r11≤| r11(θ)| ≤max_r11 та min_r22≤| r22(θ)|≤ max_r22.
Якщо
( min_r11≤ |r11(θ)| ≤max_r11 ) ( min_r22≤ |r22(θ)|≤ max_r22) ¢, (12)
Побудуємо ряд щільних укладок для деталей S1 та S2 ( рис. 6).
Пряма, що проходить через точки Oi та Oi+1 розділяє площину на дві півплощини. Позначимо p – як
множину векторів що сполучають полюси деталей першого типу та будь-яку точку на годографі Г12,
координати якої задовольняють умові: 0Ax By c , де A = Ya1, B = –Xa1, C = 0; q – як множину векторів, що
сполучають полюси деталей першого типу, які також знаходяться у середньому рядку, та задовольняють умові
0Ax By c . Тобто, множина векторів p та q знаходяться по різні боки від прямої, що сполучає полюси
деталей першого типу в середньому рядку укладки.
Позначимо криві, на яких можуть знаходитися кінці векторів p
i
та q
i
, Pu та Pd (рис. 6). Ці криві
періодичні, з періодом рівним довжині вектора a
і
1, тобто А1А2=2А3=А3А4=А4А5=В1В2=В2В3=В3В4=В4В5=О1О2=
=О2О3 =О3О4=|a
і
1|. Тому для області допустимих значень для векторів p
i
та g
i
достатньо обмежитись одним
періодом.
а б в
Рис. 5. Визначення взаємного положення двох деталей за допомогою ГВФЩР
Прикладне програмне забезпечення
634
Область допустимих значень для векторів a
і
1, p
i
та q
i
однозначно визначає множину допустимих
подвійних решіток W
і
=W(a
і
1, a
і
2, g
i
) , де і = 1, 2,..., q, тобто область допустимих розв’язків задачі укладки
плоских геометричних об’єктів виду S1 та S2.
Аналітичне представлення функції цілі для задачі проектування найщільнішої решітчастої
укладки. Так як математичною моделлю задачі проектування найщільнішої решітчастої укладки є подвійна
решітка, то щільність s(W) решітчастої укладки можна характеризувати за допомогою співвідношення ( 6).
Площі S1 та S2 плоских геометричних об’єктів S1 та S2 у цьому співвідношенні величини постійні, тому
щільність s(W) решітчастої укладки буде визначатись детермінантом решітки, значення якого дорівнює площі
паралелограма, сторонами якого є вектори решітки a1 та a2. Тоді з виразу (6) очевидно, що щільність s(W)
решітчастої укладки буде тим вища, чим менша площа цього паралелограма (5). Тобто цільовою функцією буде
детермінант det W подвійної решітки W.
Так як ми отримали аналітичний вигляд ГВФЩР Г11 та Г12, та векторів a1=f1(r11(θ)) та a2=f2(r12(θ)), то
знайдемо аналітичні вирази для векторів решітки a1 та a2. Використовуючи параметричне представлення
рівняння прямої, ГВФЩР Г11 та Г12 описуються наступним чином:
Г11:
11 11 11 11
1
11 11 11 11
1
( )
( )
i i i i
i i i i
xg Xg Xg t Xg
yg Yg Yg t Yg
, де
111,2,..., gi n та [0,1]it , (13)
Г12:
12 12 12 12
1
12 12 12 12
1
( )
( )
i i j i
i i j i
xg Xg Xg t Xg
yg Yg Yg t Yg
, де
121,2,..., gj n та [0,1]i . (14)
Тоді, множину векторів a1, що сполучають дві точки годографа Г11 можна представити наступним
чином:
a1:
11 11 11
1 1
11 11 11
1 1
( )
( )
a i i i i
a i i i i
x Xg Xg Xg
y Yg Yg Yg
, де
111,2,..., gi n та [0,1]it . (15)
При визначенні найщільнішої укладки для кожного варіанта вектора а1 визначаються всі можливі
варіанти векторів p та g, які теж можна представити у вигляді:
p:
12 12 12
1
12 12 12
1
( )
( )
p j j j j
p j i j j
x Xg Xg Xg
y Yg Yg Yg
, де
121,2,..., gj n та [0,1]j , (16)
q:
12 12 12
1
12 12 12
1
( )
( )
p k k k k
p k k k k
x Xg Xg Xg
y Yg Yg Yg
, де
121,2,..., gk n та [0,1]k . (17)
Рис. 6. Області значень векторів p
i
та q
i
для задачі укладки
O1
O2 O3
O4 B1
B2
B3
B4
B5
A1 A2
A3
A4
A5
Pu
Pd
Г12
Ф12
pi
qi
ai
1
ai
1
ai
2
ai
2
Прикладне програмне забезпечення
635
Різниця цих векторів визначає вектор а2. Звідси, функція цілі матиме наступний вигляд:
det W =|[ a1 х a2 ]|=
1 1 1 1
2 2
x y x y
x y p g p g
a a a a
a a x x y y
1 1 1 1 1 1( ) ( ) ( , , , , , )x p g p g y x p x g p y g y i j ka y y x x a a y a y x a x a F t i j k
( ) ,ij i j ik i k ij ik i ij j ik k ijkA t B t C D t E F L (18)
де
11 11 12 12 11 11 12 12
1 1 1 1
11 11 12 12 11 11 12 12
1 1 1 1
12 11 11 12 11 11
1 1
12 11 1
1
( )( ) ( )( ),
( )( ) ( )( ),
( ) ( ),
(
ij i i j j i i j j
ik i i k k i i k k
ij j i i j i i
ik k i i
A Xg Xg Yg Yg Yg Yg Xg Xg
B Yg Yg Xg Xg Xg Xg Yg Yg
C Xg Yg Yg Yg Xg Xg
D Yg Xg Xg 1 12 11 11
1
11 12 12 11 12 12
1 1
11 12 12 11 12 12
1 1
11 12 11 12 11 12 11 12
) ( ),
( ) ( ),
( ) ( ),
.
k i i
ij i j j i j j
ij i k k i k k
ijk i j i k i k i j
Xg Yg Yg
E Yg Xg Xg Xg Yg Yg
F Xg Yg Yg Yg Xg Xg
L Xg Yg Yg Xg Xg Yg Yg Xg
(19)
Як видно з рівнянь (18–19) функція цілі det W є лінійна функція від кожної із трьох змінних [0,1]it ,
[0,1]j , [0,1]k при фіксованих інших двох інших змінних та трьох дискретних параметрів
i, j, k (
111,2... gi n ,
121,2... gj n ,
121,2,..., gk n ) та має вигляд:
detW= ( , , , , , )i j kF t i j k ( )ij i j ik i k ij ik i ij j ik k ijkA t B t C D t E F L . (20)
Тоді локальний екстремум цієї функції може бути тільки на граничних значеннях змінних, тобто
0
;
1
it
0
;
1
j
0
.
1
k (21)
Таким чином, нам не потрібно перебирати всі значення для змінних [0,1]it , [0,1]j , [0,1]k , а
тільки ті випадки, де досягається локальний екстремум для функції цілі (20), серед яких вибираємо мінімальне
значення як розв’язок оптимізаційної задачі побудови найщільніших укладок. Проведені дослідження функції
цілі дозволили вказати теоретично обґрунтований метод пошуку екстремуму функції цілі в області допустимих
значень. Мінімізуючи функцію цілі (площу паралелограма А1D1C1D1 (А2D2C2D2)), мінімізуємо міжлекальні
відходи (pис. 1).
Висновки
Запропоновані математична модель та метод визначення найщільнішої укладки для двох видів деталей,
що мають довільну, тобто однакову або різну конфігурацію зовнішніх контурів. Аналіз функції цілі дозволив
представити ефективний теоретично обґрунтований метод пошуку екстремуму функції цілі в області
допустимих значень. Отриманий критерій існування щільних решітчастих укладок для двох видів плоских
геометричних об’єктів з однаковою або різною конфігурацією зовнішнього контуру. Обґрунтовано, що
найщільнішу укладку можна визначити, розглядаючи тільки випадки, коли кінці вектора 2a знаходяться на
вершинах годографа. Запропонований метод не має недоліків раніше використовуваних методів визначення
щільності укладок, які дозволяли одержати найщільнішу укладку тільки шляхом перебору всієї множини
можливих решіток. Ще одним недоліком, усунутим у розробленому методі є те, що в попередньо розроблених
методах кількість решіток визначалася умовами, які дозволяли отримати тільки певну кількість з усієї множини
решіток. Оптимальна решітка визначалася з тієї підмножини. Умови формування функції цілі у представленому
в роботі алгоритмі дозволяють визначити найщільнішу укладку з усієї множини допустимих решіток.
1. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. – Киев: Наук. думка, 1976. – 242 с.
2. Стоян Ю.Г. Размещение геометрических объектов. – Киев: Наук. думка. – 1975. – 175 с.
3. Чебанюк О.В., Чупринка В.І. Методика автоматичної п обудови розкрійних схем для двох видів плоских геометричних об’єктів //
Проблеми програмування. – 2008. – № 2–3. – C. 730–734.
4. Чупринка В.І., Чебанюк О.В. Алгоритм побудови щільних укладок для двох видів плоских геометричних об’єктів // Вісник КНУТД. –
2007. – № 6. – C. 107–112.
|
| id | pp_isofts_kiev_ua-article-963 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-02T01:01:59Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/db/f0413b9e8ec96fe18386e4acf12a57db.pdf |
| spelling | pp_isofts_kiev_ua-article-9632026-06-01T06:02:58Z The method of software building the thickest grid packing Метод програмного проектування найщільніших решітчастих укладок Chuprynka, V.I. Chebanyuk, O.V. UDC 685.3 УДК 685.3 The math model and the method of defining the thickest packing for two kinds of flat geometrical objects, which have any outside contours configuration, is proposed in this work. The criteria of defining the thickest packing for two kinds of flat geometrical objects is defined.Problems in programming 2010; 2-3: 629-635 Запропоновані математична модель та метод визначення найщільнішої укладки для двох видів плоских геометричних об’єктів, що мають довільну конфігурацію зовнішніх контурів. Визначений критерій існування щільних решітчастих укладок для двох видів плоских геометричних об’єктів.Problems in programming 2010; 2-3: 629-635 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-06-01 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/963 PROBLEMS IN PROGRAMMING; No 2-3 (2010); 629-635 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2010); 629-635 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2010); 629-635 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/963/1031 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | UDC 685.3 Chuprynka, V.I. Chebanyuk, O.V. The method of software building the thickest grid packing |
| title | The method of software building the thickest grid packing |
| title_alt | Метод програмного проектування найщільніших решітчастих укладок |
| title_full | The method of software building the thickest grid packing |
| title_fullStr | The method of software building the thickest grid packing |
| title_full_unstemmed | The method of software building the thickest grid packing |
| title_short | The method of software building the thickest grid packing |
| title_sort | method of software building the thickest grid packing |
| topic | UDC 685.3 |
| topic_facet | UDC 685.3 УДК 685.3 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/963 |
| work_keys_str_mv | AT chuprynkavi themethodofsoftwarebuildingthethickestgridpacking AT chebanyukov themethodofsoftwarebuildingthethickestgridpacking AT chuprynkavi metodprogramnogoproektuvannânajŝílʹníšihrešítčastihukladok AT chebanyukov metodprogramnogoproektuvannânajŝílʹníšihrešítčastihukladok AT chuprynkavi methodofsoftwarebuildingthethickestgridpacking AT chebanyukov methodofsoftwarebuildingthethickestgridpacking |