Найпростіші потоки марківські процеси та ланцюги рішення. Опис інформаційних систем за допомогою теорії випадкових марківських процесів

Федеральне агентство з освіти РФ

ФГОУ СПО «Перевізський будівельний коледж»

Курсова робота

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

на тему «СМО з обмеженим часом очікування. Замкнуті СМО»

Вступ................................................. .................................................. ....... 2

1. Основи теорії масового обслуговування............................................ ...... 3

1.1 Поняття випадкового процесу.............................................. .................... 3

1.2 Марківський випадковий процес.............................................. ................ 4

1.3 Потоки подій............................................... .......................................... 6

1.4. Рівняння Колмогорова для ймовірностей станів. Фінальні ймовірності станів............................................... .................................................. ........ 9

1.5 Завдання теорії масового обслуговування............................................. .. 13

1.6 Класифікація систем масового обслуговування 15

2. Системи масового обслуговування з очікуванням 16

2.1 Одноканальна СМО з очікуванням ............................................. ........... 16

2.2 Багатоканальна СМО з очікуванням ............................................. ......... 25

3. Замкнуті СМО.............................................. .......................................... 37

Рішення завдання................................................ ............................................. 45

Висновок................................................. .................................................. 50

Список літератури................................................ ....................................... 51

У цьому курсі ми розглядатимемо різні системи масового обслуговування (СМО) та мережі масового обслуговування (СМО).

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

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

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

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

Теорія масового обслуговування становить один із розділів теорії ймовірностей. У цій теорії розглядаються імовірніснізавдання та математичні моделі (до цього нами розглядалися детерміновані математичні моделі). Нагадаємо, що:

Детермінована математична модельвідображає поведінку об'єкта (системи, процесу) з позицій повної визначеностіу теперішньому та майбутньому.

Ймовірнісна математична модельвраховує вплив випадкових чинників поведінка об'єкта (системи, процесу) і, отже, оцінює майбутнє з позицій ймовірності тих чи інших подій.

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

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

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

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

Приклади:

1. Система S- технологічна система (дільниця верстатів). Верстати іноді виходять з ладу і ремонтуються. Процес, який у цій системі, випадковий.

2. Система S- Літак, що здійснює рейс на заданій висоті за певним маршрутом. Обурювальні чинники – метеоумови, помилки екіпажу тощо, наслідки – «болтанка», порушення графіка польотів тощо.

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

Нехай зараз t 0 система знаходиться у певному стані S 0 . Ми знаємо характеристики стану системи в теперішньому і все, що було при t <t 0 (передісторію процесу). Чи можемо передбачити (передбачити) майбутнє, тобто. що буде за t >t 0? В точності - ні, але якісь ймовірнісні характеристики процесу в майбутньому знайти можна. Наприклад, ймовірність того, що через деякий час система Sвиявиться в стані S 1 або залишиться в стані S 0 і т.д.

приклад. Система S- Група літаків, що беруть участь у повітряному бою. Нехай x– кількість «червоних» літаків, y- кількість "синіх" літаків. На момент часу t 0 кількість літаків, що збереглися (не збитих) відповідно – x 0 , y 0 . Нас цікавить ймовірність того, що в момент часу чисельна перевага буде на боці червоних. Ця ймовірність залежить від того, в якому стані знаходилася система у момент часу t 0 , а не від того, коли і в якій послідовності гинули збиті до моменту t 0 літаки.

Насправді Марківські процеси у чистому вигляді зазвичай зустрічаються. Але є процеси, котрим впливом «передісторії» можна знехтувати. І при вивченні таких процесів можна застосовувати Марківські моделі (теоретично масового обслуговування розглядаються і не Марківські системи масового обслуговування, але математичний апарат, який їх описує, набагато складніше).

У дослідженні операцій велике значення мають Марківські випадкові процеси з дискретними станами та безперервним часом.

Процес називається процесом із дискретним станом, якщо його можливі стани S 1 , S 2, … можна заздалегідь визначити, і перехід системи зі стану в стан відбувається «стрибком» практично миттєво.

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

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

S 0 - обидва верстати справні;

S 1 - перший верстат ремонтується, другий справний;

S 2 - другий верстат ремонтується, перший справний;

S 3 - обидва верстати ремонтуються.

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

При аналізі випадкових процесів із дискретними станами зручно користуватися геометричною схемою – графом станів. Вершини графа – стану системи. Дуги графа - можливі переходи зі стану в стан. Для нашого прикладу граф станів наведено на рис. 1.

Мал. 1. Граф станів системи

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

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

У попередньому прикладі – це потік відмов та потік відновлень. Інші приклади: потік дзвінків на телефонній станції, потік покупців у магазині тощо.

Потік подій можна зобразити поруч точок на осі часу O t- Мал. 2.

Мал. 2. Зображення потоку подій на осі часу

Положення кожної точки випадково, і тут зображена лише одна реалізація потоку.

Інтенсивність потоку подій ( ) - Це середня кількість подій, що припадає на одиницю часу.

Розглянемо деякі властивості (види) потоків подій.

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

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

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

Потік подій називається ординарнимякщо події в ньому з'являються поодинці, а не групами по кілька відразу.

Потік подій називається найпростішим (або стаціонарним пуассонівським),якщо він має відразу три властивості:

1) стаціонарний;

2) ординарний;

3) немає наслідків.

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

Для найпростішого потоку з інтенсивністю інтервал Tміж сусідніми подіями має так зване показовий (експоненційний) розподіліз щільністю:

де – параметр показового закону.

Для випадкової величини T, Що має показовий розподіл, математичне очікування є величина, обернена параметру, а середнє квадратичне відхилення дорівнює математичному очікуванню:

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

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

Для наочності на графі станів системи у кожної дуги проставляють інтенсивності потоку подій, який переводить систему з цієї дузі (стрілці). - Інтенсивність потоку подій, що переводить систему зі стану в. Такий граф називається розміченим. Для нашого прикладу розмічений граф наведено на рис. 3.

Мал. 3. Розмічений граф станів системи

На цьому малюнку – інтенсивності потоку відмов; - Інтенсивності потоку відновлень.

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

Нехай система перебуває в стані S 0 . У стан S 1 її переводить потік відмов першого верстата. Його інтенсивність дорівнює:

де – середній час безвідмовної роботи першого верстата.

Зі стану S 1 в S 0 систему переводить потік «закінчень ремонтів» першого верстата. Його інтенсивність дорівнює:

де – середній час ремонту першого верстата.

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

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

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

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

де - Кінцева кількість станів системи.

Фінальні ймовірності станів– це не змінні величини (функції часу), а постійні числа. Очевидно, що:

Фінальна ймовірність стану- Це по-суті середнє відносне час перебування системи в цьому стані.

Наприклад, система Sмає три стани S 1 , S 2 та S 3 . Їхні фінальні ймовірності рівні відповідно 0,2; 0,3 та 0,5. Це означає, що система у граничному стаціонарному стані в середньому 2/10 часу проводить у стані S 1 , 3/10 – у стані S 2 та 5/10 – у стані S 3 .

Правило складання системи рівнянь Колмогорова: у кожному рівнянні системи у лівій його частиністоїть фінальна ймовірність цього стану, помножена на сумарну інтенсивність всіх потоків, провідних із цього стану, а у правій його частини– сума творів інтенсивностей усіх потоків, що входять до -е стан, На ймовірність тих станів, з яких ці потоки виходять.

