МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
Заклад освіти
"Гомельський державний університет
імені Франциска Скорини "
Математичний факультет
Кафедра математичного аналізу
Курсова робота
Інваріантність стаціонарного розподілу трехузловой мережі масового обслуговування
Виконавець
Студентка групи М-42 Грамовіч Є.Г.
Науковий керівник
Кандидат фізико-математичних
наук, старший викладач Якубович О.В.
Гомель 2004
Зміст
Введення
1. Теоретичні відомості
1.1 Марківські процеси
1.2 Найпростіший потік
1.3 Час обслуговування
1.4 Класифікація систем масового обслуговування
1.5 Марківські системи масового обслуговування
1.6 Марківські мережі масового обслуговування
1.7 Знаходження стаціонарних ймовірностей станів відкритої марковської мережі масового обслуговування
1.8 Знаходження рішення для немарковского випадку
2. Марківський випадок
2.1 Опис моделі
2.2 Мережа масового обслуговування
2.3 Рівняння рівноваги
2.4 Знаходження стаціонарних ймовірностей
2.5 Умови ергодичності
3. Немарковского випадок
3.1 Опис моделі
3.2 Складання диференційно-різницевих рівнянь
3.3 Пошук рішення диференційно-різницевих рівнянь
Список літератури
Введення
Математична теорія масового обслуговування є розділом теорії випадкових процесів, що вивчають певний клас задач, які виникають на практиці, коли заявки, які потребують обслуговування, прибувають до деякого обслуговуючому пристрою. Як приклади заявок і обслуговуючих їх пристроїв можна назвати абонентські виклики, що надходять на телефонний комутатор, верстати, які очікують обслуговування робітниками, автомобілі, які очікують у дорожнього перетину, літаки, що прибувають в аеропорт, судна, що заходять в порт і т.д.
Системами (моделями) масового обслуговування називають математичні моделі систем, які призначені для обслуговування заявок, що надходять через випадкові проміжки часу, причому тривалість обслуговування в загальному випадку також випадкова.
Системи масового обслуговування описуються завданням:
вхідного потоку заявок;
спільного розподілу часів обслуговування заявок;
числа обслуговуючих приладів (ліній);
дисципліни обслуговування, організації черги та процесу обслуговування.
У цій роботі розглядається система масового обслуговування для якої:
1) вхідний потік заявок є пуассонівської;
2) у системі три обслуговуючих приладу;
A) Марківський випадок.
3 час обслуговування експоненціальне
4 дисципліна обслуговування FIFO;
Б) немарковского випадок.
3) час обслуговування визначається за допомогою довільної функцією розподілу часу обслуговування
-М приладом однієї заявки, такий що
;
4) дисципліна обслуговування LCFS PR; (заявка, що надходить в -Ий вузол, витісняє заявку з приладу і починає обслуговуватися, витіснена заявка йде в початок черги).
У курсовій роботі для відкритої марковської мережі масового обслуговування складемо рівняння рівноваги, знайдемо стаціонарні ймовірності, встановимо умови ергодичності. Для не марківського випадку складемо диференційно-різницеве рівняння в приватних похідних для процесу, доповненого залишковими часом, знайдемо рішення даного рівняння. Порівняємо марковський і немарковского випадок. Зробимо висновок.
1. Теоретичні відомості
1.1 Марківські процеси
Нехай Т і Х - деякі підмножини числової прямої R.
Визначення 1. Випадковий процес зі значеннями в Х називається марковским, якщо для будь-яких
з Т і будь-яких борелевскіх множин
з R
Іншими словами, марковський процес це такий випадковий процес, у якого при фіксованому теперішньому майбутнє не залежить від минулого. Якщо Х = {i} звичайно або лічильно, то марковський процес називають ланцюгом Маркова. Якщо ймовірності
не залежать від s, а залежать від t, то ланцюг Маркова називається однорідною. Ланцюг Маркова з T = {0,1,2, ... } Називають ланцюгом з дискретним часом, ланцюг Маркова c
називають ланцюгом з безперервним часом.
Позначимо
називають ймовірностями переходу зі стану i в стан j за час t. Для ланцюга Маркова з дискретним часом позначають
і називають ймовірностями переходу з i в j за n кроків.
Ймовірностями переходу за 1 крок називають просто ймовірностями переходу. Набір ймовірностей
називають початковим розподілом ланцюга Маркова.
Визначення 2. Ланцюг Маркова називається ергодічеськой, якщо при
.
Якщо все , То ланцюг називається строго ергодічеськой.
Набір називається ергодичним розподілом,
називаються фінальними імовірностями.
Визначення 3. Розподіл ймовірностей називається стаціонарним розподілом, якщо
- Розподіл ймовірностей, тобто
і
для всіх
.
Визначення 4. Однорідна марківська ланцюг називається непріводімий, якщо для будь-яких двох станів i і j, існує
таке, що
.
Визначення 5. Однорідна марківська ланцюг називається ергодічеськой, якщо для будь-яких початкових розподілів абсолютне розподіл завжди сходяться до одного й того ж розподілу, яке є єдиним стаціонарним розподілом ланцюга:
для всіх
Теорема (Ергодична теорема Фостера).
Регулярна Марковська ланцюг з безперервним часом і рахунковим числом станів ергодичності, якщо вона непріводімий і система рівнянь
має нетривіальне рішення таке, що
При цьому існує єдине стаціонарне розподіл, який збігається з ергодичним.
1.2 Найпростіший потік
Якщо у рекурентного потоку
,
то такий потік називається найпростішим або пуассоновским потоком.
Визначення 1. Якщо проміжки часу між моментами надходження заявок незалежні і мають показовий розподіл з параметром l, то потік заявок називається найпростішим або пуассоновским з параметром l.
Для найпростішого потоку ймовірність надходження k заявок в проміжку часу [0, t) дорівнює:
(K = 0,1,2, ...) (1)
Визначення 2. Потік заявок називається стаціонарним, якщо для будь-яких попарно непересічних інтервалів часу ймовірність надходження до них відповідно
заявок залежить тільки від цих чисел і від довжин
і не залежить від їх розташування на тимчасовій осі.
Визначення 3. Потік заявок називається потоком без післядії, якщо ймовірність надходження k заявок протягом проміжку часу [T, T + t) не залежить від того, скільки вимог і яким чином надходило до моменту Т.
Визначення 4. Потік заявок називається ординарним, якщо для , Де
ймовірність надходження двох або більше заявок в проміжку
.
Визначення 5. Найпростішим потоком називається стаціонарний ординарний потік без післядії.
Визначення 6. Стаціонарний потік, для якого ймовірність надходження k заявок за час t дорівнює:
(K = 0,1,2, ...; l> 0),
називається найпростішим або пуассоновским потоком з параметром l.
В силу (1) середнє число заявок, що надходять за час t, дорівнює l t. Значить l - середнє число заявок, що надходять в одиницю часу. Тому l називають інтенсивністю пуассонівського потоку.
1.3 Час обслуговування
Розглянемо роботу обслуговуючого приладу (каналу, лінії). У загальному випадку тривалості обслуговування заявок являють собою невід'ємні величини.
припускають статистично незалежної від вступника на прилад потоку заявок.
Визначення 1. Кажуть, що обслуговування задано, якщо для будь-якого
Визначення 2. Обслуговування називається рекурентним, якщо
Визначення 3. Рекурентне обслуговування з
(Показовим) обслуговуванням з параметром m. Якщо
Т. е. час обслуговування будь-якої заявки невипадково (і одно b одиниць часу), то обслуговування називають детермінованим або регулярним.
1.4 Класифікація систем масового обслуговування
Класифікація систем масового обслуговування найчастіше роблять за такими ознаками:
вхідний потік заявок;
спільний розподіл часів обслуговування заявок;
число обслуговуючих приладів (каналів, ліній);
дисципліна обслуговування, організація черги та процесу обслуговування.
Існують наступні типи систем. У системах з втратами заявки, які при вступі не знаходять жодного вільного приладу, губляться. Для систем з очікуванням можливе очікування будь-якого числа вимог, які не можуть бути обслужені відразу. Для систем з обмеженим числом місць для очікування очікувати може тільки число заявок, менше деякого фіксованого числа N +1. Якщо заявка надходить у систему, застає чергу з N заявок, вона губиться для системи. Для заявок, що стоять в черзі до обслуговуючих приладів, за допомогою деякої дисципліни обслуговування визначається, в якому порядку очікують заявки вибираються з черги на обслуговування. Найважливішими дисциплінами обслуговування є:
FIFO (first in - first out) ¾ заявки обслуговуються в порядку надходження;
LIFO (last in - first out) ¾ інверсійний порядок обслуговування, при якому в першу чергу обслуговується заявка, що надійшла останньої;
SIRO (service in random order) ¾ чергова заявка вибирається навмання.
Для позначення простих процесів обслуговування використовуються позначення, запропоновані Кендалом:
А / B / n / N.
Буква А характеризує потік вимог: наприклад, А = М - пуассоновский потік. Буква B характеризує випадкові послідовності тривалостей обслуговування на окремих приладах: B = M - експоненціальне обслуговування (з однаковою інтенсивністю для різних приладів). Буква n означає кількість обслуговуючих приладів, буква N - кількість місць для очікування заявок в черзі.
1.5 Марківські системи масового обслуговування
До марковским систем відносяться системи, поведінка яких у момент часу t може бути описано марковским процесом . Зокрема, сюди відносяться всі системи виду M / M / n / N, де
. Дійсно, нехай
позначає число заявок в системі у момент t. Імовірнісний розподіл
після моменту t визначаються:
1) числом заявок в системі у момент t;
2) моментами надходження заявок після моменту t;
3) моментами закінчень обслуговування заявок після моменту t.
В силу того, що вхідний потік найпростіший, моменти надходження заявок після моменту t не залежать від передісторії системи до моменту t. Аналогічно, оскільки часи обслуговування показово розподілені, через "відсутність пам'яті" у показового розподілу моменти закінчення обслуговування заявок після моменту t не залежать від передісторії системи до моменту t. Тому ймовірнісна поведінку після моменту t залежить тільки від
і не залежить від поведінки
до моменту t. Значить
- Марковський процес з кінцевим або рахунковим числом станів. Тому для знаходження залежних від часу ймовірностей станів
слід вирішити систему рівнянь Колмогорова для безумовних ймовірностей. Якщо інтерес представляє стаціонарні ймовірності, то слід вирішити систему рівнянь рівноваги. Для отримання рівнянь Колмогорова використовується граничний перехід при D t ® ¥, який називається D t-методом.
1.6 Марківські мережі масового обслуговування
Мережа масового обслуговування являє собою сукупність систем масового обслуговування, в якій циркулюють заявки, що переходять з однієї системи в іншу. Припустимо, що мережа складається з n систем масового обслуговування (СМО) кожна з яких має необмежене число місць для очікування.
Під станом мережі в момент часу t будемо розуміти вектор:
де - Число заявок в i-ой СМО (на обслуговування і в черзі).
Мережі масового обслуговування поділяють на два типи: замкнуті та відкриті (розімкнуті). У замкнутій мережі обслуговування постійне число заявок , Тобто заявки не надходять ззовні і не йдуть з мережі. У відкриту мережу заявки надходять із зовнішніх джерел і після завершення обслуговування можуть залишати її.
Традиційний підхід в описі моделей мереж масового обслуговування залежить від ряду припущень з теорії стохастичних процесів, наприклад:
Переходи заявок між СМО мережі описуються непріводімий ланцюгом Маркова.
Заявки стохастически незалежні.
Існує стаціонарний режим, робота мережі може бути описана стаціонарним стохастичними процесами.
Часи обслуговування заявок в СМО мережі розподілені за показовим законом.
1.7 Знаходження стаціонарних ймовірностей станів відкритої марковської мережі масового обслуговування
Нехай включений у відкриту марковскую мережу масового обслуговування потік заявок описується чистим процесом розмноження з інтенсивністю l, причому в i-у систему масового обслуговування входить заявка надходить з імовірністю . Часи обслуговування заявок в i-тій системі масового обслуговування розподілені за показовим законом
, Що залежать від поточного числа заявок в i-тій системі
i = 1 ,..., n.
Дисципліни обслуговування заявок в системі мережі FIFO. Переходи заявок між системами, а також догляд заявки з мережі описується непріводімий ланцюгом Маркова. Заявка, що завершує обслуговування в системі , Переходить з імовірністю
в систему
,
є імовірність звільнення заявки з i-ої системи масового обслуговування мережі.
У цьому випадку багатовимірний процес N (t), що визначає стан мережі, є багатовимірним аналогом процесу розмноження і загибелі. Припустимо, що існує стаціонарний розподіл
,
приймає всі можливі значення. Тоді, аналогічно як і для одновимірного процесу розмноження і загибелі, можна показати, що стаціонарний розподіл єдино і задовольняє системі рівнянь рівноваги (балансу), яка являє собою систему лінійних різницевих рівнянь:
Для спрощення системи (1) введемо величини так, що
є повна інтенсивність надходження заявок в системи
. Інтенсивність
складається з інтенсивності потоку заявок, що надходять ззовні
, І інтенсивності надходження заявок в систему
від інших СМО, в тому числі і від самої системи
.
Тому (2).
З (2) отримаємо (3).
Співвідношення (2) іноді називають законом збереження потоку заявок. Воно говорить про те, що інтенсивність вхідного потоку заявок в i-ту СМО, i = 1 ,..., n, в стаціонарному режимі дорівнює інтенсивності вхідного потоку заявок з цієї системи.
Теорема1. (Джексона) Стаціонарне розподіл може бути знайдено у вигляді:
1.8 Знаходження рішення для немарковского випадку
Склавши і вирішивши систему диференційно-різницевих рівнянь, знайдеться вид функції розподілу
для випадкового процесу . Тоді можна знайти
і
.
Так що знаходження функцій
вирішить поставлену задачу.
2. Марківський випадок
2.1 Опис моделі
1
2.2 Мережа масового обслуговування
Дана відкрита марківська мережу масового обслуговування, що складається з трьох підсистем. Стан мережі в момент часу t визначається вектором
число заявок в i-ой підсистемі в момент часу t. Вхідний потік є пуассонівської потоком з параметром . Часи обслуговування заявок в i-ой системі масового обслуговування розподілені за показовим законом з параметром
, Що залежать від поточного числа заявок в i-ой системі, i = 1,2,3.
Заявки надходять із загального потоку заявок у другій вузол і перший вузол з імовірностями і
відповідно. Після обслуговування в другому вузлі заявки надходять на третій вузол. А після обслуговування на першому вузлі заявки надходять з імовірністю
в третій вузол або з імовірністю
в перший вузол, або з імовірністю
в третій вузол. Після обслуговування на 3 сайті заявки йдуть із системи.
2.3 Рівняння рівноваги
Припустимо, що існує стаціонарний розподіл . Складемо рівняння рівноваги.
P
P
+
P
+
+ P
+
P
+
+ P
+
P
+
+ P
2.4 Знаходження стаціонарних ймовірностей
Для того, щоб знайти рішення рівняння рівноваги , Скористаємося теоремою 1 з 1.7 з якої одержимо, що
,
-Ймовірність надходження заявок в i-у підсистему.
Таким чином, нам необхідно знайти . Для цього скористаємося співвідношенням (3) з 1.7
Із системи одержимо
де
-Ймовірності переходу
Матриця переходу має вигляд:
Тоді, отримаємо
де Io - нульовий вектор.
Отже, стаціонарний розподіл знайдено з точністю до постійного множника P (Io).
2.5 Умови ергодичності
Для дослідження ергодичності застосуємо ергодічеськой теорему Фостера (теорема 1 з 1.1)
Теорема (Ергодична теорема Фостера).
Регулярна Марковська ланцюг з безперервним часом і рахунковим числом станів ергодичності, якщо вона непріводімий і система рівнянь
має нетривіальне рішення таке, що
При цьому існує єдине стаціонарне розподіл, який збігається з ергодичним.
Розглянемо умови цієї теореми.
Регулярність випливає з того, що . Неприводимого випливає з того, що всі стани сполучаються з нульовим, тобто в будь-який стан
можна перейти з нульового (0,0,0) шляхом надходження, переходу, обслуговування заявок.
Як нетривіального рішення системи рівнянь з теореми Фостера візьмемо . Тоді для ергодичності потрібно, щоб
Тоді отримаємо,
Умова (1) і є шукане умова ергодичності. Якщо ця умова буде виконуватися, то буде існувати єдиний стаціонарний розподіл, що збігається з ергодичним.
3. Немарковского випадок
3.1 Опис моделі
Дана модель відкритої мережі масового обслуговування, точно така як Марківському випадку Тільки передбачається, що тривалість обслуговування окремого вимоги розподілена по довільному закону. Нехай - Вироб. функція розподілу часу обслуговування
-Той заявки в
-Тому вузлі, при цьому припускаємо, що виконується таку вимогу:
.
Стан мережі в момент часу t визначається вектором
, Де
- Залишкове час обслуговування заявки, першої підсистемою, що стоїть в
-Ій позиції.
- Залишкове час обслуговування заявки, другий підсистемою, що стоїть в
-Ій позиції.
залишкове час обслуговування заявки, третьої підсистемою, що стоїть в
-Ій позиції.
Система LCFS PR.
Заявка, що надходить в -Ий вузол, витісняє заявку з приладу і починає обслуговуватися. Відтіснила заявка йде в початок черги.
-
НЕ Марковський процес.
Розглядається наступний процес
- Залишкове час обслуговування заявки, першої підсистемою, що стоїть в
-Ій позиції.
3.2 Складання диференційно-різницевих рівнянь
Розглядаємо випадковий процес
Де h-певний досить малий проміжок часу.
Тоді ймовірність події А буде дорівнює сумі наступних ймовірностей:
1. Якщо в проміжку часу h в систему не прийшло жодної вимоги і ні на одному приладі обслуговування не закінчилося, то:
2. Якщо в проміжку часу h перший підсистема обслужила одну заявку, і відбувся перехід заявки на третю підсистему з ймовірністю , То:
3. Якщо в проміжку часу h Друга підсистема обслужила одну заявку, то:
4. Якщо в проміжку часу h третій підсистема обслужила одну заявку і стався вихід заявки з системи з імовірністю 1, то:
5. Якщо в проміжку часу h на першу підсистему надійшла одна заявка з інтенсивністю , То:
6. Якщо в проміжку часу h на другу підсистему надійшла одна заявка з інтенсивністю , То:
7. Якщо в проміжку часу h перший підсистема обслужила одну заявку і відбувся перехід заявки на другу підсистему з ймовірністю , То:
8. Якщо в проміжку часу h перший підсистема обслужила одну заявку і відбувся перехід заявки на першу підсистему з ймовірністю , То:
Тоді ймовірність події А буде дорівнювати сумі даних восьми доданків.
Перейдемо до функції розподілу і складемо систему диференційно-різницевих рівнянь
(Будемо використовувати розкладання функції розподілу в ряд Тейлора)
Скоротивши однакові складові, розділимо обидві частини рівняння на h і спрямував h до нуля. В результаті перетворень ми отримаємо таку систему.
3.3 Пошук рішення диференційно-різницевих рівнянь
Тоді безпосередній підстановкою можемо переконатися, що рішенням даного рівняння буде.
Наводячи подібні доданки отримали, що F-дійсно рішення цього рівняння. І таким чином
Список літератури
Гнеденко Б.В., Коваленко І.М. Введення в теорію масового обслуговування. М.: Наука, 1966. - 431с.
Ширяєв А.Н. Ймовірність. - М.: Наука, 1980. - 575с.
Бурик А.Д., Малінковскій Ю.В., Маталицкій М.А. Теорія масового обслуговування: Навчальний посібник зі спецкурсу. - Гродно, 1984. - 108с. (ГрГу).
Феллер В. Введення в теорію вірогідності і її застосування: у 2-х т. М.: Мир, 1967, - т.1,-498с.
Кеніг Д., Штоян Д. Методи теорії масового обслуговування. - М.: Радіо і зв'язок, 1981. - 127с.