Математична модель та метод розв'язання задачі розбиття і трасування з урахуванням просторової форми області

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

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

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

ім. А. М. ПІДГОРНОГО

УДК 519.168.001.57

МАТЕМАТИЧНА МОДЕЛЬ ТА МЕТОД РОЗВ'ЯЗАННЯ ЗАДАЧІ РОЗБИТТЯ І ТРАСУВАННЯ З УРАХУВАННЯМ ПРОСТОРОВОЇ ФОРМИ ОБЛАСТІ

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

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

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

Елькін Олександр Борисович

Харків 2008

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

Робота виконана на кафедрі кібернетики Харківського національного технічного університету сільського господарства ім. П. Василенка, Міністерство аграрної політики України.

Науковий керівник: доктор технічних наук, професор Путятін Валерій Петрович, Харківський національний технічний університет сільського господарства ім. П. Василенка Міністерства аграрної політики України, завідувач кафедри кібернетики.

Офіційні опоненти: доктор фізико-математичних наук, професор, член-кореспондент НАН України Скопецький Василь Васильович, Інститут кібернетики ім. В. М. Глушкова НАН України, завідувач відділом;

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

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

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

Автореферат розісланий « 11 » лютого 2009 р.

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

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

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

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

Безперервним задачам розбиття присвячені роботи Шора Н. З., Кисельової О. М., Солтана В. П., Сухарєва А. Г., Туєва С. В., Corley H. W., Roberts S. D., Francis R. I. Дискретні задачі розбиття і розміщення розглядалися в роботах Канторовича Л. В., Рвачова В. Л., Стояна Ю. Г., Залгаллера В. А., Комяк В. М., Соболя О. М., Тота Ф. Л. Безперервні і дискретні задачі трасування досліджувалися в роботах Стояна Ю. Г., Смєлякова С. В., Базилевича Р. П., Мельника Р. А., Петренка А. І., Пріма Р. К. Задачам геометричного проектування присвячені роботи Стояна Ю. Г., Гіля М. І., Ємця О. О., Новожилової М. В., Романової Т. Є., Путятіна В. П., Яковлєва С. В.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертацію виконано відповідно до Програми «Виробництво технологічних комплексів машин і обладнання для агропромислового комплексу в 1998-2005 роках», розробленою згідно з постановою Кабінету Міністрів від 01.12.1997 р., № 1341; Комплексної програми розвитку сільського господарства Харківської області в 2001-2005 роках і на період до 2010 року; держбюджетної теми «Застосування засобів автоматизації та обчислювальної техніки в АПК» Харківського національного технічного університету сільського господарства ім. П. Василенка, № 27/5-04; НДР «Розробка і впровадження у виробництво енергозберігаючих, екологічнобезпечних технологічних систем в рослинництві», ДР № 0106U991213. При виконанні цих дослідних робіт автором розроблено та впроваджено комплекс математичних моделей, програмне та апаратне забезпечення для підтримки прийняття рішень при розбитті та трасуванні з урахуванням просторової форми області.

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

Для цього в роботі поставлені та вирішені такі основні завдання:

- здійснити постановку основної задачі розбиття і трасування з урахуванням просторової форми області як оптимізаційної задачі геометричного проектування, що була запропонована Ю. Г. Стояном;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Впровадження результатів дисертації здійснено в Науково-дослідному технологічному інституті Харківського національного технічного університету сільського господарства ім. П. Василенка (акт впровадження від 31.05.2007 в додатку А, довідка про особистий внесок у додатку Б); у Науково-виробничій і експлуатаційній фірмі «СТОЗІ» (акт впровадження від 12.09.2007 в додатку В); в навчальний процес Міжнародного Соломонового університету (акт впровадження від 14.10.2008 в додатку Д) при викладанні таких дисциплін: «Математичні методи оптимізації та дослідження операцій» по кафедрі вищої математики і теорії програмування, «Моделювання систем» та «Математичні методи в інформаційних технологіях» по кафедрі програмного забезпечення автоматизованих систем.

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