Користуючись цим правилом, напишемо систему рівнянь для нашого прикладу :

.

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

Продовження прикладу. Нехай значення інтенсивностей потоків дорівнюють: .

Четверте рівняння відкидаємо, додаючи замість нього нормувальну умову:

.

Тобто. у граничному, стаціонарному режимі система Sв середньому 40% часу проводитиме в стані S 0 (обидва верстати справні), 20% - у стані S 1 (перший верстат ремонтується, другий працює), 27% - у стані S 2 (другий верстат ремонтується, перший працює), 13% - у стані S 3 (обидва верстати ремонтуються). Знання цих фінальних ймовірностей може допомогти оцінити середню ефективність роботи системи та завантаження ремонтних органів.

Нехай система Sв стані S 0 (цілком справна) приносить в одиницю часу дохід 8 умовних одиниць, в стані S 1 – дохід 3 умовні одиниці, у стані S 2 – дохід 5 умовних одиниць, може S 3 – не дає доходу. Тоді в граничному, стаціонарному режимі середній дохід в одиницю часу дорівнюватиме: умовних одиниць.

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

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

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

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

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

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

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

Перший поділ (за наявності черг):

1. СМО з відмовами;

2. СМО з чергою.

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

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

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

Отже, наприклад, розглядаються такі СМО:

· СМО з нетерплячими заявками (довжина черги та час обслуговування обмежений);

· СМО з обслуговуванням із пріоритетом, тобто. деякі заявки обслуговуються позачергово тощо.

Крім цього СМО діляться на відкриті СМО та замкнуті СМО.

У відкритій СМОПоказники потоку заявок не залежить від того, в якому стані сама СМО (скільки каналів зайнято). У замкнутій СМО- Залежать. Наприклад, якщо один робітник обслуговує групу верстатів, іноді потребують налагодження, то інтенсивність потоку «вимог» з боку верстатів залежить від того, скільки на них вже справно і чекає налагодження.

Класифікація СМО далеко не обмежується наведеними різновидами, але цього достатньо.

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

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

Нумеруватимемо стани СМО за кількістю заявок, що знаходяться в системі (як обслуговуються, так і тих, що очікують обслуговування):

Канал вільний;

Канал зайнятий, черги немає;

Канал зайнятий, одна заявка стоїть у черзі;

Канал зайнятий, k-1 заявок стоять у черзі;

Канал зайнятий, т-заявок стоять у черзі.

ГСП показано на рис. 4. Усі інтенсивності потоків подій, що переводять у систему за стрілками зліва направо, рівні , а справа наліво - . Дійсно, за стрілками зліва направо систему переводить потік заявок (як тільки прийде заявка, система переходить у наступний стан), справа ж ліворуч - потік «звільнень» зайнятого каналу, що має інтенсивність (як тільки буде обслуговано чергову заявку, канал або звільниться, або зменшиться кількість заявок у черзі).

Мал. 4. Одноканальна СМО з очікуванням

Зображена на рис. 4 схема являє собою схему розмноження та загибелі. Напишемо вирази для граничних ймовірностей станів:

(5)

або з використанням:

(6)

Останній рядок (6) містить геометричну прогресію з першим членом 1 і знаменником р, звідки отримуємо:

(7)

у зв'язку з чим граничні ймовірності набувають вигляду:

(8).

Вираз (7) справедливо лише за< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:

Визначимо характеристики СМО: ймовірність відмови, відносну пропускну здатність q, абсолютну пропускну здатність А, середню довжину черги, середню кількість заявок, пов'язаних із системою, середній час очікування в черзі, середній час перебування заявки до СМО.

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

(9).

Відносна пропускна спроможність:

(10).

Середня довжина черги. Знайдемо середню кількість -заявок, що у черзі, як математичне очікування дискретної випадкової величини R-числа заявок, що у черги:

З ймовірністю в черзі стоїть одна заявка, з ймовірністю - дві заявки, взагалі з ймовірністю в черзі стоять k-1 заявок, і т.д., звідки:

(11).

Оскільки , суму (11) можна трактувати як похідну від суми геометричної прогресії:

Підставляючи цей вираз у (11) і використовуючи з (8), остаточно отримуємо:

(12).

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

.

та середня кількість заявок, пов'язаних із СМО, дорівнює:

(13).

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

Якщо ж k=m+1, тобто. коли заявка, що знову приходить, застає канал обслуговування зайнятим і m-заявок у черзі (ймовірність цього), то в цьому випадку заявка не стає в чергу (і не обслуговується), тому час очікування дорівнює нулю. Середній час очікування дорівнюватиме:

якщо підставити сюди вирази для ймовірностей (8), отримаємо:

(14).

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

(15).

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

.

Приклад 1. Автозаправна станція (АЗС) є СМО з одним каналом обслуговування (одною колонкою).

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

Визначити:

ймовірність відмови;

відносну та абсолютну пропускну здатність АЗС;

середня кількість машин, що очікують заправки;

середня кількість машин, що знаходяться на АЗС (включаючи обслуговувану);

середній час очікування машини у черзі;

середній час перебування машини на АЗС (включно з обслуговуванням).

Інакше висловлюючись, середній час очікування дорівнює середньому числу заявок у черзі, поділеному інтенсивність потоку заявок.

Знаходимо спочатку наведену інтенсивність потоку заявок: = 1/1,25 = 0,8; = 1/0,8 = 1,25.

За формулами (8):

Імовірність відмови 0,297.

Відносна пропускна здатність СМО: q=1-=0,703.

Абсолютна пропускна здатність СМО: A==0,703 машини за хв.

Середню кількість машин у черзі знаходимо за формулою (12):

тобто. середня кількість машин, які чекають у черзі на заправку, дорівнює 1,56.

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

отримуємо середню кількість машин, пов'язаних із АЗС.

Середній час очікування машини у черзі за формулою (15):

Додаючи до цієї величини, отримаємо середній час, який машина проводить на АЗС:

Системи із необмеженим очікуванням. У таких системах значення т не обмежена і, отже, основні характеристики можуть бути отримані шляхом граничного переходу раніше отриманих виразах (5), (6) і т.п.

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

Може бути доведено, що<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.

Якщо, то співвідношення (8) набувають вигляду:

(16).

За відсутності обмежень за довжиною черги кожна заявка, яка прийшла в систему, буде обслуговується, тому q=1, .

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

Середня кількість заявок у системі за формулою (13) при:

.

Середній час очікування отримаємо з формули (14) за:

.

Зрештою, середній час перебування заявки до СМО є:

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

Стан системи нумерується за кількістю заявок, пов'язаних системою:

немає черги:

Усі канали вільні;

Зайнятий один канал, інші вільні;

Зайняті-каналів, решта немає;

Зайняті всі каналів, вільних немає;

є черга:

Зайняті всі n-каналів; одна заявка стоїть у черзі;

Зайняті всі n-каналів, r-заявок у черзі;

Зайняті всі n-каналів, r-заявок у черзі.

ДСП наведено на рис. 17. У кожної стрілки проставлено відповідні інтенсивності потоків подій. За стрілками зліва направо систему переводить завжди той самий потік заявок з інтенсивністю , по стрілках праворуч наліво систему переводить потік обслуговування, інтенсивність якого дорівнює , помноженому на кількість зайнятих каналів.

