Математичне моделювання розміщення опуклих n-вимірних політопів у n-вимірному паралелепіпеді

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут проблем машинобудування ім. А.М. Підгорного

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

01.05.02 - математичне моделювання та обчислювальні методи

Математичне моделювання розміщення опуклих n-вимірних політопів у n-вимірному паралелепіпеді

Софронова марина сергіївна

Харків-2007

Дисертацією є рукопис.

Робота виконана в Інституті проблем машинобудування ім. А.М. Підгорного НАН України.

Науковий керівник: доктор технічних наук, старший науковий співробітник Гіль Микола Іванович, Інститут проблем машинобудування ім. А.М. Підгорного НАН України (м. Харків), провідний науковий співробітник.

Офіційні опоненти: доктор фізико-математичних наук, професор Новожилова

Марина Володимирівна, Харківський державний технічний університет будівництва і архітектури, завідувач кафедри комп'ютерного моделювання та інформаційних технологій;

кандидат фізико-математичних наук, доцент Яремчук Світлана Іванівна, Житомирський державний технологічний університет, доцент кафедри програмного забезпечення обчислювальної техніки.

Провідна установа: Дніпропетровський національний університет, кафедра математики та математичної кібернетики, МОН України, м. Дніпропетровськ.

Учений секретар спеціалізованої вченої ради, доктор технічних наук О.О. Стрельнікова

Анотація

Софронова М.С. Математичне моделювання розміщення опуклих n-вимірних політопів у n-вимірному паралелепіпеді. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків, 2007.

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

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

Ключові слова: математичне моделювання, оптимізація, розміщення, Ф-функція, n-вимірний паралелепіпед, n-вимірний політоп, опукла оболонка.

Аннотация

Софронова М.С. Математическое моделирование размещения выпуклых n-мерных политопов в n-мерном параллелепипеде. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт проблем машиностроения им. А.Н. Подгорного НАН Украины, Харьков, 2007.

Диссертационная работа посвящена созданию конструктивных средств математического моделирования, построению математических моделей и разработке методов приближенного решения оптимизационных задач размещения n-мерных (n>3) параллелепипедов (n-параллелепипедов) в области, имеющей форму n-параллелепипеда, с различными критериями качества, а также задачи размещения выпуклых многогранных n-мерных объектов (n-политопов) в области, имеющей форму n-параллелепипеда.

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

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

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

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

Разработано алгоритмическое и программное обеспечение для решения задач размещения n-параллелепипедов и n-политопов. Приведены результаты вычислительных экспериментов размещения до 200 n-параллелепипедов и до 50 n-политопов в областях пространства . Осуществлен анализ и сравнение полученных результатов.

Ключевые слова: математическое моделирование, оптимизация, размещение, Ф-функция, n-мерный параллелепипед, n-мерный политоп, выпуклая оболочка.

Abstract

Sofronova M.S. Mathematical modeling of the placement of convex n-dimensional polytopes in an n-dimensional parallelepiped. - Manuscript.

Dissertation for the scientific degree of Candidate of Physical-Mathematical Sciences in the speciality 01.05.02 - mathematical modeling and computational methods. - A.M. Pidgorny Institute in Machinery NAS of Ukraine, Kharkiv, 2007.

The dissertation deals with developing design tools for mathematical modeling, building mathematical models and developing methods for approximate solution of optimization problems in placement of n-dimensional (n>3) parallelepipeds (n-parallelepipeds) in a domain in the form of an n-parallelepiped with different quality criteria, as well as the problem of placing convex polyhedral n-dimensional objects (n-polytopes) in a domain in the form of an n-parallelepiped.

Based on the proved theorems, for the first time there were built Ф-functions of n-parallelepipeds and n-polytopes that, for the multidimensional objects considered, allow formalizing the conditions of their mutual nonintersecting and the conditions of their placement in the domain. The representation of the mathematical model of the problem of placement of n-parallelepipeds in an n-parallelepiped with the variable metric characteristics was further developed. The respective models for the problem of placement of n-parallelepipeds in an n-parallelepiped with account of prohibition zones and maximization of its filling coefficient, as well as for the problem of placing n-polytopes were built for the first time. A modified method is proposed for building a convex hull of a finite set of points in . It is used for building Ф-functions of n-polytopes and implements one of the methods of their specification. Based on the combined methods, the problem of placement of a sufficiently big number n-parallelepipeds in an n-parallelepiped and the problem of placing n-polytopes in an n-parallelepiped was solved for the first time. The algorithms and program codes were developed for these problems. The results of computational experiments are given.

