Для тривимірних многовидів зі структурою комбінаторного кліткового комплексу побудовано інваріант, який дозволяє перевіряти існування ізоморфізмів між ними. Для комплексів малої вимірності розв'язано задачу про можливість продовження ізоморфізмів підкомплексів до ізоморфізмів комплексів.

З використанням елементів інтервальної геометрії побудовано математичну модель задачі розміщення кольорових прямокутників у смузі, яка має зони, з урахуванням похибок початкових даних.

Розроблено дискретну модель укладання зерен довільних форм у тривимірні тіла. Шар сипучого матеріалу і зерна описано тривимірними множинами ознак заповнювання елементарних порожнин. За перетинання множин шару і зерна, розраховуються його координати (X, Y, Z) і орієнтація в просторі (кути нутації, прецесії і чистого обертання).

Разработана дискретная модель укладки зерен произвольных форм в трехмерные тела. Слой сыпучего материала и зерна описаны трехмерными множествами признаков заполненности элементарных пространств. При пересечении множеств слоя и зерна рассчитываются его координаты (X, Y, Z) и ориентация в пространстве (углы нутации, прецессии и чистого вращения).

The discrete model of a layer of a loose material from grains of the any forms and sizes for the first time is developed. In a basis of model the new method of the description of grains and layer using three-dimensional sets for the indication of employment of elementary space is fixed. The developed model of a layer includes the module of the description of distribution granulometric of structure for grains of each form; the module of accommodation of grains in a layer; the module of definition of parameters of a layer. Layer of a loose material and grain is broken into set of identical cubic elementary volumes. Thus, volume represent by a three-dimensional file describing the contents in each elementary volume of a share of a particle. At accommodation of a particle in a layer the crossing with the earlier stacked particles is checked. The check is carried out by comparison of attributes of employment of spaces. The optimum arrangement of a particle in a layer is defined by moving it in view of all degrees of freedom so that to achieve maximal density of packing of grains. After stacking particles in a layer its gas-dynamic parameters are determined. The results of research of model have shown its reliability.

Наведено загальну характеристику оптимізаційних задач розміщення геометричних об'єктів, розглянуто методи пошуку екстремумів функцій мети, розкрито суть багатоекстремальних комбінаторних задач. Описано існуючі методи розв'язання задач розміщення прямокутних об'єктів, які визначені на множині перестановок.

Приведена общая характеристика оптимизационных задач размещения геометрических объектов, рассмотрены методы поиска экстремумов функций цели, раскрыта сущность многоэкстремальных комбинаторных задач. Описаны существующие методы решения задач размещения прямоугольных объектов, определенные на множестве перестановок.

Ключ. слова: задача покрытия, интервальное пространство, интервальные функции
Індекс рубрикатора НБУВ: В181.25

Рубрики:

Комбінаторна геометрія

Шифр НБУВ: Ж16851 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В181.25

Рубрики:

Комбінаторна геометрія

Шифр НБУВ: Ж14648 Пошук видання у каталогах НБУВ 

Построены некоторые виды отображений комбинаторных интервальных множеств, моделирующих область допустимых решений комбинаторных задач геометрического проектирования с учетом погрешностей исходных данных в евклидово пространство. Предлагаемый подход рассмотрен на примере задачи оптимизации на множестве перестановок элементов пространства центрированных интервалов.

Розглянуто задачу розміщення об'єктів прямокутної форми в заданий прямокутник. Для розв'язку запропоновано використовувати генетичні алгоритми. Наведено деталі реалізації такого підходу. На прикладах показано високу ефективність даного методу.

It is proved that the optimal dense double lattice packing of two centrally symmetric polygons falls into three types. A finite number of non-overlapping conditions is found to be sufficient to determine the admissible solution region. A significantly more concise mathematical model as compared to its straightforward statement is built.

Зазначено, що для розробки ефективних методів розв'язку 3D задач пакування необхідний аналітичний опис взаємодій (перетин, дотик, неперетин, розташування на заданій відстані) двох довільних 3D об'єктів. З цією метою використовується концепція Ф-функцій. Побудовано Ф-функції для кожної пари базових об'єктів, що мають границю: сфера, паралелепіпед, циліндр, конус.

Ключ. слова: phi-функция, задачи покрытия
Індекс рубрикатора НБУВ: В181.25

Рубрики:

Комбінаторна геометрія

Шифр НБУВ: Ж70474 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.112.1 + В181.25

