Загальні положення

Моделювання дискретних марківських систем. Дискретні системи характеризуються скінченою множиною станів. Такі системи описуються марківськими процесами, а також скінченими та ймовірнісними авто­ма­тами. Визначення марківського процесу або процесу без післядії наведено у п. 1.3.2. Для моделювання однорідних марківських випадкових процесів з дискретними станами використовуються:

· набір станів S ₁, S ₂, …, S_n, у яких може знаходитися випадковий процес;

· матриця ймовірностей переходів P = [ p_ij, ] для процесів з дискретним часом, елементи якої задовольняють умові

, (); ; (10.1)

· початкові ймовірності

, . (10.2)

Марківський процес називається однорідним, якщо ймовірності не залежать від кроку k переходу системи від стану S_i до S_j, тобто P_ij (k) = P_ij. Для аналізу у таких системах зручно користуватися графом станів, який відобра­жає можливі стани системи (вузли графа) і переходи між ними (дуги графа). Такий граф називається розміченим графом станів.

Якщо відома матриця ймовірностей переходів (або розміщений граф станів) і початковий розподіл (у момент часу t = 0) ймовірностей для всіх станів P_i (0), (), то ймовірності станів P_i (k), () для будь-якого кроку переходу визначатися за формулою

, (10.3)

де – ймовірність переходу системи зі стану S_j → S_i за k кроків.

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

Приклад. Система складається з двох пристроїв Y ₁та Y ₂. Кожен з них може знаходитися у двох станах: 0 – включений, 1 – виключений. У певні моменти часу виділені такі стани системи:

Si	S 0	S 1	S 2	S 3
y 1
y 2

Задана матриця ймовірностей переходів

		S 0	S 1	S 2	S 3
	S 0		0.2	0.5	0.3
P =	S 1	0.5		0.1	0.4
S 2	0.5			0.5
	S 3		0.4	0.6

і початкові ймовірності р ₀(0) = 0.8, р ₁(0) = 0.2, р ₂(0) = 0, р ₃(0) = 0.

Визначимо ймовірності знаходження системи у станах S_i (i = 0, 1, 2, 3) у будь-які моменти часу.

Згідно з (10.3) ймовірності станів системи будуть:

· на першому кроці (k = 1):

р ₀(1) = р ₀(0) р ₀₀ + р ₁(0) р ₁₀ + р ₂(0) р ₂₀ + р ₃(0) р ₃₀ = 0,1;

р ₁(1) = р ₀(0) р ₀₁ + р ₁(0) р ₁₁ + р ₂(0) р ₂₁ + р ₃(0) р ₃₁ = 0,16;

р ₂(1) = р ₀(0) р ₀₂ + р ₁(0) р ₁₂ + р ₂(0) р ₂₂ + р ₃(0) р ₃₂ = 0,42;

р ₃(1) = р ₀(0) р ₀₃ + р ₁(0) р ₁₃ + р ₂(0) р ₂₃ + р ₃(0) р ₃₃ = 0,32;

· на другому кроці (k = 2):

р ₀(2) = р ₀(1) р ₀₀ + р ₁(1) р ₁₀ + р ₂(1) р ₂₀ + р ₃(1) р ₃₀ = 0,29;

р ₁(2) = р ₀(1) р ₀₁ + р ₁(1) р ₁₁ + р ₂(1) р ₂₁ + р ₃(1) р ₃₁ = 0,148;

р ₂(2) = р ₀(1) р ₀₂ + р ₁(1) р ₁₂ + р ₂(1) р ₂₂ + р ₃(1) р ₃₂ = 0,258;

р ₃(2) = р ₀(1) р ₀₃ + р ₁(1) р ₁₃ + р ₂(1) р ₂₃ + р ₃(1) р ₃₃ = 0,304.

Аналогічно розраховуються ймовірності станів для інших кроків. Неважко переконатися, що для k = 1, 2,... виконується умова р ₀(k) + р ₁(k) + р ₂(k) + р ₃(k) = 1. Значення р ₀, р ₁, р ₂, р ₃ з врахуванням умови нормування визначаються з рівнянь:

