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

Розділ 4

ЕЛЕМЕНТИ ТЕОРІЇ ВИПАДКОВИХ ПРОЦЕСІВ
ТА ТЕОРІЇ МАСОВОГО ОБСЛУГОВУВАННЯ

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

4.1. Означення випадкового процесу
та його характеристики

Випадковим процесом називається процес, значення якого за будь-якого значення аргументу t є випадковою величиною.

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

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

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

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

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

Рис. 16

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

Випадковий процес може бути заданий числовими характеристиками.

Математичним сподіванням випадкового процесу називається детермінована функція яка за будь-якого значення змінної t дорівнює математичному сподіванню відповідного перерізу випадкового процесу , тобто

Дисперсією випадкового процесу називається детермінована функція , яка за будь-якого значення змінної t дорівнює дисперсії відповідного перерізу випадкового процесу , тобто

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

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

Кореляційною функцією випадкового процесу називається детермінована функція:

двох змінних і , яка для кожної пари змінних і дорівнює коваріації відповідних перерізів і випадкового процесу.

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

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

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

Задача 55. Випадковий процес визначається формулою де Х — випадкова величина. Знайти основні характеристики цього процесу, якщо

Розв’язання. Згідно з властивостями математичного сподівання і дисперсії маємо:

.

Знаходимо далі кореляційну функцію

а також нормовану кореляційну функцію

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

4.2. Основні поняття теорії масового обслуговування

На практиці часто доводиться стикатися із системами, призначеними для багаторазового використання під час розв’язування однотипних задач. Процеси, які при цьому відбуваються, називають процесами обслуговування, а відповідні системи — системами масового обслуговування (СМО).

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

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

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

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

Показниками ефективності СМО є такі:

― середня кількість заявок, що їх вона обслуговує за одиницю часу;

― середня кількість заявок у черзі;

― середній час очікування обслуговування;

― імовірність відмови (відказу) в обслуговуванні без очікування;

― імовірність того, що кількість заявок у черзі перевищує певне значення тощо.

СМО поділяються на два основні класи: СМО з відмовами і СМО з очікуванням (чергою).

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

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

Процес роботи СМО являє собою випадковий процес.

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

Процес функціонування СМО являє собою випадковий процес із дискретними станами та неперервним часом.

Математичний аналіз роботи СМО істотно спрощується, якщо процес цієї роботи — марковський.

4.3. Поняття марковського процесу

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

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

Приклад. Система — лічильник у таксі. Стан системи в момент t характеризується кількістю кілометрів, пройдених автомобілем до даного моменту. Нехай у момент лічильник показує Імовірність того, що в момент лічильник показуватиме ту чи іншу кількість кілометрів залежить від але не залежить від того, в які моменти часу змінювались покази лічильника до моменту

Деякі процеси можна наближено вважати марковськими.

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

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

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

Розв’язання. Можливі стани системи: — обидва вузли справні; — перший вузол ремонтується, а другий справний;  — другий вузол ремонтується, а перший справний; — обидва вузли ремонтуються.

Граф системи наведено на рис. 17.

Рис. 17

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

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

4.4. Найпростіший потік подій

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

Потік називається найпростішим, якщо він має такі властивості:

1) стаціонарність — імовірність того, що за деякий проміжок часу t відбудеться та чи інша кількість подій, залежить лише від довжини проміжку і не залежить від початку його відліку, тобто інтенсивність потоку стала;

2) відсутність післядії — імовірність настання деякої кількості подій на довільному проміжку часу не залежить від того, яка кількість подій відбулась до початку цього проміжку;

3) ординарність — імовірність настання двох і більше подій за малий проміжок часу t істотно менша за ймовірність того, що відбудеться одна подія.

Якщо потік подій найпростіший, то ймовірність того, що за проміжок часу t подія А настане m раз, визначається формулою: де — інтенсивність потоку. Ця формула відбиває всі властивості найпростішого потоку, а отже, є його математичною моделлю.

Задача 57. Середня кількість заявок, які надходять до комбінату побутового обслуговування за 1 год, дорівнює 4. Знайти ймовірність того, що за 3 год надійде: 1) 6 заявок; 2) менш як 6 заявок; 3) не менш як 6 заявок.

Розв’язання. Нехай подія А — «надходження однієї заявки». Потік заявок найпростіший. Тому для розв’язування задачі застосуємо наведену щойно формулу, в якій Обчислимо відповідні ймовірності.

1)

2)

3)

4.5. Рівняння колмогорова. Граничні ймовірності станів

Імовірністю і-го стану називається ймовірність того, що в момент t система перебуватиме у стані

Очевидно, що для будь-якого моменту t сума ймовірностей станів дорівнює 1:

(1)

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

Наприклад, для системи що має чотири стани ; ; ; , система диференціальних рівнянь Колмогорова для ймовірностей станів набуває такого вигляду:

(2)

У системі (2) незалежних рівнянь на одне менше від загальної кількості рівнянь. Тому для розв’язування системи необхідно додати рівняння (1) при п = 3.

Особливість розв’язання диференціальних рівнянь взагалі полягає в тому, що потрібно задавати так звані початкові умови, у даному разі — імовірності станів системи в початковий момент Так, систему (2) маємо розв’язувати за умовою, що в початковий момент обидва вузли справні і система перебувала у стані , тобто за початкових умов

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

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

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

Задача 58. Знайти граничні ймовірності для системи з прикладу, наведеного на с. 114, граф станів якої наведено на рис. 4.2. При

Розв’язання. Система алгебраїчних рівнянь, що описує стаціонарний режим для даної системи, належить до виду (1):

Розв’язуючи цю систему рівнянь, дістаємо Отже, у граничному стаціонарному режимі система в середньому 40 % часу перебуватиме у стані 20 % — у стані 27 % — у стані 13 % — у стані

Задача 59. Знайти прибуток від експлуатації у стаціонарному режимі системи , коли відомо, що за одиницю часу справна робота першого та другого вузлів приносить дохід, який становить відповідно 10 і 6 ум. од., а їх ремонт потребує витрат, що становлять відповідно 4 і 2 ум. од.

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

Розв’язання. З прикладу 1 випливає, що в середньому перший вузол справний протягом частки часу, що становить р0 + р2 =
= 0,4 + 0,27 = 0,67, а другий вузол — протягом частки р0 + р1 =
= 0,4 + 0,2 = 0,6. В такому разі перший вузол перебуває в ремонті в середньому частку часу, що дорівнює р1 + р3 = 0,2 + 0,13 = 0,33, а другий — р2 + р3 = 0,27 + 0,13 = 0,4. Тому середній прибуток за одиницю часу від експлуатації системи (різниця між доходом та витратами) буде таким:

ПРИБУТОК = 0,67 · 10 + 0,60 · 6 – 0,33 · 4 – 0,40 ·2 = 8,18 (ум. од)

Зменшення вдвічі середнього часу ремонту кожного з вузлів згідно з означатиме збільшення вдвічі інтенсивності потоку «закінчення ремонту» кожного вузла. Отже, у такому разі і система лінійних алгебраїчних рівнянь (1) набирає вигляду:

Розв’язуючи цю систему, дістаємо