Мал. 17. Багатоканальна СМО з очікуванням

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

Отже, всі ймовірності станів знайдено.

Визначимо показники ефективності системи.

Ймовірність відмови. Заявка, що надійшла, отримує відмову, якщо зайняті всі n-каналів і всі m-місць у черзі:

(18)

Відносна пропускна здатність доповнює можливість відмови до одиниці:

Абсолютна пропускна здатність СМО:

(19)

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

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

Середню кількість заявок у черзі можна обчислити безпосередньо як математичне очікування дискретної випадкової величини:

(20)

Тут знову (вираз у дужках) зустрічається похідна суми геометричної прогресії (див. вище (11), (12) - (14)), використовуючи співвідношення для неї, отримуємо:

Середня кількість заявок у системі:

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

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

(21)

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

.

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

.

Системи із необмеженою довжиною черги. Ми розглянули канальну СМО з очікуванням, коли в черзі одночасно можуть бути не більше m-заявок.

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

Імовірність станів отримаємо з формул граничним переходом (при ). Зауважимо, що сума відповідної геометричної прогресії сходить при і розходиться при >1. Припустивши, що<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

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

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

,

а середній час очікування – з (21):

.

Середня кількість зайнятих каналів, як і раніше, визначається через абсолютну пропускну здатність:

.

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

Приклад 2. Автозаправна станція із двома колонками (n = 2) обслуговує потік машин з інтенсивністю =0,8 (машин на хвилину). Середній час обслуговування однієї машини:

У даному районі немає іншої АЗС, тож черга машин перед АЗС може рости практично необмежено. Знайти властивості СМО.

Оскільки<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

і т.д.

Середня кількість зайнятих каналів знайдемо, розділивши абсолютну пропускну здатність СМО А==0,8 на інтенсивність обслуговування =0,5:

Імовірність відсутності черги біля АЗС буде:

Середня кількість машин у черзі:

Середня кількість машин на АЗС:

Середній час очікування у черзі:

Середній час перебування машини на АЗС:

СМО з обмеженим часом очікування. Раніше розглядалися системи з очікуванням, обмеженим лише довжиною черги (числом m-заявок, що одночасно перебувають у черзі). У такій СМО заявка, що розростала в чергу, не залишає її, доки не дочекається обслуговування. Насправді зустрічаються СМО іншого типу, у яких заявка, почекавши деякий час, може піти з черги (так звані «нетерплячі» заявки).

Розглянемо СМО такого типу, припускаючи, що обмеження часу очікування є випадковою величиною.

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

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

немає черги:

Усі канали вільні;

Зайнятий один канал;

Зайнято два канали;

Зайняті всі n-каналів;

є черга:

Зайняті всі n-каналів, одна заявка стоїть у черзі;

Зайняті всі n-каналів, r-заявок стоять у черзі тощо.

Граф станів та переходів системи показаний на рис. 23.

Мал. 23. СМО з обмеженим часом очікування

Розмітимо цей граф, як і раніше; у всіх стрілок, що ведуть зліва направо, стоятиме інтенсивність потоку заявок. Для станів без черги у стрілок, що ведуть з них справа наліво, буде, як і раніше, стояти сумарна інтенсивність потоку обслуговування всіх зайнятих каналів. Що стосується станів з чергою, то у стрілок, що ведуть з них справа наліво, стоятиме сумарна інтенсивність потоку обслуговування всіх n-каналів плюс відповідна інтенсивність потоку відходів з черги. Якщо в черзі стоять r-заявок, то сумарна інтенсивність потоку догляду дорівнюватиме .

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

(24)

Зазначимо деякі особливості СМО з обмеженим очікуванням порівняно з раніше розглянутими СМО з «терплячими» заявками.

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

Навпаки, в СМО з «нетерплячими» заявками, що йдуть рано чи пізно з черги, режим обслуговування, що встановився, досягається завжди, незалежно від наведеної інтенсивності потоку заявок . Це випливає з того, що ряд для знаменника формули (24) сходиться при будь-яких позитивних значеннях і .

Для СМО з «нетерплячими» заявками поняття «імовірність відмови» не має сенсу – кожна заявка стає в чергу, але може і не дочекатися обслуговування, пішовши раніше.

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

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

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

(26)

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

а середнє число зайнятих каналів, що входить у цю формулу, можна знайти як математичне очікування випадкової величини Z, що приймає значення 0, 1, 2,..., n з ймовірностями ,:

На закінчення зазначимо, що й у формулах (24) перейти до межі при (чи, що те, при ), то при вийдуть формули (22), т. е. «нетерплячі» заявки стануть «терплячими».

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

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

Нехай n- Число каналів обслуговування, s- Число потенційних заявок, n <s , - Інтенсивність потоку заявок кожної потенційної вимоги, μ - Інтенсивність обслуговування:

Імовірність простою системи визначається формулою

Р 0 = .

Фінальні ймовірності станів системи:

P k= при k = при .

Через ці ймовірності виражається середня кількість зайнятих каналів

=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s)або

=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).

Через знаходимо абсолютну пропускну здатність системи:

а також середня кількість заявок у системі

М=s-=s-.

Приклад 1. На вхід триканальної СМО з відмовами надходить потік заявок з інтенсивністю =4 заявки за хвилину, час обслуговування заявки одним каналом tобсл =1/μ =0,5 хв. Чи вигідно з погляду пропускної спроможності СМО змусити всі три канали обслуговувати заявки відразу, причому середній час обслуговування зменшується втричі? Як це позначиться на середньому часі перебування заявки до СМО?

Рішення.Знаходимо можливість простою триканальної СМО за формулою

ρ = /μ =4/2=2, n=3,

Р 0 = = = 0,158.

Імовірність відмови визначаємо за формулою:

Р відк = Р n ==

Pвідк = 0,21.

Відносна пропускна спроможність системи:

Р обсл = 1-Р відк 1-0,21=0,79.

Абсолютна пропускна спроможність системи:

А = Р обсл 3,16.

Середня кількість зайнятих каналів визначаємо за формулою:

1,58, частка каналів, зайнятих обслуговуванням,

q = 0,53.

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

Поєднуючи всі три канали в один, отримуємо одноканальну систему з параметрами μ= 6, ρ= 2/3. Для одноканальної системи ймовірність простою:

Р 0 = = =0,6,

ймовірність відмови:

Р відк = ρ Р 0 = = 0,4,

відносна пропускна здатність:

Р обсл = 1-Р відк =0,6,

абсолютна пропускна спроможність:

А = Робсл =2,4.

t СМО =Р обсл= = 0,1 хв.

В результаті об'єднання каналів в одну пропускну здатність системи знизилася, оскільки збільшилася ймовірність відмови. Середній час перебування заявки у системі зменшився.

Приклад 2. На вхід триканальної СМО з необмеженою чергою надходить потік заявок з інтенсивністю =4 заявки на годину, середній час обслуговування однієї заявки t=1/μ=0,5 год. Знайти показники ефективності роботи системи.

Для аналізованої системи n =3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:

Р= .

P 0 = =1/9.

Середню кількість заявок у черзі знаходимо за формулою:

L =.

L = = .

Середній час очікування заявки у черзі вважаємо за формулою:

t= = 0,22 год.

Середній час перебування заявки у системі:

Т=t+ 0,22+0,5=0,72.

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

