Моделювання складних систем - Программирование, компьютеры и кибернетика методичка

Моделювання в області системотехніки та системного аналізу. Імітація випадкових величин, використання систем масового обслуговування, дискретних і дискретно-безперервних марковських процесів, імовірнісних автоматів для моделювання складних систем.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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

Міністерство освіти і науки України
Харківський національний університет радіоелектроніки
1. Практичні заняття 1 - 2. Дискретні марковські процеси
2. Практичні заняття 3 - 4. Безперервні марковські процеси
3. Практичні заняття 5 - 6. Моделювання випадкових величин
4. Практичні заняття 7 - 8. Системи масового обслуговування
З розвитком комп'ютерної техніки моделювання стає найбільш ефективним методом дослідження складних систем (СС). Реальні СС досліджуються за допомогою двох типів моделей: аналітичних та імітаційних. Створення математичної моделі представляє собою формальний опис структури та процесу функціонування системи для однозначності її розуміння та подальшого аналітичного дослідження системи. Аналітичні моделі зображають поведінку СС у вигляді деяких функціональних співвідношень або логічних умов. Розробник моделі повинен не лише вміти створювати адекватні моделі досліджуваних систем, а також аналізувати їх поведінку, можливість керування експериментом та визначати межі використання моделей.
Практика моделювання в області системотехніки та системного аналізу показала раціональність використання типових математичних схем: систем масового обслуговування, дискретних та дискретно-безперервних стохастичних систем, мереж Петрі (котрі використовуються для структуризації причинних зв'язків та моделювання систем із паралельними процесами), кінцевих та ймовірнісних автоматів (використовуються для моделювання дискретно-детермінованих систем), диференціальних рівнянь (які є математичним апаратом безперервно-детермінованих систем), мереж кусково-лінійних агрегатів (що дозволяють описувати поведінку безперервних та дискретних, детермінованих та стохастичних систем), тощо. Наявність математичного апарату та порівняна швидкість опису поведінки СС сприяє поширенню аналітичних моделей в різноманітних областях науки та техніки.
Метою практичних занять з дисципліни «Моделювання систем» є закріплення теоретичного матеріалу, викладеного на лекціях, та оволодіння практичними навичками з імітації випадкових величин та використання систем масового обслуговування, дискретних і дискретно-безперервних марковських процесів для моделювання СС. Матеріали для кожного заняття містять основний теоретичний матеріал з теми заняття, приклади розв'язання задач і варіанти завдань для самостійного розв'язання. Рівень підготовки до заняття оцінюється за допомогою контрольних запитань і завдань з теми заняття.
Здобуття практичних навиків у розв'язанні задач з моделювання фізичних систем, що переходять із стану в стан під дією найпростіших випадкових потоків подій, з застосуванням дискретних марковських процесів (МП). Самостійне розв'язання задач цієї теми розвиває вміння визначати можливі стани заданої системи та будувати за ними граф станів та матрицю ймовірностей переходів. Студенти мають навчитися обчислювати ймовірності станів нестаціонарних систем, граничні ймовірності станів, коефіцієнти використання систем та інші важливі показники, за якими проводиться аналіз ефективності функціонування систем.
1.2 Методичні вказівки для самостійної підготовки до занять
При підготовці до занять необхідно вивчити конспект лекцій та розділи, приведені в [1, 2, 6]. Далі наведені короткі теоретичні відомості з дискретних МП. Випадковий процес, який протікає в системі, є марковським, якщо для любого моменту часу t 0 ймовірнісні характеристики процесу у майбутньому (ймовірність наступного стану) залежать лише від його теперішнього стану t 0 та не залежать від того, коли та яким чином система надійшла до цього стану. Взагалі, майже кожен процес можна розглядувати як марковський, якщо всі параметри з минулого, що впливають на майбутнє, включити до теперішнього стану системи. Перевагою МП, що відбувається в системі з дискретними станами, є те, що для його опису можливо побудувати досить просту математичну модель.
Потоком подій називається послідовність однорідних подій, що йдуть одна за одною у деякі моменти часу. Потоки подій, що мають властивість стаціонарності, ординарності та не мають післядії, називаються найпростішими або стаціонарними пуассоновими. Якщо всі потоки подій, що переводять систему з одного стану в інший, є пуассоновими (стаціонарними або ні), то процес, який протікає в системі, буде марковським (тобто без післядії).
При аналізі випадкових процесів з дискретними станами зручно користуватися графом станів. Вершини такого графа зображують стани системи, а дуги - можливі переходи. При аналізі дискретних МП часто використовують граф станів, на якому біля дуг поставлені відповідні перехідні ймовірності, - розмічений граф станів. Розглянемо приклад технічного пристрою S, що складається з двох вузлів, кожен з яких може під час роботи відмовити. Можливі чотири стани системи: - обидва вузли працюють; - перший вузол відмовив, другий працює; - перший працює, другий відмовив; - обидва вузли відмовили. Граф станів приведений на рисунку 1.1.
Рисунок 1.1 - Граф станів дискретного МП
Якщо для розглянутої вище системи S переходи з S i у S j можливі лише в моменти часу t 1 , t 2 , t 3 , ... t k , ..., тоді в системі відбувається процес з дискретними станами і дискретним часом. Як S i (k) позначається подія того, що після k кроків система перейде в стан S i . Процес, який відбувається в системі, можна представити як послідовність подій: S 1 (0), S 1 (2), S 2 (1), S 2 (3),.
Така послідовність подій називається марковським ланцюгом, якщо для будь-якого кроку k імовірність переходу з будь-якого стану S i в будь-який стан S j не залежить від того, як саме система прийшла в стан S i .
P ij (k) - це ймовірність переходу (або перехідна ймовірність) системи зі стану S i в будь-який інший стан S j за один крок. Імовірності P ij (k) є основними характеристиками МП. Запишемо їх у вигляді матриці ймовірностей переходів:
Матриця перехідних ймовірностей і розмічений граф станів є еквівалентними формами зображення МП. МП називається неоднорідним, якщо ймовірності переходу змінюються зі зміною номера кроку. МП є однорідним, якщо ймовірності переходу не залежать від кроку, тобто . Надалі, якщо не буде обговорено окремо, розглядатимуться однорідні МП.
Позначимо ймовірність того, що через m кроків МП перейде в стан S j , як . Така ймовірність обчислюється за допомогою рівнянь Колмогорова-Чепмена:
де s - натуральне число, що задовольняє нерівності .
МП вважається визначеним, якщо відомі ймовірності станів P i (k), що позначають імовірності того, що на k-му кроці система буде знаходитися в стані S i . Стан S i називається зворотнім, якщо ймовірність повернення МП в даний стан при виході з нього дорівнює одиниці. У всіх інших випадках стан є незворотнім. МП є ергодичним, якщо всі стани процесу є зворотними.
Якщо в системі протікає ергодичний МП та кількість станів процесу кінцева, то за теоремою Маркова існує
P i називаються граничними (стаціонарними) ймовірностями станів. Ці ймовірності являють собою середній відносний час перебування системи у відповідних станах.
Практичне використання моделей дискретних МП покажемо наступним прикладом. Нехай до деякої обчислювальної системи в дискретні моменти часу звертаються три користувачі. Пріоритет користувача збільшується зі збільшенням його номеру. В системі є абсолютний пріоритет і перервані заявки втрачаються. У початковий момент часу система знаходиться у стані очікування та користувачів не обслуговує. Необхідно визначити ймовірності станів ОС на кожному кроці та коефіцієнт використання системи, якщо матриця ймовірностей переходів задана:
Визначимо стани системи: S1 - система знаходиться у стані очікування; S2 - система обслуговує першого користувача; S3 - система обслуговує другого користувача; S4 - система обслуговує третього користувача.
Граф станів обчислювальної системи приведений на рисунку 1.2.
Рисунок 1.2 - Розмічений граф станів обчислювальної системи
Очевидно, що розподіл імовірностей для всіх станів при t = 0 буде таким:
P 1 (0) = 1, P 2 (0) = P 3 (0) = P 4 (0) = 0.
Імовірності станів на першому кроці обчислюються легко. Практично, вони беруться з першого рядка матриці перехідних імовірностей:
P 1 (1) = 0.2; P 2 (1) = 0.4; P 3 (1) = 0.2; P 4 (1) = 0.2.
Для підрахунку ймовірностей станів на другому кроці будемо користуватися виразом
де - імовірність переходів системи зі стану S j в стан S i за k кроків. Таким чином, імовірності станів на третьому кроці системи дорівнюють:
P 1 (2) = P 1 (1)P 11 + P 2 (1)P 21 + P 3 (1)P 31 + P 4 (1)P 41 =
0.2*0.2 + 0.4*0.1 + 0.2*0.2 + 0.2*0.8 = 0.28;
P 2 (2) = 0.2*0.4 + 0.4*0.4 + 0.2*0 + 0.2*0 = 0.24;
P 3 (2) = 0.2*0.2 + 0.4*0.3 + 0.2*0.3 = 0.22;
P 4 (2) = 0.2*0.2 + 0.4*0.2 + 0.2*0.5 + 0.2*0.2 = 0.26.
При досить великій кількості кроків (k > ?) у системі встановлюється стаціонарний режим. Для нього знайдемо граничні (стаціонарні) ймовірності станів (P i ). Для цього виразимо P i за формулою
та замінимо одне з рівнянь умовою нормування
Система рівнянь для визначення граничних імовірностей має вигляд:
P 1 = 0.2P 1 + 0.1P 2 + 0.2P 3 + 0.8P 4 ;
P 4 = 0.2P 1 + 0.2P 2 + 0.5P 3 + 0.2P 4 ;
0.7P 3 = 0.2P 1 + P 1 *0.3*0.4/0.6 = 0.4P 1 ;
0.8P 4 = 0.2P 1 + P 1 *0.2*0.4/0.6 + P 1 *0.5*0.4/0.7;
З нормувального рівняння знайдемо граничні ймовірності:
P 1 = 1/(1 + 0.667 + 0.57 + 0.773) = 1/3 = 0.333;
Коефіцієнт використання системи дорівнює К в = 1 - P 1 = 0.667.
1.3 Завдання для самостійної роботи
1. Система S може знаходитися в одному з п'яти можливих станів: S1 - система справна, працює; S2 - система несправна, очікує огляду; S3 - система діагностується; S4 - система ремонтується; S5 - система списана. Побудувати граф станів заданої системи.
2. Система S являє собою технічний пристрій, що складається з двох вузлів. Кожен із них може в якийсь момент часу відмовити. Кожен вузол спочатку піддається огляду з метою локалізації несправності, а потім починає відновлюватися. Побудувати граф станів системи.
3. Після обробки в одному з п'яти вузлів кільцевої мережі, повідомлення у фіксовані моменти часу з імовірністю Р надходить у наступний по номеру вузол, та з імовірністю (1 - Р) у попередній. Побудувати модель передачі повідомлень ланцюгом.
4. На колі розташовані шість точок Е1, ... , Е6 рівновіддалених одна від одної. Частка рухається з точки в точку таким чином. Із даної точки вона переміщується в одну з найближчих сусідніх точок з імовірністю 0.25 або в діаметрально протилежну точку з імовірністю 0.5. Скласти матрицю ймовірностей переходів для цього процесу та побудувати граф станів.
5. У моменти часу t 1 , t 2 , t 3 ,... відбувається діагностика технічного пристрою (ТП). Можливі наступні стани: пристрій цілком справний; незначні несправності, що дозволяють експлуатувати ТП; значні несправності, що дають можливість виконувати обмежене число функцій ТП; пристрій цілком вийшов з ладу. Знаючи матрицю перехідних імовірностей:
а) Побудувати розмічений граф станів.
б) Знайти ймовірності станів після кожного огляду, якщо при t = 0 ТП був цілком справний.
6. Точка S на рисунку 1.3 рухається по осі ОХ таким чином: на кожному кроці вона не змінює свого положення з імовірністю 0.5, або переходить на одиницю вправо з імовірністю 0.3 чи вліво з імовірністю 0.2. Після k кроків стан системи визначається розташуванням точки S. Первинне розташування - початок координат. Розглядаючи послідовність станів точки S як марковський ланцюг, знайти ймовірність того, що після чотирьох кроків точка виявиться не далі ніж на одиницю від початку координат.
Рисунок 1.3 - Точка S на осі координат ОХ
7. Процесор комп'ютера в будь-який заданий момент часу виконує команди з програми користувача; підпрограми операційної системи (ОС), що явно викликається з програми користувача та виконує для неї деяку задачу (наприклад, операцію вводу-виводу); підпрограми ОС, що виконує загальносистемну задачу керування, наприклад, планування, переключення, розподіл ресурсів чи відновлення після збою системи; циклу очікування. Провести аналіз ефективності комп'ютера - оцінити коефіцієнти використання процесора й ОС. Розмічений граф станів приведений на рисунку 1.4.
Рисунок 1.4 - Граф станів моделі процесору комп'ютера
8. Казкова країна Оз славиться багатьма речами, але тільки не гарною погодою. Два дні підряд ніколи не бувають ясними. Якщо в який-небудь день ясно, то наступного дня з рівними ймовірностями буде або дощ, або сніг. Якщо йде дощ (або сніг), то з однією та тією ж імовірністю погода наступного дня або залишиться такою ж, або зміниться. Якщо вона міняється, то в половині випадків наступного дня буде ясна погода. Побудувати систему прогнозу погоди в країні Оз.
моделювання системотехніка дискретний марковський
3. Які МП називаються однорідними, а які - неоднорідними?
4. Як можна описати систему за допомогою розміченого графу станів?
6. Які МП називаються зворотними, а які - незворотними?
7. Які правила використовуються для розрахунку граничних ймовірностей станів дискретного МП?
8. Розкрийте зміст теореми Маркова.
9. Які властивості є у найпростішого потоку подій?
10. Для чого використовується матриця ймовірностей переходів?
Отримання практичних навиків у розв'язанні задач з моделювання складних фізичних систем, які переходять із стану в стан в випадкові моменти часу під дією пуассонових потоків подій. Розрахунок параметрів безперервних МП та проведення аналізу ефективності функціонування таких систем, що можуть бути описаними у вигляді безперервних МП.
2.2 Методичні вказівки для сам о стійної підготовки до занять
При підготовці до занять необхідно вивчити конспект лекцій та розділи, приведені в [1, 2, 6]. Далі наведені короткі теоретичні відомості з безперервних МП. Нехай деяка фізична система складається з n станів S i , та переходить із одного стану до іншого під дією випадкових потоків подій. Перехід системи зі стану S i в S j можна розглядати як наслідок дії потоку з інтенсивністю л ij , а перехід з S k у S i буде зумовлений появою події потоку з інтенсивністю л ki . Випадковий процес S(t) утворює безперервний ланцюг Маркова, якщо для всіх цілих чисел n і довільної послідовності t 1 , t 2 , …, t n+1 такої, що t 1 < t 2 < … < t n+1 , виконується рівність
Тобто, як і для дискретних МП, майбутні стани безперервного МП залежать від минулого тільки через поточний стан, у якому процес знаходиться в даний момент.
2.2.1 Рівняння Колмогорова для визначення ймовірностей станів
Для знаходження ймовірностей станів для будь-якого моменту часу (P i (t), ) можливо користуватися рівняннями Колмогорова. У загальному вигляді вони записуються в такий спосіб:
Рівняння Колмогорова описують динаміку ймовірнісного процесу. Для розв'язання цієї системи одне з рівнянь необхідно замінити умовою нормування, оскільки для кожного моменту часу всі стани системи утворять повну групу подій:
Щоб розв'язати систему рівнянь Колмогорова, необхідно задати початкові умови. Якщо відомий вихідний стан системи, наприклад S i , то в початковий момент часу (при t = 0) P i (0) = 1, а всі інші початкові ймовірності станів дорівнюють нулю.
Аналіз структури рівнянь Колмогорова дає можливість визначити правило їхнього складання. Кількість рівнянь дорівнює кількості станів. У лівій частині кожного рівняння стоїть похідна ймовірності стану, а права частина містить стільки членів, скільки дуг інцидентні відповідній вершині графа. Якщо стрілка спрямована з вершини, відповідний член рівняння має знак "мінус", якщо у вершину - знак "плюс". Кожен член рівняння дорівнює добутку інтенсивності переходу, відповідній даній дузі, помноженій на ймовірність того стану, з якого виходить ця дуга.
Це правило складання диференціальних рівнянь Колмогорова для ймовірностей станів є загальним та справедливим для будь-якого безперервного МП. Як приклад, розглянемо систему, котра має два стани. Розмічений граф системи приведений на рисунку 2.1.
Рисунок 2.1 - Розмічений граф станів безперервного МП
Зі стану S 0 в стан S 1 систему переводить потік подій з інтенсивністю л; з S 1 в S 0 - м. Визначимо ймовірності станів системи P 0 (t) і P 1 (t). Для цього складемо систему диференціальних рівнянь Колмогорова:
З двох рівнянь одне замінимо умовою нормування. Відкинемо друге рівняння, а в перше замість P 1 (t) підставимо P 1 (t) = 1 - P 0 (t).
За теоремою Маркова для ергодичного безперервного МП, як і для дискретного, існує стаціонарний режим при , тобто lim P i (t)=P i , . Таким чином, граничні ймовірності P i постійні і не залежать від початкового стану системи. Для їх обчислення необхідно наступне.
У системі рівнянь Колмогорова, котрі описують імовірності станів, потрібно прирівняти всі ліві частини до нуля. Дійсно, у сталому режимі всі ймовірності станів постійні, і, як наслідок, їх похідні дорівнюють нулю. Якщо всі ліві частини рівнянь Колмогорова для ймовірностей станів прирівняти до нуля, то система диференціальних рівнянь перетвориться в систему однорідних лінійних рівнянь. Разом з нормувальною умовою ці рівняння дають можливість обчислити граничні ймовірності P i , .
Відкинемо перше рівняння, а друге і третє розв'яжемо спільно:
2.2.2 Процеси загибелі та розмноження
Розглянемо типову схему безперервного МП, яка має велике практичне значення при моделюванні комп'ютерних систем на архітектурному рівні. Безперервний МП називається процесом загибелі та розмноження, якщо його розмічений граф станів являє собою схему, яка приведена на рисунку 2.2.
Рисунок 2.2 - Розмічений граф станів типового процесу загибелі та розмноження
У стаціонарному режимі система диференціальних рівнянь вироджується в систему лінійних алгебраїчних рівнянь:
З першого рівняння системи виходить, що
Отже, всі ймовірності P i , , виражені через P 0 . В свою чергу, значення P 0 можна отримати, використовуючи нормуючу умову:
МП, який протікає в системі, називається циклічним, якщо його стани пов'язані між собою в кільце (цикл) з однобічними переходами (див. рисунок 2.3).
Рисунок 2.3 - Приклад циклічного МП
Для заданого циклічного процесу напишемо алгебраїчні рівняння граничних імовірностей станів:
та замінимо одне з рівнянь нормувальною умовою P 1 + P 2 + … + P n = 1. Виразимо всі ймовірності P 2 , …, P n через P 1 :
P 1 = 1/(1 + л 12 (1/л 23 + 1/л 34 + … + 1/л n 1 )) =
= 1/(л 12 (1/л 12 + 1/л 23 + 1/л 34 + … + 1/л n 1 ))
Одержані формули можна привести до більш зручного вигляду, якщо перейти від інтенсивностей л ij до середніх часів t і перебування системи у стані S і , і = 1 ч n.
Примітка: з S і є перехід тільки в S j , де j = і + 1. Беручи до уваги те, що л ij є інтенсивністю потоку подій, які переводять систему зі стану S і до стану S j , для останнього середній інтервал часу між подіями дорівнює t i = 1/л ij , тоді л ij = 1/t i , для i = nл n 1 = 1/t n .
Цей час система знаходиться в стані S і
Після елементарних перетворень отримаємо результати:
Тобто граничні ймовірності станів у циклічній системі відносяться як середні часи перебування системи підряд у кожному стані. Введемо поняття середнього часу перебування системи підряд у стані S i (t i ) та визначимо його через л ij . Розглянемо наступний розмічений граф переходів:
Рисунок 2.5 - Розмічений граф переходів деякої системи
Припустимо, що моменти переходу з S і в S j на осі часу ot виглядають так:
Рисунок 2.6 - Ось часу з точками переходів зі стану в стан
На рисунку 2.6. ф є часом перебування системи у стані S1 та обчислюється як
2.2.4 Приклад розв'язання типової задачі з безперервних МП
Фізична система S має ймовірні стани S1, S2, S3, S4. Розмічений граф станів заданий на рисунку 2.7. Обчислити граничні ймовірності станів: Р1, Р2, Р3, Р4.
Рисунок 2.7 - Розмічений граф станів заданої системи
Складемо систему рівнянь Колмогорова. Для кожного рівняння розглядаємо одну з вершин, та для неї беремо суму вихідних інтенсивностей зі знаком мінус, та вхідних зі знаком плюс:
В стаціонарному режимі всі ймовірності є сталими. А похідна від сталої величини дорівнює 0. Тобто, так як dPi/dt = 0 при t > ?, тоді
За методом підстановки виразимо всі інші ймовірності через P1:
Використовуючи нормуючий вираз (Р1 + Р2 + Р3 + Р4 = 1), одержимо:
Фізичний зміст P і - це частка часу, протягом якого система буде знаходитися у стані S і .
2.3 Завдання для самостійної роботи
1. Побудувати систему диференціальних рівнянь Колмогорова та визначити граничні ймовірності станів:

2. Побудувати систему диференціальних рівнянь Колмогорова та визначити граничні ймовірності станів:

3. Побудувати систему диференціальних рівнянь Колмогорова та визначити граничні ймовірності станів:

4. У системі S протікає безперервний МП. Визначити граничні ймовірності станів.

5. Побудувати систему диференціальних рівнянь Колмогорова та визначити граничні ймовірності станів:

6. Прилад складається з трьох вузлів, потік відмов - найпростіший, середній час безвідмовної роботи кожного вузла дорівнює =10 годин. Вузол, який відмовив, відразу ж починає ремонтуватися, середній час відновлення вузла дорівнює =5 годин, закон розподілу цього часу експоненціальний. Знайти середню продуктивність приладу, якщо при трьох працюючих вузлах вона дорівнює 100%, при двох - 50%, а при одному - 10%.
7. Технічний пристрій (ТП) підкоряється найпростішому потоку відмов з інтенсивністю 1 . Відмова виявляється не відразу, а через випадковий інтервал часу, розподілений експоненціально з інтенсивністю 2 . Як тільки відмова виявлена, проводиться діагностика ТП, у результаті якої пристрій або відправляється до ремонту з імовірністю P, або списується та замінюється новим. Час діагностики - експоненціальний з параметром 3 . Час ремонту - експоненціальний з параметром 4 . Час заміни списаного ТП новим - експоненціальний з параметром 5 . Визначити яку частку часу ТП буде працювати нормально; яку частку часу ТП буде працювати з невиявленою відмовою; яка середня вартість ремонту ТП і його замін за одиницю часу, якщо середня вартість одного ремонту дорівнює r, а нового ТП дорівнює с; яка середня величина втрат за одиницю часу від ТП, який працює іноді з невиявленою відмовою, якщо такий ТП приносить в одиницю часу збиток L.
8. ОС може знаходитися в одному зі станів: S1 - система справна, працює; S2 - система несправна та зупинена, ведеться пошук несправності; S3 - несправність локалізована, ведеться ремонт; S4 - ремонт закінчений, ведеться підготовка до пуску машини. Усі потоки подій - найпростіші. Середній час безвідмовної роботи ОС підряд дорівнює 0.5 доби. Для ремонту машину доводиться зупиняти в середньому на шість годин. Пошук несправності триває в середньому 0.5 години. Після закінчення ремонтних робіт машина готується до пуску в середньому 1 годину. Знайти граничні ймовірності станів.
1. В чому полягає різниця між дискретними та безперервними МП?
2. Як можна обчислити граничні ймовірності станів для безперервного МП?
3. За якими правилами складається система рівнянь Колмогорова?
4. Які є особливості у процесів загибелі та розмноження?
5. В чому полягає фізичний зміст граничних ймовірностей станів?
6. За якими правилами розв'язується система рівнянь Колмогорова?
Закріплення знань та отримання практичних навиків з генерування випадкових чисел довільного закону розподілу, з'ясування переваг та недоліків кожного з методів генерування випадкових величин та набуття вміння правильно обирати метод для розв'язання різних задач з отримання послідовностей випадкових чисел.
3.2 Методичні вказівки для сам о стійної підготовки до занять
При підготовці до занять необхідно вивчити конспект лекцій та розділи, приведені в [1, 3, 4, 6]. Далі наведені короткі теоретичні відомості з моделювання випадкових чисел (ВЧ). При дослідженні складних систем методом імітаційного моделювання особлива увага приділяється врахуванню випадкових факторів або статистичних параметрів системи. Прикладами статистичних параметрів комп'ютерних систем можуть бути інтервали часу між заявками, тривалість їх обслуговування, частота помилок вводу-виводу даних тощо.
До генераторів ВЧ ставляться наступні вимоги. По-перше, це відсутність кореляції між числами випадкової послідовності. По-друге, період послідовності має бути досить довгим (довжиною відрізка аперіодичності L є найбільше ціле число, таке, що при 0 <= i < j <= L подія P (X i = X j ) не має місця, тобто всі випадкові числа X i у межах відрізка аперіодичності не повторюються). По-третє, послідовність чисел повинна мати можливість відтворюватися. По-четверте, генератор ВЧ повинен бути досить швидкодіючим. Нарешті, використання пам'яті має бути мінімальним. Отримання ВЧ може здійснюватися трьома способами.
Апаратний або фізичний спосіб застосовує спеціальні електронні генератори випадкових сигналів. Їх дія заснована на фізичних випадкових явищах, таких, як шуми у приладах. Основними недоліками способу є нестабільність імовірнісних характеристик випадкової функції S(t) і неможливість повторного одержання однієї і тієї ж послідовності ВЧ.
Табличний спосіб складається з ретельного формування та збереження послідовностей ВЧ у запам'ятовуючих приладах з наступним зчитуванням і відтворенням. Основний недолік цього способу полягає у використанні пам'яті великої місткості. Перевагою є висока точність імовірнісних характеристик моделюємих ВЧ.
Алгоритмічний спосіб програмною реалізацією спеціальних алгоритмів відтворює ВЧ на комп'ютері. Кожне ВЧ обчислюється програмою в міру виникнення потреби при моделюванні деякої системи на комп'ютері. Цей спосіб забезпечує отримання періодичних числових послідовностей з великим періодом. У межах свого періоду такі послідовності мають задані властивості та називаються псевдовипадковими або квазівипадковими. Значною перевагою методу є можливість одержання на комп'ютері послідовності ВЧ без зовнішніх пристроїв при малих витратах пам'яті. Основними недоліками є менша точність (у порівнянні з іншими способами) ймовірнісних характеристик отриманих ВЧ, та збільшення часу на отримання одного числа.
У стохастичних моделях дуже часто виникає необхідність в отриманні ВЧ з довільним законом розподілу F(x). Метод, що застосовується найчастіше, являє собою двоетапну процедуру. На першому етапі генерується послідовність ВЧ, рівномірно розподілених в інтервалі [0, 1]:
а на другому етапі здійснюється функціональне перетворення послідовності ВЧ г i у послідовність ВЧ x i, , що мають заданий розподіл F(x):
Тобто випадкова величина є основою для генерації вибірки будь-яких розподілів ВЧ. Почнемо зі способів здобуття .
3.2.2 Генерація ВЧ, рівномірно розподілених в інтервалі [0, 1]
Зараз широкого поширення набули конгруентні методи генерації г i : мультиплікативний і змішаний. Змішаний метод використовує наступні співвідношення:
де - псевдовипадкове число, - невід'ємні цілі числа, такі, що , а х 0 - початкове значення послідовності.
Запис означає, що z є залишком від розподілу г на М. Якщо задане початкове значення х 0 , множник л та константа м, то можна визначити послідовність цілих чисел {x 1 , x 2 , x 3 , ..., x i , ... }, які є рівномірно розподіленими в інтервалі [0, M]. Поділивши всі числа на М, отримаємо послідовність псевдовипадкових чисел з рівномірним розподілом в інтервалі [0, 1]. Теоретично може бути отримана послідовність чисел з періодом Т = М, якщо виконуються наступні умови: м і М є взаємно простими числами та. л має порядок .
Мультиплікативний конгруентний метод заснований на використанні наступних співвідношень:
Видно, що цей метод є окремим випадком змішаного методу. Вибираючи відповідним чином л і х 0 , за допомогою цього методу можна отримати послідовність рівномірно розподілених некорельованих випадкових чисел, що мають максимальний при даному модулі М період. Найчастіше вибирають модуль , де q - це основа системи числення, котра використовується в комп'ютері (2 або 10), m - розрядність машинного слова. При виходять якісні послідовності (за критерієм , довжині відрізка аперіодичності L).
Для імітації випадкові величини з довільним законом розподілу повинні бути задані функція розподілу або щільність імовірності. Серед існуючих методів звернемо увагу на метод зворотної функції та метод кусочно-лінійної апроксимації. Ці методи використовують рівномірно розподілену на інтервалі [0, 1] випадкову величину г.
Нехай потрібно побудувати процедуру імітації безперервної випадкової величини X. Нагадаємо, що функцією розподілу випадкової величини X називається ймовірність того, що ця випадкова величина набуде значення меншого, ніж задане Х:
Якщо F(x) - функція розподілу випадкової величини X, а г - випадкова величина, рівномірно розподілена в інтервалі [0, 1], тоді випадкова величина X після розв'язання рівняння
буде мати функцію розподілу F(x), де F -1 - функція, зворотна по відношенню до F. Тобто, якщо отримати випадкове число г і знайти те значення випадкової величини X, при якому , тоді отримана випадкова величина X буде мати функцію розподілу F(x).
Таким чином, алгоритм моделювання випадкової величини Х за методом оберненої функції є наступним: отримати випадкову величину та як значення випадкової величини взяти X, обчислений як .
Розглянемо наступний приклад: побудувати процедуру імітації послідовності ВЧ, розподілених за експоненціальним законом. Для такого закону густина розподілу випадкової величини Х має вигляд:
За заданою густиною f(x) знаходимо функцію розподілу:
Прирівнюємо значення функції розподілу до випадкової величини г:
Розв'яжемо це рівняння відносно Х (за методом оберненої функції):
Розглянемо наступний приклад. Функція густини ймовірності представлена на рисунку 3.1. Обчислимо значення параметра с та складемо алгоритм моделювання Х за методом оберненої функції.
Рисунок 3.1 - Функція густини ймовірності
Використовуючи головну властивість функції густини ймовірності
Функція розподілу випадкової величини Х має вигляд:
Використовуючи метод оберненої функції, отримаємо вираз для генерування випадкової величини Х. Для цього переозначимо F(x) як г, підставимо у попередні вирази та отримаємо х(г). Розглянемо інтервали для г, тому що на межах цих інтервалі
Моделювання складних систем методичка. Программирование, компьютеры и кибернетика.
Курсовая работа по теме Использование трудовых ресурсов предприятия
Реферат по теме Антиглобализм: истоки, сущность, политическое лицо, перспективы
Реферат: Действие норм процессуальных прав во времени и пространстве
Реферат: Линогравюра
Поджелудочная Железа Реферат
Электромагнитные излучения (ЭМИ)
Курсовая работа по теме Суд присяжних в Україні
Реферат На Тему Развитие Политической Мысли В Древней Греции
Сочинение По Картине После Дождя 5 Приложение
Эссе На Заказ Туито
Курсовая работа по теме Двойная запись
Можно Ли Оправдать Измену Катерины Гроза Сочинение
Созвездие Тельца Реферат
Курсовая работа по теме Совершенствование тактики осмотра места происшествия
Темы Эссе По Обществознанию Человек
Статья На Тему Основні Компоненти Загальної Компетентності Вчителя Іноземної Мови
Реферат Истории На Тему Культура
Изложение: Алкестида
Реферат: Сущность и виды инвестиций
Сборник Сочинений По Литературе 10 11
Конечно-разностный метод решения для уравнений параболического типа - Математика контрольная работа
Teaching sentence structure - Иностранные языки и языкознание курсовая работа
Внедрение интерактивных методов обучения на уроке истории - Педагогика реферат