Імітаційне моделювання системи масового обслуговування. Фінальні ймовірності станів виражаються формулами Ерланга. Дійсно, р0(t) є ймовірність того, що заявка, яка прийшла в момент t, буде прийнята до обслуговування. Всього в е
Аналітичне дослідженнясистем масового обслуговування(СМО) є підходом, альтернативним імітаційному моделюванню, і полягає в отриманні формул для розрахунку вихідних параметрів СМО з наступною підстановкою значень аргументів ці формули в кожному окремому експерименті.
У моделях СМО розглядають такі об'єкти:
1) заявки на обслуговування (транзакти);
2) обслуговуючі апарати(ОА), чи прилади.
Практична задача теорії масового обслуговування пов'язана з дослідженням операцій цими об'єктами і складається з окремих елементів, які впливають випадкові чинники.
Як приклад завдань, що розглядаються в теорії масового обслуговування, можна навести: узгодження пропускної спроможності джерела сполучення з каналом передачі даних, аналіз оптимального потоку міського транспорту, розрахунок ємності залу очікування для пасажирів в аеропорту та ін.
Заявка може бути або у стані обслуговування, або у стані очікування обслуговування.
Обслуговуючий прилад може бути зайнятий обслуговуванням, або вільний.
Стан СМО характеризується сукупністю станів обслуговуючих приладів та заявок. Зміна станів у СМО називається – подія.
Моделі СМО використовуються для дослідження процесів, що відбуваються в системі, при подачі на входи потоків заявок. Ці процеси є послідовністю подій.
Найважливіші вихідні параметри СМО
Продуктивність
Пропускна спроможність
Ймовірність відмови в обслуговуванні
Середній час обслуговування;
Коефіцієнт завантаження обладнання (ОА).
Заявками можуть бути замовлення на виробництво виробів, завдання, які вирішуються в обчислювальної системи, клієнти у банках, вантажі, що надходять транспортування та інших. Вочевидь, що параметри заявок, які у систему, є випадковими величинамиі при дослідженні чи проектуванні можуть бути відомі лише їхні закони розподілу.
У зв'язку з цим аналіз функціонування на системному рівні, як правило, має статистичний характер. Як математичний апарат моделювання зручно прийняти теорію масового обслуговування, а як моделі систем на цьому рівні використовувати системи масового обслуговування.
Найпростіші моделі СМО
У найпростішому випадку СМО є деяким пристроєм, званим обслуговуючим апаратом (ОА), з чергами заявок на входах.
М о д о л о б с л у ж і в а н і я с т к а з а м і (рис.5.1)
Рис. 5.1. Модель СМО з відмовами:
0 – джерело заявок;
1 – обслуговуючий прилад;
а- Вхідний потік заявок на обслуговування;
в- Вихідний потік обслужених заявок;
з- Вихідний потік необслужених заявок.
У цій моделі відсутній накопичувач заявок на вході ОА. Якщо заявка приходить від джерела 0 в момент часу, коли ОА зайнятий обслуговуванням попередньої заявки, то заявка, що знову прийшла, виходить із системи (оскільки їй відмовлено в обслуговуванні) і втрачається (потік з).
М о д о л о б с л у ж і в а н і я с о ж д а н ня м (рис. 5.2)
Рис. 5.2. Модель СМО з очікуванням
(N- 1) – кількість заявок, яка може поміститися у накопичувачі
У цій моделі є накопичувач заявок на вході ОА. Якщо заявка приходить від джерела 0 в момент часу, коли ОА зайнятий обслуговуванням попередньої заявки, то заявка, що знову прийшла, потрапляє в накопичувач, де необмежено довго чекає, поки звільниться ОА.
М о д о л о б л о в і в а н і я з о г р а н і ч е н ним у часі
про жи д а ння (рис. 5.3)
Рис. 5.4. Багатоканальна модель СМО з відмовами:
n– кількість однакових обслуговуючих апаратів (приладів)
У цій моделі є не один ОА, а кілька. Заявки, якщо це спеціально не обумовлено, можуть надходити до будь-якого вільного обслуговування ОА. Накопичувача немає, тому ця модель включає властивості моделі, показаної на рис. 5.1: відмова в обслуговуванні заявки означає її безповоротну втрату (це відбувається лише в тому випадку, якщо у момент приходу цієї заявки всіОА зайняті).
час життєда ння (рис. 5.5)
Рис. 5.6. Багатоканальна модель СМО з очікуванням та відновленням ОА:
e- Обслуговуючі апарати, що вийшли з ладу;
f– відновлені обслуговуючі апарати
Ця модельмає властивості моделей, представлених на рис. 5.2 і 5.4, а також властивостями, що дозволяють враховувати можливі випадкові відмови ОА, які в цьому випадку надходять у ремонтний блок 2, де перебувають протягом випадкових проміжків часу, що витрачаються на їх відновлення, а потім знову повертаються в обслуговуючий блок 1.
М н о го к а н а ль н я м о д е л ь ь ь С зг р а н і ч е н ним
в часи м ож д е н ня і восстання в л е н ня м ОА (рис. 5.7)
 |
