Зміст
3
1 Марківські ланцюги з кінцевим числом станів і дискретним часом 4
2 Марківські ланцюги з кінцевим числом станів і безперервним часом 8
3 Процеси народження і загибелі .......................................... .......................... 11
4 Основні поняття і класифікація систем масового обслуговування ... 14
5 Основні типи відкритих систем масового обслуговування .................... 20
5.1 Одноканальна система масового обслуговування з відмовами .............. 20
5.2 Багатоканальна система масового обслуговування з відмовами ........... 21
5.3 Одноканальна система масового обслуговування з обмеженою довжиною 23
5.4 Одноканальна система масового обслуговування з необмеженою чергою 26
5.5 Багатоканальна система масового обслуговування з обмеженою чергою 27
5.6 Багатоканальна система масового обслуговування з необмеженою чергою 30
5.7 Багатоканальна система масового обслуговування з обмеженою чергою і обмеженим часом очікування в черзі ............................................. 32
6 Метод 36
6.1 Основна ідея методу ........................................... .................................. 36
6.2 Розігрування неперервної випадкової величини ................................ 36
6.3 Випадкова величина з експонентним розподілом ................. 38
7 Дослідження системи масового обслуговування ..................................... 40
7.1 Перевірка гіпотези про показовому розподілі ............................ 40
7.2 Розрахунок основних показників системи масового обслуговування ........ 45
7.3 Висновки про роботу досліджуваної СМО ................................................ ..... 50
8 Дослідження видозміненій СМО ................................................ ........ 51
53
Список використаних джерел ................................................. ........... 54
Введення Темою моєї дипломної роботи є дослідження системи масового обслуговування. У своєму первісному стані розглянута мною СМО являє собою один з класичних випадків, а конкретно M/M/2/5 за прийнятим позначенню Кендалла. Після дослідження системи були зроблені висновки про неефективність її роботи. Були запропоновані методи оптимізації роботи СМО, але з цими змінами система перестає бути класичною. Основна проблема при дослідженні систем масового обслуговування полягає в тому, що в реальності вони можуть бути досліджені з використанням класичної теорії масового обслуговування тільки в рідкісних випадках. Потоки вхідних і вихідних заявок можуть виявитися не найпростішими, отже, знаходження граничних ймовірностей станів з використанням системи диференціальних рівнянь Колмогорова неможливо, в системі можуть бути присутніми пріоритетні класи, тоді розрахунок основних показників СМО також неможливий.
Для оптимізації роботи СМО була введена система з двох пріоритетних класів і збільшено число обслуговуючих каналів. У такому випадку доцільно застосувати методи імітаційного моделювання, наприклад метод Монте-Карло. Основна ідея методу полягає в тому, що замість невідомої випадкової величини приймається її математичне сподівання у досить великої серії випробувань. Виробляється розігрування випадкової величини (в даному випадку це інтенсивності вхідного і вихідного потоків) спочатку рівномірно розподіленим. Потім здійснюється перехід від рівномірного розподілу до показовому розподілу, допомогою формул переходу. Була написана програма на мові Visual Basic, що реалізує цей метод.
1 Марківські ланцюги з кінцевим числом станів і дискретним часом Нехай деяка система S може знаходитися в одному з станів кінцевого (Або рахункового) безлічі можливих станів S 1 , S 2 , ..., S n , а перехід з одного стану в інший можливий тільки в певні дискретні моменти часу t 1 , t 2 , t 3 , звані кроками.
Якщо система переходить з одного стану в інший випадково, то говорять, що має місце випадковий процес з дискретним часом.
Випадковий процес називається марковским, якщо ймовірність переходу з будь-якого стану S i в будь-який стан S j не залежить від того, як і коли система S потрапила в стан S i (тобто в системі S відсутня наслідок). У такому випадку говорять, що функціонування системи S описується дискретною ланцюгом Маркова.
Переходи системи S в різні стани зручно зображувати за допомогою графа станів (рис. 1).
Рисунок 1 - Приклад розміченого графа станів
Вершини графа S 1 , S 2 , S 3 позначають можливі стану системи. Стрілка, спрямована з вершини S i в вершину S j позначає перехід; число, що стоїть поруч зі стрілкою, позначає величину ймовірності цього переходу. Стрілка, замикається на i-тій вершині графа, позначає, що система залишається в стані S i з імовірністю, що стоїть біля стрілки.
Графу системи, що містить n вершин, можна поставити у відповідність матрицю NxN, елементами якої є ймовірності переходів p ij між вершинами графа. Наприклад, граф на рис. 1 описується матрицею P:
званої матрицею ймовірностей переходів. Елементи матриці p ij задовольняють умовам:
(1)
(2)
Елементи матриці p ij - дають ймовірності переходів в системі за один крок. Перехід
S i - S j за два кроки можна розглядати як відбувається на першому кроці з S i в деякий проміжний стан S k і на другому кроці з S k в S i . Таким чином, для елементів матриці ймовірностей переходів з S i в S j за два кроки отримаємо:
У загальному випадку переходу за m кроків для елементів матриці ймовірностей переходів справедлива формула:
(3)
Одержимо два еквівалентних вирази для:
Нехай система S описується матрицею ймовірностей переходів Р:
Якщо позначити через Р (m) матрицю, елементами якої є рi ймовірності переходів з S i в S j за m кроків, то справедлива формула
,
де матриця Р m виходить множенням матриці P саму на себе m раз.
Вихідний стан системи характеризується вектором стану системи Q (q i ) (званим також стохастичним вектором).
де q j - ймовірність того, що вихідним станом системи є S j стан. Аналогічно (1) і (2) справедливі співвідношення
Позначимо через
вектор стану системи після m кроків, де q j - ймовірність того, що після m кроків система знаходиться в S i стані. Тоді справедлива формула
Якщо ймовірності переходів P ij залишаються постійними, то такі марківські ланцюги називаються стаціонарними. В іншому випадку марковська ланцюг називається нестаціонарної.
2. Марківські ланцюги з кінцевим числом станів і безперервним часом
Якщо система S може переходити в інший стан випадковим чином в довільний момент часу, то говорять про випадковому процесі з безупинним часом. У відсутності післядії такий процес називається безперервної марковської ланцюгом. При цьому ймовірності переходів для будь-яких i і j в будь-який момент часу дорівнюють нулю (в силу безперервності часу). З цієї причини замість ймовірності переходу вводиться величина - щільність ймовірності переходу зі стану в стан, що визначається як межа:
Якщо величини не залежать від t, то марковський процес називається однор...
