- •3.2. Оптимізація смо за критерієм мінімуму економічних втрат від відмов в обслуговуванні .………………………………..……. 86
- •Анотація
- •Розділ 1. Моделювання випадкових процесів
- •1.1. Марковські випадкові процеси
- •1.2. Процес народження і загибелі
- •У відповідності до раніш введених позначень маємо:
- •Позначаючи , одержимо відповідні ймовірності станів смо
- •1.3. Потоки випадкових подій
- •1.4. Моделювання вхідних і вихідних потоків у смо
- •Розділ 2. Аналіз класичних моделей систем масового обслуговування
- •2.1. Загальна характеристика систем масового обслуговування
- •2.2. Системи масового обслуговування з відмовами
- •Імовірності станів смо:
- •Операційні характеристики смо:
- •2.3. Системи масового обслуговування з чергою
- •2.3.1. Смо з n каналами обслуговування і m місцями для чекання
- •Імовірності станів системи:
- •2.3.2. Смо з n каналами обслуговування і необмеженою чергою
- •1. Імовірності станів системи:
- •2.4. Смо з обмеженим часом чекання
- •Вхідні параметри смо:
- •Завдання для лабораторної роботи №4
- •2.5. Замкнуті системи масового обслуговування
- •2.6. Смо із взаємодопомогою між каналами
- •2.2. Система масового обслуговування з довільним розподілом часу обслуговування
- •3.1. Критерії оптимізації смо
- •3.2. Оптимізація замкнутої смо за критерієм максимуму прибутку
- •3.3. Оптимізація смо за критерієм мінімуму економічних втрат від відмов в обслуговуванні
- •Контрольні запитання
- •Відповіді до задач
- •Література
Розділ 1. Моделювання випадкових процесів
У СИСТЕМАХ МАСОВОГО ОБСЛУГОВУВАННЯ
1.1. Марковські випадкові процеси
Теорія систем масового обслуговування (СМО) вивчає процеси, пов’язані із задоволенням масового попиту на обслуговування при випадковому характері попиту і обслуговування і дозволяє здійснювати математичне моделювання їх закономірностей.
Для математичного опису випадкових
процесів, які протікають у СМО,
застосовується математичний
апарат, розроблений в теорії імовірностей
для так званих марковських
випадкових (стохастичних) процесів.
Під випадковим процесом розуміється
послідовність випадкових величин
які є функціями часу
Випадкові величини
можуть приймати як дискретні так і
неперервні значення. Час
також може змінюватись дискретно або
неперервно.
Випадковий процес описується за допомогою
умовних імовірностей, які виражають
імовірність того, що випадкова величина
буде дорівнювати xn
при умові, що
випадкові величини
прийняли значення
.
На практиці вивчати процеси з таким складним зв’язком важко. Тому для їх опису застосовується більш простий зв’язок. Процеси з таким зв’язком називаються процесами Маркова.
Визначимо поняття марковського
випадкового процесу. Нехай є деяка
фізична система
стани якої змінюються у часі. Під системою
може розумітись будь-що – підприємство,
комп’ютерна система або мережа, технічний
пристрій, магазин тощо. Якщо система
змінює свої стани випадковим чином, то
це значить, що у системі протікає
випадковий процес.
Марковським процесом або
процесом без
післядії називається процес
S(t), якщо він має
такі властивості: для кожного моменту
часу
імовірність будь-якого стану системи
в майбутньому (при
)
залежить тільки від її стану
в теперішній час (при
)
і не залежить від того, коли і яким чином
система прийшла
у цей стан.
Марковські випадкові процеси діляться на класи в залежності від того, як і в які моменти часу система S може змінювати свої стани.
Процесом з дискретними станами
називається випадковий процес,
якщо можливі стани системи
можна перелічити (пронумерувати) один
за одним, а сам процес полягає у тому,
що система S час від часу переходить
(миттєво перескакує) з одного стану у
інший. Для аналізу таких систем
користуються діаграмами станів, на яких
зображуються стани системи і можливі
переходи із стану у стан. Переходи і їх
напрям зображуються стрілками.
Процесом з дискретним
часом (дискретним марковським
ланцюгом) називається випадковий процес,
якщо переходи системи із стану у стан
можливі тільки
у строго визначені, заздалегідь фіксовані
моменти часу
У проміжках часу між цими
моментами система S зберігає
свої стани.
Нехай випадкова величина
визначає стан системи S
на n-му
кроці. Послідовність
випадкових величин
утворює дискретний
марковський ланцюг,
якщо для усіх n
і усіх можливих значень випадкових
величин
виконується рівність:
Вираз у правій частині цієї рівності
називають імовірністю переходу за
один крок.
Вона задає умовну ймовірність переходу
системи із стану
у якому вона знаходиться на (n–1)-му
кроці, у стан
на n-му кроці.
Марковський ланцюг називається однорідним, якщо перехідні ймовірності не залежать від номера кроку і його означення задається рівністю:
,
яка визначає ймовірність переходів із поточного стану Si у наступний стан Sj на будь-якому кроці n.
Перехідні ймовірності представляються у вигляді матриці, яка називається матрицею переходів (матрицею перехідних імовірностей):
Для кожного елемента і рядка матриці виконується умова
Це означає, що з імовірністю 1 система S із стану Si перейде у будь-який інший стан Sj. Матриця, яка задовольняє цій умові, називається стохастичною.
Аналогічно перехідним імовірностям за один крок, визначаються ймовірності переходу ріj (k) за k кроків. Має місце рівність Маркова:
Ця рівність визначає ймовірність
переходу системи із стану
у стан
за k кроків як суму добутків імовірності
переходу із стану Si
у проміжний стан Sr
за m кроків на ймовірність переходу
із стану
у стан
за останні
кроків.
Позначимо через
Pi(k)
імовірність
перебування системи
на k-му кроці у стані Si
:
Події досягнення будь-яких станів
за k
кроків
утворюють повну групу несумісних подій,
тому їх імовірності задовольняють
умові, яка називається нормуючою
умовою:
Якщо відомий початковий розподіл імовірностей і ймовірності переходів, то однозначно обчислюються ймовірності станів на k-му кроці за формулою
У матричній формі співвідношення для ймовірностей станів мають такий вигляд:
де P(k)={P0(k), P1(k), …, Pn(k)} – вектор імовірностей станів системи після k-го кроку, P(0)={P0(0), P1(0), …, Pn(0)} – вектор початкового розподілу ймовірностей, P – матриця перехідних імовірностей.
У теорії марковських ланцюгів доведено загальне положення (ергодична теорема): якщо число станів системи S скінчене і із кожного стану вона може перейти за будь-яке число кроків у кожний інший, то існують граничні (стаціонарні) імовірності станів, які не залежать від початкового розподілу ймовірностей станів системи:
Величини рj однозначно визначаються рівностями:
Граничні ймовірності pj часто називають імовірностями станів рівноваги, маючи на увазі, що повністю відсутній вплив початкового розподілу ймовірностей на стани системи.
Визначимо вектор граничного розподілу
ймовірностей станів
.
Тоді система рівнянь, яка визначає
стаціонарні ймовірності станів
системи, у матричній формі
матиме вигляд:
де Р – матриця переходів, І – одинична матриця.
Одержана система рівнянь є системою
лінійних рівнянь з n
невідомими pi
і тому є лінійно залежна і,
таким чином, вона не має єдиного розв’язку.
Але якщо у системі відкинути одне
рівняння, то одержимо єдиний розв’язок,
який дає стаціонарний розподіл
імовірностей станів системи.
Алгоритм розв’язання одержаної системи наступний. Згідно Mathcad-технології будемо оперувати з вектор-стовпцями.
Спочатку визначаємо матрицю PT
– I системи рівнянь
.
Потім замінюємо останній рядок цієї
матриці вектором, який складається із
коефіцієнтів рівняння
і має вигляд (1, 1,..., 1). Одержуємо матрицю
коефіцієнтів С. Визначимо також
вектор-стовпець q правих
частин системи рівнянь у вигляді qТ=
(0, ..., 0, 1). Одержуємо систему рівнянь p
C = q відносно
невідомих величин
pi,
розв’язком якої є вектор-стовпець p
= C–1
q.
Приклад 1.1. Кожний водій мікрорайону заправляє свій автомобіль щотижнево на одній із трьох автозаправних станцій в залежності від того, на якій станції він заправляв свій автомобіль у попередній тиждень. У якийсь тиждень було опитано 100 водіїв, серед яких: 50 заправляли свій автомобіль на станції № 1, 20 – на станції № 2, 30 – на станції № 3.
Серед 50 водіїв, які заправляли свій автомобіль на станції № 1, 45 будуть продовжувати заправляти автомобіль на цій станції, 4 – на станції № 2 і 1 на станції № 3.
Серед 20 водіїв, які заправляли свій автомобіль на станції № 2, 6 будуть продовжувати заправляти його на цій станції, 8 – на станції № 1, 6 – на станції № 3.
Серед 30 водіїв, які заправляли свій автомобіль на станції № 3, 6 будуть продовжувати заправляти на цій станції, 20 – на станції № 1, 4 – на станції № 2.
Знайти стаціонарний розподіл ймовірностей і встановити, на якій автозаправній станції буде заправлятись більше автомобілів. Показати також, як скоро встановлюється стаціонарний режим, тобто на якому кроці ймовірності станів становляться незмінними.
Розв’язання. Опишемо функціонування системи S у термінах марковського процесу. Системою S будуть автозаправні станції. Система має три стани Si (i=1, 2, 3) – водій заправляє автомобіль на станції з номером i. Діаграма інтенсивностей переходів системи має такий вигляд
Рис. 1.1. Діаграма інтенсивностей переходів системи
За початковим розподілом водіїв по
автозаправним станціям і їх розподілу
у наступні тижні визначимо вектор
початкового розподілу ймовірностей
станів Р0 і матрицю ймовірностей
переходів P. Вектор
початкового розподілу Р0 обчислюється
як відношення кількості водіїв, яка
характеризує даний стан Аі, до
загальної кількості
водіїв. Матриця ймовірностей переходів
розраховується як відношення
розподілу кількості водіїв по автозаправним
станціям у наступні тижні Bij
до відповідного розподілу їх у
початковий період Ai.
Згідно наведеному алгоритму, знайдемо стаціонарний розподіл ймовірностей p=(p0, p1, p2). Визначаємо матрицю коефіцієнтів системи рівнянь p(PT– I)=0, де PT – транспонована матриця P. Коефіцієнти першого і другого рядків цієї системи визначаються відповідними рядками матриці С=PT– I, а останній рядок складається із коефіцієнтів рівняння p0+p1+p2=1 і має вигляд (1, 1, 1 ). Визначимо також вектор–стовпець q правих частин системи рівнянь у вигляді (0, 0, 1)T. Таким чином маємо систему рівнянь pC=q, розв’язком якої є вектор p = C–1 q. Розв’язуючи її матричним способом, знаходимо стаціонарний розподіл ймовірностей станів системи, яка визначає розподіл водіїв по автозаправним станціям.
Алгоритм розрахунків у Mathcad з очевидною зміною позначень має вигляд:
Визначаємо початковий розподіл ймовірностей станів системи:
Розв’язуючи
систему рівнянь
,
одержуємо стаціонарний розподіл
ймовірностей станів системи у вигляді
вектора p:
Проводячи розрахунки, послідовно одержимо вектори розподілу ймовірностей станів системи (ймовірності розподілу водіїв по автозаправним станціям) за періоди k=1,…, 4.
Звідси видно, що більша кількість водіїв буде заправлятись на станції №1. У стаціонарний режим, тобто у режим, який надалі стає незмінним, система входить на четвертому кроці ( p4 співпадає із стаціонарним розподілом p).
Розглянемо тепер неперервні ланцюги Маркова.
Випадковий процес називається неперервним марковським ланцюгом, якщо множина його станів дискретна, а переходи із одного стану у іншій можуть здійснюватись у будь-які (не обов’язково цілочислові) моменти часу. Фізичні системи, у яких протікає такий процес, часто зустрічаються на практиці. Наприклад, поломка автомобіля може трапитись у будь-який момент часу, закінчення ремонту цього автомобіля також здійснюється у заздалегідь нефіксований момент тощо.
Імовірності
станів для неперервного марковського
ланцюга виражаються наступним чином.
Нехай S0,
S1,
..., Sn
є
ряд дискретних станів системи таких,
що перехід із одного стану у іншій може
здійснитись
у будь-який момент.
По
аналогії з дискретним ланцюгом для
неперервного марковського ланцюга
визначимо ймовірності переходу за час
Δt, які є умовними ймовірностями станів
в момент
у припущенні появи певних станів в
момент t:
де
положення
системи в момент часу t+Δt при умові, що
в момент t
вона знаходилась у стані Si.
Замість
перехідних імовірностей за один крок
введемо інтенсивності ймовірностей
переходів
Інтенсивністю
ймовірності переходу (щільністю
ймовірності переходу)
називається
границя
відношення ймовірності переходу Pij(t,
Δt)
системи
за час Δt
із стану Si
у стан Sj
до довжини проміжку Δt:
,
.
Величину
можна
трактувати як інтенсивність переходу
системи із стану Si
у
стан Sj
за умови, що
поточний
стан системи. Величина
є
інтенсивність виходу системи із стану
Si
у
будь-який інший стан в момент t.
Якщо
щільності ймовірностей переходів
не залежать від t
–
,
то
марковський процес називається
однорідним.
Далі будемо розглядати однорідні
марковські процеси.
Позначимо
через
імовірність того, що в момент t система
буде знаходитись у стані
Очевидно, для будь-якого моменту t
виконується рівність
Імовірності станів марковського процесу зв’язані системою диференціальних рівнянь, які називають рівняннями Колмогорова:
Продемонструємо методику виведення рівнянь Колмогорова для ймовірностей станів системи на конкретному прикладі. Поставимо задачу записати рівняння Колмогорова і визначити початкові умови для розв`язку цієї системи, якщо відомо, що в початковий момент система знаходиться у стані S0.
Введемо позначення: λij=λi при i < j, λij=μi при i > j. Нехай система S має n+1 можливих станів S0, S1,…, Sn. Розмічена діаграма станів системи і відповідних інтенсивностей переходів має вигляд:
Рис. 1.2. Діаграма інтенсивностей переходів системи
Почнемо з опису динаміки процесу.
Розглянемо можливі зміни станів процесу
на проміжку часу
і знайдемо ймовірність того, що в момент
система буде
знаходитись у стані
Ця подія може відбутись одним із
трьох взаємовиключаючих способів:
в момент t система вже була у стані Si , і за час
не
відбулось зміни стану;в момент t система знаходилась у стані Si–1 і за час перейшла у стан Si;
в момент t система знаходилась у стані Si+1 і за час перейшла у стан Si.
Імовірності цих подій з точністю до малих вищого порядку ніж дорівнюють:
Застосовуючи правило складання ймовірностей несумісних подій, одержимо рівняння:
Розкриваючи дужки у правій частині рівності, перенесемо Pi(t) у ліву і поділимо обидві частини рівності на , одержимо:
Переходячи до границі
при
,
у лівій частині рівняння одержимо
похідну
:
Гранична рівність при
має такий вигляд:
Таким чином, приходимо до системи диференціальних рівнянь, яким задовольняють функції Pi(t).
Для розвязання
одержаної системи у нестаціонарному
режимі, коли Pi(t) залежить від часу,
треба ще задати початкові умови
.
Якщо система S в початковий момент
знаходиться у стані S0 , то
Крім того повинна задовольнятись умова
Звернемо увагу на структуру рівнянь Колмогорова. Усі вони побудовані за певним правилом, яке можна сформулювати наступним чином: у лівій частині кожного рівняння стоїть похідна ймовірностей станів за часом, а права частина вміщує стільки членів, скільки стрілок звязано з даним станом.
Якщо стрілка направлена із стану, відповідний член має знак “”; якщо у стан – знак “+”. Кожний член у правій частині дорівнює добутку щільності ймовірності переходу відповідно даній стрілці на ймовірність того стану, з якого вона виходить.
Це правило складання диференціальних рівнянь для ймовірностей станів є загальним і справедливе для будь-якого неперервного марковського ланцюга. Це дозволяє записувати диференціальні рівняння для ймовірностей станів безпосередньо за розміченою діаграмою станів.
Відомо, що для однорідних ланцюгів з неперервним часом також, як і для ланцюгів з дискретним часом за умови, що усі стани системи є досягненними, завжди існують граничні (стаціонарні) імовірності:
,
які не залежать від початкового стану системи.
Покладаючи рівними нулю похідні у диференціальному рівнянні, для визначення стаціонарних імовірностей рі будемо мати систему лінійних алгебраїчних рівнянь:
з
нормуючою умовою
Ця система разом з нормуючою умовою однозначно визначає граничний розподіл ймовірностей станів неперервного марковського ланцюга.
Приклад 1.2. Нехай деяка фізична система S (автомобіль, комп’ютер тощо) може знаходитись у трьох станах S0, S1, S2. У початковий момент система знаходиться у стані S0. Складемо систему диференціальних рівнянь Колмогорова і запишемо початкові умови для її розвязку. Розмічена діаграма станів має вигляд:
Рис. 1.3. Діаграма інтенсивностей переходів системи
Система диференціальних рівнянь Колмогорова має вигляд:
Враховуючи те, що у початковий момент система знаходиться у стані S0, початкові умови мають вигляд:
