Безкоровайний Володимир Валентинович

УДК 519.71: .896

МЕТОДИ АНАЛІЗУ І СИНТЕЗУ РІШЕНЬ ПРИ АВТОМАТИЗОВАНОМУ ПРОЕКТУВАННІ СТРУКТУР ТЕРИТОРІАЛЬНО РОЗПОДІЛЕНИХ ОБ’ЄКТІВ

05.13.12 – системи автоматизації проектувальних робіт

Автореферат

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

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

Харків – 2004

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

Робота виконана у Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий консультант – доктор технічних наук, професор Петров Едуард Георгійович, Харківський національний університет радіоелектроніки, завідувач кафедри системотехніки.

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

доктор технічних наук, професор Федорович Олег Євгенович, Національний аерокосмічний університет ім. М.Є.Жуковського "Харківський авіаційний інститут", завідувач кафедри автоматизованих систем управління;

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

Провідна установа – Київський національний університет будівництва і архітектури (кафедра інформаційних технологій) Міністерства освіти і науки України, м. Київ.

Захист відбудеться " 8 " лютого 2005 р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.02 Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки, м. Харків, просп. Леніна,14.

Автореферат розісланий 06.01.2005 р.

Виконуючий обов’язки вченого секретаря

спеціалізованої вченої ради Кривуля Г.Ф.

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

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

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

Прикладами подібних територіально розподілених систем (ТРС) можуть служити інформаційно-обчислювальні мережі (ІОМ), муніципальні системи оперативного обслуговування, транспортні системи, виробничо-збутові комплекси, територіальні автоматизовані системи керування.

Сучасні методи проектування великомасштабних об’єктів базуються на теорії складних систем, основи якої викладені в роботах Г.Гуда (H.Good), Р.Маккола (R.Machol), М.Месаровича (M.Mesarovic), Д.Мако (D.Macko), Я.Такахари (Y.Takahara), Д.Лесдона (D.Lesdon), Н.П.Бусленко, Дж.Кліра (G.Klir), розвинуті в процесі розв’язання задач структурного аналізу, синтезу й оптимізації окремих видів систем у роботах П.Гріна (P.Green), Р.Лакки (R.Lucky), Л. Клейнрока (L.Kleinrock), В.М.Глушкова, В.К.Акінфієва, М.Д.Годлевского, Ю.П.Зайченка, І.В.Кузьміна, Е.Г.Петрова, В.П.Путятіна, М.Шварца, О.Є.Федоровича, А.Д.Цвіркуна, Б.Я.Еттінгера, Е.А.Якубайтіса, Г.Ф.Янбиха.

В даний час для розв’язання задач структурного синтезу при створенні і модернізації ТРС усе ширше використовуються технології і засоби систем автоматизованого проектування (САПР). Якість одержуваних проектних рішень багато в чому визначається ефективністю математичного забезпечення САПР, основу якого складають процедури аналізу і синтезу варіантів побудови ТРС.

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до планів Міністерства освіти і науки України у Харківському національному університеті радіоелектроніки в рамках науково-дослідних робіт: за темою № "Розробка комплексу математичних моделей соціально-економічного розвитку регіону з урахуванням ефективності використання інфраструктури і комунальних ресурсів" (№ ДР U012128); за темою № "Розробка принципів, методології проектування і створення інформаційно-аналітичної системи підтримки прийняття рішень при керуванні соціально-економічним розвитком регіону" розділ 3 "Розробка математичних моделей і алгоритмів синтезу, розвитку й експлуатації регіональних розподілених систем обслуговування" (№ ДР U001342); за темою №165 "Розробка теоретичних основ проектування систем підтримки прийняття рішень при керуванні соціально-економічним розвитком регіону" розділ 2 "Розробка математичних моделей, методів і алгоритмів розв’язання задач реінжинірингу територіально розподілених систем" (№ ДР U001564). Здобувач брав участь у виконанні робіт за темою №  як виконавець, за темами № і № як науковий керівник розділів.

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