Для цього завдання n =3, m =3, =12, μ =3, ρ =4, ρ/n=4/3. Імовірність простою визначаємо за формулою:

Р 0 =.

P 0 = 0,012.

Імовірність відмови в обслуговуванні визначаємо за формулою

Р відк = Р n + m = .

P відк =P n + m 0,307.

Відносна пропускну здатність системи, тобто. ймовірність обслуговування:

P обсл =1-P відк 1-0,307=0,693.

Абсолютна пропускна спроможність:

А = Р обсл 12 .

Середня кількість зайнятих каналів:

.

Середня довжина черги визначається за такою формулою:

L =

L= 1,56.

Середній час очікування обслуговування у черзі:

t= год.

Середня кількість заявок до СМО:

M=L + .

Середній час перебування заявки до СМО:

Т=М/ 0,36 год.

Приклад 4. Робочий обслуговує 4 верстати. Кожен верстат відмовляє з інтенсивністю =0,5 відмови у годину, середній час ремонту t рем=1/μ=0,8 год. Визначити пропускну спроможність системи.

Це завдання розглядає замкнуту СМО, μ =1,25, ρ=0,5/1,25=0,4. Імовірність простою робітника визначаємо за формулою:

Р 0 =.

P 0 = .

Імовірність зайнятості робітника Р зан = 1-Р 0 . А = ( 1-P 0 )μ =0,85μ верстатів на годину.

Завдання:

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

Знайдіть середню частку вільного часу кожного робочого і середній час роботи верстата.

Знайдіть ті ж характеристики для системи, в якій:

а) за кожним робітником закріплено два верстати;

б) два робочі завжди обслуговують верстат разом, причому з подвійною інтенсивністю;

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

Рішення:

Можливі такі стани системи S:

S 0 - Всі верстати справні;

S 1 – 1 верстат ремонтується, інші справні;

S 2 – 2 верстат ремонтується, інші справні;

S 3 – 3 верстат ремонтується, інші справні;

S 4 – 4 верстат ремонтується, інші справні;

S 5 - (1, 2) верстати ремонтуються, інші справні;

S 6 - (1, 3) верстати ремонтуються, інші справні;

S 7 - (1, 4) верстати ремонтуються, інші справні;

S 8 – (2, 3) верстати ремонтуються, інші справні;

S 9 - (2, 4) верстати ремонтуються, інші справні;

S 10 - (3, 4) верстати ремонтуються, інші справні;

S 11 - (1, 2, 3) верстати ремонтуються, 4 верстат справний;

S 12 - (1, 2, 4) верстати ремонтуються, 3 верстат справний;

S 13 - (1, 3, 4) верстати ремонтуються, 2 верстат справний;

S 14 - (2, 3, 4) верстати ремонтуються, 1 верстат справний;

S 15 – усі верстати ремонтуються.

Граф станів системи.

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

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

Відповідь:

Середня частка вільного часу для кожного робітника - 0,09.

Середній час роботи верстата - 3,64.

а) За кожним робітником закріплено два верстати.

Імовірність простою робітника визначається за формулою:

Імовірність зайнятості робітника:

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

Відповідь:

Середня частка вільного часу для кожного робітника - 0,62.

Середній час роботи верстата - 1,52.

б) Два робітники завжди обслуговують верстат разом, причому з подвійною інтенсивністю.

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

Порівняння 5 відповідей:

Найбільш ефективним способом організації робітників за верстатами буде початковий варіант завдання.

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

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

1. Кількість заявок у системі (яка розглядається як СМО) має бути досить великою (масово).

2. Усі заявки, що надходять на вхід СМО, мають бути однотипними.

3. Для розрахунків за формулами необхідно знати закони, що визначають надходження заявок та інтенсивність їх обробки. Більше того, потоки заявок мають бути Пуассонівськими.

4. Структура СМО, тобто. набір вимог, що надходять, і послідовність обробки заявки, повинна бути жорстко зафіксована.

5. Необхідно виключити із системи суб'єктів чи описувати їх як вимоги з постійною інтенсивністю обробки.

До перерахованих вище обмежень можна додати ще одне, що впливає на розмірність і складність математичної моделі.

6. Кількість пріоритетів, що використовуються, повинна бути мінімальною. Пріоритети заявок би мало бути постійними, тобто. вони можуть змінюватися у процесі обробки всередині СМО.

У ході виконання роботи було досягнуто основної мети – вивчено основний матеріал «СМО з обмеженим часом очікування» та «Замкнуті СМО», яка була поставлена ​​викладачем навчальної дисципліни. Також ми ознайомилися застосуванням отриманих знань практично, тобто. закріпили пройдений матеріал.

1) http://www.5ballov.ru.

2) http://www.studentport.ru.

3) http://vse5ki.ru.

4) http://revolution.

5) Фомін Г.П. Математичні методи та моделі у комерційній діяльності. М: Фінанси та статистика, 2001.

6) Гмурман В.Є. Теорія ймовірностей та математична статистика. М: Вища школа, 2001.

7) Рад Б.А., Яковлєв С.А. Моделювання систем. М: Вища школа, 1985.

8) Ліфшиц О.Л. Статистичне моделювання СМО. М., 1978.

9) Вентцель Є.С. Дослідження операцій. М: Наука, 1980.

10) Вентцель Є.С., Овчаров Л.А. Теорія ймовірностей та її інженерні програми. М: Наука, 1988.

Навчальні питання:

Основні поняття Марківських процесів.

Потоки подій.

Пуасонівський потік.

Дискретні Марківські ланцюги.

Ергодичні та поглинаючі ланцюги.

Безперервні Марківські ланцюги.

Програми Марківських процесів.

Теорія Марківських випадкових процесів.

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

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

1. Скільки разів треба кинути дві гральні кістки, щоб випадків випадання одразу двох шісток було більше половини від загальної кількості кидань?

2. Як справедливо поділити поставлені на кон двома гравцями гроші, якщо вони з якихось причин припинили гру передчасно?

Ці завдання послужили приводом для початкового запровадження поняття «математичне очікування» та формулювання основних теорем складання та перемноження ймовірностей. Незабаром було визначено практичні додатки: страхування, демографія тощо.

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

Подальші успіхи розвитку теорії ймовірностей пов'язані з П. Лапласом, К. Гауссом, С. Пуассон та ін.

У Росії математик В.Я. Буняковський на початку 19 ст. написав перший підручник з теорії ймовірностей та розробив її термінологію в сучасному вигляді. П.А. Чебишев, А.А. Марков та А.М. Ляпунов запровадили поняття «випадкової величини», з якою почала розвиватися нова гілка теорії ймовірності – теорія випадкових процесів.

Основні поняття Марківських процесів

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

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

Процес переходу називається ланцюгом.

Визначення ланцюга Маркова

Є деяка фізична система, що має кінцеве число До всіх можливих фазових станів. Нехай, залежно від втручання випадку, система крок за кроком (у моменти часу t 0 ) стрибкоподібно змінює свій фазовий стан, тобто мають місце переходи Q 0 ®Q 1 ®…, де Q n = Q(t n)- стан системи через nкроків, а Q 0 = Q (t 0)- Початковий стан системи.

де - один із можливих просторів станів.

Імовірність переходу на m-кроці (умовна ймовірність):

