Теорема 2Для ланцюга Маркова, що не приводиться і аперіодичної, завжди існує гранична вірогідність, не залежна від початкового розподілу вірогідності. Більш того, має місце одна з наступних двох можливостей: А) всі стани ланцюга неповоротні або всі поворотні нульові, і тоді вся гранична вірогідність рівна нулю і стаціонарного стану не існує; Б) всі стани поворотні ненульові і тоді існує стаціонарний розподіл вірогідності:
Стан називається ергодичним, якщо воно аперіодичне і поворотно-ненульове. Якщо всі стани ланцюга Маркова ергодичні, то весь ланцюг називається ергодичним. Граничну вірогідність ергодичного ланцюга Маркова називають вірогідністю стану рівноваги, маючи на увазі, що залежність від початкового розподілу вірогідності повністю відсутня. Ланцюг Маркова з кінцевим числом станів (кінцевий ланцюг), зручно зображати у вигляді орієнтованого графа, званого діаграмою переходів. Вершини графа асоціюються із станами, а ребра з вірогідністю переходів. Обчислення вірогідності досягнення станів проводиться прямими методами або за допомогою z-перетворення.
Ланцюг Маркова Введемо матрицю вірогідності переходів і вектор-рядок вірогідності на кроці n
Розподіл вірогідності на довільному кроці тоді підкорятиметься матричному співвідношенню:
Воно дозволяє рекурентно обчислювати всю вірогідність станів. Для знаходження граничного розподілу (стаціонарного) потрібно вирішити рівняння:
Його можна вирішувати як систему лінійних рівнянь алгебри, якщо ланцюг кінцевий. Для прикладу (мал. 1) маємо:
і рішення матричного рівняння зводиться до рішення системи трьох рівнянь:
Коефіцієнти першого рівняння в цій системі доповнюють до одиниці суму коефіцієнтів другого і третього рівнянь; це свідчить про лінійну залежність між ними. Тому для вирішення системи рівнянь потрібно ввести додаткову нормуючу умову. В даному прикладі: Вирішуючи систему отриманих рівнянь, маємо:
Рівняння для вірогідності досягнення стану в перехідному режимі вирішити значно важче. Деякого спрощення можна досягти, використовуючи z – перетворення. Застосуємо його до рівняння для перехідної вірогідності
Позначаючи відповідні перетворення, отримаємо: Всі отримані тут математичні результати відносилися до однорідних Марківських процесів, де вірогідність переходів не залежить від часу. В більш загальному випадку така залежність має місце. Розглянемо вірогідність переходу системи із стану i на m-том кроці в стан j на n-том кроці для n > m. Можна показати, що ця вірогідність зв'язана між собою, так званим рівняннями Чепмена-Колмогорова. (Chapman – Kolmogorov)
Для однорідних ланцюгів Маркова ці рівняння спрощуються оскільки
І зводяться до аналізованих вище. Системи масового обслуговування За останній час в самих різних областях практики виникла необхідність в рішенні різних задач вірогідності, пов’язаних з роботою так званих систем масового обслуговування (СМО). Прикладами таких систем можуть служити: телефонні станції, ремонтні майстерні, квиткові каси, стоянки таксі, перукарні і т.п. Теорія масового обслуговування спирається на теорію вірогідності і математичну статистику. На первинний розвиток теорії масового обслуговування зробили особливий вплив роботи Датського ученого А.К. Эрланга (1878-1929). Теорія масового обслуговування – область прикладної математики, що займається аналізом процесів в системах виробництва, обслуговування, управління, в яких однорідні події повторюються багато разів, наприклад, на підприємствах побутового обслуговування; в системах прийому, переробки і передачі інформації; автоматичних лініях виробництва і ін. Предметом теорії масового обслуговування є встановлення залежностей між характером потоку заявок, числом каналів обслуговування, продуктивністю окремого каналу і ефективним обслуговуванням з метою знаходження якнайкращих шляхів управління цими процесами. Задача теорії масового обслуговування – встановити залежність результуючих показників роботи системи масового обслуговування (вірогідність того, що заявка буде обслужена; математичного очікування числа обслужених заявок і т.д.) від вхідних показників (кількості каналів в системі, параметрів вхідного потоку заявок і т.д.). Результуючими показниками або характеристиками СМО, що цікавлять нас,є – показники ефективності СМО, які описують чи здатна дана система справлятися з потоком заявок. Задачі теорії масового обслуговування носять в імітаційний характер і зрештою включають економічний аспект за визначенням такого варіанту системи, при якому буде забезпечений мінімум сумарних витрат від очікування обслуговування, втрат часу і ресурсів на обслуговування і простоїв каналів обслуговування. Система обслуговування вважається заданою, якщо відомі: 1) потік вимог, його характер; 2) безліч обслуговуючих приладів; 3) дисципліна обслуговування (сукупність правил, задаючих процес обслуговування). Кожна СМО складається з якогось числа обслуговуючих одиниць, які називаються каналами обслуговування. Як канали можуть фігурувати: лінії зв’язку, різні прилади, особи, що виконують ті або інші операції і т.п Всяка СМО призначена для обслуговування якогось потоку заявок, що поступають в якісь випадкові моменти часу. Обслуговування заявок продовжується якийсь випадковий час, після чого канал звільняється і готовий до прийому наступної заявки. Випадковий характер потоку заявок і часів обслуговування призводить до того, що в якісь періоди часу на вході СМО накопичується надмірно велике число заявок (вони або стають в чергу, або покидають СМО не обслуженими); в інші ж періоди СМО працюватиме з недовантаженням або взагалі простоюватиме. Процес роботи СМО є випадковим процесом з дискретними поляганнями і безперервним часом; полягання СМО міняється стрибком в моменти появи якихось подій (або приходу нової заявки, або закінчення обслуговування, або моменту, коли заявка, якій набриднуло чекати, покидає чергу). Перелік характеристик систем масового обслуговування можна представити таким чином:
· середній час обслуговування; · середній час очікування в черзі; · середній час перебування в СМО; · середня довжина черги; · середнє число заявок в СМО; · кількість каналів обслуговування; · інтенсивність вхідного потоку заявок; · інтенсивність обслуговування; · інтенсивність навантаження; · коефіцієнт навантаження; · відносна пропускна спроможність; · абсолютна пропускна спроможність; · частка часу простою СМО; · частка обслужених заявок; · частка втрачених заявок; · середнє число зайнятих каналів; · середнє число вільних каналів; · коефіцієнт завантаження каналів; · середній час простою каналів.
СМО поділяють на різні групи в залежності від складу і від часу перебування в черзі до початку обслуговування, і від дисципліни обслуговування заявок. По складу СМО бувають: одноканальні – характеризуються одним вхідним потоком,одним обслуговуючим пристроєм; багатоканальн і – з великим числом обслуговуючих пристроїв. Багатоканальні системи можуть складатися з обслуговуючих пристроїв як однакової, так і різної продуктивності. За часом перебування вимог у черзі до початку обслуговування системи поділяються на три групи: 1) з необмеженим часом очікування – чергова заявка (вимога), заставши всі пристрої зайнятими, стає в чергу й очікує обслуговування доти, поки один із пристроїв не звільниться; 2) з відмовами – вимога, яка надійшла, заставши всі пристрої зайнятими, залишає систему; 3) змішаного типу – вимога, що надійшла, заставши всі пристрої зайнятими, стає у чергу й очікує обслуговування протягом обмеженого часу. Не дочекавшись обслуговування у встановлений час, заявка залишає систему. Практична частина: Завдання №1 Розробити модель роботи видавничого центру та дослідити поведінку характеристик її ефективності. У видавничому центрі є принтери для друку документів. Інтенсивність друку документів дорівнює λ документів у хв.. Середній час друку складає s хв. Передбачається, що черга документів, що очікують друкування, може бути необмеженої довжини. Параметри завдання: r = 3; λ = 0,9; s = 4
|
.
.
.
.
.
.
.
.
