Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
21
ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
РАДІОЕЛЕКТРОНИКИ
Плєхова Ганна Анатоліївна
УДК 519. 673+681.3
МОДЕЛЮВАННЯ ТА ОПТИМІЗАЦІЯ З'ЄДНАНЬ ПРИ ОБМЕЖЕННЯХ НА ГЕОМЕТРИЧНІ ПАРАМЕТРИ ТРАС
.05.02 - математичне моделювання та обчислювальні методи
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Харків - 2000
Дисертацією є рукопис.
Робота виконана в Харківському державному технічному університеті радіоелектроніки, Міністерство освіти і науки України
Науковий керівник член-кореспондент НАН України, доктор технічних наук, професор Стоян Юрій Григорович, Інститут проблем машинобудування ім. А.М. Підгорного НАН України (м. Харків), завідувач відділу математичного моделювання і оптимального проектування
Офіційні опоненти: доктор технічних наук, професор Шаронова Наталія Валеріївна, Харківський гуманітарний інститут “Народна українська академія”, завідувач кафедрою інформаційних технологій та документоведення, проректор по НДР
доктор технічних наук, ст. науковий співробітник Комяк Валентина Михайлівна, Харківський інститут пожежної безпеки, професор кафедри фундаментальних дисциплін
Провідна установа Харківський національний університет, кафедра математичного моделювання, Міністерство освіти України, м. Харків
Захист відбудеться “24” жовтня 2000 р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському державному технічному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14. fax (0572) 40-91-13
З дисертацією можна ознайомитись у бібліотеці Харківського державного технічного університету радіоелектроніки, м. Харків, пр. Леніна, 14.
Автореферат розісланий “15” вересня 2000 р.
Вчений секретар
спеціалізованої вченої ради
кандидат технічних наук Безкоровайний В.В.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність тeми. Задачі з'єднання виникають при проектуванні автомобільних шляхів і залізничних колій, інженерних мереж: магістральних трубопроводів, каналізації, водопроводу, теплових і інших типів мереж, при упорядкуванні регіонів, плануванні маршрутів пересування крупногабаритної і спеціальної техніки на пересіченій місцевості. Вони характеризуються великим різноманіттям критеріїв оптимальності й обмежень, що накладаються на геометричні параметри трас, і пов'язані з моделюванням і пошуком оптимальних трас в областях складної геометричної форми (неоднозв’язних різноманітностях), для опису яких у сучасних топогеодезичних системах використовується полігональне уявлення місцевості. При цьому функціонали та обмеження, що визначаються будівельними нормами і правилами (БНіП) такі, що до розв'язання відповідних задач не можуть бути застосовані традиційні методи варіаційного числення або математичного програмування.
Незважаючи на відсутність адекватних моделей і методів оптимізації (з функціональних класів ліній, що визначають траси), їх розробці почали приділяти значну увагу, оскільки використання навіть наближених та евристичних методів стало прибутковою статтею експорту. Тому розвиток в Україні власної бази для створення й удосконалення подібних систем автоматизації проектування і управління дозволить не тільки економити кошти на імпорті, але й створювати власні конкурентноспроможні наукоємнісні перспективні технології.
Це вказує на актуальність проблеми розробки ефективних методів і алгоритмів моделювання й оптимізації з'єднань на різноманітних функціональних класах ліній у неоднозв’язних областях при обмеженнях на кривину та інші геометричні та топологічні параметри трас з метою автоматизації процесу проектування, виключення “ручної” доробки розв’язків, одержаних на ЕОМ, і можливості оперативного одержання точних розв’язків для некласичних і некоректно поставлених задач у процесі інтерактивного проектування.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана у Харківському державному технічному університеті радіоелектроніки (ХТУРЕ) в період із 1990 по 2000 роки у відповідності до планів НДР ХТУРЕ і Інституту проблем машинобудування (ІПМаш) НАНУ у рамках держбюджетних тем: “Розробка теоретичних основ створення нових інформаційних ресурсозберігаючих технологій добування, підготовки, транспорту та розподілу нафти і природного газу” (№ДР 0197U014153), “Створення математичних методів, алгоритмів і програм розміщення геометричних об'єктів при проектуванні в машинобудуванні” (№ ДР 73013478), “Розробка методів і алгоритмів розв'язання компонувальних задач при проектуванні промислових споруд” (№ ДР 01829012355).
Мета і завдання дослідження. Метою даної дисертаційної роботи є розробка математичної моделі і методів розв'язання оптимізаційних задач з'єднання в неоднозв’язних областях при типових технологічних обмеженнях на геометричні та топологічні параметри трас, перш за все, на кривину і кількість зламів. Ця модель повинна бути поєднана з існуючими і перспективними топогеодезичними моделями полігонального зображення територій, а методи оптимізації повинні забезпечувати ефективний розв’язок основних класів прикладних задач і допускати природну інтеграцію в існуючі і перспективні системи автоматизації проектування і управління.
Для досягнення цієї мети необхідно вирішити такі задачі:
а) виділити основні критерії й обмеження, пов'язані з геометричними і топологічними параметрами трас, які необхідно враховувати при проектуванні з'єднань, і на цій основі сформулювати основну оптимізаціну задачу;
б) розробити загальну модель задач з'єднання, яка забезпечує постановку основних типів задач оптимізації і моделювання трас на необхідних функціональних класах ліній, що вимагаються, допускає поповнення та інтеграцію в існуючі системи;
в) розробити методи й алгоритми розв'язання задач пошуку оптимальних з'єднань на основних функціональних класах ліній, прийнятих для опису трас, з урахуванням вимог нормативних документів та оцінити їх обчислювальну ефективність.
Об’єкт дослідження –математичні моделі задач пошуку оптимальних мереж і маршрутів, які виникають при автоматизації проектування і управління з урахуванням ландшафта при обмеженнях на форму, взаємне положення та інші параметри з’єднань.
Предмет дослідження –розробка математичної моделі та ефективних методів розв’язання задач пошуку оптимальних трас і зв’язуючих мереж в неоднозв’язних областях при обмеженнях на кривину, кількість зламів та інші геометричні і топологічні параметри з’єднань, що відображають типові технологічні вимоги.
Методи дослідження: в роботі використовуються методи оптимізації, обчислювальні методи, обчислювальна геометрія, методи математичного моделювання і комбінаторної топології.
Наукова новизна отриманих результатів:
а) дістав подальшого розвитку загальний підхід до топологічного моделювання трас у неоднозв’язних областях на випадок трас з обмеженнями на кривину;
б) побудована математична модель основних функціональних класів ліній, яка допускає ефективну реалізацію на ЕОМ і визначає основні структурні елементи задач проектування інженерних мереж і транспортних комунікацій, а також пошуку оптимальних маршрутів на місцевості при обмеженнях і функціоналах, що враховують кривину, кількість зламів та інші параметри з'єднань;
в) поставлена основна оптимізаційна задача пошуку у неоднозв’язній області оптимальних трас при обмеженнях на кривину та інші геометричні і топологічні параметри, проведена її декомпозиція на систему базових і стандартних задач;
г) сформульовані базові оптимізаційні задачі, для яких одержані методи побудови у даній неоднозв’язній полігональній області:
- ламаної: (1) мінімальної кількості зламів; (2) мінімальної довжини на множині ламаних фіксованої кількості зламів;
- найкоротшої гладкої траси (при обмеженні на кривину), складеної з (1) відрізків і дуг кіл; (2) відрізків, дуг кіл і перехідних кривих у вигляді клотоід; (3) відрізків, дуг кіл і перехідних кривих типу кубічних парабол; (4) дуг кіл і відрізків, паралельних осям координат;
- узагальненої траси, де критерії і (або) обмеження визначаються її геометричними і надійнісними характеристиками;
д) розв’язано спектр стандартних задач, які відрізняються від базових типом граничних умов, що відображають типові вимоги проектування;
е) одержав подальший розвиток метод оптимізації з’єднуючих мереж щодо обліку критеріїв і обмежень геометричного і топологічного типу;
ж) отримані близькі до лінійних оцінки трудомісткості і витрат пам'яті для запропонованих методів і алгоритмів розв'язання базових і стандартних задач.
Практичне значення отриманих результатів. Розроблені моделі, методи й алгоритми розв'язання задач з'єднання в неоднозв’язних областях при обмеженнях на геометричні та топологічні параметри трас є ефективними в обчислювальному відношенні, основані на використанні уніфікованих полігональних моделей областей, допускають природну (для особи, що приймає рішення, ОПР) візуалізацію і дозволяють розглядувати, в різноманітних сполученнях, основні типи функціоналів, обмежень і класів ліній, що виникають при розв'язанні прикладних задач оптимізації інженерних мереж, транспортних комунікацій і маршрутів. Тому запропоновані моделі, методи й алгоритми дозволяють суттєво підвищити ефективність систем автоматизації проектування і управління за рахунок їх використання для створення нових систем або інтеграції в існуючі системи.
Практичне значення отриманих результатів підтверджується впровадженням моделей, методів і алгоритмів оптимізації полігональних трас і трас з обмеженням на кривину для всіх розглядаємих на практиці функціональних класів ліній у Харківському державному інституті з проектування шляхового господарства “Харківдіпрошлях”, як доповнення до широко використовуваного САПР автомобільних шляхів “CREDO” і перспективна основа для розвитку САПР автомобільних шляхів, у СПКБ АСУВ ТВО “Харківкомунпромвод”, з метою підвищення показників ефективності проектних рішень по трасах водопровідних мереж, що реконструюються і проектуються, у навчальний процес на кафедрі Застосування ЕОМ ХТУРЕ.
Особистий внесок здобувача. В роботах, які виконані в співавторстві, особистий внесок здобувача такий: [4] - основні елементи моделі; загальна математична модель комунікаційних мереж на місцевості при обмеженнях на кривину і надійність трас; постановка основних оптимізаційних задач і підходи до їх розв'язання. [7] - постановка базової задачі на класі SKC; точний і наближений методи її розв'язання. Методи розв'язання задач Z(SCl ), Z(SKCl ), Z(SPCl ). [9] –формалізація і класифікація нормативних, економічних і технологічних обмежень і критеріїв, що пов'язані з геометричними і топологічними характеристиками трас; методи обліку обмежень і критеріїв при розв'язанні задач з'єднання. [10] - метод виділення базових і стандартних задач при декомпозиції загальної задачі з'єднання; схема декомпозиції, яка основана на аналізі геометричних і топологічних критеріїв і обмежень. [11] - модель квазіманхеттенових трас у неоднозв’язній області; постановка основної оптимізаційної задачі і метод її зведення до задачі пошуку манхеттенової траси мінімальної довжини і мінімальної кількості зламів. [12] –формалізація задачі пошуку оптимального маршруту на неоднорідній території поза шляхової мережі; метод її зведення до варіаційної задачі оптимізації в класі еквівалентності шляхів. [13] - метод регуляризації задач з'єднання, що заснований на їх зведенні до системи стандартних задач шляхом глобальної і локальної регуляризації. [14] - клітково-полігональна модель неоднозв’язних різноманітностей і тополого-геометрична модель параметризації простору траєкторій для них.
Апробація результатів дисертації. Основні результати доповідалися та обговорювалися на таких конференціях: ХI студентська науково-технічна конференція Харківського інституту радіоелектроніки (Харків, 1991); Третя Всесоюзна науково-технічна конференція “Метрологія у гравіметрії” (Харків, 1991); Міжнародна школа “Проектування автоматизованих систем контролю і управління складними об'єктами” (Туапсе, 1992); Воронезька весняна математична школа “Сучасні методи в теорії краєвих задач” (Воронеж, 1992); 3-й Міжнародний молодіжний форум “Радіоелектроніка і молодь у ХХІ ст.” (Харків, 1999); VI Міжнародна науково-технічна конференція “Інформаційні технології: наука, техніка, технологія, освіта, здоров'я - MicroCAD-99 (Харків, 1999), а також на постійних семінарах, у тому числі: “Математичні методи геометричного проектування” Наукової ради з проблеми “Кібернетика” НАН України (Харків, 1991 - 1999); на наукових семінарах кафедр кібернетики Харківського технічного університету сільського господарства, інформатики і програмного забезпечення ХТУРЕ, будівництва автомобільних доріг Харківського автошляхового університету.
Публікації. Основні результати роботи опубліковані в 15 наукових працях (8 статтях, які опубліковані у виданнях, затверджених ВАК України, 4 тезах доповідей на наукових конференціях, 3 депонованих рукописах).
Структура та обсяг дисертації. Дисертація складається з вступу, основної частини, що складається з п'яти розділів, висновків, списку використаних джерел із 138 найменувань і додатка, в якому наведені три акти запровадження результатів дослідження, всього 177 сторінок (із них 35 сторінок –рисунки, список використаних джерел і додатки).
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність теми, якій присвячена дана дисертаційна робота, визначена мета, основні задачі дослідження, вказаний зв'язок роботи з науковими програмами, наведені дані про наукову новизну, практичне значення та впровадження результатів дослідження, про публікації й апробацію роботи, про структуру і обсяг дисертації.
Перший розділ присвячений побудові загальної математичної моделі задач з'єднання з обмеженнями на геометричні і топологічні параметри трас і аналізу існуючих методів їх розв’язання. На концептуальному рівні під задачею з'єднання розуміють побудову в даній області F трас, що описують різного роду комунікації, які зв'язують даний набір точок. Сукупність трас називають мережею s. На траси, що складають шукану мережу, накладаються обмеження Q, які визначаються технологічними вимогами БНіП. Вимагається, щоб мережа s була ефективна в розумінні деякого принципу оптимальності R(s) або функціонала f(s), що визначає вартість споруди і експлуатації трас.
Найбільш ефективний підхід до розв’язання цієї задачі, яка є NP-повною навіть для випадку ламаних в опуклій області, розвинений у роботах Ю.Г. Стояна, С.В. Смелякова. Він полягає у синтезі комбінаторних і варіаційних методів оптимізації в рамках ієрархічної системи моделей. Моделі нижнього рівня орієнтовані на розв’язання базових задач пошуку оптимальної траси за допомогою варіаційних методів, розробкою яких займалися М.М. Моісеєв, С.В. Смеляков, Н.З. Шор, а верхнього - на переборі гомотопічних сімейств шляхів і мереж на основі методів дискретної оптимізації, розвинених у роботах В. І. Михалєвича, І.В. Сергієнка, Ю.Г. Стояна, С.В. Яковлєва й ін. Неможливість повної формалізації вимог БНіП (внаслідок їх суперечливості і не повної строгості формулювань) і підлеглий характер задач з'єднання по відношенню до задач упорядкування регіонів визначає необхідність їх розв’язання в двох режимах - оптимізації та імітації, коли необхідна участь ОПР у процесі інтерактивного розв’язання задач з'єднання.
У відповідності з вимогами до точності рішень, що одержуються, і обчислювальної ефективності методів їхньої побудови, а також існуючими у світовій практиці тенденціями використання полігональних моделей місцевості в системах топо-геодезичного забезпечення, моделі областей і методи оптимізації при розв’язанні задач з'єднання повинні замість сіткових моделей (що використовуються в сучасних системах типу ReCAD, CREDO) використовувати полігональні моделі заданої для прокладки з'єднань неоднозв’язної області
(1)
де Fi , (i=1,2, …, nF), - однозв’язні області, які взаємно не перетинаються (“зони заборони” для прокладки трас) в однозв’язній області F0 на площині.
Загальною математичною особливістю гладких трас (автомобільних шляхів, залізничних і трамвайних колій) є вимога неперервності і обмеженості кривини, виконання якої необхідно для забезпечення рівня безпеки руху транспортних засобів і відсутності динамічних ударів. У зв'язку з цим у БНіП визначено, що осьові лінії трас повинні представлятися сплайнами вигляду
p = S1 r1 C1 R1 S2 r2 C2 R2 … Sm rm Cm Rm Sm+1 , (2)
де Si - відрізки, Ci - дуги кіл; ri , Ri - перехідні криві, в якості яких можуть використовуватися фрагменти клотоід і кубічних парабол.
Аналіз БНіП визначає, що більшість технологічних обмежень для розглядаємих транспортних та інженерних мереж можуть бути зведені до таких основних класів обмежень геометричного і топологічного характеру: Q1- обмеження на максимальну довжину прямолінійних дільниць; Q2 - обмеження на кут повороту α, α∈(-90º, 90º), у вершинах; Q3 - обмеження на функціональний клас гладких кривих: , SC, SKC, SPC; Q4 - умови на кінцях (визначають дотичні і їх довжину в точках і ); Q5 - примикання з допустимих дільниць; Q6 - примикання з узгодженням потоків по напрямку; Q7 - примикання з забезпеченням досяжності; Q8 - примикання до границь і трас; Q9 - топологічна структура шуканої мережі (із зв’язності, циклах).
БНіП визначають, що вибір траси трубопроводу, автомобільного шляху та ін. повинен проводитися за допомогою математичних методів по одному або декількох критеріях оптимальності (наприклад, криві слід проектувати можливо великими радіусами). При цьому критерії, як правило, виражаються через геометричні параметри трас і топологічні параметри мереж, причому деякі з них можуть не бути адитивними. Серед основних геометричних параметрів траси p слід вказати: довжину l(p), кількість m(p) колових вставок і їх радіуси кривини {ρi}i=1,m(p) (або - для ламаної - кількість зламів n(p) і кути повороту {φi}i=1,m(p)), положення траси p в області F. Вони визначають вартість будівництва c(p) і експлуатаційні витрати e(p), технологічність t(p) і надійність b(p), яка є однією із найважливіших і являє добуток таких імовірних аналогів надійності
(3)
У підсумку загальна задача оптимізації з'єднань (ЗЗЗ) з урахуванням введених критеріїв і обмежень може бути сформульована таким чином.
ЗЗЗ. У заданій області F маємо набір точок {Ai}i=1,N і деякі мережі {sj}j=1,M.. Вимагається з'єднати ці точки і мережі зв'язуючою мережею s* , складеної з ліній заданого функціонального класу SΘC так, щоб для неї виконувалися задані обмеження Q типу Q1 –Q9 і вона була найбільш ефективною в значенні заданого принципу оптимальності R(s).
Враховуючи вказану вище ефективність декомпозиції ЗЗЗ, заснованої на зведенні цієї задачі до системи базових задач на безперервних сім'ях шляхів, що допускають точне рішення, приходимо до типової основної оптимізаційної задачі (ООЗ) пошуку оптимального путі в класі еквівалентності шляхів [τ] на заданому функціональному класі ліній P(A,B) із фіксованими кінцями А, В при відповідному звуженні обмежень Q*:
ООЗ. Знайти arg extr R* (p) . (4)
pP Q* (A,B)
Далі в розділі формулюються вимоги інформаційного і обчислювального характеру до моделей і методів розв'язання поставлених задач.
У другому розділі вирішується задача глобальної і локальної декомпозиції і регуляризації ЗЗЗ на основі її зведення до системи однорідних базових задач вигляду (4), що забезпечує конструктивну регуляризацію і ефективний обчислювальний підхід до розв’язання ЗЗЗ за рахунок використання дискретних і континуальних моделей і методів. Для цього використовується дворівнева FL-модель, запропонована в роботах Ю.Г. Стояна і С.В. Смелякова. На верхньому, топологічному, рівні структура цієї моделі визначається алгебраїчним розшаруванням ліній на класи еквівалентності шляхів і мереж, а на геометричному - розгляданням у кожному з цих класів вимагаючого функціонального класу ліній. Обмеження можуть накладатися на елементи обох цих рівнів. Оскільки різноманітність F вигляду (1), має гомотопічний характер типу диска з nF≥0 дірками, структуру гомотопічної моделі ліній складає вільна група , що задає дискретизацію безперервних сімейств шляхів.
Під мережею Γ={γi}i=1,m в області F розуміється сукупність кінцевої кількості спрямляємих кривих, які самонеперетинаються та не мають загальних точок, крім кінців. Розгляд зв'язних з'єднань типу мереж, граф і ін. призводить до задач трьох класів: пошуку оптимальних мереж на топологічному рівні, без урахування геометрії області F; оптимізації вкладень абстрактної моделі в область F і побудови оптимальної мережі в області F. Для розв'язання цих задач вводяться поняття абстрактної мережі s* = (V* , R*) як кінцевого зв'язного абстрактного симпліціального комплексу K = (V* , R*), реалізація якої геометричним комплексом s = (V , R) являє геометричну мережу. Мережі s1 = (V1, R1) і s2 = (V2 , R2) гомотопні в F, якщо для їх абстрактних аналогів існує ізоморфізм ω: s1 → s2, при якому відповідність 0-симплексів означає збіг вершин у F, а відповідність 1-симплексів означає їх приналежність одному класу еквівалентності шляхів в F; мережі s1 і s2 вільно гомотопні, якщо вони гомотопні з точністю до зсуву 0-симплексів в F, і деформаційно еквівалентні, якщо вони ізоморфні і гомотопні, а різні ребра кожної з них можуть мати загальні точки тільки в з'єднаних ними базових вершинах. Зазначимо, що ізоморфізм мереж зберігає алгебраїчні інваріанти для базових вершин, але не враховує структури області F при вкладеннях в неї. Гомотопія зберігає гомотипність мереж, але не забезпечує їх ізоморфізму через можливості появи додаткових вершин. Деформованість мереж зберігає гомотопічні інваріанти.
Геометричною моделлю трас є функціональні класи ліній Λ={S, SC, SKC, SPC, W, в області F, які мають сплайнове зображення (2). На них можуть бути накладені і топологічні обмеження. Введені в роботі моделі мереж і ліній дозволили звести ЗЗЗ до системи базових задач типу (2) на різноманітних функціональних класах ліній Λ і стандартних задач на цих же класах, які відображають типові для прикладних задач сполучення обмежень і зводяться до базових задач.
У третьому розділі представлені моделі, методи і алгоритми розв’язання базових і стандартних задач пошуку оптимальних трас у неоднозв’язній області F вигляду (1) при обмеженні на кривину (кількість зламів) на функціональних класах ліній S, SC, SKC, SPC.
У першому підрозділі запропоновані моделі і методи розв’язання базових і стандартних задач мінімізації кількості зламів на класі ламаних S
р = С0, С1, … , Сn ; С0 = A, Сn = B; pU=S Q* (A,B).
Базова задача Z(Sn) мінімізації кількості зламів: n(p) → min, pU. Стандартні задачі: Z(Sn>l) лексикографічної оптимізації: l(p) → min, pUn = arg min n(p); Z(Sn+l) оптимізації згортки критеріїв: f (p) = a· l(p)+ b· n(p) ) → min; pU.
Лема 3.1. Нехай pl , pn і pnl - розв’язок задач Z(Sl), Z(Sn) і Z(Sn>l), k = v(pl). Тоді
n(pnl) = n(pn) ≥ ν(pl) –+ (1+ φi) + φk . (5)
Методи розв’язання задачі Z(Sn) полягає в симпліціальній деформації найкоротшої ламаної pl,U. Одержану ламану позначимо . Оскільки в задачі Z(Sn>l) кількість зламів n не обов'язково мінімальна, виникає
Задача 3.1. Дана траса р, яка на дільниці А0АВВ0 збігається з границею області F на відрізку OO′⊂AB. Знайти в F положення прямої A′B′, що проходить через вершини О або O′, щоб довжина ламаної B0B′A′A0 була мінімальною.
Рішення задачі 3.1 дається ітераційною формулою для кута повороту х*. Тоді рішення задачі Z(Sn>l) задається послідовним розв’язанням задачі 3.1 для симпліціально непоповнених 1-симплексів, що визначає ламану .
Теорема 1. Якщо всі симпліціальні поповнення ламаної pl (крім, можливо, фінальних) лежать у F, то путь ( ) дає рішення задачі Z(Sn>l) для кількості вершин і задач Z(Sn), Z(Sn+l), якщо в (5) досягається рівність.
Трудомісткість розв’язання задач Z(Sn), Z(Snl) i Z(Sn+l), складає κmax = (κ1 + κ2 + κ3) m, ~ ½ (κ1 + κ2 + κ3) , ~ 50 ≈ 103 .
Далі дається модель і методи рішення базової і стандартних задач у класі
p = S1C1 S2C2 … Sn-1Cn-1 Sn , n≥1.
Базова задача Z(SC). Для даних точок A, B, C, де С збігається з вершиною границі Fr F, знайти таке положення w*=(x*,r*) центру кола радіуса R що для породжуваної ним траси p* = p(x*,r*)∈ Pτw(A,B) виконується
L(p*) = min L(p) . (6)
p ∈ Pτw(A,B)
Доведено, що коло O, що визначає оптимальне розв’язок p* = p(x*,r*), проходить через точку С, координати її центру О якої задовольняють умовам
x* ∈ X = (- π/2 + δ; π/2), r* = R . (7)
При цьому мають місце такі умови зв'язку для кутів x і α (x і β, відповідно):
R [1 sin(x α)] = a sin α, (8)
R [1 sin( δ x β)] = b sin β; (9)
γ1 = π/2 + α x, γ2 = π/2 + β δ + x; (10)
а оптимальний розв’язок x* задачі (6) задовольняє умовам
a sin α = b sin β , (11)
2 x = α + δ β . (12)
Теорема 2. При виконанні нерівностей
a ≥ 2R , b≥ 2R , (13)
існує нормальний розв’язок x*∈X базової задачі (6), що визначає геометричні параметри оптимальної траси p* (x* , R), яке може бути одержано розв’язанням системи Σ вигляду (14), складеної з умов зв'язку (8), (9) і оптимальності (11), (12). У випадку порушення хоча б однієї з нерівностей в (13), система Σ може здаватися несумісною, і тоді задача (6) має сингулярний розв’язок x′*, яке може бути одержане із системи Σ′, що включає відповідно ситуації x′* ∉ X умову зв'язку і ті ж умови оптимальності (11), (12):
(14)
Якщо задані одна або дві граничних умови, що визначають кут, або мінімально допустима довжина начального відрізка, отримаємо стандартні задачі Z(SCα), Z(SCαβ), ,, які зводяться до базової задачі (6). Метод розв’язання задачі Z(SC), в загальному випадку полягає в ітераційному розв’язанні послідовності базових задач вигляду (6) до ліквідації нев’язки - кута β (α) (рис. 1). Якщо Δ - крок варіювання кута β, трудомісткість цього методу можна оцінити величиною
κSC ≈ 102 n/Δ. (15)
Рис.1. Приклад розв’язку задачі Z(SCl)
Лінії класу SKC складені з відрізків (Si), дуг клотоід (Ki) і кіл (Ci), що у загальних точках задовольняють умові трансверсальності:
p = S1 K1 C1 K1′ S2 K2 C2 K2′ S3 … Kn Cn Kn′ Sn+1 , n ≥1. (16)
Фрагменти клотоід Ki , Ki′ розглядаються на інтервалі від точки з нулевою кривиною до точки з необхідним радіусом кривини r. Натуральне рівняння клотоїди має вигляд
, (17)
де ρ - радіус кривини, a - параметр клотоіди, а s - довжина дуги.
Базова задача . Для даної ламаної знайти
p* = arg min L(p) . (18)
p ∈ Pτ,SKC [A,B]
Якщо в базовій задачі Z(SC) точка C розташована внутрі кола радіуса R на відстані r≤R від центру, то задачу (6) позначимо Z(SCrR), її розв’язок –p*rR. Метод його побудови назвемо згладжуванням клотоїдою. Умови зв'язку й оптимальності для задачі (18) такі:
R− r sin ( x− α ) = a sin α, (19)
a sin α = b sin β, (20)
2x = α + δ − β. (21)
Теорема 3. Якщо розв’язок q* базової задачі (18) в області F існує, воно задається розв’язком p*rR базової задачі (6) для радіусів r і R, що визначаються умовами (19) - (21) до яких застосовано згладжування клотоїдою.
Розглянемо клас ліній SPC, що складаються з відрізків Si , фрагментів кубічних парабол Pi і дуг кіл Ci, що задовольняють умові трансверсальності
p = S1 P1 C1 P1′ S2 P2 C2 P2′ S3 … Pn Cn Pn′ Sn+1 , n ≥1.. (22)
Використовуючи ті ж позначення, розглянемо задачу сполучення відрізків і дуг кіл фрагментом параболи, рівняння якої в системі координат Zxy має вигляд
, , (23)
де d - параметр, а xmax - межа монотонного зростання кривини.
Базова задача Z(SPC). Для заданої ламаної τ=ACB знайти
(24)
Для задачі (24) розв’язок одержуємо так, як і для (18). Цей метод розв’язання задачі (24) назвемо згладжуванням кубічною параболою.
Теорема 4. Якщо розв’язок p* ∈ F базової задачі (23) існує, воно задається розв’язком p*rR базової задачі для радіусів r і R, що визначаються умовами (19) - (21), до якого застосовано згладжування кубічною параболою.
Трудомісткість розв’язання базової задачі Z(SPC) складає
κp ≈ 50 (операцій). (25)
Для функціонала f (p) = f(l, n, k, c), p ∈ PX = Pτ,SXC [A,B], X {∅, P, K}, , маємо
f (p) = f(l, n, k, c) → min . (26)
Для розв’язання задачі (26) можна застосувати методи оптимізації, розвинені в роботах В.І. Міхалєвіча, М.М. Моісєєва, І. В. Сергієнка, базуючись на природній параметризації простору PX: вершинами {Ci}i, кутами {xi}i та ін.
У розділі 4 розглядаються модель і метод розв’язку ООЗ на класі ліній , складених з відрізків si , паралельних осям декартової системи координат Oxy і дуг кола ci з кутовою мірою π/2 і радіусом r які мають вигляд
w = s1 c1 s2 c2 … sk ck sk+1 , (k ≥ 0), (27)
і описують траси на території підприємств, де пересування транспорту здійснюється з малою швидкістю, а прямолінійні дільниці доріг паралельні осям споруд. Функція мети може відображувати довжину l(w), кількість k(w) дугових вставок вигляду ci в (27). У цій роботі метод розв’язання базової задачі мінімізації функції φ(w) - довжини l(w) і числа зламів k(w)
Z(Wτ): φ(w) → min, w∈Wτ , (28)
запропонований С.В. Смеляковим і Ю.Г. Стояном, узагальнюється на клас (27):
Базова задача : (29)
Як і для задач Z(SC), Z(SKC), Z(SPC), для (29) ставляться стандартні задачі: : ; , яка подібна , але на множині ; та : знайти допустимий шлях в . Задача Z(Wτ) має розв’язок, причому єдине щодо безперервній сім’ї екстремалей. Однак це не означає, що задача матиме розв’язок. Методи розв’язання задач , , на множині полягають в їх поліномінальному зведенні до задачі , яка, в свою чергу, зводиться до задачі Z(W). Це зведення здійснюється на підставі множини = , що визначає сім’ю екстремалей задачі (29) по області деформацій розв’язку р* задачі (28).
Теорема 5. Для існування розв’язку задач , , в області Q достатньо, щоб область ( ) була зв’язною. Тоді довжина і кількість складаючих розв’язок с-дуг дорівнюють довжині і кількості зламів розв’язання p* задачі (28). При цьому розв’язок задач p* по довжині відзначається від оптимальної р-ламаної p*∈ Wτ не більш, ніж на .
У розділі 5 розглядаються методи й алгоритми рішення ЗЗЗ для типових сполучень критеріїв і обмежень при трасуванні транспортних і інженерних мереж з системним урахуванням аспектів точності і трудомісткісті. Для розв’язання ЗЗЗ запропоновані два алгоритми. В алгоритмі 5.1 принцип розростання вихідної мережі узагальнений на випадок трас обмеженої кривини. Він орієнтований на розв’язання задач реконструкції і пошуку оптимальних маршрутів. Алгоритм 5.2 забезпечує оптимізацію на топологіях мереж із структурою, яка вимагається, і орієнтований на проектування нових мереж.
Розглянуті типові задачі типу ООЗ, актуальні при інтерактивному проектуванні гладких трас, які сьогодні вирішуються за допомогою сіткових моделей і без оптимізації: локальної оптимізації траси оптимальним фрагментом, оптимізації траси в полосі варіювання, пошуку оптимальних маршрутів руху по пересіченій місцевості, які зводяться до розглянутих базових задач.
Розглядаються інтерактивні і системні аспекти моделювання транспортних і інженерних мереж, які дозволяють інтегрувати запропоновані методи моделювання і оптимізації в процес проектування з метою підвищення ефективності роботи ОПР, методи й алгоритми обліку обмежень на досяжність і зв’язність, оптимізація мереж за критерієм надійності, оскільки БНіП потребують підвищувати надійність трас і визначають її залежність від знаходження траси і її геометричних параметрів, без резервування і з резервуванням.
ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ
1. Розроблена ієрархічна математична модель загальної задачі з'єднання, яка полягає у пошуку оптимальних з'єднань (трас і зв'язуючих мереж) у неоднозв’язних областях, та виникає при проектуванні транспортних і інженерних мереж і управлінні рухом техніки по пересіченій місцевості, в рамках якої ця задача зведена до системи базових і стандартних задач пошуку оптимальних трас. Використання цієї ієрархічної структури моделей в системах прийняття рішень дозволяє вирішити проблему адекватного моделювання з'єднань у неоднозв’язних полігональних областях щодо точності, обчислювальної ефективності і відсутності інформаційної надлишковості для всіх нормативно заданих у БНіП функціональних класів ламаних і гладких ліній {S, SC, SKC, SPC, при обмеженнях на кривину та інші геометричні і топологічні параметри трас.
. Проведена глобальна декомпозиція і регуляризація ЗЗЗ, які засновані на її зведенні до основної оптимізаційної задачі, типові випадки якої подані системою базових задач оптимізації в неоднозв’язній полігональній області на різноманітних функціональних класах ліній: мінімізації числа зламів на класі , побудови найкоротшої траси обмеженої кривини на класах ліній SC, SKC, SPC, , що містять відрізки, дуги кіл, клотоід і кубічних парабол. Методи розв’язання цих задач засновані на отриманих умовах оптимальності.
. Поставлені стандартні задачі, що відображають типові варіанти задач проектування і управління і тих, що відзначаються від базових іншим сполученням критеріїв, обмежень і граничних умов. Запропоновано методи й алгоритми їх розв’язання на основі їх зведення до базових задач.
. Для методів і алгоритмів розв’язання базових і стандартних задач отримано оцінки трудомісткості, які мають переважно лінійний характер.
. Поставлена задача оптимізації функціонала, що залежить від геометричних параметрів траси і її знаходження на неоднорідній території, що зведена до типової варіаційної задачі, параметри якої визначається базовими задачами.
. Поставлені основні задачі оптимізації надійності трас (за їх геометричними характеристиками) і мереж (за складаючими їх трасами), які зведени до базових задач і відомих задач на графах, що ефективно вирішуються.
. Запропонований процедурний підхід до рішення ЗЗЗ, орієнтований на реконструкцію і будівництво нових мереж. Дано оцінки його трудомісткості.
. Показано, що введені моделі ліній, критеріїв і обмежень адекватні вимогам нормативних документів для розглянутого класу задач з'єднання і систем полігонального уявлення земної поверхні, відповідають вимогам поповнювання систем і організації інтерактивного проектування і управління.
. Практичне використання розроблених моделей, методів і алгоритмів підтвердило їх ефективність для розв’язання задач проектування транспортних і інженерних мереж.
ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
АНОТАЦІЯ
Плєхова Г. А. Моделювання та оптимізація з'єднань при обмеженнях на геометричні параметри трас. –Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Харківський державний технічний університет радіоелектроніки, Харків, 2000.
У дисертаційній роботі розроблена ієрархічна математична модель загальної задачі з'єднання, яка актуальна для автоматизації проектування інженерних і транспортних комунікацій, пошуку оптимальних маршрутів на місцевості і полягає в пошуку в неоднозв’язній області оптимальних зв'язуючих мереж і трас на різноманітних функціональних класах ліній при обмеженнях на кривину й інші геометричні і топологічні параметри з'єднань.
Для нормативно заданих класів ліній, обмежень і функционалів поставлені базові і, зведені до них, стандартні оптимізаційні задачі, для яких одержані умови оптимальності і відповідні їм методи рішення, які мають лінійну трудомісткість. Адекватність введених моделей ліній, критеріїв і обмежень вимогам нормативних документів підтверджені упровадженням алгоритмів і програм.
Ключові слова: з'єднання, математична модель, оптимізація, ламана, крива, кривина, клотоіда, гомотопічний клас, будівельні норми і правила.
ABSTRACT
Plechova G.A. Modeling and optimization of connections upon restrictions on geometrical parameters of routes. – Manuscript.
Thesis for a candidate’s degree in speciality 01.05.02 - mathematical modeling and calculating methods. - Kharkov State Technical University of Radioelectronics, Kharkov, 2000.
The thesis presents hierarchical mathematical model for the general connection problem being actual for a computer aided laying-out of the networks (water-supply line, railway system, etc.) and routes for vehicles at a rugged terrain. This problem consists in searching of optimal routes and networks in a given non-singly-connected manifold, that are specified on a special functional classes of curves under constraints on curvature and other geometrical and topological restrictions imposed onto connection parameters.
For the standard types of curves, constraints, and functionals the basic optimization problems are stated, as well as the standard problems being reduced to the former ones, for which the optimality conditions and respective optimization methods are obtained that show linear time consumption. Adequacy of the proposed models of curves, criterions and constraints to the requirements of the design standards is supported by introduction of the developed algorithms and software.
Key words: connection, mathematical model, functional, optimization, polygonal line, curve, curvature, clothoid, homotopic class, civil engineering standards.
АННОТАЦИЯ
Плехова А.А. Моделирование и оптимизация соединений при ограничениях на геометрические параметры трасс. –Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 –математическое моделирование и вычислительные методы. –Харьковский государственный технический университет радиоэлектроники, Харьков, 2000.
В диссертационной работе разработана иерархическая математическая модель общей задачи соединения (ОЗС) о поиске оптимальных соединений (трасс и связывающих сетей) в неодносвязных областях, которая возникает при проектировании транспортных и инженерных сетей и управлении движением транспортными средствами вне дорожной сети, в рамках которой эта задача сведена к системе базовых и стандартных задач поиска оптимальных трасс. На топологическом и геометрическом уровне эта модель отражает типовые ограничения и критерии, которые возникают при проектировании автомобильных дорог и железнодорожных линий, различных типов трубопроводов, а также при поиске оптимальных маршрутов перемещения специальной техники (пожарных машин, автомобилей, оборудованных для перевозки относительного гравиметра, и др.) по пересеченной местности в заданные районы.
Использование этой структуры моделей в системах принятия решений позволяет решить проблему адекватного моделирования соединений в неодносвязных полигональных областях в смысле точности, вычислительной эффективности и отсутствия информационной избыточности, причем для всех нормативно заданных в приложениях функциональных классов ломаных и гладких линий {S, SC, SKC, SPC, при ограничениях на кривизну и иные геометрические и топологические параметры трасс.
Произведена глобальная декомпозиция и регуляризация ОЗС, основанные на ее сведении к основной оптимизационной задаче (ООЗ), типовые случаи которой представлены системой базовых задач оптимизации в неодносвязной полигональной области на различных функциональных классах линий: минимизации числа изломов на классе ломаных S, построения кратчайшей трассы ограниченной кривизны на классах линий SC, SKC, SPC, , включающих отрезки, дуги окружностей и сопрягающие их клотоиды или кубические параболы, использование которых необходимо для обеспечения безопасности движения и исключения динамических ударов. Предложены методы решения этих задач, основанные на полученных условиях оптимальности. Поставлены стандартные задачи, отражающие типовые варианты задач проектирования и управления и отличающиеся от базовых иным сочетанием критериев, ограничений и граничных условий. Предложены методы и алгоритмы их решения, основанные на сведении к базовым задачам.
Для методов и алгоритмов решения базовых и стандартных задач получены оценки трудоемкости и затрат памяти, которые имеют преимущественно линейный вид. Предложен процедурный подход к решению ОЗС, ориентированный на реконструкцию и строительство новых сетей. Даны оценки его вычислительной эффективности. В частности, поставлена задача оптимизации функционала, зависящего от геометрических параметров трассы и ее положения на неоднородной территории, которая сведена к типовой вариационной задаче, пространство параметров которой определяется решением системы однородных базовых задач. Поставлены основные задачи оптимизации надежности соединений для трасс (по их геометрическим характеристикам) и сетей (по составляющим их трассам), предложены алгоритмы их сведения к базовым задачам и известным эффективно решаемым задачам на графах.
Показано, что введенные модели областей, линий, критериев и ограничений адекватны требованиям нормативных документов для рассматриваемых задач интерактивного управления и проектирования транспортных и инженерных сетей, принятому в мировой практике использованию топо-геодезических систем полигонального представления земной поверхности и требованиям пополнимости систем. Эффективность предложенных в работе моделей, методов и алгоритмов подтверждена при их практическом использовании.
Ключевые слова: соединение, математическая модель, оптимизация, ломаная, кривая, кривизна, клотоида, гомотопический класс, строительные нормы и правила.
Відповідальний випусковий В.В.Безкоровайний ________________________________________________________________
Підп. до друку 12. 09. 2000 р.
Формат 60х84 1/16. Папір друк. офсетний.
Умов. друк. арк.1,1. Облік. вид. арк. 1.0
Зам. № 2 – Безкоштовно Тираж 100 прим.
ХТУРЕ, 61166, Харків, просп. Леніна, 14
Надруковано в учбово-виробничому видавничо-поліграфічному центрі ХТУРЕ
, Харків, просп. Леніна, 14