Для досягнення поставленої мети необхідно:– 

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

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

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

розробити математичні моделі і методи для розв’язання задач структурно-топологічної оптимізації в процесі реінжинірингу ТРС, що враховують обмеження, пов’язані з існуючими структурами, і враховують можливості їхньої трансформації;– 

удосконалити існуючі і розробити нові математичні моделі і методи розв’язання задач структурно-топологічного синтезу ТРС, що відповідають різним наборам вимог "розмірність задачі – точність розв’язку – час розв’язання", а також різним ступеням визначеності мети і даних;– 

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

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

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

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

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

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

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

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

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

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

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

7. Удосконалено моделі вибору проектних рішень за умов інтервальної невизначеності вихідних даних, що дозволяє знизити часову складність методів розв’язання задач у порівнянні з традиційними методами (на основі критеріїв Лапласа, максимаксу, Вальда, Гурвиця, Севіджа).

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

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

10. Одержали подальший розвиток моделі синтезу топології кільцевих і радіально-кільцевих структур ТРС шляхом включення в них нової змінної оптимізації – місця розміщення центру. Удосконалено точні і наближені методи розв’язання задач шляхом зведення їх до задач комівояжера з обмеженнями і без обмежень.

11. Удосконалено методи оцінки живучості в задачах синтезу й оптимізації ТРС із надлишковими і ненадлишковими структурами шляхом врахування питомої ваги зв’язаних елементів при ушкодженнях елементів і (чи) зв’язків між елементами об’єкта. Одержали подальший розвиток методи структурно-топологічної оптимізації централізованих і багатозв’язних ТРС підвищеної живучості із заданим значенням показника зв’язності вершин у частині реалізації спрямованого перебору варіантів за кількістю перемичок і місцями їхнього підключення до виконання обмежень по показниках оперативності і живучості.

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

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

Практичне значення результатів підтверджується їхнім впровадженням. Результати дисертаційної роботи впроваджені в держбюджетні науково-дослідні роботи (акт від 17.05.2004 р.) і в навчальний процес (акт 24.05.2004 р.) Харківського національного університету радіоелектроніки. Ітераційна схема системного проектування, математичні моделі і методи структурно-топологічної оптимізації об’єктів при розв’язанні задач їхнього синтезу і реінжинірингу, багатофакторного оцінювання і вибору проектних рішень використані: у ВАТ "Хартрон" при синтезі структури мережі збору первинної інформації в рамках створюваних автоматизованих систем керування технологічними процесами для атомних електростанцій (довідка від 06.09.2004 р.); на ДП "Завод ім. В.О.Малишева" для визначення структури з’єднання підмереж заводоуправління і комерційного управління (довідка  від 13.09.2004 р.); у Національній акціонерній компанії "Нафтогаз України" при проектуванні і плануванні розвитку телекомунікаційних і інформаційно-обчислювальних мереж, призначених для розв’язання задач керування магістральними нафто- і газопроводами (довідка від 04.10.2004 р.); при виконанні держбюджетних тем у ВАТ "АТ Науково-дослідний інститут радіотехнічних вимірювань" (акт від 02.11.2004 р.); у Головному управлінні з питань надзвичайних ситуацій і цивільного захисту населення Харківської обласної державної адміністрації при створенні розподіленої інформаційної системи і розробці структури спеціалізованих засобів територіальної підсистеми (акт від 25.10.2004 р.).