Keywords: mathematical modeling, optimization, placement, Ф-function, n-dimensional parallelepiped, n-dimensional polytope, convex hull.

1. Загальна характеристика роботи

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в період з 2003 по 2006 рр. у відділі математичного моделювання й оптимального проектування Інституту проблем машинобудування ім. А. М. Підгорного НАН України відповідно до планів науково-дослідних робіт з бюджетної теми III-4-02 “Розробка методів і алгоритмів оптимізації для розв'язання задач розміщення тривимірних опуклих геометричних об'єктів у заданих опуклих областях" (№ ДР 0102U001480).

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

Основними науковими задачами дослідження, відповідно до поставленої мети, є:

- постановка оптимізаційних задач розміщення n-паралелепіпедів і n-політопів в областях простору , які мають форму n-паралелепіпеда;

- формалізація (за допомогою Ф-функцій) умов взаємного неперетину n-паралелепіпедів та n-політопів і умов розміщення їх в області;

- побудова математичних моделей задач розміщення n-паралелепіпедів і n-політопів, а також дослідження їхніх основних особливостей;

- розробка методів і алгоритмів розв'язання зазначених задач на основі існуючих методів геометричного проектування;

- створення програмних систем, які реалізують розроблені методи розв'язання задач.

Об'єкт дослідження. Об'єктом дослідження є процес моделювання розміщення n-паралелепіпедів і n-політопів в областях простору , що мають форму n-паралелепіпеда.

Предмет дослідження. Предметом дослідження є математичні моделі та методи наближеного розв'язання задач розміщення n-паралелепіпедів і n-політопів.

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

Наукова новизна отриманих результатів полягає у такому.

1. Вперше побудовані Ф-функції n-паралелепіпедів і n-політопів, що дозволяють для розглянутих багатовимірних об'єктів формалізувати умови їхнього взаємного неперетину, а також умови розміщення їх в області.

2. Набуло подальшого розвитку представлення математичної моделі задачі розміщення n-паралелепіпедів у n-паралелепіпеді зі змінними метричними характеристиками.

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

4. Запропоновано модифікований метод побудови опуклої оболонки скінченної множини точок у , що використовується при побудові Ф-функцій n-політопів, а також реалізує один із способів їхнього задання.

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

6. Вперше здійснено розв'язання оптимізаційної задачі розміщення n-політопів на підставі модифікованого методу оптимізації за групами змінних, модифікованого симплекс-методу та модифікованого методу околів, що звужуються.

Практичне значення отриманих результатів. На підставі розроблених методів розв'язання поставлених задач створені програмні системи “Packing of n-parallelepipeds” і “Packing of n-polytopes”, що можуть бути застосовані для розв'язання різноманітних задач розміщення багатовимірних об'єктів, які виникають у різних галузях промисловості при розв'язанні проблеми ресурсозбереження, задач планування експериментів, а також для розв'язання інших оптимізаційних задач, що зводяться до задач розміщення n-паралелепіпедів і n-політопів.

Результати дисертаційної роботи впроваджені в навчальний процес у Харківському національному університеті радіоелектроніки, про що свідчить відповідний акт.

Особистий внесок автора. Усі основні наукові результати дисертаційної роботи отримані особисто автором. У працях, що написані у співавторстві, дисертантові належать такі результати: [1] - розробка методу і алгоритму побудови Ф-функції n-паралелепіпедів; [2] - побудова математичної моделі задачі розміщення n-паралелепіпедів у n-паралелепіпеді зі змінними метричними характеристиками, дослідження її особливостей, розробка методу розв'язання задачі; [3] - формалізація умов розміщення n-політопів в області розміщення й умов їхнього взаємного неперетину; [4] - побудова математичної моделі задачі розміщення n-політопів, дослідження її особливостей, розробка методу розв'язання задачі; [6] - алгоритмічна та програмна реалізація розв'язання задачі розміщення n-паралелепіпедів у n-паралелепіпеді зі змінними метричними характеристиками; [7] - алгоритмічна та програмна реалізація розв'язання задачі розміщення n-політопів; [14] - розробка методу розв'язання задачі розміщення n-паралелепіпедів зі змінними метричними характеристиками.

