Моделювання складних систем

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

Міністерство освіти і науки України

Харківський національний університет радіоелектроніки

МЕТОДИЧНІ ВКАЗІВКИ

до практичних занять з курсу

"Моделювання СИСТЕМ"

для студентів напряму

6.091 “Комп'ютерна інженерія”

(денної та заочної форми навчання)

Харків 2008

ЗМІСТ

Вступ

1. Практичні заняття 1 - 2. Дискретні марковські процеси

2. Практичні заняття 3 - 4. Безперервні марковські процеси

3. Практичні заняття 5 - 6. Моделювання випадкових величин

4. Практичні заняття 7 - 8. Системи масового обслуговування

Перелік посилань

ВСТУП

З розвитком комп'ютерної техніки моделювання стає найбільш ефективним методом дослідження складних систем (СС). Реальні СС досліджуються за допомогою двох типів моделей: аналітичних та імітаційних. Створення математичної моделі представляє собою формальний опис структури та процесу функціонування системи для однозначності її розуміння та подальшого аналітичного дослідження системи. Аналітичні моделі зображають поведінку СС у вигляді деяких функціональних співвідношень або логічних умов. Розробник моделі повинен не лише вміти створювати адекватні моделі досліджуваних систем, а також аналізувати їх поведінку, можливість керування експериментом та визначати межі використання моделей.

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

Метою практичних занять з дисципліни «Моделювання систем» є закріплення теоретичного матеріалу, викладеного на лекціях, та оволодіння практичними навичками з імітації випадкових величин та використання систем масового обслуговування, дискретних і дискретно-безперервних марковських процесів для моделювання СС. Матеріали для кожного заняття містять основний теоретичний матеріал з теми заняття, приклади розв'язання задач і варіанти завдань для самостійного розв'язання. Рівень підготовки до заняття оцінюється за допомогою контрольних запитань і завдань з теми заняття.

1. ПРАКТИЧНІ ЗАНЯТТЯ 1 - 2.

Дискретні марковські процеси

1.1 Мета занять

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

1.2 Методичні вказівки для самостійної підготовки до занять

При підготовці до занять необхідно вивчити конспект лекцій та розділи, приведені в [1, 2, 6]. Далі наведені короткі теоретичні відомості з дискретних МП. Випадковий процес, який протікає в системі, є марковським, якщо для любого моменту часу t₀ ймовірнісні характеристики процесу у майбутньому (ймовірність наступного стану) залежать лише від його теперішнього стану t₀ та не залежать від того, коли та яким чином система надійшла до цього стану. Взагалі, майже кожен процес можна розглядувати як марковський, якщо всі параметри з минулого, що впливають на майбутнє, включити до теперішнього стану системи. Перевагою МП, що відбувається в системі з дискретними станами, є те, що для його опису можливо побудувати досить просту математичну модель.

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

При аналізі випадкових процесів з дискретними станами зручно користуватися графом станів. Вершини такого графа зображують стани системи, а дуги - можливі переходи. При аналізі дискретних МП часто використовують граф станів, на якому біля дуг поставлені відповідні перехідні ймовірності, - розмічений граф станів. Розглянемо приклад технічного пристрою S, що складається з двох вузлів, кожен з яких може під час роботи відмовити. Можливі чотири стани системи: - обидва вузли працюють; - перший вузол відмовив, другий працює; - перший працює, другий відмовив; - обидва вузли відмовили. Граф станів приведений на рисунку 1.1.

Рисунок 1.1 - Граф станів дискретного МП

