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

Міністерство освіти і науки, МОЛОДІ ТА СПОРТУ України

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Інститут комп‘ютерних наук та інформаційних технологій

Кафедра автоматизованих систем управління

РОЗРАХУНКОВА РОБОТА

з дисципліни «Математичні моделі синтезу та оптимізації систем»

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

Виконав:

ст. гр. ІУСм-12

Демкович О.В.

Перевірив:

Різник В.В.

Львів - 2011

Вступ

Математичні моделі синтезу та оптимізації систем - це дисципліна, яка розкриває основні підходи та методологію побудови дискретних систем з поліпшеними технічними показниками за роздільною здатністю, швидкодією, надійністю на основі використання комбінаторних моделей 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 елементів.

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

Метод розрахунку системи із оптимальним розподілом елементів структури. Синтез моделей із розімкненою (розгалуженою) структурою

Алгоритм побудови розгалуженої лінійки

Алгоритм дає змогу генерувати розгалужені (n,R) - лінійки будь-якої конфігурації і містить такі дії:

.        визначити число Smax за формулою (8);

.        враховуючи топологічну конфігурацію розгалуженої лінійки,задатися кількістю L елементів (1<L<n) у послідовності чисел, сума якихповинна дорівнювати числу Smax серед утворених сум на цій послідовності;

.        розбити число Smax усіма можливими способами на L частин,серед яких жодне з чисел не повинно траплятися більше R разів;

.        на кожному розбитті знайти всі впорядковані L- послідовності;

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

.        обчислити всі суміжні суми чисел послідовностей розгалуженої (n,R)-лінійки.

Побудована числова конструкція є ідеальною розгалуженою лінійкою, якщо утворена на ній множина вciх суміжних числових сум є множиною R натуральних рядів чисел від 1 до Smax.

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

Практична частина

Завдання на розрахункову роботу

Варіант №6

Завдання

.        Розробити програму для мінімізації суми цілочислових значень k1, k2, ..., k6 елементів системи з розгалуженою структурою.

.        Обмеження:)       числові значення k1, k2, ..., k6 не повинні повторюватися;)         суми двох, трьох i т.д. послідовно розміщених чисел не повинні повторюватися;)         множина ycix обчислених сум, включно з числовими значениями елементів розгалуженої системи не повинні повторюватися.

.        Реалізацію здійснити на мові об‘єктно-орієнотваного програмування.

В розрахунковій робті з дисципліни математичні моделі синтезу та оптимізації систем я розробив програму для мінімізації суми цілочислових значень k1, k2, ..., k6 елементів системи з розгалуженою структурою за допомогою мови ООП C# в середовищі Visual Studio. Моя програма дає можливість знаходити всі можливі величини, які може виміряти розгалужена структура, після того як користувач введе ваги ребер. Також програма обчислює Smax (Smax=n(n-1)/2R) та Sn (сума всіх ваг ребер).

S= (6*7)/2=21

K1+K2+K5+K6+K3+K4+K5+K6+K2+K5+K2+K6+K2+K3+K3+K4+K3+K4+K3+K4+K2+K3+K4

Втрачені числа: 11, 16, 18, 20

Отримані числа: 1,2,3,4,5,6,7,8,9,10,12,13,14,15,17,19,21

Висновок

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

Список літератури

1.      Холл М. Комбинаторика, - М., 1970, -471 с.

.        Гантмахер Ф.Р. Теорияматриц, - М,: Наука, 1970,

.        Pзізник В.В. Синтез оптимальних комбшаторних систем., - Львів: Вищашкола, 1989.- 168 с.

.        Цымбал В.Л. Теорияинформации и кодирования, - К., 1982.