Оптимізація системи з розгалуженою структурою

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

Теоретична частина

Класифікація комбінаторних структур

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

Класифікації комбінаторних моделей систем за топологічною структурою:

· Розімкнена: ланцюжкова, розгалужена.

· Замкнена: кільцева, коміркова

· Комбінована

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

Kn= n(n+1)/2 , (1)

де n- кількість елементів ланцюжкової структури.

Найбільше числове значення, яке можна отримати на лінійці чисел (ланцюжкової структури) єдино можливим способом - це сума Snycixїї елементів. Решта Kn-1 способів припадає на утворення Sn-1 чисел натурального ряду, кожне з яких можна одержати R різними способамипослідовного додавання відповідних числових значень елементів лінійки. Залежність між кількістюKn способів реалізації сум на n-послідовності, параметром R та сумою Sn всіх чисел лінійки визначається формулою

(Sn-l)*R = Kn-1, (2)

Залежності (1) та (2) встановлюють зв'язок між параметрами n, R i Sn многократної ідеальної лінійки чисел.

=[n(n+1)/2-l]/R-1, (3)

Залежність (1) є справедливою для конфігурацій з розімкненою структурою.

Для будь-якої розімкненої структури мінімальна кількість m зовнішніх контактних зв'язків обчислюється як m=n+1, а з формули (1) випливає співвідношення:

=m(m-1)/2, (4)

Ідеальною розгалуженою лінійкою n-го порядку, кратності R, називається утворена на множиніKn= {kі}, i=l,2 ,n цілих чисел розгалужена лінійка чисел, на якійвci можливі суми зв'язаних між собою чисел послідовності, зокрема значення її окремих елементів, набувають значень чисел натурального ряду 1,2,…, S1, кожне з яких е значенням R різних сум, що відрізняються між собою, де S1 - максимальна сума на 1-послідовності чисел цієї розгалуженої лінійки.

Найбільше числове значення суми Smaxрозгалуженій лінійці при R=l:

=S1=Sn-Sk, (5)

де Sn - сума всіх чисел розгалуженої лінійки, Sk - сума всіх чисел, що не входять до складу 1-послідовності.

Максимально можлива кількість К способ1в реалізації сум на розгалуженій лінійці визначається як

=Smax*R, (6)=n(n+1)/2R+Sk, (7)=n(n+1)/2R, (8)

комбінаторний модель система дискретний

де R - максимальна кількість повторень чисел у розгалуженійлінійці.

На відміну від систем з розімкненою структурою, система з кільцевою конфігурацією характеризується таким виразом;

=m(m-l), (9)

де Kk - кількістьспособів утворення вcix можливих комбінацій з різних впорядкованих пар формування зовнішніх контактних зв'язків на кільцевійструктурі, що мають n == m елементів.

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