Якщо для розглянутої вище системи S переходи з S_i у S_j можливі лише в моменти часу t₁, t₂, t₃, ... t_k, ..., тоді в системі відбувається процес з дискретними станами і дискретним часом. Як S_i(k) позначається подія того, що після k кроків система перейде в стан S_i. Процес, який відбувається в системі, можна представити як послідовність подій: S₁(0), S₁(2), S₂(1), S₂(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 називаються граничними (стаціонарними) ймовірностями станів. Ці ймовірності являють собою середній відносний час перебування системи у відповідних станах.

Практичне використання моделей дискретних МП покажемо наступним прикладом. Нехай до деякої обчислювальної системи в дискретні моменти часу звертаються три користувачі. Пріоритет користувача збільшується зі збільшенням його номеру. В системі є абсолютний пріоритет і перервані заявки втрачаються. У початковий момент часу система знаходиться у стані очікування та користувачів не обслуговує. Необхідно визначити ймовірності станів ОС на кожному кроці та коефіцієнт використання системи, якщо матриця ймовірностей переходів задана:

0.2	0.4	0.2	0.2
0.1	0.4	0.3	0.2
0.2	0	0.3	0.5
0.8	0	0	0.2

Визначимо стани системи: S1 - система знаходиться у стані очікування; S2 - система обслуговує першого користувача; S3 - система обслуговує другого користувача; S4 - система обслуговує третього користувача.

Граф станів обчислювальної системи приведений на рисунку 1.2.



Рисунок 1.2 - Розмічений граф станів обчислювальної системи

Очевидно, що розподіл імовірностей для всіх станів при t = 0 буде таким:

P₁(0) = 1, P₂(0) = P₃(0) = P₄(0) = 0.

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

P₁(1) = 0.2; P₂(1) = 0.4; P₃(1) = 0.2; P₄(1) = 0.2.

Для підрахунку ймовірностей станів на другому кроці будемо користуватися виразом

,

де - імовірність переходів системи зі стану S_j в стан S_i за k кроків. Таким чином, імовірності станів на третьому кроці системи дорівнюють:

P₁(2) = P₁(1)P₁₁ + P₂(1)P₂₁ + P₃(1)P₃₁ + P₄(1)P₄₁ =

0.2*0.2 + 0.4*0.1 + 0.2*0.2 + 0.2*0.8 = 0.28;

P₂(2) = 0.2*0.4 + 0.4*0.4 + 0.2*0 + 0.2*0 = 0.24;

P₃(2) = 0.2*0.2 + 0.4*0.3 + 0.2*0.3 = 0.22;

P₄(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₁ = 0.2P₁ + 0.1P₂ + 0.2P₃ + 0.8P₄;

P₂ = 0.4P₁ + 0.4P₂;

P₃ = 0.2P₁ + 0.3P₂ + 0.3P₃;

P₄ = 0.2P₁ + 0.2P₂ + 0.5P₃ + 0.2P₄;

P₁ + P₂ + P₃ + P₄ = 1.

Із другого рівняння виразимо:

P₂ = P₁*0.4/0.6 = 0.667Р₁.

Із третього рівняння отримаємо:



0.7P₃ = 0.2P₁ + P₁*0.3*0.4/0.6 = 0.4P₁;

P₃ = P₁*0.4/0.7 = 0.57P₁.

З четвертого рівняння виходить:

0.8P₄ = 0.2P₁ + P₁*0.2*0.4/0.6 + P₁*0.5*0.4/0.7;

P₄ = 0.773P₁.

З нормувального рівняння знайдемо граничні ймовірності:

P₁ = 1/(1 + 0.667 + 0.57 + 0.773) = 1/3 = 0.333;

P₂ = 0.222;

P₃ = 0.19;

P₄ = 0.26.

Коефіцієнт використання системи дорівнює К_в = 1 - P₁ = 0.667.

1.3 Завдання для самостійної роботи

1. Система S може знаходитися в одному з п'яти можливих станів: S1 - система справна, працює; S2 - система несправна, очікує огляду; S3 - система діагностується; S4 - система ремонтується; S5 - система списана. Побудувати граф станів заданої системи.

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

3. Після обробки в одному з п'яти вузлів кільцевої мережі, повідомлення у фіксовані моменти часу з імовірністю Р надходить у наступний по номеру вузол, та з імовірністю (1 - Р) у попередній. Побудувати модель передачі повідомлень ланцюгом.

4. На колі розташовані шість точок Е1, ... , Е6 рівновіддалених одна від одної. Частка рухається з точки в точку таким чином. Із даної точки вона переміщується в одну з найближчих сусідніх точок з імовірністю 0.25 або в діаметрально протилежну точку з імовірністю 0.5. Скласти матрицю ймовірностей переходів для цього процесу та побудувати граф станів.

5. У моменти часу t₁, t₂, t₃,... відбувається діагностика технічного пристрою (ТП). Можливі наступні стани: пристрій цілком справний; незначні несправності, що дозволяють експлуатувати ТП; значні несправності, що дають можливість виконувати обмежене число функцій ТП; пристрій цілком вийшов з ладу. Знаючи матрицю перехідних імовірностей:

0.5	0.3	0.2	0
0	0.4	0.4	0.2
0	0	0.3	0.7
0	0	0	1

а) Побудувати розмічений граф станів.

б) Знайти ймовірності станів після кожного огляду, якщо при t = 0 ТП був цілком справний.

6. Точка S на рисунку 1.3 рухається по осі ОХ таким чином: на кожному кроці вона не змінює свого положення з імовірністю 0.5, або переходить на одиницю вправо з імовірністю 0.3 чи вліво з імовірністю 0.2. Після k кроків стан системи визначається розташуванням точки S. Первинне розташування - початок координат. Розглядаючи послідовність станів точки S як марковський ланцюг, знайти ймовірність того, що після чотирьох кроків точка виявиться не далі ніж на одиницю від початку координат.

Рисунок 1.3 - Точка S на осі координат ОХ

