Міністерство транспорту і зв’язку України

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

(61050,м. Харків, майд. Фейєрбаха,7)

ЛІСТРОВИЙ Сергій Володимирович

УДК 519.854 ; 681.324 ; 519.7 (043)

ОПЕРАТИВНЕ УПРАВЛІННЯ ТЕЛЕКОМУНІКАЦІЙНИМИ СИСТЕМАМИ ТА МЕРЕЖАМИ НА ОСНОВІ РАНГОВИХ МЕТОДІВ РІШЕННЯ ЗАДАЧ БУЛЕВОГО ПРОГРАМУВАННЯ

ТА ТЕОРІЇ ГРАФІВ

05.12.02 – “Телекомунікаційні системи та мережі”

АВТОРЕФЕРАТ

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

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

Харків-2005

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

Робота виконана у Харківському університеті Повітряних Сил

Офіційні опоненти: – Заслужений діяч науки і техніки України д.т.н., професор Баранов В.Л.,

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

та керуючих систем в енергетиці, Інституту проблем моделювання в

енергетиці ім.. Г.Є.Пухова НАН України, м. Київ;

– д.т.н., професор Кривуля Г.Ф. , завідуючий кафедри

“Автоматизація проектування обчислювальної техніки”,

Харківського національного університету радіоелектроніки,

Міністерство освіти та науки України, м. Харків;

– Заслужений винахідник України д.т.н., професор Краснобаєв В.А.,

професор кафедри “Автоматизації та комп’ютерних технологій”,

Харківський національний технічний університет сільського

господарства імені Петра Василенка,

Міністерство аграрної політики України, м. Харків.

Провідна установа Одеська національна академія зв’язку, ім. О.С.Попова,

кафедра документального електрозв’язку,

Міністерство транспорту і зв’язку України, м. Одеса.

Захист відбудеться 27.04.2005 р. о__14____ годині

на засіданні спеціалізованої вченої ради Д 64.820.01 при Українській

державній академії залізничного транспорту за адресою:

Україна, 61050, м. Харків, майдан Фейєрбаха,7.

З дисертацією можна ознайомитись у бібліотеці академії.

Відгук на автореферат просимо надсилати за адресою

Україна, 61050, м. Харків, майд. Фейєрбаха,7.

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

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

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

к.т.н., доцент М.В. Книгавко

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана на кафедрі бойового застосування АСУ Харківського університету Повітрянихтитуитуту ________________________________________________________________________________________________ Сил при виконанні НДР по автоматизації управління військами, створеної відповідно до рішення секції АПСУ РВ і А та Координаційної Ради МО України, затвердженого Начальником Генерального штабу ВР України від 23.02.1995 і наказом Командуючого РВ і А ВР України й у рамках співробітництва з аерокосмічним університетом ім. Н.Е. Жуковського "Харківський авіаційний інститут" і в межах державної науково-технічної програми № 7 "Перспективні інформаційні технології, пристрої комплексної автоматизації, системи зв'язку" ДКНТПП (постанова Верховної Ради України від 16.10.1992 р. 27-05-ХІІ "Про пріоритетні напрямки розвитку науки і техніки").

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

Поставлена мета досягається шляхом рішення таких задач дисертаційного дослідження:–

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– управління рішенням задач , та використанням ресурсів мережі, що забезпечує підвищення функціональної потужності мережі на 25–85% (що дозволило підвищити ефективність управління мережами – акт реалізації в в/ч А-0161,1998р);

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

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

Оперативність рішення задач управління в телекомунікаційних мережах на основі рангового підходу суттєво вище, ніж відомих методів, при цьому значення показника оперативності Р ? 0,9 може бути забезпечено для задач з числом змінних від 250 до 500.

Розроблені ПОС дозволяють підвищити оперативність рішення задач визначення оптимальних маршрутів та оцінки пропускної спроможності мережі, що підтверджено 6 авторськими свідоцтвами на винаходи.

