Декомпозиційні методи оптимального розміщення об’єктів в системах технічного призначення

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦІ

ім. г.є. Пухова

ДЕКОМПОЗИЦІЙНІ МЕТОДИ ОПТИМАЛЬНОГО РОЗМІЩЕННЯ ОБ'ЄКТІВ В СИСТЕМАХ ТЕХНІЧНОГО ПРИЗНАЧЕННЯ

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

Автореферат

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

ШАПОВАЛОВ Юрій Олександрович

УДК 519.6:514.1

Київ - 2007

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

Робота виконана в Житомирському державному технологічному університеті Міністерства освіти і науки України.

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

Офіційні опоненти:

доктор технічних наук, професор Саух Сергій Євгенович, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, головний науковий співробітник

кандидат фізико-математичних наук Заславський Володимир Анатолійович, Київський національний університет ім. Тараса Шевченка, доцент кафедри математичної інформатики

Захист відбудеться 20 вересня 2007 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитись у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України (03164, м. Київ, вул. Генерала Наумова, 15).

Автореферат розісланий 16 серпня 2007 р.

Вчений секретар

спеціалізованої вченої ради, к.т.н. Е.П. Семагіна

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Задачами оптимізації розміщення геометричних об'єктів займались такі вчені: Л.В. Канторович, В.Л. Рвачов, Ю.Г. Стоян і його учні: М.І. Гіль, В.М. Комяк, М.В. Новожилова, Т.Є. Романова, С.Л. Магас, Г.М. Яськов, О.В. Панкратов, О.К. Пандорін, В.П. Путятін, С.І. Яремчук, В.Б. Крижанівський та ін.., а також: Б.М. Пшеничний, Л.А. Соболенко, Е.О. Мухачева, E.G. Birgin, J.M. Martinez, F.H. Nishihara, D.P. Ronconi та ін.

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

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

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

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

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

Питаннями використання декомпозиції для розв'язання задач оптимізації займалися: Дж. Данциг, Н.З. Шор, В.С. Михалевич, О.Ф. Волошин та інші вчені.

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

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

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

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

2. Зробити математичну постановку задачі пошуку невигідного розміщення навантажень.

3. Розробити методи, які б дозволяли розв'язувати отримані оптимізаційні задачі з урахуванням їх особливостей.

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

Об'єкт дослідження: розміщення об'єктів із заданими геометричними характеристиками.

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

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

Наукова новизна одержаних результатів

1. Вперше розроблено метод спрямованого переходу між підмножинами в межах однієї компоненти зв'язності для розв'язання вихідної задачі.

2. Вперше розроблено модифікацію генетичного алгоритму для організації пошуку початкової підмножини.

3. Вперше розроблено модифікацію методу можливих напрямків для розв'язання мінімаксних підзадач.

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

5. Набула подальшого розвитку ідея декомпозиції множини допустимих розв'язків задачі на опуклі підмножини та розв'язання вихідної задачі шляхом розв'язування послідовності підзадач.

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

Практичне значення одержаних результатів полягає в побудові та реалізації на ПЕОМ побудованих алгоритмів. В результаті створено програмний комплекс для розв'язання задач оптимізації розміщення об'єктів, кожен з яких можна розбити на прямокутники (паралелепіпеди). Результати дисертаційної роботи використовуються при побудові карт розкрою металопрокату на дочірньому підприємстві “Житомир Ворд Білдінг Сістемс Україна” (акт впровадження від 04.2007р.), при проектуванні будівельних конструкцій для оцінювання максимального можливого повздовжнього згинального моменту, що виникає від тимчасових навантажень на ПП “Здобуток ІІ” (м.Житомир), (акт впровадження від 04.2007р.), в навчальному процесі у Житомирському державному технологічному університеті при викладанні курсу “Математичні методи дослідження операцій” та в дипломному проектуванні при підготовці бакалаврів, спеціалістів та магістрів (довідка від 05.2007р.).