7. Процесор комп'ютера в будь-який заданий момент часу виконує команди з програми користувача; підпрограми операційної системи (ОС), що явно викликається з програми користувача та виконує для неї деяку задачу (наприклад, операцію вводу-виводу); підпрограми ОС, що виконує загальносистемну задачу керування, наприклад, планування, переключення, розподіл ресурсів чи відновлення після збою системи; циклу очікування. Провести аналіз ефективності комп'ютера - оцінити коефіцієнти використання процесора й ОС. Розмічений граф станів приведений на рисунку 1.4.

Рисунок 1.4 - Граф станів моделі процесору комп'ютера

8. Казкова країна Оз славиться багатьма речами, але тільки не гарною погодою. Два дні підряд ніколи не бувають ясними. Якщо в який-небудь день ясно, то наступного дня з рівними ймовірностями буде або дощ, або сніг. Якщо йде дощ (або сніг), то з однією та тією ж імовірністю погода наступного дня або залишиться такою ж, або зміниться. Якщо вона міняється, то в половині випадків наступного дня буде ясна погода. Побудувати систему прогнозу погоди в країні Оз.

моделювання системотехніка дискретний марковський



1.4 Контрольні питання

1. Що таке марковський ланцюг?

2. Які є особливості в МП?

3. Які МП називаються однорідними, а які - неоднорідними?

4. Як можна описати систему за допомогою розміченого графу станів?

5. Які МП називаються ергодичними?

6. Які МП називаються зворотними, а які - незворотними?

7. Які правила використовуються для розрахунку граничних ймовірностей станів дискретного МП?

8. Розкрийте зміст теореми Маркова.

9. Які властивості є у найпростішого потоку подій?

10. Для чого використовується матриця ймовірностей переходів?

2. ПРАКТИЧНІ ЗАНЯТТЯ 3 - 4

Безперервні марковські процеси

2.1 Мета занять

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

2.2 Методичні вказівки для самостійної підготовки до занять

При підготовці до занять необхідно вивчити конспект лекцій та розділи, приведені в [1, 2, 6]. Далі наведені короткі теоретичні відомості з безперервних МП. Нехай деяка фізична система складається з n станів S_i, та переходить із одного стану до іншого під дією випадкових потоків подій. Перехід системи зі стану S_i в S_j можна розглядати як наслідок дії потоку з інтенсивністю л_ij, а перехід з S_k у S_i буде зумовлений появою події потоку з інтенсивністю л_ki. Випадковий процес S(t) утворює безперервний ланцюг Маркова, якщо для всіх цілих чисел n і довільної послідовності t₁, t₂, …, t_n+1 такої, що t₁ < t₂ < … < t_n+1, виконується рівність

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



2.2.1 Рівняння Колмогорова для визначення ймовірностей станів

Для знаходження ймовірностей станів для будь-якого моменту часу (P_i(t), ) можливо користуватися рівняннями Колмогорова. У загальному вигляді вони записуються в такий спосіб:

, .

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

.

Щоб розв'язати систему рівнянь Колмогорова, необхідно задати початкові умови. Якщо відомий вихідний стан системи, наприклад S_i, то в початковий момент часу (при t = 0) P_i(0) = 1, а всі інші початкові ймовірності станів дорівнюють нулю.

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

Це правило складання диференціальних рівнянь Колмогорова для ймовірностей станів є загальним та справедливим для будь-якого безперервного МП. Як приклад, розглянемо систему, котра має два стани. Розмічений граф системи приведений на рисунку 2.1.

Рисунок 2.1 - Розмічений граф станів безперервного МП

Зі стану S₀ в стан S₁ систему переводить потік подій з інтенсивністю л; з S₁ в S₀ - м. Визначимо ймовірності станів системи P₀(t) і P₁(t). Для цього складемо систему диференціальних рівнянь Колмогорова:

,

.

З двох рівнянь одне замінимо умовою нормування. Відкинемо друге рівняння, а в перше замість P₁(t) підставимо P₁(t) = 1 - P₀(t).

Отримаємо:

.

Знаходимо розв'язання рівнянь:

;

.

За теоремою Маркова для ергодичного безперервного МП, як і для дискретного, існує стаціонарний режим при , тобто lim P_i(t)=P_i, . Таким чином, граничні ймовірності P_i постійні і не залежать від початкового стану системи. Для їх обчислення необхідно наступне.

У системі рівнянь Колмогорова, котрі описують імовірності станів, потрібно прирівняти всі ліві частини до нуля. Дійсно, у сталому режимі всі ймовірності станів постійні, і, як наслідок, їх похідні дорівнюють нулю. Якщо всі ліві частини рівнянь Колмогорова для ймовірностей станів прирівняти до нуля, то система диференціальних рівнянь перетвориться в систему однорідних лінійних рівнянь. Разом з нормувальною умовою ці рівняння дають можливість обчислити граничні ймовірності P_i, .

Для нашого прикладу:

,

,

.

Відкинемо перше рівняння, а друге і третє розв'яжемо спільно:

,

.

2.2.2 Процеси загибелі та розмноження