Результати досліджень використані в науково-дослідних роботах військових частин, навчальних і виробничих підприємств України і країн СНД: А-0161, в/ч 25840, ВА ім. Ф.Е. Дзержинського, виробниче об'єднання "Маяк", про що маються відповідні висновки й акти реалізації за результатами дослідницьких робіт: акт про реалізацію А-0161, вих. № 155/5/339 від 19.04.97 р.; висновок в/ч 25840 н/вх 14/54 від 16.01.90 р.; висновок в/ч 25840 н/вх 1448 від 6.11.91 р.; висновок ВА ім. Ф.Е. Дзержинського н/вх 14/938 від 2.01.92 р.; акт про впровадження на заводі "Маяк" н/вх 14/288 від 2.07.92 р.; висновок в/ч А-0161 1998 р.; акт про реалізацію в навчальному процесі Харківського військового університету. За архітектурою розроблених паралельних обчислювальних систем отримано 6 авторських посвідчень і одна патентна довідка.

Особистий внесок здобувача. Усі результати отримані автором самостійно. У статтях, написаних у співавторстві, дисертанту належать: [1] – у монографії викладений ранговий підхід до рішення задач дискретної оптимізації, розглянуті питання організації паралельних обчислень при рішенні задач дискретної оптимізації і задачі динамічного управління в телекомунікаційних системах і мережах; [2] – розроблений ранговий підхід до рішення задач визначення найкоротших шляхів; [5] – на основі рангового підходу розроблений паралельний алгоритм визначення шляхів з максимальною пропускною спроможністю; [6] – розроблена узагальнена процедура рішення задач булевого програмування, принцип оптимізації за напрямком в n-мірному одиничному кубі і принцип виділення коридору, а так само ряд стратегій відсікання безперспективних варіантів рішення; [7] – розроблено паралельні алгоритми рішення задач булевого програмування; [8] – розроблений метод рішення задач про найменше покриття на основі ідей рангового підходу; [10] – доведена теорема, що дозволила побудувати узагальнені конструкції графів, на основі яких було побудовано наближений поліноміальний алгоритм визначення мінімальних верхових покрить і максимальних незалежних множин у довільних графах; [11] – розроблена система каліброваних векторів для визначення песимістичних і оптимістичних прогнозів у ранговому методі рішення задач про найменше покриття на основі ідей рангового підходу, з метою відсікання безперспективних варіантів рішення; [12] – розроблена система каліброваних векторів для визначення песимістичних і оптимістичних прогнозів у ранговому методі рішення багатомірних задач 0,1-рюкзак; [14] – розглянуті наближені алгоритми рішення задач 0,1-рюкзак і вплив сортувань коефіцієнтів у функціоналі й обмеженнях на погрішність рішення; [15] – розглянуті особливості рішення задач булевого програмування для випадку рівності коефіцієнтів у функціоналі; [16] – показане, що використання гарантованих прогнозів у рангових алгоритмах дозволяє знизити їхню тимчасову складність, підвищити точність наближених алгоритмів, запропонована процедура формування гарантованих прогнозів; [17] – розроблений ____________________________________________________________________________________________________________________а оцінка часової складності алгоритму визначення шляхів з максимальною пропускною спроможністю на основі рангового підходу; [18] – показана можливість розпаралелювання задач комбінаторної оптимізації на основі використання стягнутого дерева шляхів графу; [19] – розглянута можливість застосування паралельних алгоритмів на основі рангового підходу в обчислювальних системах; [20] – запропонований алгоритм рішення задачі визначення максимальних незалежних множин на основі введення конструкцій графу; [21] – запропонований алгоритм рішення задачі визначення клік у довільних графах; [22] – запропонований алгоритм рішення задачі 0,1-рюкзак на основі стратегії max; [23] – побудований точний алгоритм рішення задачі про найменше покриття, використовуючи принцип оптимізації за напрямком; [24] – розглянута паралельна реалізація рішення одномірних задач 0,1-рюкзак; [25] – запропонований універсальний алгоритм рішення задач комбінаторної оптимізації і на його основі обґрунтована можливість побудови інтелектуальних обчислювальних систем у межах функціонально повних систем; [26] – розроблена функціональна схема пристрою для визначення шляхів у графі на основі ідей рангового підходу; [27] – розроблена функціональна схема пристрою для визначення найкоротших шляхів у довільних графах на основі ідей рангового підходу; [28] – розроблена функціональна схема пристрою для рішення оптимізаційних задач на графах на основі ідей рангового підходу; [29] – розроблена функціональна схема пристрою для рішення оптимізаційних задач на графах на основі ідей рангового підходу; [30] – розроблена функціональна схема пристрою для визначення найкоротших гамільтонових шляхів на графах на основі ідей рангового підходу; [31] – розроблена функціональна схема пристрою для рішення комбінаторних задач на графах на основі ідей рангового підходу;

Апробація результатів дисертації. Результати досліджень доповідалися і були схвалені на міжнародних семінарах: "Питання оптимізації обчислень" м. Алушта; "Формальні моделі паралельних обчислень" м. Новосибірськ; "Проектування автоматизованих систем контролю і управління складними об'єктами" м. Туапсе; на наукових семінарах в Інституті кібернетики АН України; в інституті проблем моделювання в енергетиці НАН України; в Інституті проблем управління АН Росії; на ОЦ АН Росії; в Академії Ф.Э. Дзержинського; НТК виду військ ХВВКИУ РВ; на ІV-V МНТК “Інформаційні технології: наука, техніка, технологія, утворення, здоров'я”, НТК “Обробка інформації і забезпечення надійності систем управління”, у результатах роботи школи-семінару “Перспективні системи управління на залізничному, промисловому і міському транспорті”, НТК “Проблеми удосконалювання систем управління і зв'язку”, МНТК “Mathematіcal modellіng and іnformatіon technologіes”.

Публікації. Основний зміст дисертаційної роботи відбито у 81 науковій праці, з них у: 45 наукових статтях у журналах і збірниках наукових праць АН України, 6 тезах доповідей і праць міжнародних науково-технічних конференцій, 1-й монографії, 8 навчально-методичних посібниках , 14 звітах по НДР, 6 авторських посвідченнях і 1 патентній довідці.

Структура роботи. Дисертаційна робота виконана на 392 сторінках, ілюстрована 85 рисунками, 27 таблицями. Робота складається з вступу, 6 розділів, висновків, 7 додатків і списку використовуваної літератури, що має 322 найменування.

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

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

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

Kсэ = ; (1) ; Р(т) = 1-е, (2)

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

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

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

При цьому варто мати на увазі, що практично всі задачі комбінаторної оптимізації на графах можуть бути сформульовані як задачі цілочислового лінійного програмування з булевими змінними (ЦЛП із БЗ). Задачі ЦЛП із БЗ і велика частина комбінаторних оптимізаційних задач відносяться до класу NP-повних, і важко піддаються рішенню навіть при використанні сучасних ЕОМ. Підвищення продуктивності сучасної ЕОМ у 1000 разів дозволяє збільшити розмірність розв'язуваної задачі за прийнятний час на (5 – 7) змінних.