Особистий внесок здобувача. Усі наукові результати дисертаційної роботи отримані здобувачем особисто й опубліковані в роботах [1  ]. У роботах, опублікованих зі співавторами, здобувачу належать: у [1] – математичні моделі, метод, алгоритми і програмне забезпечення задач синтезу топологічних структур мереж передачі даних; у [2] – постановка і декомпозиція проблеми синтезу ТРС, дискретні математичні моделі, методи й алгоритми синтезу ТРС, модель і метод розв’язання задачі планування розвитку ТРС, розв’язання прикладних задач синтезу мереж передачі даних, зональної мережі контейнерних терміналів, маршрутів багаторівневої транспортної системи; у [3] – вид, модель і метод ідентифікації універсальної функції корисності часткових критеріїв; у [6] – модифікація методу спрямованого перебору локальних екстремумів для синтезу топологічних структур ІОМ; у [7] – модель і метод оцінки кількості вузлів в ІОМ із радіально-вузловою структурою; у [8] – модифікація еволюційного методу синтезу деревоподібних структур; у [9] – модифікація методу спрямованого перебору локальних екстремумів, що знижує кількість потенційних місць розміщення вузлів; у [10] – багатофакторна постановка і модель задачі синтезу топології централізованих мереж; у [11] – формалізоване представлення ТРС як об’єкта проектування; у [23] – модель і метод структурного синтезу, а також планування розвитку структур територіально розподілених об’єктів за умов невизначеності вихідних даних; у [25] – програмна реалізація і практичне застосування схеми прийняття рішень за умов невизначеності; у [27] – підхід до оцінки раціональних значень структурних параметрів ТРС; у [28] – схема і склад ітераційної процедури структурно-топологічної оптимізації мереж передачі й обробки інформації; [31] – моделі і методи структурно-топологічного синтезу інформаційно-обчислювальних мереж; у [33] – модель задачі реінжинірингу топологічних структур ТРС; у [34] – метод ідентифікації параметрів адитивних моделей багатофакторного оцінювання; у [35] – метод структурно-топологічної оптимізації централізованих систем; у [37] – постановка і підхід до розв’язання задачі моделювання динаміки функціонування ТРС оперативного обслуговування; у [38] – схема моделі для аналізу динаміки процесу функціонування об’єкта.