Апробація результатів дисертації. Основні положення дисертаційної роботи доповідалися й обговорювалися на:

- конференції молодих вчених і фахівців “Сучасні проблеми машинобудування” (м. Харків, 2003-2006 рр. У 2003 і 2005 рр. доповіді були відзначені грамотами);

- XIII Міжнародній науково-практичній конференції “MicroCAD 2005. Інформаційні технології: наука, техніка, технологія, освіта, здоров'я” (м Харків, 2005 р.);

- II Міжнародній науковій конференції студентів, аспірантів і молодих вчених “Комп'ютерний моніторинг і інформаційні технології” (м. Донецьк, 2006 р.);

- Сьомій Міжнародній науково-технічній конференції “Штучний інтелект. Інтелектуальні багатопроцесорні системи” (м. Донецьк, 2006 р.);

- Міжнародній конференції “Euro Special Interest Group on Cutting and Packing “3^rd ESICUP Meeting”” (м. Порто, Португалія, 2006 р.);

- постійно діючих семінарах у відділі математичного моделювання й оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України (м. Харків, 2003-2007 рр.).

Публікації. Основні результати дисертаційної роботи опубліковані в 14 наукових працях, з них статей в наукових спеціалізованих виданнях, що входять до переліку ВАК України - 5 [1-5], матеріалів конференцій - 7 [8-14] та два свідоцтва про реєстрацію авторського права на твір [6, 7].

Структура й обсяг дисертації. Робота складається зі вступу, п'яти розділів, висновків, списку літератури зі 151 найменування (14 с.) та одного додатку (1 с.). Загальний обсяг роботи складає 148 сторінок, включаючи 18 рисунків і 9 таблиць.

2. Основний зміст роботи

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

У першому розділі ”Огляд літератури та вибір напряму дослідження” представлений огляд робіт вітчизняних і закордонних авторів, спрямованих на розв'язання оптимізаційних задач геометричного проектування. Великий внесок у розвиток теорії геометричного проектування при розв'язанні задач розміщення дво- і тривимірних геометричних об'єктів зробили такі вітчизняні вчені, як Залгаллер В.А., Рвачов В.Л., Стоян Ю.Г., Гіль М.І., Комяк В.М., Новожилова М.В., Панкратов О.В., Путятін В.П., Смеляков С.В., Яковлев С.В. та ін. Вивченню класу задач розміщення багатовимірних об'єктів присвячені роботи Васильєвої Л.І., Картака В.М., Мухачової Е.О., Новожилової М.В., Чорноморця А.О., Freville A., Hong D., Kodydet G., Leung J.,Y.-T., Lins L., Lins S, Morabito R, Pisinger D. Raidl G. R., Schepers J. та ін.

Аналіз літературних джерел показав недостатню вивченність задач розміщення багатовимірних об'єктів: об'єктами в розглянутих задачах є здебільшого n-вимірні прямокутні паралелепіпеди, що дещо спрощує підходи до їх розв'язання; запропоновані методи розв'язання оперують з невеликою кількістю об'єктів і є переважно евристичними. Задачі розміщення багатовимірних об'єктів довільної форми практично не розглядаються, що можна пояснити великою складністю таких задач і відсутністю єдиного математичного апарату, що дозволяє описувати умови взаємного неперетину розміщуваних об'єктів та умови належності об'єктів області розміщення. В дисертації на підставі математичного апарату Ф-функцій, запропонованого Ю. Г. Стояном, ці умови формалізовані для n-паралелепіпедів і n-політопів, що дозволило побудувати математичні моделі та розробити методи наближеного розв'язання багатовимірних оптимізаційних задач геометричного проектування на базі сучасних ПЕОМ.

Дисертаційна робота є логічним продовженням досліджень задач геометричного проектування, які проводяться у відділі математичного моделювання й оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України під керівництвом члена-кореспондента НАН України Ю.Г. Стояна.

В другому розділі ”Постановка задач розміщення n-вимірних геометричних об'єктів” наводяться основні поняття та визначення багатовимірної геометрії, формулюються оптимізаційні задачі розміщення n-паралелепіпедів у n-паралелепіпеді з різними функціями мети та задача розміщення n-політопів у n-паралелепіпеді. Аналізуються відомі методи розв'язання оптимізаційних задач геометричного проектування стосовно поставлених задач, робиться висновок про необхідність розробки комбінованих методів для розв'язання цих задач.

У дисертації розглядаються такі багатовимірні об'єкти:

n-паралелепіпед - n-вимірна поліедральна множина, що у деякій прямокутній системі координат задається нерівностями , де .

n-політоп - непуста континуальна обмежена n-вимірна поліедральна множина, за умови, що ця множина не є підмножиною ніякого простору меншої розмірності.

Зауваження. Надалі будуть розглядатися лише орієнтовані n-паралелепіпеди та n-політопи, тобто такі, що не допускають поворотів.

Розглядаються постановки таких задач.

Задача 1. Є M n-політопів , заданих координатами вершин , j=1,2,..,t_i ( - кількість вершин n-політопа T_i) або у вигляді перетинання скінченного числа замкнених півпросторів. Задано область у вигляді n-паралелепіпеда з вектором розмірів , причому величина є змінною і , k=2,…,n, де , , . Необхідно розмістити n-політопи , i=1,2,…,M, у n-паралелепіпеді таким чином, щоб n-політопи попарно не перетиналися, а довжина h зайнятої частини області у напрямку ребра з розміром d₀₁ була мінімальною.

Задача 2. Є N n-паралелепіпедів з векторами розмірів , i=1,2,…,N, відповідно. Задана також область у вигляді n-паралелепіпеда з вектором розмірів (величина є змінною) і виконується умова , k=2,…,n. Необхідно розмістити n-паралелепіпеди , i=1,2,…,N, у n-паралелепіпеді таким чином, щоб n-паралелепіпеди попарно не перетиналися, а довжина d зайнятої частини області у напрямку ребра з розміром b₀₁ була мінімальною.

Задача 3. Є N n-паралелепіпедів з векторами розмірів , i=1,2,…,N, відповідно. Задана багатозв'язна область ; - n-паралелепіпед з вектором розмірів (величина є змінною); - зона заборони у вигляді n-паралелепіпеда , з вектором розмірів , j=1,2,…,, де - кількість зон заборони, і виконується умова , k=2,…,n. Необхідно розмістити n-паралелепіпеди , i=1,2,…,N, у багатозв'язній області таким чином, щоб n-паралелепіпеди попарно не перетиналися, а довжина d зайнятої частини області у напрямку ребра з розміром b₀₁ була мінімальною.

Задача 4. Задані пари , ,…,, де - кількість типів n-паралелепіпедів; - кількість n-паралелепіпедів j-го типу, j=1,2,…,; - вектор розмірів n-паралелепіпедів j-го типу, . Таким чином, задані n-паралелепіпедів , з векторами розмірів , . Задано область у вигляді n-паралелепіпеда з вектором розмірів . Припускаємо, що .

Потрібно вибрати з множини такі n-паралелепіпеди та розмістити їх у з урахуванням попарного неперетину, щоб сумарний об'єм розміщених n-паралелепіпедів був максимальним.

У третьому розділі ”Математичне моделювання розміщення опуклих n-вимірних політопів” формалізуються умови взаємного неперетину n-політопів та умови розміщення їх у n-паралелепіпеді. Надається опис модифікованого методу побудови опуклої оболонки скінченної множини точок в . Будується математична модель задачі розміщення n-політопів, досліджуються її особливості. Виходячи з особливостей математичної моделі задачі, пропонується підхід до її розв'язання.

Зв'яжемо з кожним n-політопом , i=1,2,…,M, прямокутну ортогональну рухому (власну) систему координат , а з областю - нерухому систему . Припускаємо, що для кожного n-політопа , i=1,2,…,M, з вершинами , j=1,2,..,, , виконується умова .

Як полюс n-політопа , i=1,2,…,M, виберемо початок O_i рухомої системи координат. Координати полюса n-політопа , i=1,2,…,M, відносно нерухомої системи координат є його параметрами розміщення і визначають положення n-політопа в просторі . Позначимо через - n-політоп , трансльований на вектор параметрів розміщення , i=1,2,…,M.

При розв'язанні задачі розміщення n-політопів необхідно враховувати обмеження двох видів: умови взаємного неперетину n-політопів , i=1,2,…,M, та умови розміщення n-політопів , i=1,2,…,M, в області розміщення - n-паралелепіпеді .

Для аналітичного опису цих умов використовується математичний апарат Ф-функцій.

Безперервна, всюди визначена функція називається Ф-функцією n-політопів та , якщо вона задовольняє такі характеристичні властивості:

, якщо clcl,

, якщо ,