Таким чином, для обчислення спільних ймовірностей Р(Q 0 , .., Q n)необхідно задати початковий стан системи та вказати фізичний механізм здійснення зміни станів, що дозволяє обчислити ймовірність переходу.

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

- Послідовність незалежних випробувань.

2. Імовірність фазового стану параметра Q nу момент часу t nзалежить лише від цього, у стані перебувала система у безпосередньо попередній йому час t n-1і не залежить від того, в яких станах знаходилася система в більш ранні моменти часу t 0, ..., t n-2.

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

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

Найпростішою імовірнісною характеристикою випадкового процесу є набір ймовірностей станів P 1 (t), P 2 (t), ... P n (t),де Pi (t)- Імовірність переходу системи в стан S iу момент часу t. Умова нормування P 1 +P 2 +...+P n =1.

Якщо в процесі функціонування система перебуває в стані S i, то можливість переходу її в стан S jу загальному випадку залежить не тільки від стану S i, А й від попереднього стану.

Випадковий процес, що протікає в системі, називається Марківським(процесом без післядії), якщо для будь-якого моменту часу t 0ймовірність стану системи в майбутньому (при t>t 0) залежить тільки від стану в теперішньому (при t=t 0) і не залежить від того, як і яким чином, система прийшла в даний стан (тобто не залежить від передісторії).

Потоки подій

Перехід системи в деякий стан є подією.

Послідовність переходів системи у стан S iявляє собою потік подій.

Потік подій називається ординарнимякщо подія в ньому відбувається поодинці.

Інтервали часу t 1 , t 2 , ... t nординарного потоку можуть бути однаковими чи різними, дискретними чи безперервними, випадковими чи невипадковими.

Якщо інтервали часу t 1 , t 2 , ... t n- невипадкові величини, то потік називається регулярним або детермінованим, і цей потік описується шляхом завдання значень T 1 ,T 2 , ... T n.

Якщо T 1 ,T 2 , ... T nє випадковими, то потік називається випадковимі він характеризується законом розподілу величин T 1 ,T 2 ,... T n.

Насправді часто зустрічаються системи, у яких T i- Безперервна випадкова величина. У цих випадках система може бути описана щільністю імовірності f(t 1 , t 2 , ... t n), де t i- Конкретне значення випадкової величини T i.

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

Інтенсивність (щільність) потоку подій (середня величина подій за одиницю часу) є постійною.

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

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

f(t 1 ,t 2 , ...t n) = f 1 (t 1) f 2 (t 2) ... f n (t n)(6.5)

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

f i (t i) = f (t i)(6.6)

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

Пуасонівський потік

Потоки випадкових подій називаються пуасонівськими, якщо кількість подій потоку m,які потрапляють на будь-яку ділянку t,розподілено за законом Пуассона

P m = e - a, (6.7)

де а- Середня кількість подій, що знаходяться на ділянці t.

Пуасонівський потік є стаціонарним, якщо щільність подій lпостійна, тоді середня кількість подій дорівнює lt, інакше потік буде нестаціонарним.

Випадковий потік подій, який має властивість стаціонарності, ординарності і не має післядії, називається найпростішим і є стаціонарним пуассонівським потоком.

Просіяні потоки

Процес переходів системи з дискретним часом функціонування може розглядатися як вплив дискретного потоку подій, що характеризується тим, що в моменти часу t 1 , t 2 ..., t n події відбуваються з ймовірністю P i. Функція розподілу такого потоку:

Просіяння потоку подій S 1 , S 2 , ... S n ,які наступають у певні моменти часу з ймовірностями p 1 , p 2 , ... p n, означає перетворення цих ймовірностей на , , ..., . Якщо потік є стаціонарним, ці ймовірності рівні: = =...=1-p.

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

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

Якщо найпростішому потоці зберегти лише кожну третю подію, то отримаємо потік Ерланга III порядку тощо. У загальному випадку, потоком Ерланга k-порядкуназивається найпростіший потік, отриманий винятком (k- 1) подій та збереженням k-ї події.

Дискретні Марківські ланцюги

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

S 1 (0) ® S 2 (1) ® ... ® S i (n) ® ... ® S n (k).

Ця послідовність називається дискретним Марківським ланцюгом, якщо для кожного кроку n=1,2, ... kймовірність переходів із будь-якого стану (S i ®S j)не залежить від того, як система прийшла в стан S i. Кожному переходу системи відповідає умовна можливість

P. (6.9)

Для кожного номера кроку nможливі переходи утворюють повну групу подій.

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

	P 11	P 12	...	P 1n
P ij =	P 21	P 22	...	P 2n
	...	...	...	...
	P n1	P n2	...	P nn

та вектор початкового розподілу ймовірностей для всіх станів у момент часу t=0.

= . (6.10)

Перехідні ймовірності, що відповідають неможливим переходам, дорівнюють 0, а ймовірності, розташовані по головній діагоналі, відповідають тому факту, що система не змінила свого стану.

Дискретний Марківський ланцюг називається неоднорідний, якщо перехідні можливості змінюються зі зміною номера кроку. Для опису таких кіл необхідно задати kматриць перехідних ймовірностей P ij (k- Число аналізованих кроків). Головним завданням аналізу Марківських процесів є визначення ймовірності всіх станів системи після будь-якої кількості кроків. При цьому, якщо відома матриця перехідних ймовірностей і вектор початкового розподілу, то ймовірності станів системи після кожного кроку визначаються за формулою повної ймовірності:

P(A) = P(B i)*P(A/B i)(6.11)

Після першого кроку ймовірність P iможе бути визначена наступним чином:

P i (1) = P j (0) , (6.12)

де P j(0) – вектор початкових станів,

P ji- Рядок матриці умовних ймовірностей.

P i (2) = P j (1) P ji = P j (0) P ji (1)(6.13)

Після kкроків:

P i (k) = P j (k-1) P ji = P j (0) P ji (k),(6.14)

де P ji (k)- Імовірності переходів системи зі стану S iв S jза kкроків.

Якщо можливий перехід із стану S iу стан S jза kкроків, то величина P ji (k)>0. Якщо при цьому можливий зворотний перехід за ту ж кількість кроків, стан S iназивається зворотним. Імовірність того, що система вийде зі стану S iі за kкроків повернеться до нього ж, що дорівнює 1 для зворотних станів.

Стан S i - безповоротнеякщо ця ймовірність відмінна від 1.

Стану S iі S jназиваються повідомляютьсяякщо можливий перехід S i ®S jза кінцеве число кроків.

Потоки подій Це послідовність подій, що відбуваються одна за одною у певні інтервали часу. T - середня величина часу між сусідніми подіями Якщо T = const, то події в потоці розподілені рівномірно. - Інтенсивність потоку, тобто середня кількість подій, що відбуваються в одиницю часу.

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

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

Економічне застосування Сучасні фінансово – банківські операції передбачають погашення заборгованості на виплат, періодичне надходження доходів від інвестицій. Такі послідовність, чи ряд платежів, можна назвати потоком платежів. Потік платежів усі члени якого – позитивні величини, а часові інтервали між платежами однакові, називають фінансовою рентою. Рентою є послідовність отримання відсотків за облігаціями, платежі за споживчим кредитом, виплати на виплат страхових премій. Характеристики потоку платежів: інтервал між двома сусідніми платежами, ймовірність виплати платежу широко застосовуються в різних фінансових розрахунках. Без них неможливо розробити план послідовного погашення заборгованості, виміряти фінансову ефективність проекту, здійснити порівняння чи беззбиткову зміну умов контрактів.