Тому, що при використанні комбінаторних методів обчислювальний процес є кінцевим за своєю побудовою, то питання про збіжність методу не виникає. Особливу важливість у цьому випадку здобуває оцінка практичної застосовності методів, тобто можливості одержання рішення задачі за припустимий час. Застосування методів гілок та кордонів для одержання точних рішень, при управлінні мережею, стає неможливим вже при розмірах задач, рівних 40. Відомі наближені і ? – оптимальні алгоритми рішення задачі ЦЛП із БЗ самі по собі відносяться до NP-повних, тобто з підвищенням точності алгоритмів число кроків алгоритму, необхідне для забезпечення заданої точності, починає экспоненциально зростати. Використання локальних алгоритмів для рішення задачі ЦЛП із БЗ досить великої розмірності не може гарантувати наперед задану точність. Як показують дослідження, локальний екстремум може відрізнятись від глобального на 70 – 90%. Останнє неприпустимо, при динамічному управлінні в мережах спеціального призначення, оскільки це може призвести до того, що значення показника ефективності роботи мережі виявиться нижче припустимого, і цілі управління в системі не будуть досягнуті. Методи ж рішення довільних нелінійних задач булевого програмування практично відсутні. У сучасних мережах, через зазначені труднощі, для рішення задач, використовуються евристичні алгоритми, що базуються на деяких "розумних" правилах, і, так само як і локальні алгоритми, не гарантують одержання рішень з високою точністю. Таким чином, існує проблема оперативного рішення задач динамічного управління мережею, формальними моделями яких є задачі ЦЛП із БЗ великої розмірності і задачі нелінійного булевого програмування.

Слід зазначити, що спроби зменшити час рішення задач ЦЛП із БЗ за рахунок розпаралелювання зіштовхуються з іншою проблемою теорії паралельних обчислень, що полягає в тому, що з погляду теорії паралельних алгоритмів даний тип задач відноситься до класу сильно зв’язаних задач, які важко піддаються розпаралелювання. У роботах Сергиенко И.В. показано, що при реалізації методів гілок та кордонів на багатопроцесорних обчислювальних системах збільшення числа процесорних елементів призводить до зниження продуктивності системи в цілому і, що для цього класу задач необхідно визначати оптимальне число процесорних елементів, на якому доцільно вирішувати задачу. Таким чином, при розробці паралельних алгоритмів рішення задачі ЦЛП із БЗ, крім протиріччя між точністю рішення задачі і часом її рішення виникає ще одне протиріччя між сильною зв'язаністю задачі і необхідністю її розпаралелювання з метою одержання припустимого часу рішення. Тому в даній роботі, для усунення зазначених протиріч, при рішенні задач динамічного управління мережею і задач автоматизації процесу ухвалення рішення, розглядається рішення такого комплексу задач:

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

2. Розробка моделей та алгоритмів рішення задач динамічного управління в телекомунікаційних мережах на основі рангового підходу;

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

Другий розділ присвячений розробці теорії рішення задач ЦЛП із БЗ на основі ідей рангового підходу, що розглянутий на прикладах рішення задач 0,1-рюкзак і задачі визначення мінімального покриття. Формальні моделі, яких відповідно мають вигляд (3, 4, 5) і (6, 7, 8).

(3) , (6)

(4) (7)

(5) . (8)

В основі ідеї рангового підходу лежить представлення n-мірного одиничного куба у виді графа G, геометричний зміст якого полягає в наступному. Геометрично вершина k графа G рангу r – це множина векторів (x1, x2, ... , xk, ... , xn), у яких xk = 1, а на позиціях від 1 до k знаходиться r одиниць. Ребру, що входить у вершину k графу G , відповідає одиничний вектор (0, 0, ... , 0, 1, 0, ... , 0) n – мірного одиничного куба Bn з одиницею в k-й позиції.

Тоді, шляху рангу r у графі G відповідає вектор , який дорівнює сумі одиничних векторів ребер, по яким він досяг вершину j рангу r, починаючи з вершини s. Множину шляхів у графі G до вершин j, розташованим на ярусах від вершини s, можна представити у вигляді

(9)

де – множина шляхів у графі G від вершини s до вершин j, розташованих на r-х ярусах графа G, ( ранг шляху визначається числом ребер, що утворюють цей шлях ). Варто мати на увазі, що множину шляхів у графі G відповідає множині векторів, що містять k одиниць. Отже, тобто кожному шляху в множині відповідає деякий вектор . З (9) випливає (10)

