ПРОЦЕС ЗАГИБЕЛІ ТА РОЗМНОЖЕННЯ

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

Граф станів процесу загибелі і розмноження має вигляд, показаний на рис. 15.4.

Мал. 15.4

Розглянемо впорядкована множина станів системи Переходи можуть здійснюватися з будь-якого стану тільки в стани з сусідніми номерами, тобто зі стану можливі переходи тільки або в стан , або в стан [1] .

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

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

Відповідно до правила складання таких рівнянь (див. 15.10) отримаємо: для стану S 0

(15.12)

для стану S,

, Яке з урахуванням (15.12) приводиться до вигляду

(15.13)

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

(15.14)

до якої додається нормувального умова

(15.15)

Вирішуючи систему (15.14), (15.15), можна отримати

(15.16)

(15.17)

Легко помітити, що в формулах (15.17) для коефіцієнти при є складові, які стоять після одиниці у формулі (15.16). Чисельники цих коефіцієнтів представляють твір всіх інтенсивностей, що стоять біля стрілок, що ведуть зліва направо до даного стану , а знаменники - твір всіх інтенсивностей, що стоять біля стрілок, що ведуть справа наліво зі стану до .

15.4. Процес загибелі та розмноження представлений графом (рис. 15.5). Знайти граничні ймовірності станів.

Мал. 15.5

Рішення. За формулою (15.16) знайдемо

по (15.17) тобто в сталому, стаціонарному режимі в середньому 70,6% часу система буде перебувати в стані 5 (), 17,6% - в стані 5, і 11,8% - в стані S2. ►

СМО З ВІДМОВАМИ

Як показники ефективності СМО з відмовами будемо розглядати:

А - абсолютну пропускну здатність СМО, тобто середнє число заявок, що обслуговуються в одиницю часу;

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

Р тк - ймовірність відмови, тобто того, що заявка покине СМО необслуженной;

k - середнє число ком каналів (для багатоканальної системи).

Одноканальна система з відмовами. Розглянемо задачу.

Є один канал, на який надходить потік заявок з інтенсивністю λ. Потік обслуговувань має інтенсивність μ [2] . Знайти граничні ймовірності станів системи і показники її ефективності.

Система 5 (СМО) має два стани: 50 - канал вільний, 5, - канал зайнятий. Розмічений граф станів представлений на рис. 15.6.

Мал. 15.6

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

(15.18)

тобто система вироджується в одне рівняння. З огляду на нормувального умова р 0 + р х = 1, знайдемо з (15.18) граничні ймовірності станів

(15.19)

які висловлюють середнє відносне час перебування системи в стані 50 (коли канал вільний) і 5, (коли канал зайнятий), тобто визначають відповідно відносну пропускну здатність Q системи і ймовірність відмови :

(15.20)

(15.21)

Абсолютну пропускну здатність знайдемо, помноживши відносну пропускну здатність Q на інтенсивність потоку заявок

(15.22)

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

Рішення. Маємо λ = 90 (1 / ч), хв. Інтенсивність потоку обслуговуванні μ = 1 / ίο6 = 1/2 = 0,5 (1 / хв) = = 30 (1 / ч). По (15.20) відносна пропускна спроможність СМО Q = 30 / (90 + 30) = 0,25, тобто в середньому тільки 25% заявок складуть переговори по телефону. Відповідно, ймовірність відмови в обслуговуванні складе Р тк = 0,75 (див. (15.21)). Абсолютна пропускна спроможність СМО але (15.22) А = 90 ∙ 0,25 = 22,5, тобто в середньому на годину будуть обслужені 22,5 заявки на переговори. Очевидно, що при наявності тільки одного телефонного номера СМО буде погано справлятися з потоком заявок. ►

Багатоканальна система з відмовами. Розглянемо класичну задачу Ерланга.

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

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

де - стан системи, коли в ній знаходиться k заявок, тобто зайнято k каналів.

Граф станів СМО відповідає процесу загибелі і розмноження і показаний на рис. 15.7.

Мал. 15.7

Потік заявок послідовно переводить систему з будь-якого лівого стану в сусіднє праве з однієї і тієї ж інтенсивністю λ. Інтенсивність же потоку обслуговувань, що переводять систему з будь-якого правого стану в сусіднє ліве, постійно змінюється в залежності від стану. Дійсно, якщо СМО знаходиться в стані S., (два канали зайняті), то вона може перейти в стан 5, (один канал зайнятий), коли закінчить обслуговування або перший, або другий канал, тобто сумарна інтенсивність їх потоків обслуговувань буде 2μ. Аналогічно сумарний потік обслуговувань, що переводить СМО зі стану 53 (три канали зайняті) в 52, буде мати інтенсивність 3μ, тобто може звільнитися будь-який з трьох каналів і т.д.

У формулі (15.16) для схеми загибелі і розмноження отримаємо для граничної ймовірності стану

(15.23)

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

(15.24)

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

(15.25)

(15.26)