Завдання Для аналізу зміни з часом розміру поточного фонду банку, що займається видачею довгострокових позичок, важливо володіти інформацією про процес надходження до банку виплат за позиками. Спостереження за банком у попередньому періоді показало, що кількість виплат, що надходять до банку, за будь-який проміжок часу не залежить від моменту часу з якого почався відлік проміжку часу, а залежить тільки від його тривалості. Очікуване число виплат до банку протягом тижня дорівнює 2. Досліджуємо, яка ймовірність надходження до банку протягом місяця 7 виплат і знайдемо ймовірність того, що інтервал часу між двома сусідніми виплатами менше 2 днів.

Рішення За умовою завдання потік виплат можна вважати найпростішим з інтенсивністю =2 (за тиждень). Отже, кількість виплат, що надійшли за проміжок часу = 4 тижні (1 місяць), розподілено згідно із законом Пуассона. Інтервали між двома послідовними виплатами в найпростішому потоці мають показовий закон розподілу.

Рішення Нехай X() - дискретна випадкова величина, яка є числом виплат, що надійшли за проміжок часу. Вона розподілена згідно із законом Пуассона. M(X)=D(X)= Тоді - ймовірність того, що за проміжок часу в потоці наступлять точно m подій дорівнює Отже, при інтенсивності потоку виплат =2 ймовірність надходження до банку за місяць (=4) 7 виплат (m=7 ) дорівнює

Рішення Нехай безперервна випадкова величина T – проміжок часу між двома будь-якими сусідніми виплатами (подіями найпростішого потоку). Вона має показовий закон розподілу. M(T)=1/ , D(T)=1/ 2 Тоді можливість P(T

Завдання для самостійного вирішення 1. Зазвичай студент приходить на зупинку рівно о 8-й годині ранку і, сівши в перший автобус, що прийшов до напрямку університету, вчасно прибуває на заняття, які починаються рівно о 9-й ранку. Інтервали руху автобуса становлять у середньому 10 хвилин, а час у дорозі автобуса дорівнює 30 хвилин. Нехай потік автобусів є найпростішим. Знайдіть ймовірність того, що студент все ж таки запізниться на заняття.

Завдання для самостійного рішення 2. Потік заявок, що надходять до певної системи масового обслуговування, досить моделюється найпростішим. При вивченні досвідчених даних розглядалося 200 вибраних навмання проміжків часу довжиною в 2 хв. Виявилося, що кількість тих, у яких не було зареєстровано жодної заявки, дорівнює 27. Знайти математичне очікування та середнє квадратичне відхилення числа заявок за 1 годину.

Основні поняття Під системою S розумітимемо всяку цілісну множину взаємопов'язаних елементів, яку не можна розчленувати на незалежні підмножини. Якщо система S з часом t змінює свої стани S(t) випадковим чином, то кажуть, що у системі S протікає випадковий процес. У будь-який момент часу система перебуває лише в одному із станів, тобто для будь-якого моменту часу t знайдеться єдиний стан Si такий, що S(t) = Si. Безліч станів може бути дискретно (технічний стан об'єкта: справний - несправний, завантажений - перебуває у просте; чисельність персоналу; кількість об'єктів, які очікують обслуговування в черзі) або безперервно (дохід, обсяг виробництва).

Основні поняття У разі дискретної множини станів система змінює свої стани стрибком (миттєво). У разі безперервної множини станів перехід системи відбувається безперервно (плавно). Залежно від часу перебування системи у кожному стані розрізняють процеси з дискретним часом (штучна чисельна сітка часу) та з безперервним часом (фізичний час, перехід системи з одного стану до іншого може здійснюватися у будь-який момент часу). Випадковий процес, що протікає в системі S, називається Марковським, якщо він має властивість відсутності наслідку, що полягає в тому, що для кожного моменту часу t 0 ймовірність будь-якого стану S(t) системи S у майбутньому (при t>t 0) залежить тільки від її стану S(t 0) у цьому (при t=t 0) і залежить від цього, як і скільки часу розвивався цей процес у минулому (при t>t 0).

А. А. Марков (1856 – 1922) Андрій Андрійович Марков – старший – видатний російський математик, який розробив основи теорії випадкових процесів без післядії, які в математиці називають Марківськими процесами на його честь. А. А. Марков - старший відомий також як той, що дав ймовірнісне обґрунтування методу найменших квадратів (МНК), що привів один з доказів граничної теореми теорії ймовірностей і багато іншого.

Види Марківських процесів Дискретні стани та дискретний час (ланцюг Маркова) Безперервні стани та дискретний час (Марківські послідовності) Дискретні стани та безперервний час (безперервний Марківський ланцюг) Безперервні стани та безперервний час. Насправді більшість завдань з Марківським процесам описуються з допомогою Марківських ланцюгів з дискретним чи безперервним часом.

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

Завдання Марківського ланцюга безліччю станів S = (s 1, …, sn), подією є перехід з одного стану в інший в результаті випадкового випробування вектором початкових ймовірностей (початковим розподілом) p(0) = (p(0)(1), … p(0)(n)), визначальним ймовірності p(0)(i) того, що в початковий момент часу t = 0 процес знаходився в стані si матрицею перехідних ймовірностей P = (pij), що характеризує ймовірність переходу процесу з поточним станом si в наступний стан sj, сума ймовірностей переходів з одного стану дорівнює 1

Види Марківських ланцюгів Марківський ланцюг називається однорідним, якщо перехідні ймовірності від часу не залежать, тобто від кроку до кроку (k+1) не змінюються. Марківські ланцюги, що розкладаються, містять безповоротні стани, звані поглинаючими. З поглинаючого стану не можна перейти в жодне інше. На графі поглинаючому стану відповідає вершина, з якої не виходить жодна дуга. Ергодичні Марківські ланцюги описуються сильно пов'язаним графом. У такій системі можливий перехід із будь-якого стану в будь-який стан за кінцеве число кроків.

Мета моделювання - визначити ймовірність системи знаходиться в j-му стані після k-го кроку. Позначимо цю ймовірність - однорідний Марківський ланцюг - неоднорідний Марківський ланцюг

Завдання № 1 Деяка сукупність робочих сімей поділена на три групи: 1 – сім'ї, що не мають автомашини і не мають наміру її придбати; 2 – сім'ї, які мають автомашини, але які збираються її придбати, і, нарешті, 3 – сім'ї, мають автомашину. Статистичні обстеження дали можливість оцінити можливість переходу сімей з однієї групи протягом року в іншу. При цьому матриця переходу виявилася такою:

Завдання № 1 Знайти: а) ймовірність того, що сім'я, яка не мала машини і не збиралася її придбати, перебуватиме в тій самій ситуації через 2 роки; б) ймовірність того, що сім'я, яка не мала автомашини і має намір придбати її, матиме автомашину через 2 роки. (Виконати рішення пункту (б) даної задачі самостійно)

Розв'язання задачі № 1 а) Дано: тобто вектор початкових ймовірностей p(0)=(1, 0, 0) (зараз система у стані 1) Знайти: (через 2 роки у стані 1) Знайдемо ймовірність системи опинитися в кожному станів через 1 рік (множення вектора початкових ймовірностей на 1 стовпець матриці перехідних ймовірностей) (множення вектора початкових ймовірностей на 2 стовпець матриці перехідних ймовірностей) (множення вектора початкових ймовірностей на 3 стовпець матриці перехідних ймовірностей)