Таким чином, граф G являє собою упорядкований по рангах еквівалент n-мірного одиничного куба Bn , у якому шляхи відповідають вершинам Bn. Для рішення задач (3 – 5), (6 – 8) у розділі 1 запропонована система каліброваних векторів що дозволяє звести рішення цих задач до визначення екстремальних шляхів у графі G. Сформульовано:–

принцип оптимізації за напрямком, обумовлений співвідношенням

(11) –

принцип виділення коридору в підмножинах, , (12) де {Lw} правила відсікань шляхів у множинах ; – шлях з вершини s графу G шлях у вершину p, що проходить через проміжну вершину j та задовольняє правилам {Lw}, тобто шлях отриман за рахунок приєднання до шляху ребра (j,p), якщо таке з'єднання не суперечить правилам {Lw}. Для рішення задач типу (3 – 5) , (6 – 8), запропонована узагальнена процедура А0, що дозволяє визначити локальні екстремуми в W-областях графу G щораз і потім виділяти глобальний екстремум з n(n+1)/2 локальних, отриманих на основі принципу оптимізації за напрямком (11) з використанням правил відсікань{Lw} шляхів у множинах, що вводяться. У розділі розглянуті стратегії відсікання {Lw} безперспективних шляхів у множинах, що призводять до наближених і точних рішень задачі ЦЛП із БЗ, і побудоване множину ефективних точних і наближених алгоритмів рішення задач ЦЛП із БЗ. Запропоновано процедуру визначення гарантованих прогнозів і досліджений їхній вплив на часову складність алгоритмів і погрішність. Показано, що введення гарантованих прогнозів дозволяє на 40% знизити часову складність розроблюваних алгоритмів і підвищити їхню точність.

Важливим достоїнством розроблених алгоритмів на основі рангового підходу є той факт, що збільшення числа обмежень практично не впливає на погрішність рішень алгоритмів, тоді як для методів рішення задач дискретної оптимізації, заснованих на ідеях методу гілок та кордонів, зростання числа обмежень до декількох сотень приводить фактично до неможливості їхнього практичного застосування. Показано, що наближені алгоритми для рішення задачі 0,1-рюкзак і ЗНП на основі рангового підходу мають властивість збіжності до точного рішення зі зростанням розмірності розв'язуваної задачі, що є важливим достоїнством рангового підходу до рішення задач ЦЛП із БЗ у порівнянні з відомими алгоритмами. У розділі проведене експериментальне дослідження розроблених алгоритмів і їхній порівняльний аналіз із кращими відомими алгоритмами на основі метода гілок та кордонів (МГК), приклади порівняння показані на рис.1 з якого видно, що за швидкодії розроблені алгоритми суттєво перевершують відомі й у середньому мають часову складність не перевищуючу О(n3m) та залишаються експоненціальними у загальному випадку.

У розділі 3 розглянуті підходи до рішення задач булевого програмування на основі теорії графів і булевої алгебри, а також до рішення, виділеного в розділі 1, з погляду рішення задач управління в телекомунікаційних мережах, підкласу задач теорії графів. У розділі 3 на основі методу рішення ЗНП, розробленого в розділі 2, побудовано алгоритм рішення задач "3-виконавчість" поліноміальної складності О(26m) для трьох змінних ( де m кількість диз’юнктів), та алгоритм експоненціальної складності для рішення задачі “k-виконавчість”", який працює у середньому як поліноміальний з часовою складністю О(0,25k3).

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

Теорема. Якщо f булева функція, побудована за графом G = (V, E) у вигляді добутку диз’юнктів (vі v vj), де {vі} {0, 1} і при цьому кожен диз’юнкт (vі v vj) відповідає ребру (vі, vj), то всі набори змінних {vі, vj} на яких вона приймає значення "істинно", відповідають верховим покриттям у графі G = (V, E).