Розв’язуючи таку систему рівнянь, отримаємо значення ймовірностей:

, , , .

Отже, система знаходиться у робочому стані більше 76% часу і протягом 29,1% часу будуть включені обидва пристрої Y ₁та Y ₂. Протягом 23,6% часу система перебуватиме у неробочому стані. В середньому, у включеному стані перебуватиме один пристрій, оскільки р ₁ + р ₂ + 2 р ₃ = 1,055.

Суть моделювання марківських процесів зводиться до моделювання повної групи випадкових подій із використанням рівномірно розподілених випадкових чисел r_i Î (0,1). Результат кожного наступного переходу залежить від попереднього стану. Процедура моделювання складається з двох етапів.

На першому етапі згідно з дискретним розподілом, заданим матрицею-рядком початкових ймовірностей Р (0), розігрується початковий стан марківського процесу S ₀. Якщо виконується умова

, де , , ,

тоді будемо вважати, що на початку моделювання система знаходиться у стані S ₀ = S_i.

На другому етапі поступаємо аналогічно з j -м рядком матриці Р (1). Використовуємо алгоритм моделювання повної групи подій. Отриманий результат дає номер рядка матриці Р (1) для наступного кроку моделювання. Процедура повторюється до здійснення заданої кількості кроків. Результатом моделювання є послідовність станів системи, що пов’язані між собою відповідними переходами із стану в стан.

Моделювання ймовірнісного автомата. Поняття ймовірнісного авто­мата є узагальненням математичних моделей систем, які функціонують у дискретному часі t із дискретними імовірнісними множинами вхідних Х, вихідних Y сигналів та внутрішніх станів Z. Таким чином, для опису скінче­ного ймовірнісного автомата з випадковими переходами необхідно знати:

· множину станів Z = { z ₁, z ₂, …, z_n } і дискретний розподіл ймовір­ностей початкових станів

, ;

· множину вхідних сигналів Х = { х ₁, х ₂, …, х_l } і дискретний розподіл ймовір­ностей вхідних сигналів

, ;

· функцію переходів Н за допомогою сукупності матриць ймовірнос­тей переходів

,

де – умовні ймовірності того, що за умови, що , , .

Ймовірнісний автомат із випадковими переходами функціонує наступ­ним чином. У початковий момент часу t ₀ згідно з дискретним розподілом Р_і (0) в автоматі встановлюється деякий початковий стан z ₀ = z_i. У момент часу t_k, k = 1, 2, … на вхід автомата поступає вхідний сигнал , значення якого формується згідно з дискретним розподілом Р_х. За значенням x_s із матриць Р (1, x_s) вибирають одну, що відповідає номеру S. За станом автомата на попередньому такті t_{k- 1} у стохастичній матриці вибирають єдиний рядок

.

Відповідно до дискретного розподілу ймовірностей Pz (s,i) автомат у момент часу t_k переходить у новий стан . Згідно заданої функції виходів G на виході автомата встановлюється вихідний сигнал

.

Отже, моделювання ймовірнісного автомата з випадковими переходами зводиться до розіграшу повної групи подій згідно з дискретними розподілами Pz (0), Px, Pz (s,i) і алгоритм моделювання містить такі етапи:

· моделювання випадкового початкового стану автомата;

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

· моделювання послідовності випадкових переходів автомата;

· визначення вихідного сигналу автомата.

Завдання для виконання роботи

Відповідно до заданого варіанту необхідно виконати наступні дії:

· отримати послідовність вхідних сигналів, станів та вихідних сигналів на кожному з кроків;

· навести результати виконання етапів моделювання відповідно до індивідуального завдання;

· розробити програмний код для реалізації алгоритмів.

Індивідуальні завдання для моделювання

