Математична модель та методи розв'язання задачі розміщення прямокутників з урахуванням припустимих відстаней

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ПРОБЛЕМ МАШИНОБУДУВАННЯ ІМ.А.М. ПІДГОРНОГО

УДК 519.6:514.1

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

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

АВТОРЕФЕРАТ

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

кандидата технічних наук

Яськов Георгій Миколайович

Харків 2000

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

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

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

Офіційні опоненти: доктор технічних наук, старший науковий співробітник Комяк Валентина Михайлівна, Харківська академія пожежної безпеки України, професор кафедри фундаментальних дисциплін;

кандидат технічних наук, доцент Шеховцов Сергій Борисович, Університет внутрішніх справ МВС України, доцент кафедри прикладної математики

Провідна установа: Харківський державний технічний університет радіоелектроніки, кафедра прикладної математики, Міністерство освіти та науки України, м. Харків

Захист відбудеться “05” липня 2001 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.180.01 в Інституті проблем машинобудування ім. А.М. Підгорного НАН України за адресою: 61046, Харків, вул. Дм. Пожарського, 2/10.

З дисертацією можна ознайомитися у бібліотеці Інституту проблем машинобудування ім. А.М. Підгорного НАН України за адресою: 61046, Харків, вул. Дм. Пожарського, 2/10.

Автореферат розісланий “24” травня 2001 р.

Вчений секретар спеціалізованої вченої ради

кандидат технічних наук Зайцев Б.П.

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана в період з 1994 по 2000 рр. у відділі математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України згідно з планами науково-технічних робіт за такими темами:

- пошукова тема № 4 “Постановка задач та розробка математичних моделей оптимізації елементів енергоустановок” (№ 0198 И004127);

- тема № 2 “Розробка та дослідження математичних моделей задач оптимізації розміщення геометричних об'єктів” (за рішенням ВФТПЕ НАН України, пр. № 3, §16, п. 1, 17.03.98);

- пошукова тема № 12 “Дослідження математичних моделей задач оптимізації елементів енергоустановок і вибір методів їх розв'язання”.

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

Основними задачами дослідження є:

дослідження властивостей екстремальних точок області припустимих розв'язків;

модифікація методу гілок та границь для пошуку глобального оптимального розв'язку задачі;

розробка методу пошуку локального оптимального розв'язку задачі;

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

розробка проблемно-орієнтованих моделей та математичного забезпечення задачі компонування обладнання у цехах збагачувальних фабрик та задачі утилізації відходів у техногенній зоні відчуження ЧАЕС.

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

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

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

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

уперше визначено та досліджено множину екстремальних точок області припустимих розв'язків задачі розміщення прямокутників у прямокутнику з урахуванням мінімально припустимих відстаней;

уперше запропоновано модифікацію методу гілок та границь для розв'язання задачі розміщення прямокутників з урахуванням мінімально припустимих відстаней;

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

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

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

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

Практичне значення одержаних результатів полягає в розробці та реалізації на ПЕОМ програм для розв'язання оптимізаційної задачі розміщення прямокутників з урахуванням мінімально припустимих відстаней та оптимізаційної задачі розміщення кругів. Створене програмне забезпечення “Rectangles with minimal distances” використовується у ВАТ “Південдіпрошахт” при розміщенні виробничих будівель на етапі розробки генплану та при компонуванні обладнання у цехах збагачувальних фабрик. Програми можна також застосувати при створенні технології реалізації техногенної 30-кілометрової зони відчуження ЧАЕС, в енергетиці (при проектуванні машинної зали електростанцій), при розв'язанні задачі раціонального розміщення обладнання та комунікацій на різних промислових об'єктах, а також в інших предметних областях, де є необхідність урахувати технологічні обмеження на відстані між об'єктами.

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

семінарах наукової ради НАН України з проблеми “Кібернетика”: “Математичні методи геометричного проектування” (м. Харків, 1994, 2000 рр.);

науково-практичній конференції “Архитектура России: региональное своеобразие” (Росія, м. Ростов-на-Дону, Ростовський державний архітектурний інститут, 1994 р.);