Наслідок. Для перерахування усіх верхових покрить графу G = (V, E) необхідно визначити ті системи значень змінних {vі, vj}, при яких вираз f (V1,V2...Vn) = 1 (13) "істинний". Щоб знайти ці системи значень змінних {vі, vj} необхідно привести ліву частину (13) до мінімальної ДНФ (диз'юнктивна нормальна форма), розкриваючи дужки і користуючись законом поглинання.

Така форма єдина через відсутність у (13) логічних заперечень. Показано, що на основі булевої функції, побудованої за довільним графом G = (V, E) з n вершинами можна побудувати конструкції Qі = Lі Dі, де Lі – деяка підмножина вершин, вхідних у верхове покриття графа G = (V, E) без вершини і , а Dі – дводольний граф із ще непокритих ребер графу, і на їхній основі побудувати наближений алгоритм визначення мінімального верхового покриття в довільних графах з тимчасовою складністю, не перевищуючу О(n3), та середнім значенням похибки, не більш 6-7%. Проведено порівняльний аналіз розробленого алгоритму з відомими і показано, що часова складність даного алгоритму суттєво менше ніж у кращих відомих алгоритмів (див. рис. 2).

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

У розділі розглянутий загальний підхід до рішення довільних задач теорії графів і дискретної оптимізації та побудований універсальний алгоритм їхнього рішення, який являє собою схему рішення довільних задач теорії графів. Робота розробленого в розділі підходу продемонстрована на прикладі рішення задач визначення незалежних максимальних зважених множин і задачі визначення найкоротшого гамільтонового циклу і показано, що якщо базові елементи, з яких будується цікавлячий нас об'єкт, характеризуються m + 1 ваговими характеристиками й оптимізація об'єкта здійснюється за однією ваговою характеристикою, то в загальному випадку при довільних об'єктах складність наближених алгоритмів не перевищить О(kn3), де k – число операцій, необхідних для визначення оптимальної ваги об'єкта при додаванні в нього ще одного базового елемента. У випадку, коли на m ваг об'єкта накладається обмеження, то в цьому випадку ми приходимо до задач лінійного і нелінійного булевого програмування. На основі запропонованої загальної схеми рішення комбінаторних задач у розділі розроблений і загальний метод рішення довільних задач булевого програмування, який дозволяє будувати наближені алгоритми, що володіють малою часовою складністю і погрішністю. Слід відзначити, що погрішність рішень алгоритмів побудованих на основі запропонованого методу для кожного комбінаторного об'єкту необхідно оцінювати окремо. Для опису всієї множини адитивних цілочислових функцій з довільними нелінійностями, які можуть виникнути на множині змінних {X1, X2 ... Xn}, уведене поняття породженої функції F(x) рівної

(14)

де – сума всіх можливих сполучень добутків змінних, утримуючих у кожному добутку (не лінійності) r різних змінних; ; –цілочислові коефіцієнти, що знаходяться в добутках , утримуючих змінних. Позначимо через H множину усіх цілочислових адитивних функцій, які можна породити на основі F(x), покладаючи рівними нулю різні сполучення в (14). Множина H є повна у тому розумінні, що містить у собі всі можливі нелінійності, що складаються з усіх можливих сполучень змінних, утворюючих ці нелінійності, які можна взагалі побудувати на основі даної підмножини змінних {X1, X2 ... Xn}.

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

,де (15)

Розглянемо граф G(Х, Е), у якому вершини Хі та Хj з'єднані ребром (і, j), якщо вони можуть бути об'єднані в кліку. У графі G(Х, Е) кожній вершині Хі відповідає змінна Хі. Виділимо в графі G довільну кліку Q = , що складається з r вершин, де r < n, і розглянемо її перетинання з , а також з . Кожне перетинання можна охарактеризувати сумами коефіцієнтів, що стоять при у функціоналі та обмеженнях , при цьому в загальному випадку довільна кліка Q завжди буде характеризуватися відповідною вагою по функціоналу і не більш ніж m вагами по обмеженням . Таким чином, довільна задача булевого програмування може розглядатися як задача визначення кліки Q* максимальної ваги по вагах функціонала, у графі G, у якої всі m ваг по вагах обмежень не перевищують відповідно bj. Кожному шляху рангу r у графі D, який задає весь простір рішень, минаючому через вершини (vh, vk ... vp) у вихідному графі G розв'язуваної задачі відповідає кліка з (r – 1)- вершини (), що характеризується відповідною вагою за функціоналом і не більш ніж m вагами по обмеженнях. Вагові характеристики {dsjr–1} довільної кліки Qr–1(j) складаються з ваг (r – 1)- вершини й обумовлені одним зі шляхів рангу r у графі D вони обчислюються, по вагам функціонала, шляхом підсумовування коефіцієнтів підмножини Lf ={}, стоячими при Рf , де Рf – усі підмножини { }f задовольняючі умові f Qr – 1(j) , а f визначається функціоналом . Аналогічно визначаються вагові характеристики по вагах обмежень шляхом підсумовування коефіцієнтів підмножини LВ = {}, що стоять при РВ, де В усі підмножини, задовольняючі умові Qr – 1(j) , а визначається обмеженнями . Таким чином, вагові характеристики клік Qr – 1(j) шляхів, що характеризуються множиною , по вагам функціонала й обмежень визначаються відповідно рівностями dsjf(r – 1) = ; dsjВ(r – 1) =.

Для рішення задачі (15) розроблені три різних алгоритми, реалізуючі однопрохідні і n-прохідні процедури рішення задачі (15) з часовими складностями О(n5 k(m + 1)), О(n4 k(m + 1)), О(n3 k(m + 1)) і проведене їх експериментальне дослідження.

При дослідженні коефіцієнти у функціоналі й обмеженнях генерувалися за рівномірним законом розподілу у функціоналі у діапазоні від 0 до10, а у обмеженнях від 0 до 20. На кожну точку графіків при оцінці часової складності алгоритмів у середньому і погрішності алгоритмів вирішувалось не менше 50 тестових задач, результати отримані з довірчою імовірністю 0,95. У якості точного алгоритму використовувався розроблений алгоритм для рішення задачі квадратичного і лінійного програмування, скомбінований на основі використання ідей рангового підходу (для прогнозування верхньої оцінки рішення) і методу гілок та кордонів ( для відсівання безперспективних шляхів), який дозволив оцінити погрішності для задач до розмірності, не перевищуючої n = 70. Графіки залежності погрішності від розмірності (n) розв'язуваних задач і від числа обмежень (m) наведені на (рис. 3,4) з яких видно, що погрішність алгоритмів зі збільшенням числа обмежень m асимптотично зменшується, а при m 50 погрішність алгоритмів стабілізується і для задач лінійного програмування не перевищує 2%, а для задач квадратичного 5 – 10%. Рішення тестових задач показало, що збільшення діапазону зміни коефіцієнтів у функціоналі й обмеженнях призводить до різкого зниження погрішностей алгоритмів, перехід від нелінійностей одного порядку до нелінійностей більш високого порядку може призводити до незначного зростання погрішностей при невеликому числі обмежень, але з зростанням числа обмежень зростання погрішності дуже швидко компенсується. Експериментальне дослідження часової складності показало (рис. 5), що число оброблюваних векторів слабко залежить від числа обмежень і в середньому для алгоритмів часова складність не перевищує відповідно О(0,1n4, 9), О(0, 3n3, 7) та О(0, 4n2, 8).

У розділі 4 розглянуті паралельні алгоритми визначення оптимальних маршрутів і шляхів з максимальною пропускною спроможністю в телекомунікаційних мережах на основі рангового підходу з використанням переходу від вихідного графа G до стягнутого дерева всіх шляхів D0. Що дозволяє представити множину усіх шляхів {Мst}, між даною парою вершин s і t у вигляді наступного об'єднання підмножин Mst = Mr =1st U Mr = 2st U ... U Mr = n – 1st, де Mst r – множини шляхів