Неаналітичні методи оптимізації

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

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

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

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

Потрібно оцінити або Н(р) - імовірність порушення з'єднань у мережі через ушкодження компонентів, або математичне сподівання для р значень числа пар вузлів, між якими неможливо здійснити зв'язок.

Існує три способи рішення цієї задачі.

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

Другий спосіб називається способом функціонального моделювання. У ньому, як і в примітивному способі, для кожного елемента одержують деяке випадкове число. Елементи і відповідні числа групують по парам, причому числа розміщаються в порядку спадання (г_i1, г_i2,... г_іN+B — зазначені випадкові значення, i — номер елемента). Відповідно до примітивного методу, якщо r_lh p r_ih+1, необхідно проаналізувати на з’вязність підмережу, що складається з елементів ,..., При цьому значення з’вязності і показника надійності може бути знайдене для кожного значення р задопомогою наступної процедури: при 1 р> г_i1 мережа не містить несправних вузлів або гілок; при г_i1 р> г_i2 мережа складається з елементів і т.д.

Таким способом можна скористатися для «корекції» результатів у процесі аналізу заданої мережі при введенні в неї додаткових резервних елементів. У цьому відношенні він ефективний і дає можливість вирішувати задачі синтезу мереж при введенні нових компонентів у структуру з номером від до i_{N +B} .Одночасно можна виконати аналіз підмереж, складених з ,..., , для k = 1, 2,...., В. Зокрема, можна визначити h(р) або п(р) відразу для ряду значень р, використовуючи алгоритм зв'язності тільки один раз для кожної крапки вибору.

Третій спосіб — метод Мура — Шеннона, заснований на застосуванні наступних співвідношень для h(р) і п(р):

де q = 1-р— імовірність безвідмовної роботи елемента ІС, а C (k) -число незв'язаних підмереж, що містять рівно N елементів, і D(k) - середнє число пар вузлів, не зв'язаних між собою у всіх підмережах, що містять рівно k елементів.

С (k) і D(k) знаходяться за допомогою моделювання, тому що всі C(k) і D(k), крім k = B—N + 2, відомі заздалегідь. Мається С_Л^В підмереж, що містять рівно k елементів. Для малих k C(k) і D(k) можна знайти шляхом простого перерахування.