Рис. 5.7. Багатоканальна модель СМО з обмеженим часом очікування та відновленням ОА
Ця модель є досить складною, оскільки одночасно враховує властивості двох не самих простих моделей(рис. 5.5 та 5.6).
Курсова робота
« Імітаційне моделюваннясистеми масового обслуговування»
за курсом «Дослідження операцій»
Вступ
При дослідженні операцій часто доводиться стикатися із системами, призначеними для багаторазового використання під час вирішення однотипних завдань. Виникаючі у своїй процеси отримали назву процесів обслуговування, а системи – систем масового обслуговування (СМО). Кожна СМО складається з певної кількості обслуговуючих одиниць (приладів, пристроїв, пунктів, станцій), які називаються каналами обслуговування. Каналами можуть бути лінії зв'язку, робочі точки, обчислювальні машини, продавці та ін. За кількістю каналів СМО поділяють на одноканальні та багатоканальні.
Заявки надходять у СМО зазвичай не регулярно, а випадково, утворюючи так званий випадковий потік заявок (вимог). Обслуговування заявок також триває якийсь випадковий час. Випадковий характер потоку заявок та часу обслуговування призводить до того, що СМО виявляється завантаженою нерівномірно: у якісь періоди часу накопичується дуже велика кількістьзаявок (вони або стають у чергу, або залишають СМО не обслуженими), в інші періоди СМО працює з недовантаженням або простоює.
Предметом теорії масового обслуговування є побудова математичних моделей, що пов'язують задані умови роботи СМО (кількість каналів, їх продуктивність, характер потоку заявок тощо) з показниками ефективності СМО, що описують її здатність справлятися з потоком заявок. Як показники ефективності СМО використовуються:
- Абсолютна пропускна спроможністьсистеми ( А
Q
– ймовірність відмовлення обслуговування заявки ();
k);
– середня кількість заявок у черзі ();
СМО ділять на 2 основних типи: СМО з відмовами та СМО з очікуванням (чергою). У СМО з відмовими заявка, що надійшла в момент, коли всі канали зайняті, отримує відмову, залишає СМО і в подальшому процесі обслуговування не бере участі (наприклад, заявка на телефонна розмовау момент, коли всі канали зайняті, отримує відмову та залишає СМО не обслуженою). У СМО з очікуванням заявка, яка прийшла в момент, коли всі канали зайняті, не йде, а стає на чергу на обслуговування.
Одним із методів розрахунку показників ефективності СМО є метод імітаційного моделювання. Практичне використаннякомп'ютерного імітаційного моделювання передбачає побудову відповідної математичної моделі, що враховує фактори невизначеності, динамічні характеристики та весь комплекс взаємозв'язків між елементами системи, що вивчається. Імітаційне моделювання роботи системи починається з деякого конкретного початкового стану. Внаслідок реалізації різних подій випадкового характеру модель системи переходить у наступні моменти часу в інші свої можливі стани. Цей еволюційний процес триває остаточного моменту планового періоду, тобто. до кінцевого моменту моделювання.
1. Основні характеристики CМО та показники їх ефективності
1.1 Поняття марковського випадкового процесу
Нехай є деяка система, яка з часом змінює свій стан випадковим чином. І тут кажуть, що у системі протікає випадковий процес.
Процес називається процесом з дискретними станами, якщо його стану можна заздалегідь перерахувати і перехід системи з одного стану до іншого відбувається стрибком. Процес називається процесом з безперервним часом, якщо переходи системи зі стану на стан відбуваються миттєво.
Процес роботи СМО – це випадковий процес із дискретними станами та безперервним часом.
Випадковий процес називають марковским чи випадковим процесом без післядії, якщо будь-якої миті часу ймовірнісні характеристики процесу у майбутньому залежить тільки від його стану у цей час і залежить від того, коли як і система прийшла у цей стан.
При аналізі процесів роботи СМО зручно користуватися геометричною схемою графом станів. Зазвичай стани системи зображуються прямокутниками, а можливі переходи зі стану - стрілками. Приклад графа станів наведено на рис. 1.
Потік подій – послідовність однорідних подій, наступних одне одним у випадкові моменти часу.
Потік характеризується інтенсивністю λ – частотою появи подій чи середнім числом подій, які у СМО в одиницю часу.
Потік подій називається регулярним, якщо події йдуть одна одною через певні рівні проміжки часу.
Потік подій називається стаціонарним, якщо його ймовірні характеристики не залежать від часу. Зокрема, інтенсивність стаціонарного потоку є постійна величина: .
Потік подій називається ординарним, якщо ймовірність попадання на малу ділянку часу двох і більше подій мала в порівнянні з ймовірністю попадання однієї події, тобто якщо події з'являються в ньому поодинці, а не групами.
Потік подій називається потоком без післядії, якщо для будь-яких двох ділянок часу, що не перетинаються, і кількість подій, що потрапляють на одну з них, не залежить від числа подій, що потрапляють на інші.
Потік подій називається найпростішим (або стаціонарним пуассонівським), якщо він одночасно стаціонарний, ординарен і не має післядії.
1.2 Рівняння Колмогорова
Усі переходи в системі зі стану до стану відбуваються під деяким потоком подій. Нехай система перебуває у певному стані , з якого можливий перехід у стан , тоді вважатимуться, що у систему впливає найпростіший потік з інтенсивністю , переводящий її із стану . Як тільки з'являється перша подія потоку, відбувається її перехід. Для наочності на графі станів кожної стрілки, відповідної переходу, вказується інтенсивність . Такий розмічений граф станів дозволяє збудувати математичну модель процесу, тобто. знайти ймовірність усіх станів як функції часу. Їх складаються диференціальні рівняння, звані рівняннями Колмогорова.
Правило складання рівнянь Колмогорова:У лівій частині кожного з рівнянь стоїть похідна за часом від ймовірності цього стану. У правій частині стоїть сума творів усіх станів, у тому числі можливий перехід у цей стан, на інтенсивності відповідних потоків подій мінус сумарна інтенсивність всіх потоків, які виводять систему з цього стану, помножена на ймовірність цього стану.
Наприклад, для графа станів, наведеного на рис. 1, рівняння Колмогорова мають вигляд:
Т.к. у правій частині системи кожне доданок входить 1 раз зі знаком і 1 раз зі знаком , то, складаючи всі рівняння, отримаємо, що
,
,
Отже, одне із рівнянь системи можна відкинути та замінити рівнянням (1.2.1).
Щоб отримати конкретне рішення треба знати початкові умови, тобто. значення ймовірностей у початковий час.
1.3 Фінальні ймовірності та граф станів СМО
При досить великому часі перебігу процесів у системі (при ) можуть встановлюватися ймовірності станів, які від часу, які називаються фінальними ймовірностями, тобто. у системі встановлюється стаціонарний режим. Якщо кількість станів системи звісно, і з кожного їх за кінцеве число кроків м. перейти у будь-який інший стан, то фінальні ймовірності існують, тобто.
Сенс фінальних ймовірностей у тому, що вони рівні середньому відносному часу перебування системи у цьому стані.
Т.к. у стаціонарному стані похідні за часом дорівнюють нулю, то рівняння для фінальних ймовірностей виходять із рівнянь Колмогорова шляхом прирівнювання нулю їхніх правих частин.
Графи станів, що використовуються в моделях систем масового обслуговування, називаються схемою загибелі та розмноження. Така назва обумовлена тим, що ця схема використовується в біологічних задачах, пов'язаних із вивченням чисельності популяції. Його особливість полягає в тому, що всі стани системи можна подати у вигляді ланцюжка, в якому кожен із станів пов'язаний з попереднім і наступним (рис 2).
Рис. 2. Граф станів у моделях СМО
Припустимо, що всі потоки, що переводять систему з одного стану до іншого, найпростіші. За графом, представленим на рис. 2, складемо рівняння для фінальних ймовірностей системи. Вони мають вигляд:
 |
Виходить система з ( n +1) рівняння, що вирішується методом виключення. Цей метод полягає в тому, що послідовно всі можливості системи виражаються через можливість .
,
.
Підставляючи ці висловлювання останнє рівняння системи, знаходимо , потім знаходимо інші ймовірності станів СМО.
1.4 Показники ефективності СМО
Мета моделювання СМО полягає в тому, щоб розрахувати показники ефективності системи через її характеристики. Як показники ефективності СМО використовуються:
- Абсолютна пропускна здатність системи ( А), тобто. середня кількість заявок, що обслуговуються в одиницю часу;
- Відносна пропускна здатність ( Q), тобто. середня частка заявок, що надійшли, обслуговуються системою;
- Імовірність відмови (), тобто. ймовірність того, що заявка залишить СМО не обслуженою;
- Середня кількість зайнятих каналів ( k);
– середня кількість заявок до СМО ();
– середній час перебування заявки у системі ();
– середня кількість заявок у черзі () – довжина черги;
– середня кількість заявок у системі ();
– середній час перебування заявки у черзі ();
– середній час перебування заявки у системі ()
- Ступінь завантаження каналу (), тобто. ймовірність того, що канал зайнятий;
- Середня кількість заявок, що обслуговуються в одиницю часу;
- Середній час очікування обслуговування;
– ймовірність того, що кількість заявок у черзі перевищить певне значення тощо.
Доведено, що з будь-якому характері потоку заявок, за будь-якого розподілі часу обслуговування, за будь-якої дисципліни обслуговування, середній час перебування заявки у системі (черги) дорівнює середній кількості заявок у системі (черги), поділеному на інтенсивність потоку заявок, тобто.
(1.4.1)
Формули (1.4.1) та (1.4.2) називаються формулами Літтла. Вони випливають речей, що у граничному стаціонарному режимі середнє число заявок, які прибувають у систему, дорівнює середньому числу заявок, що залишають її, тобто. обидва потоки заявок мають однакову інтенсивність .
Формули для обчислення показників ефективності наведені у таблиці. 1.
Таблиця 1.
| Показники | Одноканальна СМО з обмеженою чергою |
Багатоканальна СМО з обмеженою чергою |
Фінальні ймовірності |
|
|
Ймовірність |
 |
 |