47-й науковій конференції викладачів та студентів Полтавського технічного університету (Полтава, 1995 р.);

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

міжнародній конференції з прикладної математики та механіки (GAMM-98, Бремен, Німеччина, 1998 р.).

Публікації. Основні результати дисертації викладено у 7 наукових працях, із них статей у збірниках наукових праць - 4, препринтів - 1, тез доповідей - 2.

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

Структура та обсяг дисертації. Дисертація складається зі вступу, п'яти розділів, висновків, додатка та списку використаних джерел. Повний обсяг дисертації становить 127 сторінок, серед них 107 сторінок тексту, 28 рисунки, 4 таблиці та 97 найменувань літератури.

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

точка границя задача екстремальний

У першому розділі зроблено огляд літератури за темою дисертації та вибрано напрям досліджень. Розглянуто літературу, яка присвячена задачам геометричного проектування, зокрема задачам розміщення геометричних об'єктів з нелінійними обмеженнями. Вивченню цього класу задач присвячені праці багатьох учених, у тому числі В.Л. Рвачова, Ю.Г. Стояна, Р.І. Базілевича, М.І. Гіля, В.М. Комяк, С.В. Яковлєва, М.В. Новожилової, W. Dowsland, J.A.S. Ferreira, I. Terno, V. Milencovic та ін.

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

Робота є продовженням досліджень, виконаних під керівництвом члена-кореспондента НАН України Ю.Г. Стояна такими вченими, як М.В. Новожилова Л.Д. Пономаренко, І.В. Арістова, В.Г. Шміголь.

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

Для опису області припустимих розв'язків використано поняття -функції та структури нерівностей.

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

, якщо ;

, якщо та

;

, якщо ,

де та - замикання та внутрішність множин відповідно;

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

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

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

Визначення 3. Перетином структур нерівностей та називається структура нерівностей така, що , , , ,

де та - елементи матриць та відповідно.

У третьому розділі розглянуто математичну модель задачі та досліджено її особливості.

Нехай є прямокутник ширини a-const змінної довжини у системі координат XOY. Визначимо сторони прямокутника як , де , , , (рис. 1). Нехай також є орієнтовані прямокутники ширини та довжини (i=1,2,...,n)(сторони паралельні сторонам прямокутника і не допускається поворот прямокутника). Вважаємо, що полюс (початок власної системи координат) i-го прямокутника знаходиться у точці перетину його діагоналей.

Визначимо відстань між прямокутниками та як

і відстань від прямокутника до сторін прямокутника як

Нехай є обмеження на мінімально , та максимально , припустимі відстані між заданими об'єктами, i<j =1, 2,..., n, l =1, 2, 3, 4. При таких обмеженнях необхідно знайти таке розміщення прямокутників у прямокутнику , для якого його довжина є мінімальною.

Математична постановка задачі може бути зображена так. Визначити , при якому

де - вектор змінних задачі,

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

Структури та визначають множини та відповідно, які описують обмеження на мінімально та максимально припустимі відстані між прямокутниками та , i<j=1, 2,..., n, відповідно, де

,

.

Структури та визначають множини та відповідно, які описують умови розміщення прямокутників , , у з урахуванням мінімально та максимально припустимих відстаней до сторін відповідно, де

}

,.

Множина D - замкнена, неопукла, обмежена, незв'язна (в загальному випадку). Кожна її компонента зв'язності - багатозв'язна. Задача (1), (2) є багатоекстремальною задачею математичного програмування.

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

На основі особливостей математичної моделі (1), (2) проведено аналіз класу задач, які виникають для різних вихідних даних. Якщо та , то задача розміщення прямокутників з урахуванням мінімально припустимих відстаней еквівалентна задачі розміщення кругів

Досліджені точки області D, в яких може досягатися екстремум.

Визначення 4. Точка називається крайньою точкою області D, якщо існують такий окіл точки X та така площина, яка проходить через цю точку, що їх перетином є точка X.

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

Теорема 1. Якщо функція цілі досягає у точці нестрогого локального мінімума, то завжди існує крайня точка , у якій функція цілі має таке ж значення.