Варіант 1. Операційна система (ОС) приймає для оброблення три класи завдань А, В і С з різним обсягом оперативної пам'яті. Ймовір­нос­ті появи завдань Р(А) = 0,5; Р(В) = 0,3; Р(С) = 0,2. В момент надходження завдання система може знаходитися в одному з двох станів: z ₁– має вільні ресурси і може прийняти додаткові завдання; z ₂ – монополізована поперед­німи завданнями. Матриці перехідних ймовірностей системи такі:

Змоделювати роботу ОС при надходженні k = 20 завдань, якщо функціонування системи починається за відсутності завдань.

Варіант 2. Ремонтний цех, що включає в себе декілька ліній, здійснює обслуговування блоків з різним ступенем пошкодження. Можливі пошкодження трьох типів: А, В і С, ймовірності настання яких Р(А) = 0,5; Р(В) = 0,15; Р(С) = 0,35. Блоки надходять у цех в дискретні моменти часу. Можливі стани цеху: z₁ – є хоча б одна лінія, на яку надходить блок; z ₂ – всі лінії зайняті. Матриці перехідних ймовірностей станів цеху:

Змоделювати роботу цеху з обслуговування k = 18 блоків, якщо в початковий момент всі лінії цеху вільні.

Варіант З. Система передавання даних має два незалежні канали. Через кожні 30 с надходять повідомлення для передавання. Кожний із каналів може знаходитися в одному з двох станів: z ₁ – вільний; z ₂– зайнятий передаванням повідомлення. Матриці перехідних ймовірностей і початкових ймовірностей першого і другого каналів відповідно мають вигляд:

Змоделювати стани системи передавання за 10 хв.

Варіант 4. Процесор автоматизованої інформаційної системи може перебу­вати в одному зі станів:

z ₁- обробка інформації;

z ₂ - простій через несправність процесора;

z ₃- простій через відсутність інформації.

Контроль станів системи здійснюється через кожні 15 хв. Якщо виявлена несправність фахівці приступають до ремонту. Матриця початкових ймовірностей станів системи має вигляд Р (0) = (0,5 0,4 0,4), а матриця перехідних ймовірностей

Змоделювати процес роботи системи за 5 год.

Варіант 5. Електронний блок експлуатується в одному з таких режимів: Х ₁, Х ₂, Х ₃, імовірності виникнення яких відповідно Р (Х ₁) = 0.5; Р (Х ₂) = 0.3; Р(Х ₃) = 0.2. Інтенсивність відмов блоку залежить від режиму роботи. Стани блоку: z ₁ – справний; z ₂ – несправний. У випадку відмови блок відновлюється. Змоделювати стани блоку в дискретні моменти контролю t_k , t = 1, 2,..., 20. У початковий момент роботи блок справний, а матриці перехідних ймовірностей рівні

Варіант 6. Точка А „блукає” на осі абсцис відповідно до закону – на кожному кроці вона з ймовірністю 0,5 залишається на місці, із ймовірністю 0,3 зміщується на одиницю вправо і з ймовірністю 0,2 – вліво.

Промоделювати реалізацію переходів і визначити кінцевий стан точки А за k = 20 кроків, якщо її початковий стан перебуває в початку координат.

Варіант 7. Тригер може знаходитися в одному з двох стійких станів: z ₁ = 0 і z ₂= 1. Сукупність вхідних сигналів надходить у дискретні моменти часу t₁, t ₂ ,... і приймає дві різні комбінації значень, які кодуються X ₁ і Х ₂, і переводять тригер з одного стану в інший. Тригер функціонує в стохастичних умовах під дією внутрішніх і зовнішніх випадкових збурень. Ймовірності вхідних сигналів: Р(Х ₁) = 0.55; Р(Х ₂) = 0.45. Матриці перехідних ймовірностей:

Змоделювати переходи станів тригера за k = 20 тактів, якщо його початкові стани рівномірні.

Варіант 8. ОС включає в себе два процесори. Завдання на оброблення надто­дять кожні 30 хв. і залежно від складності займають один або два процесори. Система може знаходитись в станах: z₁ – справні два процесори; z ₂ – справний перший процесор; z ₃– справний другий процесор; z ₄ – обидва процесори несправні. Процесор, що вийшов з ладу, відновлюється. Змоделювати стан системи протягом 10 год, якщо в початковий момент два процесори справні, а матриці перехідних ймовірностей кожного процесора мають вигляд:

