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

Аналіз сучасних систем управління на основі застосування телекомунікаційних мереж показує, що останнім часом істотно зросла роль факторів обумовлених часом, затрачуваним системою на доведення інформації про стан керованого процесу до пунктів управління, на обробку інформації, що надходить, ухвалення рішення на основі прийнятої інформації та доведення прийнятого рішення до виконавчих органів. Поставлена мета досягається шляхом рішення таких задач дисертаційного дослідження: - розробка теоретичних основ рішення задач управління які базуються на розробці методів рішення задач булевого програмування та теорії графів на основі рангового підходу, який дозволяє знизити часову складність та погрішність отриманих рішень; Розроблені методи рішення задач булевого програмування та теорії графів и науково-методичний є подальшим розвитком теорії дослідження операцій і теорії графів, і являють собою додаток до теорії побудови мереж і паралельних обчислювальних систем, що відбито в наступних основних результатах роботи: Вперше розроблені комплекс методів рішення задач булевого лінійного та нелінійного програмування, а також теорії графів, використання яких дозволяє суттєво, в десятки разів, підвищити оперативність управління телекомунікаційними системами і мережами: - за рахунок зниження часової складності алгоритмів їх рішення та відповідно зменшення часу реалізації алгоритмів управління в них. Отримав подальший розвиток метод рішення задач динамічного управління телекомунікаційними системами і мережами, який базується на запропонованому у роботі принципі оптимізації за напрямком у n-мірному одиничному кубі, що представляється у вигляді графу, з упорядкованими по рангах множинами рішень, і розробленій узагальненій процедурі рішення задач дискретної оптимізації, а також принципі виділення коридору у множинах рішень, який дозволяє у десятки разів зменшити час рішення задач управління в телекомунікаційних системах і мережах.У якості основних критеріїв ефективності функціонування мережі у роботі використовувались коефіцієнт збереження ефективності, що характеризує ступінь впливу відмов на ефективність застосування мережі за призначенням і показник оперативності рішення задач динамічного управління в мережі за деякий припустимий час рішення Тд , що кількісно оцінюють імовірністю Р(Т) рішення комплексу задач динамічного управління потоками інформації в мережах Р(Т) за час Т, не перевищуючий Тд: Ксэ = ; (1) ; Р(т) = 1-е , (1) де Ев - корисний ефект операції управління; E? - значення показника ефективності функціонування мережі після здійснення керуючого впливу в мережі; E0 - номінальне значення показника ефективності функціонування мережі. Серед задач оптимізації на графах з погляду побудови інтелектуальних телекомунікаційних мереж і процесів управління в них, на основі проведеного аналізу, можна виділити такі задачі: задачі визначення найкоротших шляхів і найкоротших гамільтонових шляхів у графах; задача визначення мінімальних верхових покрить і незалежних максимальних множин, у довільних графах; задача оптимального фарбування графів; задачі “виконавчість” і “3-виконавчість”; задачі ізоморфізму підграфів і графів. Таким чином, існує проблема оперативного рішення задач динамічного управління мережею, формальними моделями яких є задачі ЦЛП із БЗ великої розмірності і задачі нелінійного булевого програмування. Таким чином, при розробці паралельних алгоритмів рішення задачі ЦЛП із БЗ, крім протиріччя між точністю рішення задачі і часом її рішення виникає ще одне протиріччя між сильною звязаністю задачі і необхідністю її розпаралелювання з метою одержання припустимого часу рішення. У розділі 3 на основі методу рішення ЗНП, розробленого в розділі 2, побудовано алгоритм рішення задач "3-виконавчість" поліноміальної складності О(26m) для трьох змінних (де m кількість дизюнктів), та алгоритм експоненціальної складності для рішення задачі “k-виконавчість”", який працює у середньому як поліноміальний з часовою складністю О(0,25k3).У даній роботі на основі теоретичних досліджень вирішена важлива науково-технічна проблема, повязана з підвищенням оперативності рішення задач управління в телекомунікаційних системах та мережах на основі рангових методів рішення задач булевого програмування і теорії графів.Створені наукові основи рангових методів рішення задач булевого лінійного та нелінійного програмування, а також теорії графів, застосування яких дозволяє підвищити оперативність управління в телекомунікаційних системах та мережах завдяки: - зниженню часової складності алгоритмів їх рішення та, відповідно, зменшенню часу реалізації алгоритмів управління в телекомунікаційних системах та мережах; використанню рангового підходу до організації обчислювального процесу, утворюючого можливості ефективно розпаралелити процес рішення задач управління телекомунікаційними системами та мережами, що дозволяє додатково підвищити оперативність рішення задач управління в них. Показано, що використання розроблених методів рішення задач булевого

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