frfr,

, якщо .

Отже, Ф-функція дозволяє описати умови попарного перетину, торкання та неперетину відповідних геометричних об'єктів.

Теорема 1. Нехай , p=1,2,…,, і , q=1,2,…,,- вершини n-політопів Т_i(0) та Т_j(0) відповідно, які задані у власних системах координат, а , k=1,2,…,m, ,- рівняння гіперплощин, що утворюють опуклу оболонку H множини , причому , якщо . Тоді функція є Ф-функцією n-політопів Т_i(u_i) та Т_j(u_j).

Теорема 2. Нехай , , - вершини n-вимірної багатогранної області D₀(0); , , - вершини n-політопа Т_j(0); , k=1,2,…,m, - рівняння гіперплощин, що визначають область D₀(0) і таких, що , якщо ; , , - рівняння гіперплощин, кожна з яких паралельна відповідній гіперплощині і проходить через точку ( ), де , : . Тоді функція є Ф-функцією точкової множини та n-політопа Т_j(u_j).

У розділі наводиться опис модифікованого методу побудови опуклої оболонки скінченної множини точок у як одного з етапів побудови Ф-функції та одного зі способів задання n-політопів.

Основні особливості розробленого підходу полягають у такому:

- результатом є побудована опукла оболонка - n-політоп, представлений у вигляді перетину замкнених півпросторів;

- у процесі побудови не потрібно підтримувати опис усіх k-граней n-політопа, , достатньо тільки знаходження опорних гіперплощин, що беруть участь у його представленні;

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

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

Математичну модель задачі розміщення n-політопів можна представити у вигляді

, (1)

де , W - область припустимих розв'язків, що описується системою нерівностей

(2)

- (3)

Ф-функція n-політопів Т_i(u_i) та Т_j(u_j); - рівняння гіперплощин, що визначають опуклу оболонку множини точок , p=1,2,…,, q=1,2,…,, , , k=1,2,…,n, l=1,2,…,, - загальне число таких гіперплощин;

- (4)

Ф-функція точкової множини та n-політопа Т_j(u_j), де , .

У дисертації досліджені особливості математичної моделі задачі розміщення n-політопів, основними з яких є.

Функція мети G(X)=h є лінійною і .

Область W неопукла, незв'язна, має кусково-лінійну границю. Кожна компонента зв'язності області W багатозв'язна.

Враховуючи (3) та (4), область W можна представити у вигляді системи нерівностей

(5)

де знак означає набір (або сукупність) нерівностей.

Загальна кількість нерівностей у системі (5) - .

Для виконання системи (5) необхідно, щоб виконувалась одна із систем

(6)

де - одна з нерівностей відповідного набору в системі (5), i=1,2,…,M-1, j=i+1,…,M, . У загальному випадку . Таким чином, область W можна описати в еквівалентному вигляді набором із відповідних систем нерівностей вигляду (6).

Неопуклу область W можна представити так:

,

де - опукла підобласть, що описується відповідною системою вигляду (6).

Локальні мінімуми функції мети G(X) досягаються у вершинах області W.

Кількість локальних екстремумів функції мети G(X) - не менш , тобто поставлена задача є NP-складною.

Задача 1 належить до класу багатоекстремальних задач великої розмірності з лінійною функцією мети і може бути зведена до такої:

,

, . (7)

Оптимальний розв'язок задачі 1 може бути отриманий в результаті послідовного розв'язання задач вигляду (7), тобто розв'язання задачі на кожній опуклій підобласті.

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

а) одержання припустимого варіанта розміщення n-політопів за допомогою апроксимації n-політопів відповідними n-паралелепіпедами , i=1,2,…,М, і розв'язання допоміжної задачі розміщення n-паралелепіпедів у n-паралелепіпеді;

б) знаходження локального екстремуму задачі 1 за допомогою модифікованого симплекс-методу (з початковою точкою, отриманою в результаті реалізації пункту а);

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

Апроксимуємо n-політопи , i=1,2,…,М, задані координатами вершин , , відповідними n-паралелепіпедами , де = - вектор розмірів , . Нехай Р_i(u_i) - n-паралелепіпед , трансльований на вектор , i=1,2,…,M. Вважаємо, що полюси n-паралелепіпедів Р_i(u_i), i=1,2,…,М, співпадають з початком їх власних систем координат. Поставимо у взаємно однозначну відповідність кожному n-паралелепіпедові Р_i(u_i) пару , де , тобто , i=1,2,…, M.

