Курсова робота
В«Імітаційне моделювання системи масового обслуговування В»
по курсу В«Дослідження операційВ»
Введення
При дослідженні операцій часто доводиться стикатися з системами, призначеними для багаторазового використання при рішенні однотипних завдань. Виникаючі при цьому процеси одержали назву процесів обслуговування, а системи - систем масового обслуговування (СМО). Кожна СМО складається з певного числа обслуговуючих одиниць (приладів, пристроїв, пунктів, станцій), які називаються каналами обслуговування. Каналами можуть бути лінії зв'язку, робочі точки, обчислювальні машини, продавці та ін За кількістю каналів СМО підрозділяють на одноканальні і багатоканальні.
Заявки надходять у СМО зазвичай не регулярно, а випадково, утворюючи так званий випадковий потік заявок (вимог). Обслуговування заявок також триває якесь випадкове час. Випадковий характер потоку заявок і часу обслуговування призводить до того, що СМО виявляється завантаженою нерівномірно: в якісь періоди часу накопичується дуже велика кількість заявок (вони або стають в чергу, або залишають СМО не обслуговуваними), в інші ж періоди СМО працює з недовантаженням або простоює.
Предметом теорії масового обслуговування є побудова математичних моделей, зв'язують задані умови роботи СМО (число каналів, їх продуктивність, характер потоку заявок і т.п.) з показниками ефективності СМО, які описують її здатність справлятися з потоком заявок. В якості показників ефективності СМО використовуються:
- Абсолютна пропускна здатність системи ( А ), тобто середнє число заявок, обслуговуються в одиницю часу;
- відносна пропускна здатність ( Q ), тобто середня частка заявок, що надійшли, обслуговуються системою;
- ймовірність відмови обслуговування заявки ();
- середнє число зайнятих каналів ( k );
- середнє число заявок в СМО ();
- середнє час перебування заявки в системі ();
- середнє число заявок в черзі ();
- середнє час перебування заявки в черзі ();
- середнє число заявок, що обслуговуються в одиницю часу;
- середнє час очікування обслуговування;
- ймовірність того, що число заявок в черзі перевищить певне значення і т.п.
СМО ділять на 2 основних типи: СМО з відмовами і СМО з очікуванням (чергою). У СМО з відмовами заявка, що надійшла в момент, коли всі канали зайняті, отримує відмову, залишає СМО і в подальшому процесі обслуговування не бере участь (наприклад, заявка на телефонна розмова в момент, коли всі канали зайняті, отримує відмову і покидає СМО не обслужених). У СМО з очікуванням заявка, що прийшла в момент, коли всі канали зайняті, не йде, а стає в чергу на обслуговування.
Одним з методів розрахунку показників ефективності СМО є метод імітаційного моделювання. Практичне використання комп'ютерного імітаційного моделювання передбачає побудову відповідної математичної моделі, враховує фактори невизначеності, динамічні характеристики і весь комплекс взаємозв'язків між елементами системи, що вивчається. Імітаційне моделювання роботи системи починається з деякого конкретного початкового стану. Внаслідок реалізації різних подій випадкового характеру, модель системи переходить в наступні моменти часу в інші свої можливі стану. Цей еволюційний процес продовжується до кінцевого моменту планового періоду, тобто до кінцевого моменту моделювання.
1. Основні характеристики CМО і показники їх ефективності
1.1 Поняття марківського випадкового процесу
Нехай є деяка система, яка з плином часу змінює свій стан випадковим чином. У цьому випадку говорять, що в системі протікає випадковий процес.
Процес називається процесом з дискретними станами, якщо його стану можна заздалегідь перерахувати і перехід системи з одного стану в інший відбувається стрибком. Процес називається процесом з безперервним часом, якщо переходи системи зі стану в стан відбуваються миттєво.
Процес роботи СМО - це випадковий процес з дискретними станами і безперервним часом.
Випадковий процес називають марковским або випадковим процесом без післядії, якщо для будь-якого моменту часу імовірнісні характеристики процесу в майбутньому залежать тільки від його стану в даний момент і не залежать від того, коли і як система прийшла в цей стан.
При аналізі процесів роботи СМО зручно користуватися геометричній схемою - графом станів . Зазвичай стану системи зображуються прямокутниками, а можливі переходи зі стану в стан - стрілками. Приклад графа станів наведено на рис. 1.
Рис. 1.
Потік подій - Послідовність однорідних подій, наступних одне за іншим у випадкові моменти часу.
Потік характеризується інтенсивністю О» - частотою появи подій або середнім числом подій, що надходять у СМО в одиницю часу.
Потік подій називається регулярним, якщо події слідують одне за іншим через певні рівні проміжки часу.
Потік подій називається стаціонарним, якщо його імовірнісні характеристики не залежать від часу. Зокрема, інтенсивність стаціонарного потоку є величина постійна:.
Потік подій називається ординарним, якщо ймовірність попадання на малий ділянку часу двох і більше подій мала в порівнянні з ймовірністю влучення однієї події, тобто, якщо події з'являються в ньому поодинці, а не групами.
Потік подій називається потоком без післядії, якщо для будь-яких двох непересічних ділянок часу і число подій, що потрапляють на одне з них, не залежить від числа подій, що потрапляють на інші.
Потік подій називається найпростішим (або стаціонарним пуассонівської), якщо він одночасно стационарен, ординарій і не має післядії.
1.2 Рівняння Колмогорова
Всі переходи в системі зі стану в стан відбуваються під деяким потоком подій. Нехай система перебуває в деякому стані, з якого можливий перехід в стан, тоді можна вважати, що на систему впливає найпростіший потік з інтенсивністю, що переводить її зі стану в. Як тільки з'являється перша подія потоку, відбувається її перехід. Для наочності на графі станів у кожної стрілки, відповідної переходу, вказується інтенсивність. Такий розмічений граф станів дозволяє побудувати математичну модель процесу, тобто знайти ймовірності всіх станів як функції часу. Для них складаються диференціальні рівняння, звані рівняннями Колмогорова.
Правило складань рівнянь Колмогорова: У лівій частині кожного з рівнянь стоїть похідна за часом від ймовірності даного стану. У правій частині стоїть сума добутків всіх станів, з яких можливий перехід в дане стан, на інтенсивності відповідних потоків подій мінус сумарна інтенсивність всіх потоків, які виводять систему з даного стану, помножена на ймовірність даного стану.
Наприклад, для графа станів, наведеного на рис. 1, рівняння Колмогорова мають вигляд:
Т.к. в правій частини системи кожний доданок входить 1 раз зі знаком і 1 раз зі знаком, то, складаючи всі рівнянь, одержимо, що
,
,
. (1.2.1)
Отже, одне з рівнянь системи можна відкинути і замінити рівнянням (1.2.1).
Щоб отримати конкретне рішення треба знати початкові умови, тобто значення ймовірностей в початковий момент часу.
1.3 Фінальні імовірності і граф станів СМО
При достатньо великому часі протікання процесів в системі (при) можуть встановлюватися ймовірності станів, які не залежать від часу, які називаються фінальними ймовірностями, тобто в системі встановлюється стаціонарний режим. Якщо число станів системи звичайно, і з кожного з них за кінцеве число кроків м. перейти в будь-яке інше стан, то фінальні ймовірності існують, тобто