Особистий внесок здобувача. Результати, опубліковані в роботах [1, 7, 11 - 13], отримані особисто здобувачем і опубліковані без співавторів. У роботі [2] автором запропонована і досліджена математична модель задачі розбиття області з урахуванням її просторової форми на підобласті рівної площі. У роботі [3] автором запропонована математична модель дискретної задачі оптимізації трас з урахуванням просторової форми області. У публікації [4] автором запропонована структура апаратної реалізації моделей задач розбиття і трасування для скорочення часових витрат на реалізацію математичних моделей. У патенті на корисну модель [5] автором запропонована структура апаратної реалізації моделі оптимізації трас в області з урахуванням її просторової форми для скорочення часових витрат. У патенті на корисну модель [6] автором запропонована структура апаратної реалізації математичної моделі задачі комбінаторної оптимізації для рішення комплексної задачі розбиття і трасування. У публікаціях [8, 9] автором запропоновані та обґрунтовані області можливого використання патентів на корисні моделі [5, 6]. У роботі [10] автором досліджуються особливості математичної моделі прикладної задачі оптимізації трас в області з урахуванням її просторової форми.

Апробація результатів дисертації. Основні результати роботи доповідалися й обговорювалися на: II Міжнародній науково-практичній конференції «Сучасні наукові досягнення - `2007», Дніпропетровськ-Бєлгород, 1-14 лютого 2007 р.; XI Міжнародному молодіжному форумі «Радіоелектроніка і молодь у XXI столітті», Харків, Харківський національний університет радіоелектроніки, 10-12 квітня 2007 р.; Міжнародному форумі молодих вчених «Ринкова трансформація економіки: стан, проблеми, перспективи», Харків, Харківський національний технічний університет сільського господарства ім. П. Василенка, 19-20 квітня 2007 р.; науково-практичній конференції «Інформатизація бізнесу очима молодих: прогресивні технології, наука, підприємництво», Харків, Харківський національний економічний університет, 17-18 травня 2007 р.; II Міжнародній науковій конференції «Сучасні інформаційні системи. Проблеми і тенденції розвитку», Харків-Туапсе, Харківський національний університет радіоелектроніки, 2-5 жовтня 2007 р.; постійно діючому семінарі «Технічна кібернетика» при кафедрі кібернетики Харківського національного технічного університету сільського господарства ім. П. Василенка, 2007-2008 рр.; постійно діючому семінарі при відділі математичного моделювання і оптимального проектування Інституту проблем машинобудування імені А. М. Підгорного НАН України, 2008 р.; IV Міжнародному салоні винаходів і нових технологій «Новое время», присвяченому 40-річчю Міжнародної Федерації асоціацій винахідників (IFIA Jubilee, 1968-2008), Севастополь, Український культурно-інформаційний центр, 25-27 вересня 2008 р., де було отримано два дипломи, одна золота і одна срібна медалі за патенти № 22708 «Пристрій для моделювання і оптимізації трас» [5] та № 22623 «Пристрій для комбінаторної оптимізації розміщення об'єктів і трасування» [6] відповідно.

Публікації. За темою дисертації опубліковано 13 робіт, у тому числі два патенти України на корисні моделі [5, 6], публікації [1 - 4] у виданнях, рекомендованих ВАК України. Публікації [7 - 13] - матеріали і тези конференцій.

Структура роботи. Дисертація складається зі вступу, 5 розділів, висновків, 4 додатків (на 4 стор.) і списку використаних джерел із 124 найменувань (на 16 стор.). Загальний обсяг дисертації - 143 сторінки, у тому числі 21 рисунок та 1 таблиця.

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

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

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

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

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

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

, (1)

, (2)

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

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

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

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

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

, (3)

де , - обмеження, що пов'язані відповідно з розбиттям і трасуванням.

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

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

, , , (4)

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

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

, (5)

та може бути задана співвідношенням

, (6)

де - функція визначення площі області;

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

- кут орієнтації розбиття.

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

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

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

, , (7)

яка може бути задана співвідношенням

, (8)

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

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

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

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

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

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

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

Апробація запропонованих у цьому розділі методу і алгоритму реалізації математичної моделі задачі розбиття з урахуванням просторової форми області здійснена при паюванні поля № 7 фермерського господарства «Олександрівське» Ізюмського району Харківської області. Це дозволило скоротити на 15% загальні витрати часу на прийняття рішення і підвищити точність реалізації математичної моделі.

На рис. 1 ілюструється результат розв'язання задачі паювання земельного угіддя. Масштаб - 1 см:800 м. При цьому: загальна площа поля га; площа кожної підобласті га; площа під розбитими ділянками - 168 га; число підобластей ; крок сітки м; м; прирощення плоско-паралельного зсуву сітки ; кут орієнтації сітки прирощення зміни орієнтації сітки ; коефіцієнт відношення зайнятої частини області до загальної - 0,964; незайнята площа - 6,21 га, що складає 3,565 % від загальної площі поля. Інші результати чисельного розв'язання задачі розбиття зведені в таблиці 1.

Витрати часу на ПЕОМ запропонованою системою підтримки прийняття рішень не перевищують 6 хвилин. Основний машинний час (до 70 %) витрачається на реалізацію операції розміщення прямокутних об'єктів в області граничних комірок.

Таблиця 1

Результати розбиття області граничних комірок на прямокутники

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

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

, , (9)

, , (10)

де - сума довжин ребер, які входять до остова ;

- мінімальна відстань до підобласті від рубежу ;

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

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

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

Властивість 1. Якщо не пуста множина, то всякий його остов - дерево.

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

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

Властивість 3. Деяке дерево лісу може містити декілька компонент із системи остовів , причому відповідні пари з них можуть мати спільну вершину з .

Властивість 4. В оптимальному -покритті деякі підобласті можуть бути досяжні з різних компонент.

Властивість 5. Оптимальне -покриття може містити тільки найдовші ребра графа .

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

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

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

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

Розділ 5. Технічні засоби для реалізації математичних моделей задач геометричного проектування. Обґрунтовано основну структуру і склад блоків апаратної реалізації математичних моделей багатомірних і багатоекстремальних дискретних задач геометричного проектування (призначень, розбиття, комунікаційних сполучень) на основі результатів теоретичного і чисельного дослідження розглядуваних моделей, проведеного в розділах 2 - 4.

Узагальнена структура апаратної реалізації математичних моделей задач геометричного проектування за патентами на корисну модель [5, 6] включає наступні основні блоки (рис. 3): блок 1 електронних моделей; блок 2 генерування та перебирання шуканих параметрів моделі; блок 3 завдання обмежень на шукані параметри моделі; блок 4 порівняння і виділення області допустимих рішень; блок 5 обчислення функції мети і визначення її раціонального значення; блок 6 введення-виводу.

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

- відсутності етапів складання і налагодження програм;

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

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

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

На IV Міжнародному салоні винаходів і нових технологій «Новое время», присвяченому 40-річчю Міжнародної Федерації асоціацій винахідників (Севастополь, 27 - 30 вересня 2008 р.), отримані два дипломи, одна золота і одна срібна медалі за патенти на пристрої № 22708 [5] і № 22623 [6] відповідно.

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

ВИСНОВКИ

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

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

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

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

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

5. Апробацію і впровадження результатів дисертаційної роботи здійснено в Науково-дослідному технологічному інституті Харківського національного технічного університету сільського господарства ім. П. Василенка (акт впровадження від 31.05.2007 в додатку А, довідка про особистий внесок у додатку Б); у Науково-виробничій і експлуатаційній фірмі «СТОЗІ» (акт впровадження від 12.09.2007 в додатку В); у навчальний процес Міжнародного Соломонового університету (акт впровадження від 14.10.2008 в додатку Д). Впровадження запропонованих у роботі математичних моделей, методів і засобів для їх реалізації дають можливість: організації системи підтримки прийняття рішень на базі розроблених математичних моделей та чисельних методів їх реалізації, що дозволяє скоротити на 15% загальні витрати часу на прийняття рішень про розбиття та трасування, а також підвищити точність розв'язання задачі оптимізації за рахунок наявної можливості аналізу більшого числа проектних рішень; застосування запропонованих і запатентованих у роботі спеціалізованих обчислювальних пристроїв для реалізації розглянутих математичних моделей, які дозволяють скоротити часові витрати на формування одного варіанта системи в раз, де - кількість дискретних елементів системи, підвищити точність реалізації математичної моделі за рахунок можливості аналізу більшої кількості варіантів системи та організувати процес автоматизації дослідження властивостей математичних моделей і методів їх реалізації (акти впровадження від 31.05.2007 та 12.09.2007 в додатках А, В).

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