Здійснимо розміщення n-паралелепіпедів , i=1,2,…,M, у n-паралелепіпеді D₀ таким чином, щоб довжина h зайнятої частини області D₀ у напрямку ребра з розміром d₀₁ була мінімальною (розв'язання задачі 2). У результаті розв'язання цієї допоміжної задачі (процес розв'язання описаний у розділі 4) знаходимо точку її локального мінімуму , якій відповідає деякий припустимий варіант розміщення n-політопів.

Для пошуку локального мінімуму основної задачі 1, як задачі лінійного програмування (функція мети G(X) і обмеження (2) лінійні), використовується модифікований симплекс-метод^* з початковою точкою , координати якої задовольняють одну із систем вигляду (6). У результаті, за скінченне число ітерацій знаходимо локальний мінімум задачі 1.

Для реалізації спрямованого перебору локальних екстремумів відповідно до модифікованого методу околів, що звужуються^**, здійснимо занурення множини П, елементами якої є переставлення , , i=1,2,…,М, j=1,2,…,k₀, , з номерів n-політопів, в арифметичний евклідовий простір , встановивши взаємно однозначну відповідність між переставленням та вектором ,…,, де - розміри n-паралелепіпеда з номером , i=1,2,…,М, j=1,2,…,k₀, що апроксимує відповідний n-політоп. Тоді множині переставлень П буде відповідати множина К точок , j=1,2,…,k₀, простору .

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

На кожному етапі , за певним правилом формуються околи , h=1,2,3, однакового радіуса () з центрами в точках множини К. У кожному околі випадково обираються точки , і відповідні їм переставлення , . Використовуючи комбінований метод, що включає модифіковані метод оптимізації за групами змінних і симплекс-метод, з обраних точок здійснюється спуск у відповідні локальні мінімалі та обчислюються значення функції мети , . У залежності від характеру зміни значення функції мети, отриманого на даному етапі, відбувається зміна значення радіуса околу і корегуються центри околів. Перебір локальних екстремумів припиняється у випадку, коли: , , , (значення залежить від розмірності простору).

Значення функції мети в точці локального екстремуму приймається як наближення до глобального мінімуму задачі розміщення n-політопів.

Основні результати розділу опубліковані в працях [3, 4, 10, 11, 13].

У четвертому розділі ”Математичне моделювання розміщення n-вимірних паралелепіпедів” формалізуються умови взаємного неперетину n-паралелепіпедів та умови розміщення їх в однозв'язній області у вигляді n-паралелепіпеда, а також в області з урахуванням зон заборони. Будуються математичні моделі задач розміщення n-паралелепіпедів з різними функціями мети, досліджуються особливості математичних моделей задач. Пропонуються підходи для знаходження наближень до глобальних естремумів задач 2-4.

Для формалізації умов взаємного неперетину n-паралелепіпедів та умов розміщення їх в області у вигляді n-паралелепіпеда побудовані відповідні Ф-функції.

Теорема 3. Нехай - n-паралелепіпеди з векторами розмірів , трансльовані на вектори параметрів розміщення , . Тоді функція є Ф-функцією n-паралелепіпедів та .

Теорема 4. Нехай - n-паралелепіпед з вектором розмірів , трансльований на вектор параметрів розміщення ; - n-паралелепіпед з вектором розмірів , трансльований на вектор параметрів розміщення . Тоді функція є Ф-функцією точкової множини та n-паралелепіпеда.

Математичну модель задачі 2 можна представити у вигляді

, (8)

де .

Область припустимих розв'язків W описується системою нерівностей

(9)

де

- Ф-функція n-паралелепіпедів P_i(u_i) та P_j(u_j), - Ф-функція n-паралелепіпеда P_j(u_j) та множини , де .

Математична модель задачі 3 може бути представлена в аналогічному вигляді, при цьому до системи (9) додаються нерівності, що реалізують умови взаємного неперетину розміщуваних об'єктів і зон заборони.

Математична модель задачі 4 має вигляд (8), (9) з тією лише різницею, що

де =1, якщо , за умови , або , за умови ; =0 - в іншому випадку; - об'єм n-паралелепіпеда , j=1,2,…,.

Аналіз особливостей розглянутих задач 2-4 показав, що вони належать до класу багатоекстремальних задач великої розмірності. На сьогодні не існує методу, що дозволяє знайти глобальні екстремуми задач 2-4 вже при .

Запропонована стратегія наближеного розв'язання задач 2-4 містить у собі такі етапи:

- знаходження локальних екстремумів, з огляду на їхню нестрогість, на базі модифікованого методу оптимізації за групами змінних (побудова припустимих варіантів розміщення);

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

Процес розміщення заданої кількості n-паралелепіпедів містить у собі дві основні процедури:

а) представлення області (незайнятої частини області після розміщення n-паралелепіпедів ) у вигляді об'єднання областей у формі n-паралелепіпедів. У задачах 2 і 4: ; , , ; у задачі 3: ; , , де - область, у яку можливо (за певних умов) розмістити n-паралелепіпед P_i, і для якої виконується умова невключення: не існує області такої, що ;

б) розміщення n-паралелепіпеда , i=1,2,…,N, в одній із областей , , з урахуванням мінімізації зайнятої частини області D₀ у напрямку ребра з розміром b₀₁.