Апробація результатів дисертації. Основні теоретичні і практичні результати дисертаційної роботи доповідалися й одержали схвалення: на 39. Internationales Wissenschaftliches Kolloquium (Ilmenau, Germany, 1994); на 2-ій Національній науковій конференції "Інформатика: теорія, технологія, техніка – ІТТТ-95" (Одеса, 1995 р.); на Міжнародній конференції "Теорія і техніка передачі, прийому й обробки інформації" (Туапсе – Харків, 1995, 1997-2004 р.); на 2-ій науково-методичній конференції "Використання комп’ютерних технологій у навчальному процесі" (Харків, 1998 р.); на 5-ій Міжнародній науково-технічній конференції "Контроль і керування в складних системах – КУСС-99" (Вінниця, 1999 р.); на науково-методичній конференції "Інформаційні технології в освіті і управлінні" (Нова Каховка, 1999-2004 р.); на семінарі "Системний аналіз, математичне моделювання і прийняття рішень у соціально-економічних і технічних системах" наукової ради НАН України по проблемі "Кібернетика" (Харків, 1999-2002 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в
38 роботах, з них: 2 монографії, 22 статті в журналах і збірниках наукових праць, що включені до переліків ВАК України, 14 доповідей і тез, опублікованих у матеріалах наукових конференцій.

Структура й обсяг дисертації. Дисертація складається зі вступу, шести розділів, висновків, списку використаних джерел з 316 найменувань (на 31 стор.), двох додатків (на 25 стор.), містить 51 ілюстрацію (на 34 стор.), 41 таблицю (на 32 стор.). Загальний обсяг роботи – 389 сторінок.

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

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

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

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

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

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

Другий розділ присвячений розробці теоретико-методологічних основ вирішення проблеми синтезу територіально розподілених об’єктів. У ньому розглянуті питання: формалізації структурного опису і цілей створення ТРС; вибору і формалізації критеріїв оцінки ефективності ТРС; декомпозиції проблеми структурного синтезу систем; синтезу логічної схеми системного проектування; розробки технології формування і вибору розв’язків задачі системного проектування ТРС; реалізації спрямованого перебору варіантів при оптимізації топологічних структур у процесах синтезу і реінжинірингу ТРС.

Структура < (де e – множина елементів; r – множина відношень між елементами) будь-якої ТРС може бути реалізована множиною різних топологій G*= {g}. Виходячи з цього, кожній з топологічних реалізацій структури gG* відповідає свій набір властивостей системи  : (e, r, g )  де – деяке відображення. Опис ТРС на всіх етапах життєвого циклу має відображати її топологічні властивості sде g – топологічна реалізація структури <r. При цьому g {E,R,A }, де gE,R,A – топології елементів, відношень (зв’язків) і переміщень інформації, енергії, інших ресурсів, зумовлених, технологією А функціонування системи.

Для оцінки якості варіантів побудови ТРС використовується методологія функціонально-вартісного аналізу. Згідно з цією методологією метою створення будь-якої ТРС є максимізація співвідношення ефекту від її функціонування Q і витрачуваних на це ресурсів С. Функціональний ефект ТРС подається неубуваючою функцією від витрачених на його досягнення ресурсів (вартості) , де й – узагальнені скалярні оцінки ефекту і вартості ТРС; F – оператор, що відображає стратегію використання ресурсів, зумовлену вибором варіанта побудови ТРС s . Задача вибору варіанта побудови ТРС за комплексним критерієм подається у вигляді

, |

(1)

де opt – оператор, що визначає конкретний вид критерію ефективності.

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

Задано множини: потребуючих обслуговування територіально розосереджених об’єктів Ob {obi}, і їхніх характеристик Obj; типових елементів і зв’язків , на базі яких створюється система; місць можливого розміщення елементів ; припустимих технологій її функціонування . Необхідно визначити: кількість елементів системи ; їхні типи , , ; місця розміщення елементів , , ; множини і типи зв’язків між елементами , , ; підмножини об’єктів, що обслуговуються кожним з елементів , , і технології їхнього обслуговування , , . Метою є екстремізація обраних часткових критеріїв ефективності: витрат С,; оперативності , ; живучості ( , .

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

MetaTask = {Taskl}, Taskl = {}, , , | (2)

де Taskl  – множина задач, що належать до рівня l; nl  – кількість рівнів опису ТРС; i – номер задачі; il  – кількість задач, що підлягають розв’язанню на рівні l.

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

:, , , (3)

де  – відповідно вхідні і вихідні дані i-ї задачі l-го рівня.

Запропонована трирівнева модель декомпозиції проблеми, що містить описи об’єктів на мета-, макро- і мікрорівнях. На метарівні проблема MetaTask розглядається в цілому. Задачі макрорівня по своїй суті є задачами системного проектування і відрізняються обмеженнями, що відбивають специфіку основних етапів життєвого циклу ТРС:  – формування вимог і розробка технічного завдання;  – системне проектування;  – планування розвитку;  – структурна адаптація;  – реінжиніринг. Основні задачі мікрорівня пов’язані з вирішенням питань системного проектування ТРС: – вибір принципів побудови; – вибір структури; – визначення топології елементів і зв’язків; – вибір технології функціонування; – визначення параметрів елементів і зв’язків; – оцінка ефективності варіантів і вибір рішень.

Для всіх задач макро- і мікрорівня розроблені моделі виду (3). На основі аналізу моделей підзадач Task, задачі за обмеженнями, вхідними і вихідними даними синтезована лінійна логічна схема системного проектування ТРС: Task Task Task Task Task Task.

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

За результатами аналізу комплексу задач проблеми сформульовані вимоги, яким повинні задовольняти ефективні методи (процедури) їхнього розв’язання і розроблена ітераційна логічна схема системного проектування ТРС

CirDes = (Tasks, InDat, Res, DesDec, ProcDec), | (4)

де Tasks={Task} – упорядкована множина задач проектування; Task – i-та задача l-го рівня; InDat – множина вихідних даних; Res – множина обмежень; DesDec – множина проектних рішень; ProcDec – відображення, що має смисл проектної процедури.

На основі ітераційної логічної схеми (4) (рис. 1) і особливостей задач проблеми одержав подальший розвиток метод формування рішень задачі системного проектування ТРС, що передбачає: ітераційне розв’язання задач Task, (розв’язуваність за входами); використання банків методів для розв’язання кожної із задач, що мають різну складність і точність (розв’язуваність за ресурсами); інтерактивність процедур (розв’язуваність за процесом); використання прийомів, що знижують трудоємність розв’язання задач. Така схема дозволяє підвищити точність одержуваних рішень.

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

Вважатимемо, що центр і вузли системи утворюються на базі її елементів. Витрати на ТРС можна представити, такими що складаються з витрат на її центр СС, вузли СU , елементи СЕ, а також зв’язки між вузлами CUU, вузлами і центром CUC , елементами і вузлами CEU у вигляді

C = СС + СU + CUU + CUC + СЕ + CEU. | (5)

Залежність витрат (5) від кількості вузлів у системі C() є багатоекстремальною. Її локальні мінімуми відповідають оптимальним розв’язкам задачі розміщення фіксованої кількості вузлів системи  , , ,…пЕ – . Обгинаюча локальних мінімумів функції (5) є одноекстремальною залежністю від кількості вузлів . Це дозволяє здійснювати перебір в обмеженій області :  чи : пЕ, пЕ – ,…, , де – оптимальна кількість вузлів у системі.

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

Витрати на елементи (вузли, центр) у новій структурі як функція від кількості вузлів представлені у вигляді C1() = СЕ + CU () + СС , витрати на зв’язки між ними – C2() = CEU () + CUU () + CUC (), а їх мінімальні і максимальні значення – C1min(), C1max(), C2min(), C2max(). З урахуванням цього мінімальні і максимальні додаткові витрати на нову структуру можна подати у вигляді (рис. 2)

Cmin() C1min() C2min();

Cmax() C1max() C2max(). | (6)

Обгинаюча локальних мінімумів функції C()  може виявитися багатоекстремальною. Для розв’язання задачі визначимо відрізок [], що гарантовано містить оптимум функції додаткових витрат C(). З цією метою знайдемо оптимум функції максимальних додаткових витрат Cmax() (6), вирішивши задачу  arg  (рис. 2). Це визначає мінімум витрат у випадку повної зміни структури ТРС. Визначимо відрізок [], на якому значення функції витрат C() може бути не гіршим, ніж знайдений мінімум . Для визначення оптимального розв’язку необхідно пройти відрізок [], змінюючи значення кількості вузлів системи  . Часова складність запропонованого методу [b(n)], де b(n) – складність методу структурно-топологічного синтезу ТРС.

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

Підхід, що використовується до розв’язання задач аналізу і вибору проектних рішень, базується на теорії корисності, теорії нечітких множин, моделях і методах багатофакторного оцінювання. Ситуація вибору розв’язку кожної із задач Task проблеми визначається завданням її вихідних даних InDat і обмежень Res. Етапи оцінки корисності варіантів U(s) є евристичними і присвячені виявленню переваг особи, що приймає рішення (ОПР), і формуванню на цій основі правила для ранжирування альтернатив s

Для зменшення області пошуку кращого рішення пропонується двоступінчаста процедура формування множини компромісів K з виділенням наближеної області компромісів (НОК) SPK паралельно процесу генерації варіантів. Для опуклих множин альтернатив S* запропонований метод формування НОК. Він передбачає визначення на множині допустимих рішень S* найкращих рішень за кожним з часткових критеріїв . Отримані при цьому значення часткових критеріїв визначають крайні точки границі НОК  (), . Гіперплощина, що проходить через граничні точки  (), , відтинає від області S* наближену область компромісів . Запропонований метод дозволяє одержувати НОК меншого розміру, ніж НОК, побудована за методом інтервального завдання області.

У моделях оцінювання і вибору рішень пропонується використовувати функції загальної корисності U(s), побудовані на основі ФК часткових критеріїв , . Запропоновано універсальну ФК, що дозволяє реалізувати лінійні, опуклі, увігнуті і комбіновані залежності від значень часткових критеріїв , вигляду (рис. 3) |

(7)

де  – нормоване значення координати точки перегину функції;  – нормоване значення i-го часткового критерію для s-го варіанта побудови ТРС;  – коефіцієнти, що визначають вид залежності відповідно на початковому і кінцевому відрізках функції.

Рис. 3. Універсальна функція корисності (7)

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

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

,

    , |

(8)

де {=,}; m – кількість часткових критеріїв; n = Card) – потужність відношення .

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

, | (9)

де – норма вектора нев’язки; – матриця коефіцієнтів для системи (9), елементи якої визначаються за співвідношенням = ; – номер пари у бінарному відношенні ;

При виборі рішень за умов невизначеності вихідних даних використано апарат інтервального аналізу. Позначимо вхідні параметри проектної задачі через , (де  Card – кількість вхідних параметрів),  In, а вихідні – через , (де  Card – кількість вихідних параметрів), Out. До числа вхідних параметрів проектних задач In { } належать: вага (потреба) об’єктів, що обслуговуються, вартості і продуктивності елементів, вузлів, центру, а також зв’язків між ними. Інтервальне представлення i-го вхідного параметра має вигляд

[], ] {    ,   ,  }, , | (10)