Абсолютна пропускна здатність |
 |
|
Відносна пропускна здатність |
 |
|
Середня кількість заявок у |
 |
 |
Середня кількість заявок під обслуговуванням |
 |
|
| Середня кількість заявок у системі |  |
1.5 Основні поняття імітаційного моделювання
Основна мета імітаційного моделювання полягає у відтворенні поведінки системи, що вивчається, на основі аналізу найбільш істотних взаємозв'язків її елементів.
Комп'ютерне імітаційне моделювання слід як статичний експеримент.
З теорії функцій випадкових величин відомо, що для моделювання випадкової величини з будь-якою безперервною та монотонно зростаючою функцією розподілу достатньо вміти моделювати випадкову величину, рівномірно розподілену на відрізку. Отримавши реалізацію випадкової величини, можна знайти відповідну їй реалізацію випадкової величини, оскільки вони пов'язані рівністю
Припустимо, що у деякій системі масового обслуговування час обслуговування однієї заявки розподілено за експоненційним законом з параметром , де – інтенсивність потоку обслуговування. Тоді функція розподілу часу обслуговування має вигляд
Нехай - реалізація випадкової величини , рівномірно розподіленої на відрізку , а відповідна їй реалізація випадкового часу обслуговування однієї заявки. Тоді, згідно (1.5.1)
1.6 Побудова імітаційних моделей
Перший етап створення будь-якої імітаційної моделі – етап опису реально існуючої системиу термінах характеристик основних подій. Ці події, як правило, пов'язані з переходами системи, що вивчається, з одного можливого стану в інший і позначаються як точки на тимчасовій осі. Для досягнення основної мети моделювання достатньо спостерігати систему у моменти реалізації основних подій.
Розглянемо приклад одноканальної системи масового обслуговування. Метою імітаційного моделювання подібної системи є визначення оцінок її основних характеристик, таких як середній час перебування заявки у черзі, середня довжина черги та частка часу простою системи.
Характеристики самого процесу масового обслуговування можуть змінювати свої значення або в момент надходження нової заявки на обслуговування, або після завершення обслуговування чергової заявки. До обслуговування чергової заявки СМО може розпочатись негайно (канал обслуговування вільний), але не виключена необхідність очікування, коли заявці доведеться зайняти місце в черзі (СМО з чергою, канал обслуговування зайнятий). Після завершення обслуговування чергової заявки СМО може відразу приступити до обслуговування наступної заявки, якщо вона є, але може простоювати, якщо така відсутня. Необхідну інформацію можна отримати, спостерігаючи різні ситуації, що виникають при реалізаціях основних подій Так, при надходженні заявки до СМО з чергою при зайнятому каналі обслуговування довжина черги збільшується на 1. Аналогічно довжина черги зменшується на 1, якщо завершено обслуговування чергової заявки та безліч заявок у черзі не порожнє.
Для експлуатації будь-якої імітаційної моделі потрібно вибрати одиницю часу. Залежно від природи моделюється такою одиницею може бути мікросекунда, година, рік і т.д.
Так як по своїй суті комп'ютерне імітаційне моделювання є обчислювальним експериментом, то його результати, що спостерігаються, в сукупності повинні володіти властивостями реалізації випадкової вибірки. Лише в цьому випадку буде забезпечена коректна статистична інтерпретація системи, що моделюється.
При комп'ютерному імітаційному моделюванні основний інтерес становлять спостереження, отримані після досягнення системою стаціонарного режиму функціонування, що вивчається, оскільки в цьому випадку різко зменшується вибіркова дисперсія.
Час, необхідне досягнення системою стаціонарного режиму функціонування, визначається значеннями її параметрів і початковим станом.
Оскільки основною метою є отримання даних спостережень із можливо меншою помилкою, то для досягнення цієї мети можна:
1) збільшити тривалість часу імітаційного моделювання процесу функціонування системи, що вивчається. У цьому випадку не тільки збільшується ймовірність досягнення системою стаціонарного режиму функціонування, а й зростає число псевдовипадкових чисел, що використовуються, що також позитивно впливає на якість одержуваних результатів.
2) при фіксованій тривалості часу Тімітаційного моделювання провести Nобчислювальних експериментів, званих ще прогонами моделі, з різними наборами псевдовипадкових чисел, кожен із яких дає одне спостереження. Всі прогони починаються при одному і тому ж початковому стані системи, що моделюється, але з використанням різних наборів псевдовипадкових чисел. Перевагою цього є незалежність одержуваних спостережень , показників ефективності системи. Якщо число Nмоделі досить велике, то межі симетричного довірчого інтервалудля параметра визначаються так:
, 
, тобто. 
, де
Виправлена дисперсія, 
,
N- Число прогонів програми, - надійність, .
2. Аналітичне моделювання СМО
2.1 Граф станів системи та рівняння Колмогорова
Розглянемо двоканальну систему масового обслуговування (n = 2) з обмеженою чергою, що дорівнює шести (m = 4). У СМО надходить найпростіший потік заявок із середньою інтенсивністю λ = 4,8 і показовим закономрозподіл часу між надходженням заявок. Потік заявок, що обслуговуються в системі, є найпростішим із середньою інтенсивністю μ = 2 і показовим законом розподілу часом обслуговування.
Ця система має 7 станів, позначимо їх:
S 0 - Система вільна, немає заявок;
S 1 – 1 заявка на обслуговування, черга порожня;
S 2 – 2 заявки на обслуговуванні, черга порожня;
S 3 – 2 заявки на обслуговування, 1 заявка у черзі;
S 4 – 2 заявки на обслуговування, 2 заявки у черзі;
S 5 – 2 заявки на обслуговуванні, 3 заявки у черзі;
S 6 – 2 заявки на обслуговування, 4 заявки у черзі;
Імовірності приходу системи стану S 0 , S 1 , S 2 , …, S 6 відповідно рівні Р 0 , Р 1 , Р 2 , …, Р 6 .
Граф станів системи масового обслуговування є схемою загибелі та розмноження. Усі стани системи можна у вигляді ланцюжка, у якому кожен із станів пов'язані з попереднім і наступним.
Рис. 3. Граф станів двоканальної СМО
Для збудованого графа запишемо рівняння Колмогорова:
Для того щоб вирішити цю системупоставимо початкові умови:
Систему рівнянь Колмогорова (систему диференціальних рівнянь) вирішимо чисельним методомЕйлер за допомогою програмного пакета Maple 11 (див. Додаток 1).
Метод Ейлера
де 
- у разі, це праві частини рівнянь Колмогорова, n=6.
Виберемо крок за часом. Припустимо, де Т- Це час, за який система виходить на стаціонарний режим. Звідси отримуємо кількість кроків 
. Послідовно Nраз обчислюючи за такою формулою (1) отримаємо залежності ймовірностей станів системи від часу, наведеної на рис. 4.
Значення ймовірностей СМО при рівні:
Рис. 4. Залежність ймовірностей станів системи від часу
|
|
|
|
|
|
При досить великому часі перебігу процесів у системі () можуть встановлюватися ймовірності станів, які від часу, які називаються фінальними ймовірностями, тобто. у системі встановлюється стаціонарний режим. Якщо кількість станів системи звичайно, і з кожного з них за кінцеве число кроків можна перейти в будь-яке інше стан, то фінальні ймовірності існують, тобто. 
Т.к. у стаціонарному стані похідні за часом дорівнюють 0, то рівняння для фінальних ймовірностей виходять із рівнянь Колмогорова шляхом прирівнювання правих частин 0. Запишемо рівняння для фінальних ймовірностей для нашої СМО.
Вирішимо цю систему лінійних рівняньза допомогою програмного пакета Maple 11 (див. Додаток 1).
Отримаємо фінальні можливості системи:
Порівняння ймовірностей, отриманих із системи рівнянь Колмогорова при , з фінальними ймовірностями показує, що помилки 
рівні:
Тобто. досить малі. Це підтверджує правильність одержаних результатів.
2.3 Розрахунок показників ефективності системи за фінальнимі ймовірностями
Знайдемо показники ефективності системи обслуговування.
Спочатку обчислимо наведену інтенсивність потоку заявок:
1) Ймовірність відмовивши у обслуговуванні заявки, тобто. ймовірність того, що заявка залишає систему не обслуженою. У нашому випадку заявці відмовляється в обслуговуванні, якщо всі 2 канали зайняті, і черга максимально заповнена (тобто 4 особи в черзі), це відповідає стану системи S 6 . Т.к. ймовірність приходу системи стан S 6 дорівнює Р 6 , то
4) Середня довжина черги, тобто. середня кількість заявок у черзі, що дорівнює сумі творів числа заявок у черзі на ймовірність відповідного стану.
5) Середній час перебування заявки у черзі визначається формулою Літтла:
3. Імітаційне моделювання СМО
3.1 Алгоритм методу імітаційного моделювання СМО (покроковий підхід)
Розглянемо двоканальну систему масового обслуговування (n = 2) із максимальною довжиною черги рівною шести (m = 4). У СМО надходить найпростіший потік заявок із середньою інтенсивністю λ = 4,8 та показовим законом розподілу часу між надходженням заявок. Потік заявок, що обслуговуються в системі, є найпростішим із середньою інтенсивністю μ = 2 і показовим законом розподілу часом обслуговування.
Для імітації СМО скористаємося одним із методів статистичного моделювання- Імітаційним моделюванням. Будемо використовувати покроковий підхід. Суть цього підходу в тому, що стан системи розглядаються в наступні моменти часу, крок між якими є досить малим, щоб за його час відбулося не більше однієї події.
Виберемо крок за часом (). Він може бути набагато менше середнього часу надходження заявки () і середнього часу її обслуговування (), тобто.
Де (3.1.1)
Виходячи з умови (3.1.1) визначимо крок за часом.
Час надходження заявки до СМО та час її обслуговування є випадковими величинами. Тому при імітаційному моделюванні СМО їх обчислення проводиться за допомогою випадкових чисел.
Розглянемо надходження заявки до СМО. Імовірність того, що на інтервалі до СМО надійде заявка, дорівнює: 
. Згенеруємо випадкове число , і якщо 
, то вважатимемо, що заявка цьому етапі до системи надійшла, якщо 
, то не вчинила.
У програмі це здійснює isRequested () . Інтервал часу приймемо постійним і рівним 0,0001, тоді відношення дорівнюватиме 10000. Якщо заявка надійшла, вона приймає значення «істина», інакше значення «брехня».
bool isRequested()
double r = R. NextDouble();
if (r< (timeStep * lambda))
Розглянемо тепер обслуговування заявки до СМО. Час обслуговування заявки у системі визначається виразом 
, де - Довільне число. У програмі час обслуговування визначається за допомогою функції GetServiceTime
()
.
double GetServiceTime()
double r = R. NextDouble();
return (-1/mu*Math. Log (1-r, Math.E));
Алгоритм методу імітаційного моделювання можна сформулювати в такий спосіб. Час роботи СМО ( Т) розбивається на кроки за часом dtна кожному з них виконується ряд дій. Спочатку визначаються стани системи (зайнятість каналів, довжина черги), потім за допомогою функції isRequested () , визначається, чи надійшла на цьому кроці заявка чи ні.
Якщо надійшла, і при цьому є вільні канали, то за допомогою функції GetServiceTime () генеруємо час обробки заявки та ставимо її на обслуговування. Якщо всі канали зайняті, а довжина черги менше 4, то поміщаємо заявку в чергу, якщо довжина черги дорівнює 4, то заявці буде відмовлено в обслуговуванні.
У разі, коли на цьому кроці заявка не надходила, а канал обслуговування звільнився, перевіряємо, чи є черга. Якщо є, то із черги заявку ставимо на обслуговування у вільний канал. Після виконаних операцій час обслуговування для зайнятих каналів зменшуємо на величину кроку dt .
По закінченню часу Т, тобто після моделювання роботи СМО, обчислюються показники ефективності роботи системи і результати виводяться на екран.
3.2 Блок-схема програми
Блок-схема програми, що реалізує описаний алгоритм, наведено на рис. 5.
Рис. 5. Блок-схема програми
Розпишемо деякі блоки докладніше.
Блок 1. Встановлення початкових значень параметрів.
Random R; // Генератор випадкових чисел
public uint maxQueueLength; // Максимальна довжина черги
public uint channelCount; // Число каналів у системі
public double lambda; // Інтенсивність потоку надходження заявок
public double mu; // Інтенсивність потоку обслуговування заявок
public double timeStep; // Крокучасу
public double timeOfFinishProcessingReq; // Час закінчення обслуговування заявки у всіх каналах
public double timeInQueue; // Час перебування СМО у станах з чергою
public double processingTime; // Час роботисистеми
public double totalProcessingTime; // Сумарний час обслуговування заявок
public uint requestEntryCount; //Заявок, що надійшли
public uint declinedRequestCount; // Число відмовлених заявок
public uint acceptedRequestCount; // Числообслуговуваних заявок
uint queueLength; // Довжина черги //
Тип, що описує стани СМО
enum SysCondition (S0, S1, S2, S3, S4, S5, S6);
SysCondition currentSystemCondition; // Поточний стан системи
Завдання станів системи.Виділимо у цієї 2-х канальної системи 7 різних станів: S 0 , S 1 . S 6 . СМО перебуває у стані S 0 коли система вільна; S 1 – хоча один канал вільний; в стані S 2 коли всі канали зайняті, і є місце в черзі; у стані S 6 - всі канали зайняті, і черга досягла максимальної довжини (queueLength = 4).
Визначаємо поточний стан системи за допомогою функції GetCondition()
SysCondition GetCondition()
SysCondition p_currentCondit = SysCondition.S0;
int busyChannelCount = 0;
for (int i = 0; i< channelCount; i++)
if (timeOfFinishProcessingReq[i] > 0)
busyChannelCount++;
p_currentCondit + = k * (i + 1);
if (busyChannelCount > 1)
(p_currentCondit++;)
return p_currentCondit + (int) QueueLength;
Зміна часу перебування СМО у станах із довжиною черги 1, 2,3,4.Це реалізується наступним програмним кодом:
if (queueLength > 0)
timeInQueue += timeStep;
if (queueLength > 1)
(timeInQueue += timeStep;)
Є така операція, як розміщення заявки на обслуговування у вільний канал. Проглядаються, починаючи з першого, всі канали, коли виконується умовачасузакінченнямперіодингу Req [ i ] <= 0 (канал вільний), до нього подається заявка, тобто. генерується час закінчення обслуговування заявки.
for (int i = 0; i< channelCount; i++)
if (timeOfFinishProcessingReq [i]<= 0)
timeOfFinishProcessingReq [i] = GetServiceTime();
totalProcessingTime+= timeOfFinishProcessingReq [i];
Обслуговування заявок в каналах моделюється кодом:
for (int i = 0; i< channelCount; i++)
if (timeOfFinishProcessingReq [i] > 0)
timeOfFinishProcessingReq [i] -= timeStep;
Алгоритм методу імітаційного моделювання реалізовано мовою програмування C#.
3.3 Розрахунок показників ефективності СМО на основі результатів її імітаційного моделювання
Найбільш важливими є такі показники, як:
1) Ймовірність відмови у обслуговуванні заявки, тобто. ймовірність того, що заявка залишає систему не обслуженою. У нашому випадку заявці відмовляється в обслуговуванні, якщо всі 2 канали зайняті, і черга максимально заповнена (тобто 4 особи в черзі). Для знаходження ймовірності відмови розділимо час перебування СМО у стані з чергою 4 загальний час роботи системи.
2) Відносна пропускна здатність – це середня частка заявок, що надійшли, обслуговуються системою.
3) Абсолютна пропускна спроможність - це середня кількість заявок, що обслуговуються в одиницю часу.
4) Довжина черги, тобто. середня кількість заявок у черзі. Довжина черги дорівнює сумі творів числа осіб у черзі на ймовірність відповідного стану. Імовірності станів знайдемо як відношення часу знаходження СМО у цьому стані до загального часу роботи системи.
5) Середній час перебування заявки у черзі визначається формулою Літтла
6) Середня кількість зайнятих каналів визначається наступним чином:
7) Відсоток заявок, яким було відмовлено в обслуговуванні, перебуває за формулою
8) Відсоток обслужених заявок знаходиться за формулою
3.4 Статистична обробка результатів та їх порівняння з результатами аналітичного моделювання
Т.к. показники ефективності виходять у результаті моделювання СМО протягом кінцевого часу, вони містять випадкову компоненту. Тому для отримання більш надійних результатів потрібно провести їх статистичну обробку. З цією метою оцінимо довірчий інтервал для них за результатами 20 прогонів програми.
Величина потрапляє у довірчий інтервал, якщо виконується нерівність
, де
математичне очікування (середнє значення), що знаходиться за формулою
Виправлена дисперсія,
,
N =20 - Число прогонів,
- Надійність. При і N =20 .
Результат роботи програми представлено на рис. 6.
Рис. 6. Вид програми
Для зручності порівняння результатів, отриманих різними методами моделювання, представимо їх у вигляді таблиці.
Таблиця 2.
Показники ефективності СМО |
Результати аналітичного моделювання |
Результати імітаційного моделювання (послід. крок) |
Результати імітаційного моделювання | |
Нижня границя довірчого інтервалу |
Верхня межа довірчого інтервалу |
|||
| Ймовірність відмови | 0,174698253017626 | 0,158495148639101 |
0,246483801571923 | |
| Відносна пропускна спроможність | 0,825301746982374 | 0,753516198428077 | 0,841504851360899 | |
| Абсолютна пропускна спроможність | 3,96144838551539 | 3,61687775245477 | 4,03922328653232 | |
| Середня довжина черги | 1,68655313447018 | 1,62655862750852 | 2,10148609204869 | |
| Середній час перебування заявки у черзі | 0,4242558575 | 0,351365236347954 | 0,338866380730942 | 0,437809602510145 |
| Середня кількість зайнятих каналів | 1,9807241927577 | 1,80843887622738 | 2,01961164326616 | |
З табл. 2 видно, що результати, одержані при аналітичному моделюванні СМО, потрапляють у довірчий інтервал, одержаний за результатами імітаційного моделювання. Тобто результати, отримані різними методами, узгоджуються.
Висновок
У цій роботі розглянуто основні методи моделювання СМО та розрахунку показників їхньої ефективності.
Проведено моделювання двоканальної СМО з максимальною довжиною черги рівною 4 за допомогою рівнянь Колмогорова, а також знайдено фінальні ймовірності станів системи. Розраховано показники її ефективності.
Проведено імітаційне моделювання роботи такої СМО. На мові програмування C# складено програму, що імітує її роботу. Проведено серію розрахунків, за результатами яких знайдено значення показників ефективності системи та виконано їх статистичну обробку.
Отримані під час імітаційного моделювання результати узгоджуються з результатами аналітичного моделювання.
Література
1. Вентцель Є.С. Дослідження операцій. - М.: Дрофа, 2004. - 208 с.
2. Волков І.К., Загоруйко О.О. Дослідження операцій. - М.: Вид.-во МДТУ ім. н.е. Баумана, 2002. - 435 с.
3. Волков І.К., Зуєв С.М., Цвєткова Г.М. Випадкові процеси. - М.: Вид.-во МДТУ ім. н.е. Баумана, 2000. - 447 с.
4. Гмурман В.Є. Керівництво до вирішення завдань з теорії ймовірностей та математичної статистики. - М.: Вища школа, 1979. - 400 с.
5. Івницький В.Л. Теорія мереж масового обслуговування. - М.: Фізматліт, 2004. - 772 с.
6. Дослідження операцій на економіці/ під ред. Н.Ш. Кремер. - М.: Юніті, 2004. - 407 с.
7. Таха Х.А. Введення у дослідження операцій. - М.: ВД «Вільямс», 2005. - 902 с.
8. Харін Ю.С., Малюгін В.І., Кирлиця В.П. та ін. Основи імітаційного та статистичного моделювання. - Мінськ: Дизайн ПРО, 1997. - 288 с.
p align="justify"> Класифікація, основні поняття, елементи моделі, розрахунок основних характеристик.
Під час вирішення завдань раціональної організації торгівлі, побутового обслуговування, складського господарства тощо. дуже корисною буває інтерпретація діяльності виробничої структури як системи масового обслуговування, тобто. системи у якій, з одного боку, постійно виникають запити виконання будь-яких робіт, з другого - відбувається постійне задоволення цих запитів.
Будь-яка СМО включає чотири елементи: вхідний потік, черга, обслуговуючий пристрій, потік, що виходить.
Вимогою(клієнтом, заявкою) у СМО називається кожен окремий запит на виконання будь-якої роботи.
Обслуговування- це виконання роботи із задоволення вимоги. Об'єкт, що виконує обслуговування вимог, називається пристроєм (приладом) або каналом обслуговування.
Часом обслуговування називається період, протягом якого задовольняється вимога обслуговування, тобто. період від початку обслуговування та до його завершення. Період від моменту надходження вимоги до системи до початку обслуговування називається часом очікування обслуговування. Час очікування обслуговування разом із часом обслуговування становить час перебування вимоги у системі.
СМО класифікуються за різними ознаками.
1. За кількістю каналів обслуговування СМО діляться на одноканальні та багатоканальні.
2. Залежно від умов очікування вимогою початку обслуговування розрізняють СМО з втратами (відмовами) та СМО з очікуванням.
У СМО із втратами вимоги, що надійшли в момент, коли всі прилади зайняті обслуговуванням, отримують відмову, вони губляться для даної системи і ніякого впливу на подальший процес обслуговування не надають. Класичним прикладом системи з відмовими є телефонна станція - вимога на з'єднання отримує відмову, якщо абонент зайнятий.
Для системи з відмовами основною характеристикою ефективності функціонування є можливість відмови або середня частка заявок, що залишилися необслуженими.
У СМО з очікуванням вимоги, що надійшло в момент, коли всі прилади зайняті обслуговуванням, не залишає систему, а стає в чергу і чекає, поки не звільниться один з каналів. У разі звільнення чергового приладу одна із заявок, що стоять у черзі, негайно приймається на обслуговування.
Для СМО з очікуванням основними характеристиками є математичні очікування довжини черги та часу очікування.
Прикладом системи з очікуванням може бути процес відновлення телевізорів у ремонтній майстерні.
Зустрічаються системи, що лежать між зазначеними двома групами ( змішані СМО). Їх характерно наявність деяких проміжних умов: обмеженнями може бути обмеження за часом очікування початку обслуговування, за довжиною черги тощо.
Як характеристики ефективності може застосовуватися ймовірність відмови як у системах з втратами (або характеристики часу очікування) і в системах з очікуванням.
3. За дисципліною обслуговування СМО діляться на системи з пріоритетом в обслуговуванні та системи без пріоритету в обслуговуванні.
Вимоги можуть обслуговуватися в порядку їх надходження або випадковим чином або залежно від встановлених пріоритетів.
4. СМО можуть бути однофазними та багатофазними.
У однофазнихсистемах вимоги обслуговуються каналами одного типу (наприклад робітниками однієї професії) без передачі їх від одного каналу до іншого, багатофазнихсистемах такі передачі можливі.
5. За місцем знаходження джерела вимог СМО поділяються на розімкнені (коли джерело вимоги знаходиться поза системою) і замкнуті (коли джерело знаходиться у самій системі).
До замкнутимвідносяться системи, в яких потік вимог, що надходить, обмежений. Наприклад, майстер, завданням якого є налагодження верстатів у цеху, має періодично їх обслуговувати. Кожен налагоджений верстат стає у майбутньому потенційним джерелом вимог на налагодження. У таких системах загальна кількість циркулюючих вимог звичайно і найчастіше постійно.
Якщо джерело живлення має нескінченне число вимог, то системи називаються розімкнутими. Прикладами таких систем можуть бути магазини, каси вокзалів, портів тощо. Для цих систем потік вимог, що надходить, можна вважати необмеженим.
Методи та моделі дослідження СМО можна умовно розбити на аналітичні та статистичні (імітаційного моделювання процесів масового обслуговування).
Аналітичні методи дозволяють отримати характеристики системи, як деякі функції від параметрів її функціонування. Завдяки цьому з'являється можливість проводити якісний аналіз впливу окремих факторів на ефективність СМО.
На жаль, аналітичному рішенню піддається лише досить обмежене коло завдань теорії масового обслуговування. Незважаючи на розробку аналітичних методів, що постійно ведеться, у багатьох реальних випадках аналітичне рішення або неможливо отримати, або підсумкові залежності виявляються настільки складними, що їх аналіз стає самостійним важким завданням. Тому заради можливості застосування аналітичних методів рішення доводиться вдаватися до різних спрощує припущень, що певною мірою компенсується можливістю застосування якісного аналізу підсумкових залежностей (при цьому, зрозуміло, необхідно, щоб прийняті припущення не спотворювали реальної картини процесу).
В даний час теоретично найбільш розроблені та зручні у практичних додатках методи вирішення таких завдань масового обслуговування, в яких потік вимог є найпростішим ( пуассонівським).
Для найпростішого потоку частота надходження вимог до системи підпорядковується закону Пуассона, тобто ймовірність надходження за час t, що дорівнює k вимог задається формулою:
де - параметр потоку (див. нижче).
Найпростіший потік має три основні властивості: ординарність, стаціонарність і відсутність післядії.
Ординарністьпотоку означає практичну неможливість одночасного надходження двох і більше вимог. Наприклад, досить малою є ймовірність того, що з групи верстатів, які обслуговує бригада ремонтників, одночасно вийдуть з ладу кілька верстатів.
Стаціонарнимназивається потік, Для якого математичне очікування числа вимог, що надходять до системи в одиницю часу (позначимо через λ), не змінюється у часі. Таким чином, ймовірність надходження до системи певної кількості вимог протягом заданого проміжку часу Δt залежить від його величини і не залежить від початку відліку на осі часу.
Відсутність післядіїозначає, що кількість вимог, що надійшли до системи до моменту t, не визначає того, скільки вимог надійде до системи за час t + Δt.
Наприклад, якщо на ткацькому верстаті в даний момент стався обрив нитки, і він усунений ткаля, то це не визначає того, відбудеться новий обрив на даному верстаті в наступний момент чи ні, тим більше це не впливає на ймовірність виникнення обриву на інших верстатах.
Важливою характеристикою СМО є час обслуговування вимог у системі. Час обслуговування є, зазвичай, випадковою величиною і, отже, може бути описано законом розподілу. Найбільшого поширення теорії і, особливо у практичних додатках, отримав експоненційний закон. Для цього закону функція розподілу ймовірностей має вигляд:
F(t) = 1 - e-μt,
тобто. Можливість те, що час обслуговування вбирається у деякої величини t, визначається формулою (1 – e -μt), де μ -параметр експоненційного закону часу обслуговування вимог у системі - величина, зворотна середньому часу обслуговування, тобто. .
Розглянемо аналітичні моделі СМО з очікуванням(Найпоширеніші СМО, у яких вимоги, що надійшли в момент, коли всі обслуговуючі одиниці зайняті, стають у чергу і обслуговуються в міру звільнення обслуговуючих одиниць).
Завдання з чергами є типовими у виробничих умовах, наприклад при організації налагоджувальних та ремонтних робіт, при багатоверстатному обслуговуванні тощо.
Постановка завдання у вигляді виглядає так.
Система складається з n обслуговуючих каналів. Кожен із них може одночасно обслуговувати лише одну вимогу. В систему надходить найпростіший (пуасонівський) потік вимог з параметром. Якщо в момент надходження чергової вимоги в системі на обслуговуванні вже знаходиться не менше n вимог (тобто всі канали зайняті), то ця вимога стає в чергу і чекає на початок обслуговування.
Час обслуговування кожної вимоги t є випадковою величиною, яка підпорядковується експоненційному закону розподілу з параметром μ.
Як зазначалося вище, СМО з очікуванням можна розбити на дві великі групи: замкнуті та розімкнуті.
Особливості функціонування кожної з цих видів систем накладають свій відтінок на використовуваний математичний апарат. Розрахунок характеристик роботи СМО різного виду може бути проведений на основі розрахунку ймовірностей станів СМО (формули Ерланга).
Оскільки система замкнута, то до постановки завдання слід додати умову: потік вимог обмежений, тобто. в системі обслуговування одночасно не може перебувати більше m вимог (m - число об'єктів, що обслуговуються).
Як основні критерії, що характеризують якість функціонування аналізованої системи, виберемо: 1) відношення середньої довжини черги до найбільшого числа вимог, що знаходяться одночасно в обслуговуючій системі -коефіцієнт простою об'єкта, що обслуговується; 2) відношення середньої кількості незайнятих обслуговуючих каналів до їх загального числа - коефіцієнт простою каналу, що обслуговується.
Розглянемо розрахунок необхідних ймовірнісних характеристик (показників якості функціонування) замкнутої СМО.
1. Імовірність того, що в системі знаходиться k вимог за умови, коли їх кількість не перевищує числа обслуговуючих апаратів n:
P k = α k P 0 , (1 ≤ k ≤ n),
де 
λ - частота (інтенсивність) надходження вимог до системи від одного джерела;
Середня тривалість обслуговування однієї вимоги;
m - найбільше можливе число вимог, що знаходяться в обслуговуючій системі одночасно;
n – число обслуговуючих апаратів;
Р 0 - можливість, що це обслуговуючі апарати вільні.
2. Імовірність того, що в системі знаходиться k вимог за умови, коли їх кількість більша за кількість обслуговуючих апаратів:
P k = α k P 0 , (n ≤ k ≤ m),
де 
3. Імовірність того, що всі обслуговуючі апарати вільні, визначається за умови
отже,
4. Середня кількість вимог, що очікують початку обслуговування (середня довжина черги):
5. Коефіцієнт простою вимоги в очікуванні обслуговування:
6. Імовірність того, що всі обслуговуючі апарати зайняті:
7. Середня кількість вимог, що знаходяться в обслуговувальній системі (обслуговуваних та очікуваних обслуговування):
8. Коефіцієнт повного простою вимог на обслуговуванні та в очікуванні обслуговування:
9. Середній час простою вимоги у черзі на обслуговування:
10. Середня кількість вільних обслуговуючих апаратів:
11. Коефіцієнт простою обслуговуючих апаратів:
12. Імовірність того, що кількість вимог, що очікують обслуговування, більша за деяку кількість В (ймовірність того, що в черзі на обслуговування перебуває більше В вимог):
Нижче буде розглянуто приклади найпростіших систем масового обслуговування (СМО). Поняття "найпростіші" не означає "елементарні". Математичні моделіцих систем застосовні та успішно використовуються у практичних розрахунках.
Одноканальна смо з відмовами
Дано: система має один канал обслуговування, який надходить найпростіший потік заявок з інтенсивністю. Потік обслуговування має інтенсивність. Заявка, що залишила систему зайнятою, відразу ж покидає її.
Знайти: абсолютну та відносну пропускну здатність СМО та ймовірність того, що заявка, що прийшла в момент часу t, отримає відмову.
Система за будь-якого t> 0 може бути у двох станах: S 0 – канал вільний; S 1 – канал зайнятий. Перехід із S 0 в S 1 пов'язаний з появою заявки та негайним початком її обслуговування. Перехід із S 1 в S 0 здійснюється, коли чергове обслуговування завершиться (рис.4).
Рис.4. Граф станів одноканальної СМО із відмовами
Вихідні характеристики (характеристики ефективності) цієї та інших СМО будуть надаватися без висновків та доказів.
Абсолютна пропускна спроможність(Середня кількість заявок, що обслуговуються в одиницю часу):
де – інтенсивність потоку заявок (величина, зворотна середньому проміжку часу між заявками, що надходять -);
-інтенсивність потоку обслуговування (величина, зворотна середньому часу обслуговування)
Відносна пропускна спроможність(Середня частка заявок, що обслуговуються системою):
Ймовірність відмови(ймовірність того, що заявка залишить СМО необслуженою):
Очевидні такі співвідношення: і.
приклад. Технологічна система складається з одного верстата. На верстат надходять заявки виготовлення деталей загалом через 0,5 години. Середній час виготовлення однієї деталі дорівнює. Якщо при надходженні заявки виготовлення деталі верстат зайнятий, вона (деталь) прямує інший станок. Знайти абсолютну та відносну пропускну здатність системи та ймовірність відмови з виготовлення деталі.
Тобто. в середньому приблизно 46% деталей обробляються на цьому верстаті.
.
Тобто. в середньому приблизно 54% деталей прямують на обробку на інші верстати.
N - канальна смо з відмовами (завдання Ерланга)
Це з перших завдань теорії масового обслуговування. Вона виникла з практичних потреб телефонії та була вирішена на початку 20 століття датським математиком Ерлангом.
Дано: у системі є n– каналів, куди надходить потік заявок з інтенсивністю. Потік обслуговування має інтенсивність. Заявка, що залишила систему зайнятою, відразу ж покидає її.
Знайти: абсолютну та відносну пропускну здатність СМО; ймовірність того, що заявка, що надійшла в момент часу t, Отримає відмову; середня кількість заявок, що обслуговуються одночасно (або, іншими словами, середня кількість зайнятих каналів).
Рішення. Стан системи S(СМО) нумерується за максимальним числом заявок, що знаходяться в системі (воно збігається з числом зайнятих каналів):
S 0 – у СМО немає жодної заявки;
S 1 - у СМО знаходиться одна заявка (один канал зайнятий, інші вільні);
S 2 - у СМО знаходиться дві заявки (два канали зайняті, інші вільні);
S n – у СМО знаходиться n- Заявок (усі n– каналів зайняті).
Граф станів СМО подано на рис. 5
Рис.5 Граф станів для n - канальної СМО з відмовами
Чому граф станів розмічено саме так? Зі стану S 0 у стан S 1 систему переводить потік заявок з інтенсивністю (як тільки надходить заявка, система переходить з S 0 в S 1). Якщо система перебувала в стані S 1 і прийшла ще одна заявка, то вона переходить у стан S 2 і т.д.
Чому такі інтенсивності у нижніх стрілок (дуг графа)? Нехай система перебуває в стані S 1 (працює один канал). Він здійснює обслуговування в одиницю часу. Тому дуга переходу зі стану S 1 у стан S 0 навантажена інтенсивністю. Нехай тепер система перебуває в стані S 2 (працюють два канали). Щоб їй перейти до S 1 потрібно, щоб закінчив обслуговування перший канал, або другий. Сумарна інтенсивність їх потоків дорівнює і т.д.
Вихідні характеристики (характеристики ефективності) цієї СМО визначаються в такий спосіб.
Абсолютнапропускназдатність:
де n– кількість каналів СМО;
-імовірність знаходження СМО в початковому стані, коли всі канали вільні (фінальна ймовірність знаходження СМО в стані S 0);
Рис.6. Граф станів для схеми «загибелі та розмноження»
Для того щоб написати формулу для визначення , розглянемо рис.6
Граф, представлений цьому малюнку, називають ще графом станів для схеми «загибелі і розмноження». Напишемо спочатку на загальну формулу (без підтвердження):
До речі, решта фінальних ймовірностей станів СМО запишуться наступним чином.
S 1 коли один канал зайнятий:
Імовірність того, що СМО перебуває в стані S 2, тобто. коли два канали зайняті:
Імовірність того, що СМО перебуває в стані S n, тобто. коли всі канали зайняті.
Тепер для n – канальної СМО із відмовами
Відносна пропускна спроможність:
Нагадаємо, що це середня частка заявок, які обслуговує система. При цьому
Ймовірністьвідмови:
Нагадаємо, що це ймовірність того, що заявка залишить СМО необслуговуваною. Очевидно, що .
Середня кількість зайнятих каналів (середня кількість заявок, що обслуговуються одночасно):
Московський державний технічний університет
імені Н.Е. Баумана (Калузька філія)
Кафедра вищої математики
Курсова робота
за курсом «Дослідження операцій»
Імітаційне моделювання системи масового обслуговування
Завдання на роботу: Скласти імітаційну модель та розрахувати показники ефективності системи масового обслуговування (СМО) з наступними характеристиками:
Число каналів обслуговування n; максимальна довжиначерги т;
Потік заявок, що надходять до системи, найпростіший із середньою інтенсивністю λ і показовим законом розподілу часу між надходженням заявок;
Потік заявок, що обслуговуються в системі, найпростіший із середньою інтенсивністю µ і показовим законом розподілу часу обслуговування.
Порівняти знайдені значення показників із результатами. отриманими шляхом чисельного розв'язання рівняння Колмогорова для ймовірностей станів системи. Значення параметрів СМО наведено у таблиці.
Вступ
Глава 1. Основні характеристики CМО та показники їх ефективності
1.1 Поняття марковського випадкового процесу
1.2 Потоки подій
1.3 Рівняння Колмогорова
1.4 Фінальні ймовірності та граф станів СМО
1.5 Показники ефективності СМО
1.6 Основні поняття імітаційного моделювання
1.7 Побудова імітаційних моделей
Глава 2. Аналітичне моделювання СМО
2.1 Граф станів системи та рівняння Колмогорова
2.2 Розрахунок показників ефективності системи за фінальнимі ймовірностями
Глава 3. Імітаційне моделювання СМО
3.1 Алгоритм методу імітаційного моделювання СМО (покроковий підхід)
3.2 Блок-схема програми
3.3 Розрахунок показників ефективності СМО на основі результатів її імітаційного моделювання
3.4 Статистична обробка результатів та їх порівняння з результатами аналітичного моделювання
Висновок
Література
Додаток 1
При дослідженні операцій часто доводиться стикатися із системами, призначеними для багаторазового використання під час вирішення однотипних завдань. Виникаючі у своїй процеси отримали назву процесів обслуговування, а системи – систем масового обслуговування (СМО).
Кожна СМО складається з певної кількості обслуговуючих одиниць (приладів, пристроїв, пунктів, станцій), які називаються каналами обслуговування. Каналами можуть бути лінії зв'язку, робочі точки, обчислювальні машини, продавці та ін. За кількістю каналів СМО поділяють на одноканальні та багатоканальні.
Заявки надходять у СМО зазвичай не регулярно, а випадково, утворюючи так званий випадковий потік заявок (вимог). Обслуговування заявок також триває якийсь випадковий час. Випадковий характер потоку заявок і часу обслуговування призводить до того, що СМО виявляється завантаженою нерівномірно: в якісь періоди часу накопичується дуже велика кількість заявок (вони або стають у чергу, або залишають СМО не обслуговувати), в інші періоди СМО працює з недовантаженням або простоює.
Предметом теорії масового обслуговування є побудова математичних моделей, що пов'язують задані умови роботи СМО (кількість каналів, їх продуктивність, характер потоку заявок тощо) з показниками ефективності СМО, що описують її здатність справлятися з потоком заявок.
Як показники ефективності СМО використовуються:
Абсолютна пропускну здатність системи (А), тобто. середня кількість заявок, що обслуговуються в одиницю часу;
Відносна пропускну здатність (Q), тобто. середня частка заявок, що надійшли, обслуговуються системою;
Можливість відмови обслуговування заявки (
);Середня кількість зайнятих каналів (k);
Середня кількість заявок до СМО (
);Середній час перебування заявки у системі (
);Середня кількість заявок у черзі (
);Середній час перебування заявки у черзі (
);Середня кількість заявок, що обслуговуються в одиницю часу;
Середній час очікування на обслуговування;
Імовірність того, що кількість заявок у черзі перевищить певне значення тощо.
СМО ділять на 2 основних типи: СМО з відмовами та СМО з очікуванням (чергою). У СМО з відмовами заявка, що надійшла в момент, коли всі канали зайняті, отримує відмову, залишає СМО і в подальшому процесі обслуговування не бере участі (наприклад, заявка на телефонну розмову в момент, коли всі канали зайняті, отримує відмову та залишає СМО не обслуженою) . У СМО з очікуванням заявка, яка прийшла в момент, коли всі канали зайняті, не йде, а стає на чергу на обслуговування.
Одним із методів розрахунку показників ефективності СМО є метод імітаційного моделювання. Практичне використання комп'ютерного імітаційного моделювання передбачає побудову відповідної математичної моделі, що враховує фактори невизначеності, динамічні характеристики та весь комплекс взаємозв'язків між елементами системи, що вивчається. Імітаційне моделювання роботи системи починається з деякого конкретного початкового стану. Внаслідок реалізації різних подій випадкового характеру модель системи переходить у наступні моменти часу в інші свої можливі стани. Цей еволюційний процес триває остаточного моменту планового періоду, тобто. до кінцевого моменту моделювання.
Нехай є деяка система, яка з часом змінює свій стан випадковим чином. І тут кажуть, що у системі протікає випадковий процес.
Процес називається процесом з дискретними станами, якщо його стани
можна заздалегідь перерахувати і перехід системи з одного стану до іншого відбувається стрибком. Процес називається процесом з безперервним часом, якщо переходи системи зі стану на стан відбуваються миттєво.Процес роботи СМО – це випадковий процес із дискретними станами та безперервним часом.
Випадковий процес називають марківським чи випадковим процесом без післядії, якщо для будь-якого моменту часу
вероятностные показники процесу у майбутньому залежить тільки від його стану в даний момент і не залежать від того, коли і як система прийшла в цей стан.
1.2 Потоки подій
Потік подій – послідовність однорідних подій, наступних одне одним у випадкові моменти часу.
Потік характеризується інтенсивністю λ – частотою появи подій чи середнім числом подій, які у СМО в одиницю часу.
Потік подій називається регулярним, якщо події йдуть одна одною через певні рівні проміжки часу.
Потік подій називається стаціонарним, якщо його ймовірні характеристики не залежать від часу. Зокрема, інтенсивність стаціонарного потоку є постійна величина:
.Потік подій називається ординарним, якщо ймовірність попадання на малу ділянку часу
двох і більше подій мала в порівнянні з ймовірністю попадання однієї події, тобто якщо події з'являються в ньому поодинці, а не групами.Потік подій називається потоком без післядії, якщо для будь-яких двох ділянок часу, що не перетинаються.