Формули (15.25) і (15.26) для граничних ймовірностей отримали назви формул Ерланга [3] на честь засновника теорії масового обслуговування.

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

(15.27)

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

(15.28)

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

(15.29)

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

де / ;, - гранична вірогідність станів, що визначаються але формулами (15.25), (15.26).

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

(15.30)

або, враховуючи (15.29), (15.24):

(15.31)

15.6. В умовах задачі 15.5 визначити оптимальне число телефонних номерів в телевізійному ательє, якщо умовою оптимальності вважати задоволення в середньому з кожних 100 заявок не менше нiж 90 заявок на переговори.

Рішення. Інтенсивність навантаження каналу по формулі (15.24) р = 90/30 = 3, тобто за час середнього (за тривалістю) телефонної розмови 7об = 2 хв надходить в середньому 3 заявки на переговори.

Будемо поступово збільшувати число каналів (телефонних номерів) п = 2, 3, 4, ... і визначимо за формулами (15.25-15.29) для одержуваної і-канальної СМО характеристики обслуговування. Наприклад, при п = 2 р 0 = = (1 + 3 + 32/2!) " '= 0,118 ≈ 0,12; Q = 1 - (з2 / 2l) - 0,118 = 0,47. А = 90 ∙ 0,47 = 42,3 і т.д. Значення характеристик СМО зведемо в табл. 15.1.

Таблиця 15.1

характеристика

обслуговування

Число каналів (телефонних номерів)

I

2

3

4

5

6

Відносна пропускна здатність Q

0,25

0,47

0,65

0,79

0,90

0,95

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

22,5

42,3

58,8

71,5

80,1

85,3

За умовою оптимальності Q > 0,9, отже, в телевізійному ательє необхідно встановити 5 телефонних номерів (в цьому випадку Q = 0,90 - див. Табл. 15.1). При цьому в годину будуть обслуговуватися в середньому 80 заявок = 80,1), а середнє число зайнятих телефонних номерів (каналів) за формулою (15.30) до = 80,1 / 30 = 2,67. ►

15.7. В обчислювальний центр колективного користування з трьома ЕОМ надходять замовлення від підприємств на обчислювальні роботи. Якщо працюють всі три ЕОМ, то знову надходить замовлення не приймається, і підприємство змушене звернутися в інший обчислювальний центр. Середній час роботи з одним замовленням становить 3 год. Інтенсивність потоку заявок 0,25 (1 / ч). Знайти граничні ймовірності станів і показники ефективності роботи обчислювального центру.

Рішення. За умовою п = 3, λ = 0,25 (1 / ч), ^ = 3 (ч). Інтенсивність потоку обслуговувань μ = 1 / ίο6 = 1/3 = = 0,33. Інтенсивність навантаження ЕОМ за формулою (15.24) р = 0,25 / 0,33 = 0,75. Знайдемо граничні ймовірності станів:

за формулою (15.25) р0 = (1 + 0,75 + 0,752 / 2! + 0,753 / 3!) = 0,476;

за формулою (15.26) р, = 0,75 0,476 = 0,357; р 2 = (θ, 752 / 2ΐ) χ Хо, 476 = 0,134; р 3 = (θ, 753 / 3ΐ) • 0,476 = 0,033, тобто в стаціонарному режимі роботи обчислювального центру в середньому 47,6% часу немає жодної заявки, 35,7% - є одна заявка (зайнята одна ЕОМ), 13,4% - дві заявки (дві ЕОМ), 3,3% - три заявки (зайняті три ЕОМ).

Імовірність відмови (коли зайняті всі три ЕОМ), таким чином, Ртк = р 3 = 0,033.

За формулою (15.28) відносна пропускна спроможність центру <2 = 1 - 0,033 = 0,967, тобто в середньому з кожних 100 заявок обчислювальний центр обслуговує 96,7 заявок.

За формулою (15.29) абсолютна пропускна спроможність центру А = 0,25-0,967 = 0,242, тобто в одну годину в середньому обслуговується 0,242 заявки.

За формулою (15.30) середнє число зайнятих ЕОМ до = = 0,242 / 0,33 = 0,725, тобто кожна з трьох ЕОМ буде зайнята обслуговуванням заявок в середньому лише на 72,5 / 3 = 24,2%.

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

  • [1] При аналізі чисельності популяцій вважають, що стан 5t відповідає чисельності популяції, що дорівнює до, і перехід системи зі стану S /; в стан S t _ t відбувається при народженні одного члена популяції, а перехід в стан ⅝_, - при загибелі одного члена популяції.
  • [2] Тут і надалі передбачається, що всі потоки подій, що переводять СМО зі стану в стан, будуть найпростішими. До них відноситься і потік обслуговувань - потік заявок, що обслуговуються одним безперервно зайнятим каналом. Середній час обслуговування i () r, назад за величиною інтенсивності μ, тобто = 1 / μ.
  • [3] А. К. Ерланг (кінець XIX - початок XX ст.) - данський інженер, математик.
 
< Попер   ЗМІСТ   Наст >