де , – нижня і верхня границі параметра.

До числа вихідних параметрів проектних задач Out {} належать: показники вартості С, оперативності , живучості варіантів побудови ТРС, а також значення функцій корисності для перерахованих показників

[С] , ]; [ ] , ]; [ ] , ]; [ ] , ]. | (11)

Формально задача зведена до вибору для заданого набору інтервально заданих вхідних параметрів (10) найкращого варіанта побудови ТРС за значеннями інтервально заданих вихідних параметрів (11). Це дозволяє знизити часову складність методів розв’язання задач у порівнянні з традиційними методами (на основі критеріїв Лапласа, максимаксу, Вальда, Гурвиця, Севіджа). Розглянуто задачу планування розвитку ТРС за умов інтервальної невизначеності вихідних даних.

Четвертий розділ присвячений розробці моделей і методів синтезу топологічних структур централізованих об’єктів. У ньому розглянуті питання: визначення кількості і топології елементів ТРС; оцінки оптимальної кількості підсистем у системах з регулярно розподіленими елементами; попередньої оцінки витрат на створення й експлуатацію систем; синтезу систем з радіально-вузловими і деревоподібними структурами; аналізу ефективності методів синтезу систем з централізованими структурами.

Задача визначення кількості елементів, місць їхнього розміщення і списків об’єктів, що обслуговуються ними, зведена до задачі групування (класифікації) множини об’єктів, що потребують обслуговування Ob={оbі}, . Для кожної пари об’єктів оbi, оbj Ob задане значення відстані ij = оbi, оbj ), що відображає ступінь їхньої територіальної близькості чи подібності. Метою є розбивка всієї множини об’єктів Ob на n непересічних підмножин {Obk}, , , , .