Апробація результатів дисертації. Основні положення роботи доповідалися і обговорювалися на наукових конференціях і семінарах: 34-й Регіональній молодіжній конференції “Проблемы теоретической и прикладной математики” (м.Єкатеринбург, 2002р.), Міжнародній конференції “Інформаційно-комп'ютерні технології” (м.Житомир, 2004, 2006рр.), ХХХ науковій конференції, присвяченій 45-ій річниці Житомирського державного технологічного університету (м.Житомир, 2005), науковому семінарі відділу математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М Підгорного НАН України (м.Харків, 2005, 2006рр.), ІІІ українсько-польській науковій конференції молодих вчених “Механіка та інформатика” (м.Хмельницький, 2005р.), V міжнародній науково-практичній конференції “Современные информационные и электронные технологии” (м.Одеса, 2005р.), міжкафедральному семінарі факультету інформаційно-комп'ютерних технологій Житомирського державного технологічного університету (м.Житомир, 2006р.), науковому семінарі Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова (м.Київ, 2006, 2007рр.), науковому семінарі кафедри обчислювальної математики Київського національного університету Тараса Шевченка (м.Київ, 2006р.).

Особистий внесок здобувача. В роботах, написаних у співавторстві, дисертанту належать такі результати: [1,8] - ідея використання генетичного алгоритму для перебору підзадач, побудова модифікації генетичного алгоритму для задачі оптимізації розміщення об'єктів в опуклій області; [2] - модифікація методу гілок та меж; [3] - схема розв'язання задачі та її програмна реалізація; [7] - модифікація методу можливих напрямків з використанням методу спрямованого переходу між підмножинами; [4,10] - математична постановка та метод розв'язання задачі оптимізації розміщення об'єктів, кожен з яких можна розбити на прямокутники; [5] - математична постановка та метод розв'язання задачі оптимізації розміщення об'єктів на області із зонами заборони; [11] - програмна реалізація розробленого методу; [9] - ідея та реалізація модифікації методу можливих напрямків для мінімаксної задачі розміщення; [12] - метод розв'язання мінімаксної задачі оптимізації розміщення в області із зонами заборони об'єктів, кожен з яких можна розбити на прямокутники, програмна реалізація методу та результати чисельного експерименту.

Публікації. За темою дисертації опубліковано 12 наукових праць, серед них 7 у фахових виданнях, 5 - за матеріалами доповідей на наукових конференціях різного рівня.

Структура та обсяг дисертації. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел та додатків. Загальний обсяг дисертації 166 стор. Робота містить 56 рис., 5 табл., 1 додаток. Бібліографічний список налічує 161 назву на 20 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

Серед практичних задач оптимізації розміщення, відокремлені та надалі розглядаються задачі, в яких:

· об'єкти, що розміщуються, можна розбити на орієнтовані прямокутники (паралелепіпеди);

· область розміщення - опукла, можливо, з зонами заборони;

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

Наведеним критеріям відповідають наступні практичні задачі.

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

2. Мінімізація відхилення центру мас системи від заданої точки (лінії). Виникає при конструюванні транспортних засобів (розміщення елементів конструкції та вантажів).

3. Задачі щільного розміщення (лазерний розкрій листового металопрокату та ін.).

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

5. Задача оптимального розміщення джерел фізичних полів (компонентів РЕА з метою отримання потрібного теплового режиму, джерел екологічних забруднень та ін.).

В другому розділі наведено змістовні постановки практичних задач оптимізації розміщення; зроблено математичну постановку задачі оптимізації розміщення прямокутників на опуклій області та задачі оптимізації розміщення на області із зонами заборони об'єктів, кожен з яких можна розбити на прямокутники (паралелепіпеди). Проаналізовано особливості математичних постановок цих задач, описано спосіб декомпозиції множини припустимих розв'язків.