Розглянемо типову схему безперервного МП, яка має велике практичне значення при моделюванні комп'ютерних систем на архітектурному рівні. Безперервний МП називається процесом загибелі та розмноження, якщо його розмічений граф станів являє собою схему, яка приведена на рисунку 2.2.

Рисунок 2.2 - Розмічений граф станів типового процесу загибелі та розмноження

У стаціонарному режимі система диференціальних рівнянь вироджується в систему лінійних алгебраїчних рівнянь:

,

,

,

,

…………………………………

.

Нормуюче рівняння:

.

З першого рівняння системи виходить, що



,

З другого маємо:

.

Згідно з індукцією

.

Отже, всі ймовірності P_i, , виражені через P₀. В свою чергу, значення P₀ можна отримати, використовуючи нормуючу умову:

.

2.2.3 Циклічні МП

МП, який протікає в системі, називається циклічним, якщо його стани пов'язані між собою в кільце (цикл) з однобічними переходами (див. рисунок 2.3).

Рисунок 2.3 - Приклад циклічного МП

Для заданого циклічного процесу напишемо алгебраїчні рівняння граничних імовірностей станів:

л₂₃P₂ = л₁₂P_1,

л₃₄P₃ = л₂₃P_2,

…………….

л_к,к+1P_к = л_к-1,кP_к-1,

…………….

л_n,1P_n = л_n-1,nP_n-1,

л₁₂P₁ = л_n1P_n,

та замінимо одне з рівнянь нормувальною умовою P₁ + P₂ + … + P_n = 1. Виразимо всі ймовірності P₂, …, P_n через P₁:

P₂ = P₁л₁₂/ л_23;

P₃ = P₁л₁₂/ л_34;

P₄ = P₁л₁₂/ л_45;

………………

P_к = P₁л₁₂/ л_к,к+1;

………………

P_n = P₁л₁₂/ л_n1.

Та отримаємо

P₁ = 1/(1 + л₁₂(1/л₂₃ + 1/л₃₄ + … + 1/л_n1)) =

= 1/(л₁₂(1/л₁₂ + 1/л₂₃ + 1/л₃₄ + … + 1/л_n1))

Одержані формули можна привести до більш зручного вигляду, якщо перейти від інтенсивностей л_ij до середніх часів t_і перебування системи у стані S_і, і = 1 ч n.

Примітка: з S_і є перехід тільки в S_j, де j = і + 1. Беручи до уваги те, що л_ij є інтенсивністю потоку подій, які переводять систему зі стану S_і до стану S_j, для останнього середній інтервал часу між подіями дорівнює t_i = 1/л_ij, тоді л_ij = 1/t_i, для i = nл_n1 = 1/t_n.

Цей час система знаходиться в стані S_і

Рисунок 2.4 - Тривалість стану S_і

Після елементарних перетворень отримаємо результати:

P₁ = t₁/(t₁ + t₂ + … + t_n);

P₂ = t₂/(t₁ + t₂ + … + t_n);

……………………….

P_n = t_n/(t₁ + t₂ + … + t_n);

Або

P_i = t_i/, де i = 1чn.

Тобто граничні ймовірності станів у циклічній системі відносяться як середні часи перебування системи підряд у кожному стані. Введемо поняття середнього часу перебування системи підряд у стані S_i (t_i) та визначимо його через л_ij. Розглянемо наступний розмічений граф переходів:



Рисунок 2.5 - Розмічений граф переходів деякої системи

Припустимо, що моменти переходу з S_і в S_j на осі часу ot виглядають так:

Рисунок 2.6 - Ось часу з точками переходів зі стану в стан

На рисунку 2.6. ф є часом перебування системи у стані S1 та обчислюється як

Але ,

таким чином

t₁ = 1/л₁₂.

У загальному вигляді

t_i = 1/л_i, i+1.



2.2.4 Приклад розв'язання типової задачі з безперервних МП

Фізична система S має ймовірні стани S1, S2, S3, S4. Розмічений граф станів заданий на рисунку 2.7. Обчислити граничні ймовірності станів: Р1, Р2, Р3, Р4.

Рисунок 2.7 - Розмічений граф станів заданої системи

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

dP1/dt = - 5P1 + P3;

dP2/dt = - P2 + 2P1 + 2P3;

dP3/dt = - 3P3 + 3P1 + 2P4;

dP4/dt = - 2P4 + P2;

В стаціонарному режимі всі ймовірності є сталими. А похідна від сталої величини дорівнює 0. Тобто, так як dPi/dt = 0 при t > ?, тоді

0 = - 5P1 + P3;

0 = - P2 + 2P1 + 2P3;

0 = - 3P3 + 3P3 + 2P4;

0 = - 2P4 + P2;

P1 + P2 + P3 + P4 = 1;



За методом підстановки виразимо всі інші ймовірності через P1:

P3 = 5P1;

P2 = 12P1;

P4 = P2/2 = 6P1.