З теореми 1 випливає, що для пошуку глобального екстремуму функції цілі достатньо перебрати усі крайні точки області D.

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

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

Кореню дерева відповідає увесь простір .

З кожної множини , яка відповідає вершинам дерева , (k-1)-го рівня (k<2n+1), утворимо підмножини k-го рівня , ( - кількість рівнянь дерева), . Для цього візьмемо точки відповідної множини , які задовольняють рівняння, залежні від змінної , якщо k - непарне, від змінної , якщо k - парне, або від змінної Z, якщо . Множини відповідають вершинам k-го рівня.

Таким чином, кожній вершині рівня k відповідає система k рівнянь, а кінцевій вершині - система (2n+1) рівнянь.

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

Системи можуть мати не один розв'язок. Тому при побудові дерева розв'язків потрібно враховувати всі припустимі розв'язки систем.

Коли неможливо перебрати усі вершини дерева розв'язків T, пропонується скорочене дерево .

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

Для визначення локального оптимального розв'язку сформульовано умови оптимальності.

Нехай - крайня точка області D. Зобразимо D як систему нерівностей:

Нерівність називається активною в точці , якщо , та неактивною, якщо .

Позначимо , , нерівності системи (3), активні в точці . Згідно з властивостями задачі принаймні m=(2n+1) нерівностей активні в точці , тобто . Виберемо із цих нерівностей таку систему (m нерівностей), якобіан якої невироджений.

Розглянемо систему лінійних рівнянь:

де A - якобіан системи ;

- вектор множників Лагранжа.

Розв'язок системи - . Умова , i=1, 2,..., 2n+1, є необхідною та достатньою умовою досягнення строгого локального оптимального розв'язку задачі (1), (2) у точці . Описані також умови нестрогого локального оптимального розв'язку.

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

Оптимізаційний процес зображається як

,

де - крок в методі, вибір якого розглянуто в роботі.

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

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

Математична модель задачі розміщення кругів у прямокутнику має вигляд:

Знайти

де ;

- координати центра круга ;

;

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

Позначимо систему (6) як F, а набір нерівностей, які її утворюють - як .

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

Нехай

де - вектор множників Лагранжа задачі (5), компоненти якого відповідають обмеженням, активним у точці .

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

Математична модель задачі трансформації кругів (круг трансформується у круг та навпаки) має вигляд:

знайти , таке, що

де ;

;

;

;

G описується системою F за умови, що , , та нерівностями , .

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

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

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

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

Наведена загальна схема використання розроблених методів.

Розглянуті також математична модель та метод розв'язання задачі розміщення кругів у прямокутнику фіксованих розмірів з урахуванням зон заборони у вигляді кругів, яка виникає при створенні технології реалізації техногенного радіоактивного шару 30 кілометрової зони відчуження ЧАЕС.

У п'ятому розділі розглянуті результати роботи програмного комплексу “Rectangles with minimal distances”, який реалізує усі розроблені методи. Здійснено порівняння результатів розв'язання чисельних прикладів, отриманих різними методами для тих же вихідних даних, за ефективністю розв'язків та швидкодією. Результати обчислення контрольних прикладів для задач розміщення 50 прямокутників та 30 кругів наведені на рис. 2.

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

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

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

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

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

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

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

Створено програмний комплекс “Rectangles with minimal distances”, який реалізує методи, зазначені вище.

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

Результати роботи впроваджені у виробництво у ВАТ “Південдіпро-шахт”.

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

Яськов Г.Н. Метод решения задачи размещения кругов // Математическое и компьютерное моделирование в машиностроении: Сб. науч. тр. К.: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1994. С. 72-77.

Stoyan, Yu.G., Yaskov, G.N. Mathematical Model and Solution Method of Optimization Problem of Placement of Rectangles and Circles Taking into Account Special Constraints // Int. Trans. Opl Res. 1998. Vol. 5, No. 1. P. 45-57.

Stoyan, Yu.G., Yaskov, G.N. Peculiarities of a mathematical model of optimization of a placement of circles and method of searching for an approximation to a global minimum // Доп. НАН України. 2000. №1. P. 86-90.