Варіант 9. Двоканальна інформаційна система функціонує з різними рівнями сигналу, які змінюються стрибкоподібно і можуть бути віднесені до одного з двох класів А і В, що не перетинаються. В кожний момент контролю t_k, k = 1, 2,... система може знаходитися в одному зі станів: z ₁ – обидва канали в робочому стані; z ₂– один канал несправний; z ₃ – система вийшла з ладу. Відомі ймовірності появи сигналів: Р(А) = 0.7, Р(В) = 0.3, а також матриці перехід­них ймовірностей системи:

Змоделювати стани системи за k = 15 тактів контролю, якщо на початку працездатні обидва канали.

Варіант 10. Інформаційна система, яка складається з т = 2 незалежних об'єктів, кожні 15 хв. піддається контролю. Кожний із об'єктів системи може знаходитись в одному з двох станів: z₁ – справний; z ₂– несправний. Матриці перехідних ймовірностей об'єктів контролю мають вигляд:

Змоделювати зміни станів системи за 5 год, якщо в початковий момент (t = 0) обидва об'єкти справні.

Варіант 11. Ймовірнісний автомат поданий двоканальною технічною систе­мою. В кожний момент t_k контролю системи вхідні дії X(t_k) можуть відпо­ві­дати одному з двох можливих режимів експлуатації: – нормальному; – форсованому, а система може знаходитися в одному зі станів: z ₁ – справні два канали; z ₂ – несправний один канал (він відновлюється); z ₃ – система не пра­цює. Відомі матриця розподілу вхідних дій P (х ₁)= 0,7; Р (х ₂) = 0,3 і матриці умовних перехідних ймовірностей станів системи:

Змоделювати процес функціонування системи за k = 20 тактів контролю, якщо на початковий момент (t = 0)система знаходилася в справному стані.

Варіант 12. Змоделювати процес функціонування імовірнісного автомата з випадковими переходами за k = 20 тактів, якщо його вхідний алфавіт двій­ковий X = { х ₁, х ₂}, множини станів автомата Z і вихідний алфавіт Y трійкові z = { z ₁,z₂, z ₃}, у = { у ₁, у ₂, у ₃}Матриця переходів станів автомата має вигляд:

Початковий стан z ₀і вхідний сигнал X автомата задані розподілами: Р_z (0) = [ Pz ₀₁ = 0,7 Pz ₀₂= 0.3 Pz ₀₃= 0]; Р_х (0) = [ Рх ₁= 0.5 Рх ₂ = 0.5]. Функція виходів автомата детермінована і задає вихідний сигнал у_i (t_k) = z_i { t_k }.

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

Змоделювати процес функціонування блока за 5 год., якщо в початковий момент (t = 0)обидва вузли справні.

Варіант 14. На складі зберігаються і видаються для проведення ремонту інформаційно-обчислювальної техніки запасні частини. Замовлення на видачу комплектів надходять через 2 год. У процесі роботи склад може знаходитися в одному зі станів: z ₁– наявні всі необхідні комплекти; z ₂ – видаються деякі з необхідних комплектів; z ₃ – необхідні комплекти відсутні. Змоделювати процес роботи складу протягом 40 год, якщо матриці перехідних П (1) і початкових Р (0)ймовірностей мають вигляд:

Варіант 15. Інформаційна система в дискретні моменти часу під впливом двійкового вхідного сигналу X = {0; 1} і внутрішніх випадкових факторів змінює свій стан на множині Z = { z ₁ z ₂ z ₃ z₄ }. Відомі дискретні розподіли ймовірностей вхідного сигналу Р_х і початкового стану системи P_z (0):

Р_х = [0,750,25]; P_z (0) = [0,4 0,3 0,2 0,1],

а також матриці перехідних ймовірностей:

Змоделювати процес зміни станів системи за k = 20тактів контролю.