Нехай , , a_i - вектор розмірів n-паралелепіпеда P_i, i=1,2,…,N; , , , - вектор розмірів області .

Розглянемо докладніше процес розміщення чергового n-паралелепіпеда , , в області (у задачах 2 і 4). Очевидно, , тоді . При розміщенні n-паралелепіпеда , , з вибирається така область :

, ,

для якої одночасно виконуються умови

а) , k=1,2,…,n, б) ,

де - кількість областей з , для яких виконується умова розміщення n-паралелепіпеда .

Потім здійснюється розміщення в області , тобто , тоді

.

Для розміщення наступного n-паралелепіпеда формується область , у якій , де

і для кожної області виконується умова невключення.

У дисертації наведено верхню оцінку кількості областей, що утворюються при розміщенні n-паралелепіпеда .

В задачі 3 представлення області у вигляді об'єднання областей у формі n-паралелепіпедів є частинним випадком процедури, що описана вище.

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

Після розміщення всіх n-паралелепіпедів , i=1,2,…,N, одержимо точку локального екстремуму (для задачі 4 ) і значення локального екстремуму в цій точці.

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

Основні результати розділу опубліковані в працях [1, 2, 5, 8, 9, 11-14].

У п'ятому розділі ”Практична реалізація результатів досліджень” розглядаються структура, принцип організації і схема функціонування розроблених програмних систем “Packing of n-polytopes” і “Packing of n-parallelepipeds”, що реалізують розроблені методи розв'язання задач розміщення n-політопів та n-паралелепіпедів зі змінними метричними характеристиками відповідно.

Наводяться приклади розв'язання ряду задач розміщення до 200 n-паралелепіпедів і до 50 n-політопів в областях простору , проводиться аналіз і порівняння результатів обчислювальних експериментів.

У таблиці 1 наведені деякі результати розв'язання задачі розміщення 4-політопів у 4-паралелепіпеді при за умови, що . Кількість та координати , вершин 4-політопа , i=1,2,…,M, обираються випадково за умови, що , , , . Т - загальний час оптимізації розміщення n-політопів, t - середній час знаходження одного локального екстремуму, % - поліпшення (у відсотках) значення функції мети. Результати отримані на персональному комп'ютері з процесором AMD Athlon 2200+, ОЗП - 256 МБт, що працює під управлінням операційної системи Windows XP.

Таблиця 1. Результати розв'язання задачі розміщення 4-політопів в області

n=4	M=10	M=15	M=20
T	00:25:64:422	00:33:94:999	00:41:13:16
t	00:00:00:204	00:00:00:257	00:00:00:499
%	12,92	15,11	9,88

Основні результати розділу опубліковані в працях [6, 7].

У додатку наведено довідку про використання результатів дисертаційної роботи.

Основні висновки по роботі

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

Основні наукові та практичні результати роботи полягають у такому.

1. Вперше на основі доведених теорем побудовані Ф-функції n-паралелепіпедів та n-політопів, що дозволяють для розглянутих багатовимірних об'єктів формалізувати умови їхнього взаємного неперетину та умови розміщення їх в області (n-паралелепіпеді).

2. Набуло подальшого розвитку представлення математичної моделі задачі розміщення n-паралелепіпедів у n-паралелепіпеді зі змінними метричними характеристиками.

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

4. Запропоновано модифікований метод побудови опуклої оболонки скінченної множини точок у , який використовується при побудові Ф-функцій n-політопів, а також реалізує один із способів їхнього задання.

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

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