Стоян Ю.Г., Аристова И.В., Яськов Г.Н. Адаптация метода ветвей и границ для решения задачи оптимального размещения прямоугольников с учетом минимально и максимально допустимых расстояний. Харьков, 1995. 35 с. (Препр. / НАН Украины. Ин-т пробл. машиностроения; № 384).

Яськов Г.М. Дослідження області припустимих розв'язків задачі розміщення кругів у смузі // Тр. 47-ї наук. конф. Полтав. техн. ун-ту. Ч.1. Полтава, 1995. С. 73.

Stoyan, Yu.G., Yaskov, G.N. Packing circles of various radii on a Strip // Proc. Intern. conf. on GAMM-98. Bremen (Germany). 1998. P. 135.

Аристова И.В., Яськов Г.Н. Метод решения задачи размещения прямоугольников с учетом минимальных допустимых расстояний // Автоматизация архитектурно-строительного проектирования: Межвуз. сб. Ростов н/Д: Рост. гос. архит. ин-т. 1994. С. 114-120.

Анотація

Яськов Г.М. Математична модель та методи розв'язання задачі розміщення прямокутників з урахуванням припустимих відстаней. - Рукопис.

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

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

Для розв'язання задачі розроблені нові ефективні методи.

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

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

Для розв'язання систем нелінійних рівнянь використано метод Ньютона.

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

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

Аннотация

Яськов Г.Н. Математическая модель и методы решения задачи размещения прямоугольников с учетом допустимых расстояний. - Рукопись.

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

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

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

Область допустимых решений задана условиями размещения в с учетом минимально () и максимально (), допустимых расстояний до сторон условиями непересечения и , i, j =1, 2,..., n, i>j, с учетом минимально () и максимально () допустимых расстояний.

Для описания области использована Ф-функция и структуры неравенств.

- замкнутая, невыпуклая, ограниченная, несвязная (в общем случае) область. Задача является многоэкстремальной задачей математического программирования.

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

Данная постановка охватывает широкий класс задач, в том числе задачу размещения кругов ( ).

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

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

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

Также разрабатан метод решения, в основе которого - уже упомянутый метод локальной оптимизации и идея увеличения размерности задачи за счет изменения радиусов некоторых кругов. Рассмотрена задача трансформации кругов. Это позволяет перейти к крайней точке области D, а следовательно, и к локальному минимуму, в котором значение функции меньше, чем в исходном локальном минимуме.

Разработана общая схема использования методов с учетом исходных данных.

Рассмотрены также проблемно-ориентированные модели и методы для решения задачи размещения оборудования в цехах обогатительных фабрик и задачи размещения кругов в прямоугольнике фиксированных размеров с учетом зон запрета, которая возникает при создании технологии реализации техногенной 30-километровой зоны отчуждения ЧАЭС.

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

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

Abstract

Yaskov, G.N. A mathematical model and methods of solving a placement problem of rectangles with account of admissible distances. - Manuscript.

Thesis for a candidate's degree (technical sciences) by speciality 01.05.02 - mathematical modeling and computational methods. - The A.M. Pidgorny Institute for Problems in Machinery of National Academy of Sciences of Ukraine, Kharkov, 2000.

The dissertation is a continuation of investigation of geometric design problems, namely non-linear placement problems taking into account admissible distances. A mathematical model of the problem within the framework of the -placement problems is constructed. To solve the problem new effective methods are developed.

To search for a global optimal solution of the problem an idea of branch-and-bound method is used. A tree of solutions which exhausts all extreme points of feasible region is constructed.

A method of local optimization of the problem which is based on reduced gradient method and a strategy of active set of constraints as well as a method of transition from one local minimum to another decreasing the objective due to increasing dimension of space of the problem are developed.

To solve nonlinear systems of equations Newton method is utilized.

A software which realizes the methods is developed. Effectiveness of the methods are given by numerical modelling test examples and comparing with the results obtained by the methods in existence. Taken are quality of solutions (percentage of usage of the rectangle) and runtime.

Key words: mathematical modeling, optimization, placement, minimal and maximal admissible distances, rectangle, circle.

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