Використовуючи нормуючий вираз (Р1 + Р2 + Р3 + Р4 = 1), одержимо:

P1 = 1/24;

P2 = 1/2;

P3 = 5P1 = 5/24;

P4 = 1/4.

Фізичний зміст P_і - це частка часу, протягом якого система буде знаходитися у стані S_і.

2.3 Завдання для самостійної роботи

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

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

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



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

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

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

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

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

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

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



6. Прилад складається з трьох вузлів, потік відмов - найпростіший, середній час безвідмовної роботи кожного вузла дорівнює =10 годин. Вузол, який відмовив, відразу ж починає ремонтуватися, середній час відновлення вузла дорівнює =5 годин, закон розподілу цього часу експоненціальний. Знайти середню продуктивність приладу, якщо при трьох працюючих вузлах вона дорівнює 100%, при двох - 50%, а при одному - 10%.

7. Технічний пристрій (ТП) підкоряється найпростішому потоку відмов з інтенсивністю ₁. Відмова виявляється не відразу, а через випадковий інтервал часу, розподілений експоненціально з інтенсивністю ₂. Як тільки відмова виявлена, проводиться діагностика ТП, у результаті якої пристрій або відправляється до ремонту з імовірністю P, або списується та замінюється новим. Час діагностики - експоненціальний з параметром ₃. Час ремонту - експоненціальний з параметром ₄. Час заміни списаного ТП новим - експоненціальний з параметром ₅. Визначити яку частку часу ТП буде працювати нормально; яку частку часу ТП буде працювати з невиявленою відмовою; яка середня вартість ремонту ТП і його замін за одиницю часу, якщо середня вартість одного ремонту дорівнює r, а нового ТП дорівнює с; яка середня величина втрат за одиницю часу від ТП, який працює іноді з невиявленою відмовою, якщо такий ТП приносить в одиницю часу збиток L.

8. ОС може знаходитися в одному зі станів: S1 - система справна, працює; S2 - система несправна та зупинена, ведеться пошук несправності; S3 - несправність локалізована, ведеться ремонт; S4 - ремонт закінчений, ведеться підготовка до пуску машини. Усі потоки подій - найпростіші. Середній час безвідмовної роботи ОС підряд дорівнює 0.5 доби. Для ремонту машину доводиться зупиняти в середньому на шість годин. Пошук несправності триває в середньому 0.5 години. Після закінчення ремонтних робіт машина готується до пуску в середньому 1 годину. Знайти граничні ймовірності станів.

2.4 Контрольні питання

1. В чому полягає різниця між дискретними та безперервними МП?

2. Як можна обчислити граничні ймовірності станів для безперервного МП?

3. За якими правилами складається система рівнянь Колмогорова?

4. Які є особливості у процесів загибелі та розмноження?

5. В чому полягає фізичний зміст граничних ймовірностей станів?

6. За якими правилами розв'язується система рівнянь Колмогорова?

3. ПРАКТИЧНІ ЗАНЯТТЯ 5 - 6

Моделювання випадкових величин

3.1 Мета занять

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

3.2 Методичні вказівки для самостійної підготовки до занять

При підготовці до занять необхідно вивчити конспект лекцій та розділи, приведені в [1, 3, 4, 6]. Далі наведені короткі теоретичні відомості з моделювання випадкових чисел (ВЧ). При дослідженні складних систем методом імітаційного моделювання особлива увага приділяється врахуванню випадкових факторів або статистичних параметрів системи. Прикладами статистичних параметрів комп'ютерних систем можуть бути інтервали часу між заявками, тривалість їх обслуговування, частота помилок вводу-виводу даних тощо.

До генераторів ВЧ ставляться наступні вимоги. По-перше, це відсутність кореляції між числами випадкової послідовності. По-друге, період послідовності має бути досить довгим (довжиною відрізка аперіодичності L є найбільше ціле число, таке, що при 0 <= i < j <= L подія P (X_i = X_j) не має місця, тобто всі випадкові числа X_i у межах відрізка аперіодичності не повторюються). По-третє, послідовність чисел повинна мати можливість відтворюватися. По-четверте, генератор ВЧ повинен бути досить швидкодіючим. Нарешті, використання пам'яті має бути мінімальним. Отримання ВЧ може здійснюватися трьома способами.

3.2.1 Способи генерації ВЧ

Апаратний або фізичний спосіб застосовує спеціальні електронні генератори випадкових сигналів. Їх дія заснована на фізичних випадкових явищах, таких, як шуми у приладах. Основними недоліками способу є нестабільність імовірнісних характеристик випадкової функції S(t) і неможливість повторного одержання однієї і тієї ж послідовності ВЧ.

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