Рубрики:

Комбінаторне програмування

Комбінаторна геометрія

Шифр НБУВ: Ж15477 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.112.1 + В181.25

Рубрики:

Комбінаторне програмування

Комбінаторна геометрія

Шифр НБУВ: Ж15477 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.112.1 + В181.25

Рубрики:

Комбінаторне програмування

Комбінаторна геометрія

Шифр НБУВ: Ж15477 Пошук видання у каталогах НБУВ 

  Скачати повний текст

Досліджено задачі оптимального розміщення геометричних об'єктів, кожен з яких можна розбити на прямокутники (паралелепіпеди). За цього область розміщення - опукла з зонами заборони, функція цілі - неперервно диференційована або функція максимуму неперервно диференційованих функцій. З використанням декомпозиції множини припустимих розв'язків на опуклі підмножини розв'язано підзадачі на одержаних підмножинах. Розроблено модифікований метод можливих напрямків. Для організації вибору підзадач наведено метод гілок та меж, здійснено модифікацію генетичного алгоритму у комбінації за методом спрямованого переходу, а також використано метод випадкового пошуку у комбінації за методом спрямованого переходу. Запропоновані методи програмно реалізовані, експериментально перевірено їх ефективність для задач оптимізації розміщення.

Розглянуто оптимізаційну задачу розміщення набору опуклих орієнтованих багатогранників у паралелепіпеді з заданими розмірами, мінімізацією висоти зайнятої частини паралелепіпеда. Для реалізації умов взаємного неперетину опуклих багатогранників розроблено метод побудови поверхні 0-рівня Ф-функції двох довільних опуклих багатогранників, який дозволяє послідовно формувати грані цієї поверхні. Розроблено теоретичний підхід для пошуку наближеного розв'язку поставленої задачі для великої кількості об'єктів, що грунтується на методі оптимізації за групами змінних. Зазначено, що отримані розв'язки можна використовувати як початкові припустимі точки під час реалізації точних методів для розв'язання поставленої задачі. Наведено відповідне алгоритмічне та програмне забезпечення, придатне для розв'язання практичних задач, пов'язаних з моделюванням розміщення тривимірних геометричних об'єктів.

Досліджено задачу розміщення геометричних об'єктів прямокутної форми. Для розв'язання даної задачі розроблено нові ефективні методи. Під час побудови її математичної моделі використано подання неопуклої множини припустимих розв'язків задачі у вигляді об'єднання опуклих підмножин. Доведено можливість заміни розв'язання вихідної задачі розв'язанням ряду побудованих підзадач. Обгрунтовано можливість використання методу Розена для розв'язання побудованих підзадач оптимізації. Доведено теорему про часову складність ітерації методу Розена. Надано статистичну оцінку часової складності розв'язання обраної підзадачі оптимізації методом Розена. Розроблено метод G-проекції розв'язання побудованих підзадач оптимізації. Доведено теорему про збіжність методу G-проекції до стаціонарної точки. Доведено теорему про часову складність ітерації методу G-проекції. Надано статистичну оцінку часової складності розв'язання обраної підзадачі оптимізації методом G-проекції. Для розв'язання вихідної задачі оптимізації розроблено метод спрямованого перебору підзадач оптимізації. Надано статистичну оцінку часової складності розв'язання задачі оптимізації методом спрямованого перебору. Розроблено програмне забезпечення для реалізації побудованих методів.

  Скачати повний текст

Побудовано математичну модель задачі розміщення різних циліндрів і паралелепіпедів у призмі з урахуванням мінімально припустимих відстаней і зон заборони. Запропоновано математичну модель задачі розміщення однакових циліндрів у призмі з урахуванням зон заборони. Розроблено модифікацію методу гілок і меж, яка полягає у побудові спеціального дерева розв'язків. Здійснено модифікацію методу околів, що звужуються, для розв'язання задачі розміщення однакових циліндрів у призмі з урахуванням зон заборони. Модифіковано метод околів, що звужуються, для розв'язання задачі розміщення різних циліндрів і паралелепіпедів у призмі з урахуванням мінімально припустимих відстаней і зон заборони. Запропоновано єдиний підхід до розв'язання задач оптимізаційного геометричного проектування, який полягає у комбінації методу пошуку початкових наближень до локальних екстремумів, модифікованого методу околів, що звужуються, та модифікованого методу можливих напрямків.