Розв'язання задачі № 1 Отримаємо вектор ймовірностей через 1 рік У нашому випадку це 1-ий рядок матриці перехідних ймовірностей на перший стовпець матриці перехідних ймовірностей)

Розв'язання задачі № 1 Обчислення: Відповідь: ймовірність того, що сім'я, яка не мала машини і не збиралася її придбати, перебуватиме в тій самій ситуації через 2 роки 0,64

Завдання № 2 Припустимо, що фірма здійснює доставку обладнання по Москві: у північний округ (позначимо А), південний (В) і центральний (С). Фірма має групу кур'єрів, що обслуговує ці райони. Зрозуміло, що для здійснення наступної доставки кур'єр їде до району, який на даний момент йому ближче. Статистично було визначено наступне: після здійснення доставки А наступна доставка в 30 випадках здійснюється в А, в 30 випадках - в В і в 40 випадках - в С; після здійснення доставки В наступна доставка в 40 випадках здійснюється в А, в 40 випадках - в В і в 20 випадках - в С; після здійснення доставки С наступна доставка в 50 випадках здійснюється в А, в 30 випадках - в В і в 20 випадках - в С. Таким чином, район наступної доставки визначається тільки попередньою доставкою.

Завдання № 2 Якщо кур'єр стартує із центрального округу, яка ймовірність того, що здійснивши дві доставки, він буде у південному окрузі? Виконайте розв'язання задачі самостійно: Складіть матрицю перехідних ймовірностей Намалюйте граф даного процесу Обчисліть ймовірність

Граничні ймовірності Для ергодичних ланцюгів за досить великому часі функціонування (t прагне нескінченності) настає стаціонарний режим, у якому ймовірності станів системи залежить від часу і залежить від розподілу ймовірностей у початковий час. Такі ймовірності називаються граничними (або фінальними, стаціонарними) ймовірностями станів, вони показують середній відносний час перебування системи у певному стані. Наприклад, якщо гранична можливість i-го стану pi=0. 5, це означає, що у середньому половину часу система перебуває у i-ом стані.

Граничні ймовірності Нехай xi – граничні ймовірності (i=1. n), де n – число станів. Тоді xi є єдиним рішенням системи лінійних рівнянь. До цієї системи входять рівняння:

Приклад Матриця перехідних ймовірностей (число станів n=2) та графічне зображення Марковського процесу: Граничні ймовірності х 1 і х 2 можна знайти, вирішивши систему

Завдання № 3 Дві машини А і В здаються в оренду за тією ж ціною. Ці машини мають такі матриці перехідних ймовірностей: де 1 – стан, коли машина працює добре; 2 – стан, коли машина потребує регулювання. Визначити ймовірність обох машин. Яку машину варто орендувати?

Завдання № 4 Відвідувач банку з наміром отримати кредит проходить низку перевірок (станів): е 1 – оформлення документів; е 2 - кредитна історія; е 3 - Поворотність; е 4 - платоспроможність. За результатами перевірки можливі два результати: відмова у видачі кредиту (е 6) та отримання кредиту (е 5).

Завдання № 4 Потрібно: a) описати цей процес як Марківський ланцюг та побудувати перехідну матрицю (виконати самостійно); б) знайти середній час отримання позитивного та негативного результату (рішення в Excel).

Процес роботи СМО є випадковим процесом. Під випадковим (імовірнісним чи стохастичним) процесом розуміється процес зміни у часі стану будь-якої системи відповідно до ймовірнісних закономірностей.

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

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

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

Приклад марковського процесу: система S – лічильник у таксі. Стан системи на момент t характеризується числом кілометрів, пройдених автомобілем до цього моменту. Нехай у момент t0 лічильник показує S0. Імовірність того, що в момент t>t0 лічильник покаже те чи інше число кілометрів (точніше відповідне число рублів) S1 залежить від S0, але не залежить від того, в які моменти змінювалися показання лічильника до моменту t0.

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

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

Малюнок 1 - Граф станів

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

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

Прикладами можуть бути:

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

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

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

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

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

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

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

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

Розглянемо на осі часу найпростіший потік подій як необмежену послідовність випадкових точок. (Мал. 2)

Малюнок 2 - Потік подій

Можна показати, що для найпростішого потоку число m подій (крапок), що потрапляють на довільну ділянку часу ф, розподілено за законом Пуассона

для якого математичне очікування випадкової величини дорівнює її дисперсії:

Зокрема, ймовірність того, що за час ф не станеться жодної події (m = 0), дорівнює

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

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

а можливість протилежної події, тобто. функція розподілу випадкової величини T, є

Щільність ймовірності випадкової величини є похідною її функції розподілу:

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

і назад за величиною інтенсивності потоку л.

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

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

Для найпростішого потоку з інтенсивністю л ймовірність попадання на елементарний (малий) відрізок часу? хоча б однієї події потоку дорівнює згідно

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

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

СМО ділять на два основні типи (класу): СМО з відмовами та СМО з очікуванням (чергою). У СМО з відмовами заявка, що надійшла в момент, коли всі канали зайняті, отримує відмову, залишає СМО і в подальшому процесі обслуговування не бере участі (наприклад, заявка на телефонну розмову в момент, коли всі канали зайняті, отримує відмову та залишає СМО необслуженою). У СМО з очікуванням заявка, яка прийшла в момент, коли всі канали зайняті, не йде, а стає на чергу на обслуговування.
СМО з очікуванням поділяються на різні види залежно від того, як організовано чергу: з обмеженою або необмеженою довжиною черги, з обмеженим часом очікування тощо.
Процес роботи СМО є випадковий процес.
Під випадковим (імовірнісним чи стохастичним) процесомрозуміється процес зміни у часі стану будь-якої системи відповідно до ймовірнісних закономірностей.
Процес називається процесом з дискретними станами,якщо його можливі стани S 1 , S 2 , S 3 ... можна заздалегідь перерахувати, а перехід системи зі стану до стану відбувається миттєво (стрибком). Процес називається процесом з безперервним часом,якщо моменти можливих переходів системи зі стану не фіксовані заздалегідь, а випадкові.
Процес роботи СМО є випадковим процесом з дискретними станами і безперервним часом. Це означає, що стан СМО змінюється стрибком у випадкові моменти появи якихось подій (наприклад, приходу нової заявки, закінчення обслуговування тощо).
Математичний аналіз роботи СМО значно спрощується, якщо процес цієї роботи - марківський. Випадковий процес називається марківськимабо випадковим процесом без наслідку,якщо для будь-якого моменту часу t 0 імовірнісні характеристики процесу в майбутньому залежать тільки від його стану в даний момент t 0 і не залежать від того коли і як система прийшла в цей стан.