Алгоритмічний спосіб програмною реалізацією спеціальних алгоритмів відтворює ВЧ на комп'ютері. Кожне ВЧ обчислюється програмою в міру виникнення потреби при моделюванні деякої системи на комп'ютері. Цей спосіб забезпечує отримання періодичних числових послідовностей з великим періодом. У межах свого періоду такі послідовності мають задані властивості та називаються псевдовипадковими або квазівипадковими. Значною перевагою методу є можливість одержання на комп'ютері послідовності ВЧ без зовнішніх пристроїв при малих витратах пам'яті. Основними недоліками є менша точність (у порівнянні з іншими способами) ймовірнісних характеристик отриманих ВЧ, та збільшення часу на отримання одного числа.

У стохастичних моделях дуже часто виникає необхідність в отриманні ВЧ з довільним законом розподілу F(x). Метод, що застосовується найчастіше, являє собою двоетапну процедуру. На першому етапі генерується послідовність ВЧ, рівномірно розподілених в інтервалі [0, 1]:

,

а на другому етапі здійснюється функціональне перетворення послідовності ВЧ г_i у послідовність ВЧ x_i,, що мають заданий розподіл F(x):

.

Тобто випадкова величина є основою для генерації вибірки будь-яких розподілів ВЧ. Почнемо зі способів здобуття .

3.2.2 Генерація ВЧ, рівномірно розподілених в інтервалі [0, 1]

Зараз широкого поширення набули конгруентні методи генерації г_i: мультиплікативний і змішаний. Змішаний метод використовує наступні співвідношення:

,

де - псевдовипадкове число, - невід'ємні цілі числа, такі, що , а х₀ - початкове значення послідовності.

Запис означає, що z є залишком від розподілу г на М. Якщо задане початкове значення х₀, множник л та константа м, то можна визначити послідовність цілих чисел {x₁, x₂, x₃, ..., x_i, ... }, які є рівномірно розподіленими в інтервалі [0, M]. Поділивши всі числа на М, отримаємо послідовність псевдовипадкових чисел з рівномірним розподілом в інтервалі [0, 1]. Теоретично може бути отримана послідовність чисел з періодом Т = М, якщо виконуються наступні умови: м і М є взаємно простими числами та. л має порядок .

Мультиплікативний конгруентний метод заснований на використанні наступних співвідношень:

,

.

Видно, що цей метод є окремим випадком змішаного методу. Вибираючи відповідним чином л і х₀, за допомогою цього методу можна отримати послідовність рівномірно розподілених некорельованих випадкових чисел, що мають максимальний при даному модулі М період. Найчастіше вибирають модуль , де q - це основа системи числення, котра використовується в комп'ютері (2 або 10), m - розрядність машинного слова. При виходять якісні послідовності (за критерієм , довжині відрізка аперіодичності L).

3.2.3 Метод оберненої функції

Для імітації випадкові величини з довільним законом розподілу повинні бути задані функція розподілу або щільність імовірності. Серед існуючих методів звернемо увагу на метод зворотної функції та метод кусочно-лінійної апроксимації. Ці методи використовують рівномірно розподілену на інтервалі [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 - Функція густини ймовірності

Використовуючи головну властивість функції густини ймовірності



,

одержимо

;

або

.

Звідки .

Функція розподілу випадкової величини Х має вигляд:

якщо х є (1; 2], то ;

якщо х є (2; 3], то

якщо х є (3; 4], то

якщо

х є (4; +?), то F(x) = 1.

Таким чином,

Використовуючи метод оберненої функції, отримаємо вираз для генерування випадкової величини Х. Для цього переозначимо F(x) як г, підставимо у попередні вирази та отримаємо х(г). Розглянемо інтервали для г, тому що на межах цих інтервалів значення функції розподілу змінюється. Ці інтервали є г є (0;1/6]; (1/6;2/6]; (2/6;1].

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

3.2.4 Метод кусково-лінійної апроксимації

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

Створимо процедуру імітації безперервного ВЧ Х із заданим законом розподілу F(x), (рис. 3.2). Розподілимо ось F(x) на n ділянок і визначимо відповідні їм значення аргументу на осі Х. Поєднавши всі точки , отримаємо кусково-лінійну апроксимацію функції F(x).

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

Рисунок. 3.2 - Кусково-лінійна апроксимація заданої функції розподілу

Скористаємося методом оберненої функції для кожного такого інтервалу. На першому етапі методу визначимо випадкову величину . Нехай значення г потрапило до i-го інтервалу. Тоді випадкову величину Х можна представити у вигляді

,

де - величина, визначена з подібності трикутників (рис. 3.1):



.

Так, алгоритм обчислення ВЧ методом кусково-лінійної апроксимації зводиться до виконання наступних дій:

1) генерується ВЧ ;

2) за г визначається інтервал ;

3) значення Х обчислюється за формулою .

Нехай потрібно одержати послідовність випадкових чисел, що мають нормальний розподіл:

,

де , - відповідно математичне сподівання та середньоквадратичне відхилення ВЧ Х. Тобто . Для такої залежності неможливо одержати обернену функцію F^-1.