Змістовна постановка задачі пошуку несприятливого розміщення навантажень. Відповідно до Державних будівельних норм (ДБН В.1.2-2:2006 “Система забезпечення надійності та безпеки будівельних об'єктів. Навантаження і впливи. Норми проектування”), на стадії проектування будівлі необхідно враховувати несприятливе часткове завантаження конструкцій і основ, чутливих до такої схеми завантаження. Таким чином, виникає необхідність пошуку найбільш невигідного можливого розміщення навантажень (устаткування, вантажів та ін.). В даному дослідженні розв'язується задача пошуку такого розміщення навантажень, при якому виникає максимальний повздовжній згинальний момент в стиснутих колонах і відповідно згинальний момент, який діє при цьому на фундамент колони для випадку конструктивної схеми каркасу, коли балки, які спираються на колони, та плити покриття, що спираються на балки, мають шарнірні опори.

Ця задача зводиться до задачі оптимізації розміщення об'єктів (навантажень) на заданій області. (рис.1).

Змістовна постановка задачі щільного розміщення. Розв'язуються задачі оптимального розміщення заготівок з метою найкращого використання матеріалу (листового металопрокату, ДСП та ін.) , а саме, задачі:

· розміщення заготівок у смузі мінімальної довжини;

· розміщення заготівок у прямокутнику мінімальної площі.

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

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

, ,

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

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

.

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

, ,

де - опуклі, неперервно диференційовані на опуклій множині ; - кількість обмежень, яка залежить від форми області , та кількості об'єктів.

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

Кожен з об`єктів , можна розбити на складові , ,…,(прямокутники - для випадку двовимірного простору або паралелепіпеди - для трьохвимірного). Положення об'єкта , в області визначається координатами його полюса. Полюсом об'єкта є геометричний центр складової . Полюсом складової об'єкта , , , будемо вважати її геометричний центр. В умові задачі, для визначення об`єктів , , необхідно задати розміри усіх складових , та їх положення у рухомій системі координат, центр якої співпадає з полюсом відповідного об`єкта , а осі паралельні сторонам складових.

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

, , , ,

де , - координати полюса складової (співпадають з координатами об'єкта ).

Використовуючи , вимірність задачі можна зменшити. Положення об`єктів , в області однозначно визначається координатами вектора . Положення інших складових , , однозначно визначається через Координати фіксованих об'єктів , , є константами.

Отже має місце задача умовної оптимізації

, ,

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

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

,,

де - неперервно диференційовані та опуклі функції на опуклій множині .

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

, , , , , .

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

Декомпозиція множини припустимих розв'язків. Побудова підзадач. Задання підмножин.

Розкривши модулі в отримаємо, що для кожної пари прямокутників можливими є чотири варіанти обмежень неперетину:

0. - об'єкт знаходиться праворуч об'єкту

1. - об'єкт ліворуч об'єкту

2. - об'єкт вище об'єкту

3. - об'єкт нижче об'єкту

де .

Неопуклу множину припустимих розв'язків задачі , що має складну структуру, можна подати у вигляді об'єднання опуклих підмножин , , де - вимірність простору ; - кількість прямокутників (або паралелепіпедів).

Тоді, розв'язком вихідної задачі є найкращий з розв'язків наступних підзадач

, .

Системи обмежень, які визначають підмножини , складаються з обмежень невиходу об'єктів за межі області , та з лінійних нерівностей неперетину об'єктів (по одній нерівності з для кожної пари прямокутників). Будь-яку з підмножин , , однозначно визначає вектор

,

.

Значення координати визначає номер нерівності з що задає умови неперетину пари об'єктів . Вимірність вектору : . Кількість нерівностей, що визначають кожну з підмножин , :

,

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

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

.

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



де , , , , .

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

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

В третьому розділі описано загальний підхід та методи розв'язання поставлених задач.

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

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

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

Розв'язується задача

=.

Обмеження є “-активним” в точці , якщо виконується умова: , . В класичному методі Зойтендейка для усіх можливих напрямків в точці - k-тому наближенні до розв'язку задачі виконується умова: , ,.

Якщо функція цілі задачі - неперервно диференційована, для знаходження напрямку спуска використовується наступна модифікація методу Зойтендейка

,

, , якщо - нелінійна

, , якщо - лінійна

,

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

,

,

, , якщо - нелінійна

, , якщо - лінійна

,

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

Метод гілок та меж. Початкова вершина дерева відповідає множині (обмеження взаємного неперетину об'єктів відсутні).

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

Якщо , тобто розміщення, що отримано при оцінюванні “батьківської” вершини, належить підмножині її “нащадка”, то відбувається присвоєння . Приклад дерева для задачі розміщення трьох об'єктів наведено на рис. 4.

Зондування вершини відбувається у випадку виконання хоча б однієї з умов:

1. .

2. .

3. , тобто отримано припустимий розв'язок вихідної задачі; якщо при цьому , то присвоюється значення ).

4. Якщо .

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

Для кожної вершини аналізуються перші координат вектора H.

Якщо значення координат та , вектору H, які визначають положення прямокутників та відносно , мають значення 0 та 1 або 2 та 3, де ,, та , то: якщо , то і вершину, відповідну множині - прозондовано, інакше () перевіряються координати та , де та : якщо знайдуться координати та , що визначають положення прямокутників та відносно , для яких та , то , вершину, відповідну множині - прозондовано.

Приклад системи обмежень задачі для відповідних вершин з рис.4

Нажаль, наведений метод гілок та меж дозволяє за прийнятний час отримати розв'язок задачі розміщення до 9-11 об'єктів.

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

В методі Зойтендейка, множина можливих напрямків спуску в точці , звужується через наявність “-активних” обмежень. При цьому збільшується кількість обмежень допоміжної задачі ЛП. Пропонується на кожній ітерації методу можливих напрямків, при виявленні “-активного” обмеження неперетину пари об'єктів, замінити його на обмеження неперетину цієї ж пари об'єктів, але по іншій координаті, якщо виконується та не є “-активним”. Таким чином відбувається перехід до іншої підмножини в межах даної компоненти зв'язності множини припустимих розв'язків задачі. Зроблена заміна дозволяє розширити множину можливих напрямків спуску в точці та зменшити кількість обмежень допоміжної задачі лінійного програмування.

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

1. . Обираються параметри методу , , та початкове розміщення , .

2. Відомо -те наближення , , .

2.1. Аналізуються обмеження взаємного неперетину об'єктів з системи, що визначає поточну підмножину . Якщо для розміщення обмеження , що забезпечує неперетин прямокутників ,, , задовольняє умові , тобто це обмеження є “-активним”, то робиться перевірка: якщо для цієї пари об'єктів ,, має місце умова (обмеження їх неперетину по іншій координаті), причому (тобто обмеження в точці не є “-активним”), то в системі обмежень підзадачі робиться заміна нерівності на .

2.2. Будується множина .

2.3. Знаходиться вектор спуску (розв'язується задача лінійного програмування або ).

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

Якщо та , то , , змінній присвоюється значення та здійснюється перехід до п. 2.

Якщо ж , то - вектор спуску.

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

2.5. . Змінній присвоюється значення та здійснюється перехід до п. 2.

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

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

Функція цілі задачі пошуку невигідного розміщення навантажень (максимального повздовжнього згинального моменту, що виникає у колоні, рис.1.). Центр мас об'єкта співпадає з його полюсом. Величина повздовжнього згинального моменту ,

, ,

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

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

, , . При , .

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

Функції цілі задач щільного розміщення. Розміщення у смузі мінімальної довжини

. Розміщення в прямокутнику мінімальної площі

.

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

,

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

Тестові критерії якості. Максимум суми квадратів відстаней від полюсів об'єктів, до заданих точок , де , - задані точки. Сума квадратів відстаней від полюсів до заданої точки

,

де - задана точка області.

Задача з функцією Розенброка .

Основні відомості про програмний продукт. Програма розроблена в середовищі Microsoft Visual Studio 2005 на мові програмування C++ з використанням MFC. Програма є SDI додатком. Для відображення результатів використовуються засоби бібліотеки OpenGL.

Приклад 1. Пошук невигідного розміщення навантажень (максимізація повздовжнього згинального моменту, що виникає у колоні від тимчасових навантажень). Кількість об'єктів - 60, фіксованих об'єктів - 3 (2 заштриховано та перепона). Розміри області розміщення - 12х6, розміри колони 0.5х0.5. Параметри об'єктів та початкове розміщення обиралися випадково. Величина згинального моменту, що відповідає початковому розміщенню - 883.606, результуючому - 4701.31. (рис.5) Розв'язок отримано за 31,9с. Зроблено 199 ітерацій алгоритму та 50 переходів між опуклими підмножинами.

Приклад 2. Розв'язання задач щільного розміщення. Задача розміщення об'єктів спеціального вигляду у прямокутнику мінімальної площі. Метод розв'язання вихідної задачі: метод випадкового пошуку, можливих напрямків та спрямованого переходу. Кількість об'єктів: 20.Час розв'язання (1 спроба): - 0,25с. Отримана площа: 130 (10х13) (рис.6).

Приклад 3. Порівняння з аналогами (Задача розкрою). Кількість об'єктів, що розміщуються: 20 (рис.7). Оптимальний розв'язок: 110.

- “Раскрой Кузнецова”: отримана площа: 132 (11х12). Похибка: 20% (рис.7 а).

- “ИНТЕХ Раскрой 2.3”: площа: 144 (12х12). Похибка: 30% (рис.7 б).

- Генетичний алгоритм, метод можливих напрямків та спрямованого переходу: отримана площа прямокутника: 117 (9х13). Похибка: 6% (рис.7 в).

Приклад 4. Мінімізація відхилення центру мас системи від заданої точки. Кількість об'єктів - 55. Метод можливих напрямків та спрямованого переходу (1 спроба). Час розв'язання - 6с., , (рис.8).

Приклад 5. Мінімізація відхилення центру мас системи від заданої точки. Розміщення об'єктів складної форми. Метод розв'язання вихідної задачі: метод можливих напрямків та спрямованого переходу. Кількість об'єктів, що розміщуються: 11. Час розв'язання: 3с. (рис. 9). Кількість ітерацій методу можливих напрямків: 34. Кількість спроб: 1. Початкове значення функції цілі: , отримане -.

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

ВИСНОВКИ

1. Побудовано математичну постановку та методи розв'язання задачі оптимізації розміщення об'єктів, кожен з яких можна розбити на прямокутники (паралелепіпеди), на опуклій області із зонами заборони.

2. Запропоновано математичну постановку та побудовано методи розв'язання задачі пошуку невигідного розміщення навантажень.

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

4. При розв'язанні поставлених задач:

- Набула подальшого розвитку ідея декомпозиції множини припустимих розв'язків на опуклі підмножини.

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

- Розроблено модифікацію методу можливих напрямків для розв'язання мінімаксних підзадач.

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

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

7. Результати дисертаційної роботи використовуються на дочірньому підприємстві “Житомир Ворд Білдінг Сістемс Україна”, на ПП “Здобуток ІІ” (м.Житомир) та в навчальному процесі у Житомирському державному технологічному університеті.

СПИСОК ОПУБЛІКОВАНИХ працЬ за темою дисертації

1. Яремчук С.І., Шаповалов Ю.О. Застосування генетичного алгоритму до задач розміщення // Вісник ЖІТІ / Технічні науки. - 2002. - №(2)21 - С.130-133.

2. Яремчук С.І., Шаповалов Ю.О. Оптимізація розміщення прямокутних об'єктів на опуклій області методом гілок та меж // Вісник ЖІТІ, 2004. - №4(31) Том 2 / Технічні науки - С.161-167.

3. Яремчук С.І., Шаповалов Ю.О. Модифікація методу можливих напрямків для задачі оптимізації розміщення // Вісник Хмельницького національного університету, 2005. - №5(69) Ч.1,Т.2 / Технічні науки - С.146-151.

4. Яремчук С.І., Шаповалов Ю.О. Оптимізація розміщення об'єктів, які можна розкласти на прямокутники //Радиоэлектроника и информатика, 2006. - №1. - С.87-90.

5. С.І. Яремчук, Ю.О. Шаповалов, І.М. Музика. Оптимізація розміщення об'єктів спеціального виду на області з зонами заборони // Вісник ЖДТУ, 2006. - №4(39) / Технічні науки. - С.258-263.

6. Шаповалов Ю.А. Размещение источников поля с использованием методов дискретного программирования // Проблемы теоретической и прикладной математики: Труды 34-й Региональной молодежной конференции. Екатеринбург: УрО РАН. - 2003. - С.161-167.

7. Яремчук С.И., Шаповалов Ю.А. Оптимизация размещения элементов прямоугольной формы методом возможных направлений // Труды пятой международной научно-практической конференции “Современные информационные и электронные технологии”. Одесса. - 2005. - С.214.

8. Яремчук С.І., Шаповалов Ю.О. Імовірнісні методи в задачах оптимізації розміщення // Тези ХХХ наукової конференції, присвяченої 45-ій річниці Житомирського державного технологічного університету. Житомир. - 2005. - С.40.

9. Яремчук С.І., Шаповалов Ю.О. Розв'язання мінімаксної задачі оптимізації розміщення прямокутників модифікованим методом можливих напрямків // Збірник матеріалів ІІІ українсько-польської наукової конференції молодих вчених “Механіка ті інформатика”. Хмельницький. - 2005. - С.211-214.

10. Яремчук С.І., Шаповалов Ю.О. Метод можливих напрямків для задачі оптимізації розміщення фігур, що складаються з прямокутників. // 10-й ювілейний міжнародний молодіжний форум "Радіоелектроніка і молодь в ХХІ ст.": Зб. матеріалів форуму. - Харків: ХНУРЕ, 2006. - C.473.

11. С.И. Яремчук, Ю.А. Шаповалов. Модификация метода возможных направлений для задачи оптимизации размещения объектов специального вида. // Электронное моделирование, 2007. - №2. - С. 29-38.

12. С.И. Яремчук, Ю.А. Шаповалов. Минимаксная задача оптимизации размещения объектов специального вида на многосвязной области. // Кибернетика и системный анализ, 2007. - №3. - С. 128-137.

АНОТАЦІЯ

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

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

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

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

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

АННОТАЦИЯ

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

Шаповалов Ю.А. Декомпозиционные методы оптимального размещения объектов в системах технического назначения. - Рукопись.

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

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

Размещение является допустимым, если все объекты попарно не пересекаются и не выходят за границы заданной области размещения.

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

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

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

Ключевые слова: оптимизация размещения, декомпозиция, метод возможных направлений, метод направленного перехода, метод вервей и границ, генетический алгоритм.

Abstract

Shapovalov Yu.A. Decomposition methods of optimal objects placement in technical purpose systems. - Manuscript.

The thesis of dissertation for a Candidate's degree in Technical Sciences by speciality 01.05.02 -- “Mathematical modeling and numerical methods”. -- Institute of modelling problems of the power engineering named after G.Ye. Pukhova of Ukrainian NAS, Kiev, 2007.

The dissertation researches the problems of the optimal placement of the objects that can be represented by the union of the rectangular (parallelepiped) objects. The placement area is a convex region with forbidden rectangular areas. The objective function is a continuously differentiable function or a function of maximum of continuously differentiable functions.

The feasible set is decomposed on a number of the convex subsets. The initial problem is solved by solving of series of sub problems that are constructed in a special way. The modified method of feasible directions for sub problems solution is designed. The following methods are developed for the sub problems selection: the method of directed transition, the modified method of branches and borders, and the modified of genetic algorithm that is combined with the directed transition method, and the random search method is used in combination with the directed transition method.

The proposed methods are implemented programmatically, their efficiency is tested for the optimal placement problem.

Key words: placement optimization, decomposition, method of feasible directions, method of directed transition, method of branches and borders, genetic algorithm.

Підписано до друку 13.08.2007. Формат 60Ч90/16. Папір друк № 2.

Умовн. друк. арк. 0.93. Обл.-вид. арк. 0.93 Тираж 100 прим. Зам. 235.

Редакційно-видавничий відділ ЖДТУ. 10005, м. Житомир, вул. Черняхівського, 103

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

...