Пропонується групувати об’єкти таким способом, щоб для обслуговування кожної з груп використовувався один елемент ТРС, тобто n=, де  – кількість елементів, необхідних для обслуговування всієї множини об’єктів Ob={оbi}, . Для спільного визначення кількості і топології елементів системи задача розв’язувалася за критерієм

, | (12)

де  – оцінка вартості топологічної структури на рівні елементів ТРС; ,  –  відповідно оцінки вартості міжгрупових і внутрішньогрупових зв’язків, ; – кількість елементів системи; Obk – множина об’єктів, що входять у k-у підмножину.

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

Характер функції (12) дозволяє використовувати для розв’язання задачі ідею обмеженого спрямованого перебору. Суть її полягає в послідовному розв’язанні задачі для кількості елементів  = , 2,..., , , де  – оптимальна кількість елементів ТРС. За наявності інформації щодо потреби в обслуговуванні об’єктів і продуктивності елементів ТРС для задачі, що розглядається, область пошуку розв’язку може бути скорочена до , де – мінімальна кількість елементів, достатня для обслуговування заданої множини об’єктів Ob={оbi}, .

Проведено експериментальне дослідження методу. Середня відносна похибка за результатами розв’язання 130 задач для nО = 80 і 1 4 склала  ,00395, а її максимальне значення = 0,05241. Метод має поліноміальну часову складність t(nО) і t( ) порядку O[n2].

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