Для розв'язання задачі скористаємося методом кусково-лінійної апроксимації. Процедура визначення ВЧ складається з двох етапів. На першому етапі здійснюємо генерування нормованої нормально розподіленої випадкової величини з і методом кусково-лінійної апроксимації. Щоб одержати , побудуємо кусково-лінійну апроксимацію функції (у вигляді )



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

3.2.5 Імітація дискретних випадкових величин

Розглянемо процедуру імітації дискретної випадкової величини х з заданим законом розподілу (табл. 3.1.).

Таблиця 3.1

Закон розподілу дискретної випадкової величини Х

Х	x1	x2	…	xn
P(x = xi)	P1	P2	…	Pn

Випадкова величина набуває n значень з імовірностями . При цьому функція розподілу дорівнює

,

де нерівність під знаком суми вказує на те, що підсумовування поширюється лише на такі значення x_i, що є меншими від x. Тоді функцію розподілу ВЧ Х можна визначити як наступне:

;

;

Для розв'язання задачі скористаємося методом оберненої функції, а саме знайдемо випадкову величину Х за допомогою :

якщо , то , інакше

якщо , то , інакше

якщо, то , інакше

.

Розглянемо приклад: нехай дискретна випадкова величина Х має такий закон розподілу:

P(1) = 0.25,

P(2) = 0.5,

P(3) = 0.25.

Визначимо функцію розподілу випадкової величини Х:

при ,

,

,

.

Графік функції розподілу зображений на рис. 3.3 а), а графік оберненої функції - на рисунку 3.3 б). Геометрична інтерпретація алгоритму зводиться до наступного: одиничний відрізок поділяється на n ділянок довжиною p₁, p₂, ..., p_n. Якщо ВЧ потрапило, наприклад, до ділянки p₃, тоді значення випадкової величини X буде дорівнювати x₃.

а)

б)

Рисунок 3.3 - Ілюстрація методу оберненої функції для одержання дискретної випадкової величини Х:

а) - графік функції розподілу F(x);

б) - графік оберненої функції

3.3 Завдання для самостійної роботи

1. Дискретна випадкова величина Х задана таблицею:

хi	4	6	10
Pi	0.2	0.3	0.5

Побудувати алгоритм моделювання випадкової величини Х. Узагальнити алгоритм для випадку .

2. Побудувати процедуру моделювання дискретної випадкової величини Х, заданої таблицею:

xi	4	8	9	10
Pi	0.3	0.3	0.2	0.2

3. Побудувати процедуру моделювання дискретної випадкової величини X, заданої:

xi	5	7	9	12
Pi	0.1	0.5	0.3	0.1

4. В урні є дві білих, три чорних і одна червона куля. Промоделювати процедуру виймання навмання з урни однієї кулі. Отримати 10 значень досліду.

5. Для випадкової величини побудувати алгоритм її моделювання.

6. Функція густини ймовірності представлена на рисунку 3.4. Обчислити параметр С і скласти алгоритм моделювання X за методом оберненої функції.

Рисунок 3.4 - Функція густини ймовірності

7. Функція густини ймовірності випадкової величини X представлена на рисунку 3.4. Скласти алгоритм моделювання випадкової величини.



Рисунок 3.4 - Функція густини ймовірності

8. Безперервна випадкова величина X задана функцією густини ймовірності

Визначити значення константи С₁ і записати вираз для моделювання X за методом оберненої функції.

9. Скласти алгоритм, який буде імітувати гру за наступним правилом: одночасно кидаються два кубики з цифрами на гранях від 1 до 6. Якщо сума цифр на верхніх гранях дорівнює 2 чи 12, гравець виграє 250 балів. При отриманій сумі 3 або 11 гравець виграє 100 балів, а при сумі 4 чи 10 виграш складає 50 балів. Якщо сума цифр має значення від 5 до 9, гравець програє 50 балів. Обчислити сподіваний виграш (або програш).

10. Побудувати процедуру моделювання випадкової величини, котра має густину розподілу (рис. 3.5), та отримати 2 її значення.

Рисунок 3.4 - Функція густини ймовірності



11. Розробити алгоритм моделювання випадкової величини X, яка має густину розподілу:

12. Побудувати процедуру моделювання безперервної випадкової величини та отримати щонайменше три її значення, якщо

.

13. Побудувати процедуру моделювання безперервної випадкової величини та отримати щонайменше три її значення, якщо

.

3.4 Контрольні питання

1. Які є способи генерування ВЧ та їх короткі характеристики?

2. Які переваги та недоліки є у апаратного способу імітації ВЧ?

3. Які переваги та недоліки є у табличного способу імітації випадкових величин?

4. Які переваги та недоліки є у алгоритмічного способу імітації ВЧ?

5. В чому полягає метод кусково-лінійної апроксимації?

6. Яким чином моделюються нормально розподілені випадкові величини?

7. Яким чином моделюються ВЧ, розподілені за експоненціальним законом?