Приклад марковського процесу: система S – лічильник у таксі. Стан системи в момент t характеризується числом кілометрів (десятих кілометрів), пройдених автомобілем до цього моменту. Нехай на момент t 0 лічильник показує S 0 . Імовірність того, що в момент t > t 0 лічильник покаже те чи інше число кілометрів (точніше, відповідне число рублів) S 1 залежить від S 0 але не залежить від того, в які моменти часу змінювалися показання лічильника до моменту t 0 .
Багато процесів можна приблизно вважати марківськими. Наприклад, процес гри у шахи; система S - Група шахових фігур. Стан системи характеризується числом постатей противника, що збереглися на дошці в момент t 0 . Ймовірність того, що в момент t > t 0 матеріальна перевага буде на боці одного з противників, залежать насамперед від того, в якому стані знаходиться система в даний момент t 0 , а не того, коли і в якій послідовності зникли фігури з дошки до моменту t 0 .
У ряді випадків передісторією аналізованих процесів можна просто знехтувати і застосовувати для вивчення марківські моделі.
При аналізі випадкових процесів із дискретними станами зручно користуватися геометричною схемою - так званим графом стані.Зазвичай стани системи зображуються прямокутниками (кружками), а можливі переходи зі стану - стрілками (орієнтованими дугами), що з'єднують стани.
Завдання 1 . Побудувати граф станів наступного випадкового процесу: пристрій S складається з двох вузлів, кожен з яких у випадковий момент часу може вийти з ладу, після чого миттєво починається ремонт вузла, що триває наперед невідомий випадковий час.

Рішення. Можливі стани системи: S 0 - обидва вузли справні; S 1 - перший вузол ремонтується, другий справний; S 2 - другий вузол ремонтується, перший справний; S 3 - обидва вузли ремонтуються. Граф системи наведено на рис.1.
Мал. 1
Стрілка, спрямована, наприклад, з S 0 в S 1 означає перехід системи в момент відмови першого вузла, S 1 в S 0 - перехід в момент закінчення ремонту цього вузла.
На графі відсутні стрілки з S 0 , S 3 і S 1 в S 2 . Це пояснюється тим, що виходи вузлів з ладу передбачаються незалежними один від одного і, наприклад, ймовірністю одночасного виходу з ладу двох вузлів (перехід з S 0 до S 3) або одночасного закінчення ремонтів двох вузлів (перехід з S 3 до S 0) можна знехтувати.

Потік подій

Для математичного опису марковського випадкового процесу з дискретними станами та безперервним часом, що протікає в СМО, познайомимося з одним із важливих понять теорії ймовірностей – поняттям потоку подій.
Під потоком подійрозуміється послідовність однорідних подій, наступних одна одною у якісь випадкові моменти часу (наприклад, потік викликів телефонної станції, потік відмов ЕОМ, потік покупців тощо.).
Потік характеризується інтенсивністюl- частотою появи подій чи середнім числом подій, які у СМО в одиницю часу.
Потік подій називається регулярним,якщо події слідують одна одною через певні рівні проміжки часу. Наприклад, потік виробів на конвеєрі складального цеху (з постійною швидкістю руху) є регулярним.
Потік подій називається стаціонарним,якщо його ймовірні характеристики не залежать від часу. Зокрема, інтенсивність стаціонарного потоку є постійна величина: l(t)=l.Наприклад, потік автомобілів на міському проспекті не є стаціонарним протягом доби, але цей потік можна вважати стаціонарним протягом доби, скажімо, у пік. Звертаємо увагу на те, що в останньому випадку фактична кількість автомобілів, що проходять в одиницю часу (наприклад, у кожну хвилину) може помітно відрізнятися один від одного, але середня їх кількість буде постійно і не залежатиме від часу.
Потік подій називається потоком без післядії,якщо для будь-яких двох ділянок часу, що не перетинаються, t 1 і t 2 - число подій, що потрапляють на один з них, не залежить від числа подій, що потрапляють на інші. Наприклад, потік пасажирів, які входять до метро, ​​практично не має післядії. А, скажімо, потік покупців, які відходять із покупками від прилавка, вже має післядію (хоча б тому, що інтервал часу між окремими покупцями не може бути меншим, ніж мінімальний час обслуговування кожного з них).
Потік подій називається ординарним,якщо ймовірність попадання на малу (елементарну) ділянку часу Dt двох і більше подій зневажливо мала порівняно з ймовірністю попадання однієї події. Іншими словами, потік подій ординарний, якщо події з'являються в ньому поодинці, а не групами. Наприклад, потік поем, що підходять до станції, ординарен, а потік вагонів не ординарен.
Потік подій називається найпростішим (або стаціонарним пуассонівським), якщо він одночасно стаціонарний, ординарен і не має післядії.Назва "найпростіший" пояснюється тим, що СМО з найпростішими потоками має найпростіший математичний опис. Зауважимо, що регулярний потік не є "найпростішим", оскільки він має післядію: моменти появи подій у такому потоці жорстко зафіксовані.
Найпростіший потік як граничний виникає в теорії випадкових процесів настільки ж природно, як у теорії ймовірностей нормальний розподіл виходить як граничний для суми випадкових величин: при накладенні (суперпозиції) досить великої кількості n незалежних, стаціонарних та ординарних потоків (порівняних між собою за інтенсивністю l 1 (i=1,2, ..., п) виходить потік, близький до найпростішого з інтенсивністю l, рівної сумі інтенсивностей вхідних потоків,тобто.
Розглянемо на осі часу Ot (рис. 2) найпростіший потік подій як необмежену послідовність випадкових точок.
Мал. 2
Можна показати, що для найпростішого потоку число тподій (точок), що потрапляють на довільну ділянку часу t, розподілено за закону Пуассона , (1)
для якого математичне очікування випадкової величини дорівнює її дисперсії: a=s 2 =lt.
Зокрема, ймовірність того, що за час t не відбудеться жодної події (m=0), дорівнює (2)
Знайдемо розподіл інтервалу часу Тміж довільними двома сусідніми подіями найпростішого потоку
Відповідно до (15.2) ймовірність того, що на ділянці часу завдовжки t не з'явиться жодної з наступних подій, дорівнює (3)
а можливість протилежної події, тобто. функція розподілу випадкової величини Т,є (4)
Щільність ймовірності випадкової величини є похідною її функції розподілу (рис. 3), тобто. (5)
Мал. 3
Розподіл, що задається щільністю ймовірності (5) або функцією розподілу (4), називається показовим(або експонентним).Таким чином, інтервал часу між двома сусідніми довільними подіями має показовий розподіл, для якого математичне очікування дорівнює середньому відхиленню квадратичного випадкової величини (6)
і назад за величиною інтенсивності потоку l.
Найважливіша властивість показового розподілу (притаманна лише показовому розподілу) полягає в наступному: якщо проміжок часу, розподілений за показовим законом, уже тривав деякий час t, то це ніяк не впливає на закон розподілу частини проміжку (T-t), що залишилася: він буде таким же, як та закон розподілу всього проміжку Т.
Іншими словами, для інтервалу часу Т між двома послідовними сусідніми подіями потоку, що має показовий розподіл, будь-які відомості про те, скільки часу протікав цей інтервал, не впливають на закон розподілу частини, що залишилася. Ця властивість показового закону є, по суті, інше формулювання для "відсутності післядії" - основної властивості найпростішого потоку.
Для найпростішого потоку з інтенсивністю l ймовірність попадання на елементарний (малий)відрізок часу Dt хоча б однієї події потоку дорівнює (4)
(7)
(Зауважимо, що ця наближена формула, яка отримується заміною функції e -lDtлише двома першими членами її розкладання до ряду за ступенями Dt, тим більше, що менше Dt).