- •1 Моделі однолінійних систем масового обслуговування
- •1.1 Основні поняття і визначення. Дисципліна обслуговування.
- •1.2 Марківські процеси і ланцюги та їх властивості
- •1.2.1 Поняття марківського процесу і ланцюга
- •1.2.2 Дискретний ланцюг Маркова
- •2. Математична модель процесів народження і загибелі
- •2.1 Рівняння Колмогорова-Чепмена та рівняння Колмогорова
- •2.2 Ергодичні ймовірності процесів народження і загибелі
- •3 Математична модель системи мо з кінцевим числом станів
- •3.1 Зворотні та прямі рівняння Колмогорова
- •3.2 Математичні моделі консервативних систем мо
- •3.3 Обчислення інтенсивностей переходів марківських процесів
- •3.4 Система із n приладів і r із них можуть відновлюватись
- •2. Які величини є елементами інфінітезимальної матриці?
- •4 Моделі багатолінійних систем масового обслуговування
- •4.1 Основні типи систем масового обслуговування
- •4.2 Символіка систем мо
- •4.2 Математичні моделі основних типів систем мо
- •4.3 Багатолінійна система м/м/n/n з обмеженою чергою і обмеженим часом очікування
- •4.4 Обчислення ергодичних розподілів системи мо типу m/m/n/n
- •4.4.1 Багатоканальна система з обмеженою чергою (m/m/n/n)
- •4.4.2 Багатоканальна система з нескінченою чергою і обмеженим часом очікування (m/m/n)
- •4.4.3 Система мо з очікуванням і необмеженою чергою (m/m/n; )
- •5 Оптимальні потоки у мережах
- •5.1 Поняття про мережу і основні визначення
- •5.2 Задача про максимальний потік у мережі
- •5.3 Теореми про оптимальні потоки у мережах
- •5.4 Метод розстановки поміток для знаходження максимального потоку
- •5.5 Модифікований метод розстановки поміток для знаходження максимального потоку
- •5.6 Алгоритм Форда-Фалкерсона знаходження максимального потоку
- •6 Багатополюсні максимальні потоки
- •6.1 Умова реалізації
- •6.2 Аналіз мережі
- •7 Найкоротші ланцюги і потоки мінімальної вартості
- •7.1 Найкоротші ланцюги
- •7.2 Багатополюсні найкоротші ланцюги
- •7.3 Багатополюсні ланцюги максимальної пропускної здатності
- •7.4 Потоки мінімальної вартості
3.2 Математичні моделі консервативних систем мо
Система МО називається консервативною, якщо між інтенсивностями і існує таке співвідношення:
. (3.13).
При дослідженні консервативних систем часто знаходять не всі перехідні ймовірності, а лише ті, які характеризують стани системи в момент часу t. Для розв’язку такої задачі рівняння (3.8) слід записати для випадку коли . В результаті отримаємо
.
Якщо ввести позначення і , то будемо мати таке диференціальне рівняння:
. (3.14)
з такою початковою умовою:
, (3.15)
яка характеризує стан системи в момент часу t=0
Для більшості систем МО повинні виконуватись умови нормування:
(3.16)
3.3 Обчислення інтенсивностей переходів марківських процесів
Допустимо, що при умові в момент часу t протікають операції , ,..., . При цьому величина роботи, яка пов’язана з виконанням -ої з таких операцій випадкова величина , що розподілена за експоненціальним законом з параметром , . Крім того допустимо, що - незалежні випадкові величини. Позначимо через темп виконання операції за умови, що . Якщо в даному стані деяка операція не виконується але може виконуватись, то можна включити її в число операцій що “продовжуються”, вважаючи, що відповідні .
Якщо величина роботи, пов’язана з виконанням операції, виражаються в одиницях часу, то допускають , якщо k-та операція виконується – в протилежному випадку.
Нехай система знаходиться в стані і. Позначимо через ймовірність переходу системи в стан j за умови, що закінчилася операція .
Тоді інтенсивності переходів марківського процесу обчислюються за такою формулою:
. (3.18)
3.4 Система із n приладів і r із них можуть відновлюватись
Система складається із N приладів, час безвідмовної роботи, кожного із них експоненціально-розподілена випадкова величина з параметром .
Позначимо через число елементів, що знаходяться в момент часу в неробочому стані, тоді . Є r i операторів, кожен із яких може одночасно відновлювати лише один прилад. Якщо число приладів, що відмовили більше r, то r елементів відновлюються, інші утворюють чергу на відновлення. В стані і маємо і0=mini,r операцій відновлення Оі1,..., Оіі0. Допускаємо, що операції відновлення мають експоненціальний закон розподілення з параметром і . Очевидно, що .
Закінчення однієї із операцій відновлення приводить до зменшення несправних приладів на одиницю. Це означає, що система переходить в новий стан і і-1. Отже fi,i-1(1)= fi,i-1(2)=...= fi,i-1(i0)=1 ( - ймовірності закінчень однієї із k-тих операцій відновлення Оik, ) і fij(1) = fij(2) =... = fij(io) = 0, .
Кількість операцій , які зв’язані з експлуатацією працездатних приладів, позначимо через Оі,і0+1, Оі,і0+2,..., Оі,і0+N-i. Допустимо також, що час роботи приладів, мають експоненціальний закон розподілу з параметром l, тобто . Відповідно і,і0+1 = і,і0+2 =... = і,і0+N-i = 1.
Вихід із ладу одного із робото здатних приладів переводить систему із стану і в стан і+1, а це означає, що
,
, ji+1
За формулою(3.18) знаходимо
(і0 - доданків)
(( ) - доданків)
Для інших значень j q ij = 0
Отже,
(3.19)
qi,i +1=(N-i); (3.20)
qij=0 при j i -1, i +1. (3.21)
Приклад 3.3. Розглянемо систему, яка складається із трьох придатних до роботи в момент часу приладів (наприклад, комп’ютерів) з експоненціально розподіленими тривалостями життя (параметр ).
В ремонтній майстерні одночасно може ремонтуватись тільки один прилад, що вийшов із ладу. Тривалість ремонту розподілена експоненціально (параметр ). Завжди одночасно працюють два прилади, а третій або в “холодному” резерві або ремонтується. Система припиняє свою роботу, якщо виходять із ладу два прилади.
Шукаємо ймовірність того, що система на момент часу t вийде із ладу.
Нехай стан системи означає кількість приладів, що вийшли з ладу. Тоді система буде мати наступні стани:
0 – всі прилади придатні до роботи ;
1 – вийшов з ладу один прилад ;
2 – вийшли з ладу два прилади.
Відповідними ймовірностями є . Очевидно, що .
Марківський граф системи поданий на рис. 3.2. Відбувається стрибок вверх , якщо один із працюючих приладів виходить із ладу.
Рисунок 3.2 – Граф системи МО
Оскільки розподіл ймовірностей експоненціальний, то , і . Стрибок вниз відчувається після закінчення ремонту. Стан є „поглинаючим”, тобто, коли система досягла цього стану, то вона вже його не покидає. Тому .
Складемо систему диференціальних рівнянь у відповідності з (3.14). В нашому випадку . Отже
;
;
;
Запишемо рівняння (3.14) в матрично-векторній формі:
де ; А – інфінітезимальна матриця. Для випадку, що розглядається
Якщо врахувати значення , , і , ,то
Останнє матричне рівняння розкладається на такі рівняння:
Отже, система диференціальних рівнянь буде мати вигляд:
З початковими умовами і умовою нормування .
Отриману систему диференціальних рівнянь легко розв’язати, застосувавши до неї перетворення Лапласа.
Перше і друге рівняння запишемо в такій формі:
Маємо систему лінійних алгебраїчних рівнянь з двома невідомими, із якої знаходимо:
Третє рівняння системи дає:
Враховуючи значення , маємо:
Знаходження величин , і як функцій часу t полягає в знаходженні зворотного перетворення Лапласа за формулою:
(3.17)
де - полюси функції
Відмітимо, що умови нормування зберігаються і для зображень .
Розв’яжемо задачу при значеннях і .
Спочатку знайдемо полюси функцій , розв’язавши рівняння . Тоді і . Використовуючи формулу (3.27), в якій , знаходимо , . Оскільки функція має три полюси – , і , то застосувавши формулу (3.27), в якій , знаходимо .
Задачу, яка розглянута нами, можна розв’язати дещо по-іншому, використавши векторно-матричну форму подання математичної моделі системи масового обслуговування
з вектором початкових умов - . Подальші обчислення ведемо з використанням програмного продукту MathCAD (рис. 3.3).
РОЗВ'ЯЗОК
МАТЕМАТИЧНОЇ МОДЕЛІ СИСТЕМИ МАСОВОГО
ОБСЛУГОВУВАННЯ З
КІНЦЕВИМ ЧИСЛОМ СТАНІВ
Параметри
системи МО
Інфінітіземальна
матриця системи МО
Одинична
матриця системи
Знаходимо
розв'язок матрично-векторного рівняння
системи в термінах перетворення Лапласа
Перехідні
ймовірності системи МО з кінцевим
числом станів
Графіки
ймовірностей Pj(t) як функцій часу t
Рисунок 3.3 – Програма розв'язку задачі масового обслуговування з кінцевим числом станів
Приклад 3.4. Система масового обслуговування складається із п’яти приладів. Одночасно працює три прилади. Два інші ремонтуються, або знаходяться в "холодному" резерві. Тривалості життя приладів і тривалість ремонту кожного із несправних приладів випадкові незалежні експоненціально розподілені величини з параметрами і . Ремонтує несправні прилади один оператор. Система припиняє свою роботу, якщо виходять із ладу два прилади.
Шукаємо ймовірність того, що система на момент часу t вийде із ладу.
Нехай стан системи означає кількість приладів, що вийшли з ладу. Тоді система буде мати наступні стани:
0 – всі прилади придатні до роботи ;
1 – вийшов з ладу один прилад ;
2 – вийшли з ладу два прилади;
3 – вийшли з ладу три прилади.
Відповідними ймовірностями є . Очевидно, що .
Граф системи МО показаний на рис. 3.4.
Рисунок 3.4 – Граф системи масового обслуговування з кінцевим числом станів
Знайдемо перехідні інтенсивності . У відповідності з формулою(3.19) маємо , і . Оскільки ремонтом приладів займається тільки один оператор, то за формулою (3.19) знаходимо, що і . Інші значення . Складемо інфінітезимальну матрицю системи МО
. Приймаючи до уваги знайдені значення ,отримуємо . У відповідності з формулою (3.13) для знаходження інтенсивностей , необхідно просумувати елементи відповідних рядків матриці А. Тоді , , і . Отже,
.
Знаючи інфінітезимальну матрицю А, можемо записати векторно-матричне рівняння системи масового обслуговування
(3.21)
з початковою умовою . Виконавши перетворення Лапласа над рівнянням (3.21) і врахувавши початкову умову, знаходимо
.
Тепер для того, щоб отримати необхідно перейти до зворотного перетворення Лапласа. Отже,
,
де - символ зворотного перетворення Лапласа.
Подальші обчислення доцільно здійснити, використавши програмний продукт MathCAD (рис. 3. 5).
РОЗВ'ЯЗОК
МАТЕМАТИЧНОЇ МОДЕЛІ СИСТЕМИ МАСОВОГО
ОБСЛУГОВУВАННЯ З
КІНЦЕВИМ ЧИСЛОМ СТАНІВ
Параметри
системи МО
Інфінітіземальна
матриця системи МО
Одинична
матриця системи
Знаходимо
розв'язок матрично-векторного рівняння
системи в термінах перетворення Лапласа
Перехідні
ймовірності системи МО з кінцевим
числом станів
Графіки
ймовірностей Pj(t)
як функцій часу t
Рисунок 3.5 – Програма розв'язку математичної моделі системи масового обслуговування з кінцевим числом станів
Контрольні запитання і завдання
1. Які основні допущення зроблені при складанні математичної моделі з кінцевим числом станів?