8. Як відбувається моделювання ВЧ з довільним законом розподілу?

9. В чому полягає метод оберненої функції?

10. Що дозволяють моделювати конгруентні методи?

11. В чому полягає змішаний метод імітації ВЧ з рівномірним законом розподілу на інтервалі [0;1]?

12. В чому полягає мультиплікативний метод імітації ВЧ з рівномірним законом розподілу на інтервалі [0;1]?

13. Як моделюються дискретні ВЧ?

14. Які є вимоги до генераторів ВЧ?

4. ПРАКТИЧНІ ЗАНЯТТЯ 7 - 8

Системи масового обслуговування

4.1 Мета занять

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

4.2 Методичні вказівки для самостійної підготовки до занять

При підготовці до занять необхідно вивчити конспект лекцій та розділи, приведені в [1, 5, 7, 8, 9]. Далі наведені короткі теоретичні відомості з моделювання систем масового обслуговування (СМО). СМО є динамічним об'єктом, у якому виконується послідовність операцій з обслуговування потоку заявок. Елементи системи, у яких реалізуються операції, називаються обслуговуючими приладами (каналом). У теорії масового обслуговування фізична й алгоритмічна сутність операцій ігнорується.

Функціонування СМО є випадковим процесом з дискретними станами та безперервним часом. Стан СМО змінюється у моменти появи деяких подій (приходу нової заявки, закінчення обслуговування заявки, тощо). Математичний аналіз роботи СМО значно полегшується, якщо процеси, що протікають у ній будуть марковськими. Узагальнена структурна схема СМО приведена на рисунку 4.1.

Потоки заявок на обслуговування поділяються на типи, інтенсивність потоку заявок типу позначається як . Обслуговування заявок виконується сукупністю n різнотипних каналів і продовжується протягом випадкового часу . Випадковий характер потоку заявок і часів обслуговування здатний привести до того, що в деякі періоди часу на вході СМО накопичується надто велика кількість заявок. Вони або стають у чергу з числом місць , або залишають СМО без обслуговування, утворюючи потік відмов інтенсивністю . СМО також може працювати з недовантаженням або простоювати.

Рисунок 4.1 - Узагальнена структура СМО

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

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

4.2.1 Показники СМО

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

Однією з найважливіших характеристик СМО є її абсолютна пропускна здатність, або інтенсивність обслуговування, (л_об). Це середнє число заявок, що здатна обслужити система за одиницю часу:

.

Ймовірність відмови P_в є ймовірністю того, що довільно обрана заявка з вхідного потоку інтенсивністю л виявиться в потоці відмов інтенсивністю л_в:

.

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

Середній час перебування заявки в системі - це оцінка математичного сподівання часу перебування заявки в СМО. є випадковою величиною, котра дорівнює різниці часу від моменту надходження заявки у СМО до моменту її появи у вихідному потоці:

.

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

.

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

.

Тобто, для кожної СМО, за будь-якого характеру потоку заявок, з будь-яким розподілом часу обслуговування, з будь-якою дисципліною обслуговування середній час перебування заявки в системі дорівнює середньому числу заявок у системі, поділеному на інтенсивність потоку заявок. Друга формула Літтла пов'язує середній час перебування заявки в черзі і середнє число заявок у черзі :

.



4.2.2 Розрахунок показників СМО з найпростішими потоками подій

4.2.2.1 Одноканальна СМО з відмовами

Така СМО є найпростішою СМО без черги. До неї надходить потік заявок з інтенсивністю л, а інтенсивність обслуговування в ній - м. Заявка, котра надійшла в момент часу, коли канал був зайнятий, отримує відмову. Всі потоки подій є найпростішими.

Розглянемо приклад: телефонна станція з однією телефонною лінією працює так, що виклик, який прийшов у момент часу, коли лінія зайнята, одержує відмову. Інтенсивність потоку заявок л = 0.8 заявок у хвилину. Середня тривалість розмови t_об = 1.5 хв. Усі потоки подій - найпростіші. Визначити ймовірність обслуговування заявки, інтенсивність обслуговування заявок, імовірність відмови та порівняти фактичну пропускну здатність станції з номінальною.

Структурна схема такої СМО приведена на рисунку 4.2.

Рисунок 4.2 - Структурна схема одноканальної СМО з відмовами

Визначимо інтенсивність потоку обслуговуваних заявок:

м = 1/1.5 = 0.667.

В системі є наступні стани: S₀ - лінія вільна та S₁ - лінія зайнята. Граф станів системи приведений на рисунку 4.3.



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

Рисунок 4.3 - Граф станів СМО телефонної станції

Легко показати, що для розглянутої системи P₀ = P_об. Дійсно, P₀ є імовірністю того, що в момент часу t канал буде вільним (заявка, яка надійшла в момент часу t буде обслугована). Тоді . Також P₁ = P_в, отже л_в = лP_в.