, | (13)

(де CEU , CU, CUС – вартості зв’язків елементів з вузлами, вузлів з центром, вузлів між собою як функції кількості вузлів nU ) і становить

, | (14)

де сU – вартість вузла.

З урахування цього оцінка вартості оптимального варіанта радіально-вузлової структури має вигляд

+ CC + nE cE, | (15)

де CC – вартість центру; cE – вартість типового елемента системи.

Отримані моделі для визначення оптимальної кількості вузлів (14) і вартості (15) ТРС із радіально-вузловою структурою дозволяють одержувати їхні оцінки з похибкою, що має той же порядок, що і модель Нокера для оцінки кількості вузлів без врахування вартості зв’язків між вузлами і центром.

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

, (), (16)

де – значення оцінки оптимальної кількості вузлів системи;  – вага всієї множини елементів системи El, , де – вага i-го елемента; – оцінка ваги оптимальної множини елементів підсистеми; ][ – операція округлення до найближчого цілого; – вартість центру системи;  – вартість елементів системи; ( ) – вартість зв’язку елементів, вузлів і центру як функція від оптимальної кількості вузлів .

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

, , (17)

де  – вага підмножини елементів , що безпосередньо взаємодіють з g-м вузлом; – вартість вузла, розташованого в пункті g; – вартість взаємодії вузла, розташованого в пункті g з центром; – вартість взаємодії i-го елемента з вузлом, розташованим у пункті g; = , якщо Card)>1, тобто підмножина містить більше ніж один елемент і = , якщо Card)=1.

За результатами розв’язання 122 задач синтезу топологічних структур радіально-вузлових ТРС із кількістю елементів n =  50 середнє значення похибки оцінки оптимальної кількості вузлів (16) – (17) становить = ,1718, а її модуля – = ,7587. Максимальне значення абсолютної похибки становить max =2,25, а середньоквадратичне відхилення її модуля – = 0,5238. При цьому в 32,8випадків значення оцінки збігалося з точним розв’язком. Середнє значення відносної похибки оцінки вартості структури ТРС становить =  ,0773. Максимальне значення модуля відносної похибки становить max = ,1272, а середньоквадратичне відхилення її модуля – = 0,0162. Запропонований метод має складність , де n – кількість місць можливого розміщення вузлів системи.

Для оптимізації систем з радіально-вузловими структурами запропоновані комбінований і евристичний методи розв’язання задачі, що різняться за складністю і точністю розв’язків. Ідея базового методу спрямованого перебору MDR полягає в наступному. Визначити початкове значення допустимої кількості вузлів , необхідних для обслуговування всієї множини елементів El={eli}, . Для заданої кількості вузлів   за мінімумом вартості (де – вартість зв’язку між елементом j і вузлом i) вирішити задачу найкращого розміщення вузлів і розподілу множини елементів по вузлах Elk={eli}, . Визначити місце найкращого розміщення центру (центрального вузла) і вартість отриманого варіанта С( ). Змінювати кількість вузлів у системі := 1 і вирішувати задачі розміщення вузлів, розподілу множини елементів по вузлах до одержання найкращого за заданих умов розв’язку за критерієм вартості чи за узагальненим критерієм. Для розв’язання задачі розміщення вузлів і розподілу множини елементів