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

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

Рубрика Экономико-математическое моделирование
Вид курсовая работа
Язык украинский
Дата добавления 18.01.2013
Размер файла 24,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

Виконав:

ст. гр. ІУСм-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 многократної ідеальної лінійки чисел.

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

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

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

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

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

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

Smax=S1=Sn-Sk, (5)

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

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

K=Smax*R, (6)

Sn=n(n+1)/2R+Sk, (7)

Smax=n(n+1)/2R, (8)

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

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

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

Kk=m(m-l), (9)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Варіант №6

Завдання

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

2. Обмеження:

a) числові значення k1, k2, ..., k6 не повинні повторюватися;

b) суми двох, трьох i т.д. послідовно розміщених чисел не повинні повторюватися;

c) множина ycix обчислених сум, включно з числовими значениями елементів розгалуженої системи не повинні повторюватися.

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

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

S= (6*7)/2=21

K1

K2

K3

K4

K5

K6

+

+

-

-

-

-

K1

+

+

+

-

+

+

K2

-

+

+

+

+

+

K3

-

-

+

+

-

-

K4

-

+

+

-

-

+

K5

-

+

+

-

+

-

K6

K1

K2

K3

K4

K5

K6

K1+K2

K2+K5

K2+K6

K2+K3

K3+K4

K3+K5

K3+K6

K1+K2+K5

K1+K2+K6

K1+K2+K3

K2+K3+K4

K5+K3+K4

K6+K3+K4

K1+K2+K3+K4

K1

K2

K3

K4

K5

K6

1

2

4

8

10

5

Втрачені числа: 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 с.

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

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

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

Размещено на Allbest.ru


Подобные документы

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

    реферат [662,8 K], добавлен 26.11.2010

  • Процедури та моделювання систем зв’язку, формальний опис та оцінювання ефективності. Специфіка цифрового зображення сигналів. Особливості та методи побудови математичних моделей систем та мереж зв'язку. Математичні моделі на рівні функціональних ланок.

    реферат [120,1 K], добавлен 19.02.2011

  • Поняття "моделі" та роль економетричних моделей. Формування сукупності спостережень та поняття однорідності. Принципи побудови лінійних, нелінійних економетричних моделей попиту, пропозиції. Відбір факторів і показників для побудови функції споживання.

    курсовая работа [308,9 K], добавлен 09.07.2012

  • Аналітичні методи дослідження операцій. Сутність аналогових, математичних (аналітичних) та зображувальних моделей. Математичне введення в теорію ланцюгів Маркова (Markov’schain). Дискретні ланцюги. Теорія масового обслуговування, вивчення її предмету.

    курсовая работа [374,4 K], добавлен 23.08.2014

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

    презентация [390,9 K], добавлен 10.10.2013

  • Теорія двоїстості та двоїсті оцінки у лінійному програмуванні. Економічна інтерпретація задач лінійного програмування. Правила побудови двоїстих задач. Встановлення зв’язків між оптимальними розв’язками задач за допомогою леми та теореми двоїстості.

    контрольная работа [345,7 K], добавлен 22.02.2011

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

    лабораторная работа [57,7 K], добавлен 12.05.2010

  • Предмет, об'єкт, метод та основні завдання економетрики. Розробка і дослідження эконометричних методів (методів прикладної статистики) з урахуванням специфіки економічних даних. Поняття економетричної моделі і її вибір. Типи економетричних моделей.

    контрольная работа [32,8 K], добавлен 18.06.2010

  • Поняття логістичних ланцюгів. Методи побудови початкового опорного плану. Визначення та розрахунок потенціалу кожної вершини. Методи пошуку оптимального рішення. Алгоритм оптимізації транспортної задачі: логістичного ланцюга за допомогою симплекс-методу.

    дипломная работа [1,1 M], добавлен 20.11.2013

  • Теоретико-методологічні відомості з теорії ігор, двостороння монополія та рівновага Курно. Практичне використання методу середніх, визначення типу зростання на основі абсолютних приростів. Побудова тренду та обчислення прогнозу на наступний період.

    курсовая работа [371,6 K], добавлен 22.04.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.