7. Розроблено відповідне алгоритмічне і програмне забезпечення, що може бути використане для розв'язання практичних задач, пов'язаних з моделюванням розміщення багатовимірних геометричних об'єктів.

Програмні системи “Packing of n-parallelepipeds” і “Packing of n-polytopes”, результати дисертаційної роботи можуть бути використані на підприємствах, у науково-дослідних і проектно-конструкторських організаціях при розв'язанні задач, що зводяться до оптимізаційних задач розміщення багатовимірних об'єктів.

8. Результати роботи впроваджені в навчальний процес у Харківському національному університеті радіоелектроніки.

Наукові праці, що опубліковані за темою дисертації

математичний моделювання паралелепіпед політоп

1. Стоян Ю.Г., Гиль Н.И., Муравьева М.С. Ф-функция n-мерных параллелепипедов // Доповіді Національної академії наук України. - 2005. - № 3. - C. 22-27.

2. Гиль Н.И., Софронова М.С. Решение задачи упаковки n-мерных параллелепипедов для оптимизации выполнения работ на машиностроительных предприятиях // Проблемы машиностроения. - 2005. - Т. 8, № 4. - С. 55-66.

3. Гиль Н.И., Софронова М.С. Построение Ф-функции выпуклых n-мерных политопов // Радиоэлектроника и информатика. - 2006. - № 1. - С. 101-105.

4. Гиль Н.И., Софронова М.С. Построение математической модели и решение задачи размещения выпуклых n-мерных политопов в n-мерном параллелепипеде // Доповіді Національної академії наук України. - 2006. - № 8. - С. 95-102.

5. Софронова М.С. Моделирование размещения n-мерных параллелепипедов в n-мерной области с учетом зон запрета // Штучний інтелект. - 2006. - № 4. - С. 478-487.

6. Гіль М.І., Софронова М.С. Свідоцтво про реєстрацію авторського права на твір № 14099. Комп'ютерна програма “Packing of n-parallelepipeds”, 09.09.05.

7. Гіль М.І., Панкратов О.В., Софронова М.С. Свідоцтво про реєстрацію авторського права на твір № 18166. Комп'ютерна програма “Packing of n-polytopes”, 04.10.06.

8. Муравьева М.С. Моделирование размещения n-мерных параллелепипедов в n-мерном параллелепипеде // Тезисы докладов конференции молодых ученых и специалистов “Современные проблемы машиностроения”. - Харьков. - ИПМаш им. А.Н. Подгорного НАН Украины. - 2003.- С. 14.

9. Софронова М.С. Размещение n-мерных параллелепипедов в . Перебор допустимых вариантов размещения объектов // Тезисы докладов конференции молодых ученых и специалистов “Современные проблемы машиностроения”. - Харьков. - ИПМаш им. А.Н. Подгорного НАН Украины. - 2004.- С. 20.

10. Софронова М.С. Моделирование упаковки выпуклых n-мерных политопов в n-мерном параллелепипеде // Тезисы докладов конференции молодых ученых и специалистов “Современные проблемы машиностроения”. - Харьков. - ИПМаш им. А.Н. Подгорного НАН Украины. - 2005.- С. 31.

11. Софронова М.С. Математическое моделирование размещения выпуклых n-мерных геометрических объектов // Тезисы докладов II Международной научной конференции студентов, аспирантов и молодых ученых “Компьютерный мониторинг и информационные технологии”. - Донецк. - 2006. - С. 237-238.

12. Софронова М.С. Упаковка n-мерных параллелепипедов в многосвязную область // Тезисы докладов Седьмой Международной научно-технической конференции “Искусственный интеллект. Интеллектуальные и многопроцессорные системы - 2006”. - Таганрог - Донецк - Минск, 2006. - С. 288-292.

13. Софронова М.С. Некоторые задачи размещения выпуклых многомерных объектов // Тезисы докладов конференции молодых ученых и специалистов “Современные проблемы машиностроения”. - Харьков. - ИПМаш им. А.Н. Подгорного НАН Украины. - 2006.- С. 33.

14. Stoyan, Yu., Gil, N., Sofronova, M. Packing various nD-parallelepipeds into a nD-parallelepiped // “3^rd ESICUP Meeting”. - Porto, Portugal. - 2006. - Р. 19.

Размещено на Allbest.ru

...