Реферат: Модели систем массового обслуживания. Классификация систем массового обслуживания - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Модели систем массового обслуживания. Классификация систем массового обслуживания

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 138 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ кафедра сетей и устройств телекоммуникаций РЕФЕРАТ На тему: «Модели систем массового обслуживания. Классификация систем массового обслуживания» МИНСК, 2008 Математическое введение в теорию цепей Маркова. ( Markov ’ s chain ) Дискретные цепи Маркова . Будем говорить, что задана дискретная цепь Маркова, если для последовательн о сти случайных величин выполняется равенство . Это означает, что поток случайных величин определяется только вероятностью перехода от предыдущего значения случайной величины к последующему. Зная н а чальное распределение вероятностей, можно найти распределение на любом шаге. Величины i n можно интерпретировать как номера состояний некоторой динамической системы с дискретным множеством состояний (типа конечного автомата). Если вер о ятности переходов не зависят от номера шага, то такая цепь Маркова называется о д нородной и ее определение задается набором вероятностей . Для однородной Марковской цепи можно определить вероятности перехода из с о стояния i в состояние j за m шагов Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния. Состояние i называется поглощающим, е с ли для него p ii =1. Состояние называется возвратным , если вероятность попадания в него за коне ч ное число шагов равна единице. В другом случае состояние относится к невозвра т ным. Возвратное состояние может быть периодическим и апериодическим в зав и симости от наличия кратных шагов возврата. Введем вероятности возврата в состояние i через n шагов после ухода из этого с о стояния: Они позволяют определить среднее число шагов или, иначе говоря, среднее вр е мя возврата: . Состояние называется возвратным нулевым , если среднее время возвращения в него равно бесконечности, и возвратным ненулевым , если это время конечно. И з вестны две важные теоремы: Теорема 1. Состояния неприводимой цепи Маркова либо все невозвратные, либо все возвра т ные нулевые, либо все возвратные ненулевые. В случае периодической цепи все с о стояния имеют один и тот же период. Вторая теорема рассматривает вероятности достижения состояний в стационарном (то есть не зависящем от начального распределения вероятностей) режиме. Соотве т ствующее распределение вероятностей также называют стационарным. Нахождение стационарного распределения вероятностей достижения состояний одна из основных з а дач теории телетрафика. Теорема 2. Для неприводимой и апериодической цепи Маркова всегда существуют предел ь ные вероятности, не зависящие от начального распределения вероятностей. Более того, имеет место одна из следующих двух возможн о стей: А) все состояния цепи невозвратные или все возвратные нулевые, и тогда все предельные вероятности равны нулю и стационарного состо я ния не существует; Б) все состояния возвратные ненулевые и тогда существует стационарное распр е деление вероятностей: Состояние называется эргодическим , если оно апериодично и возвратно ненул е вое. Если все состояния цепи Маркова эргодичны , то вся цепь называется эргодич е ской . Предельные вероятности эргодической цепи Маркова называют вероятностями состояния равновесия, имея в виду, что зависимость от начального распределения вероятностей полн о стью отсутствует. Цепь Маркова с конечным числом состояний (конечная цепь), удобно изображать в виде ориентированного графа, называемого диаграммой переходов. Вершины гр а фа ассоциируются с состояниями, а ребра с вероятностями перех о дов. Вычисления вероятностей достижения состояний производится прямыми мет о дами или с помощью z-преобразования. Цепь Маркова. Введем матрицу вероятностей переходов и вектор-строку вероятностей на ш а ге n . Распределение вероятностей на произвольном шаге тогда будет подчиняться ма т ричному соотношению: . Оно позволяет рекуррентно вычислять все вероятности состояний. Для нахождения предельного распределения (стационарного) нужно решить ура в нение: Его можно решать как систему линейных алгебраических уравнений, если цепь коне ч на. Для примера (рис. 1) имеем: . и решение матричного уравнения сводится к решению системы трёх уравнений: Коэффициенты первого уравнения в этой системе дополняют до единицы сумму коэффициентов второго и третьего уравнений; это свидетельствует о линейной зав и симости между ними. Поэтому для решения системы уравнений нужно ввести дополн и тельное нормирующее условие. В данном примере: . Решая систему полученных уравнений, им е ем: Уравнение для вероятности достижения состояния в переходном режиме решить значительно труднее. Некоторого упрощения можно достигнуть, используя z – пр е образование. Применим его к уравнению для переходных вероя т ностей . Обозначая соответствующие преобразов а ния, получим: Все полученные здесь математические результаты относились к однородным Марковским процессам, где вероятности переходов не зависят от времени. В более общем случае такая зависимость имеет место. Рассмотрим вероятности перехода системы из состояния i на m-том шаге в с о стояние j на n-том шаге для n > m. Можно показать, что эти вероятности связаны между собой, так называемым уравнениями Чепмена-Колмогорова .( Chapman - Kolmogorov ) . Для однородных цепей Маркова эти уравн е ния упрощаются так как . И сводятся к анализируемым выше. Непрерывные цепи Маркова. Случайный процесс X(t) с дискретным множеством значений образует непр е рывную цепь Маркова, если . Будущие состояния зависят от прошлого только через текущее состояние. Для н е прерывный цепей Маркова основным также является уравнение Чепмена – Колмогорова, для одн о родной цепи имеющее вид: . Здесь матрица H (t) = [ p ij (t)] - матрица вероятностей перехода из состояния i в с о стояние j в момент времени t , а матрица Q называется матрицей интенсивностей п е реходов. Ее элементы имеют следующий смысл: если в момент времени t система находилась в состоянии E i , то вероятность перехода в течение промежутка времени (t,t+ Дt) в произвольное состояние E j задается величиной q ij (t)Дt + o(Дt), а вероятность ухода из состо я ния E i величиной -q ii Дt + o(Дt). Таким образом, интенсивности переходов можно вычислять как соответствующие пределы при стремлении к нулю длительности временного и н тервала. Наиболее важным для дальнейшего использования является класс непрерывных цепей Маркова называемых «процессами гибели - размножения» ( Birth – death process ). Для таких систем из состояния k возможны переходы только в состояния k, k-1 и k+1 в следующие моменты времени: · в момент t объем популяции был равен k и в течение времени (t,t+ Дt) не пр о изошло изменения состояния · в момент t объем популяции был равен k-1 и в течение времени (t,t+ Дt) родился один член популяции · в момент времени t объем популяции был равен k+1 и в течение времени (t,t+ Дt) погиб один член популяции Рис. 1. Возможные переходы в состояние Ек. Будем искать вероятность того, что в момент времени t объем популяции равен k , обозначив его P k (t). Можно записать соотношения для вероятности достижения со стояния k в момент времени t+ Дt: . Определим граничные и нормирующие у с ловия: Выразим вероятности переходов за инте р вал Дt через интенсивности Вер(+1)= л k Дt+o(Дt) ; Вер(-1)= м k Дt+o(Дt). Вероятность нуля рождений 1- л k Дt+o(Дt) , а нуля гибелей 1- м k Дt+o(Дt). Таким образом, вероятность того, что состояние k сохранится неизменным, б у дет равно произведению [1- л k Дt+o(Дt)][ 1- м k Дt+o(Дt)]. Тогда уравнения Чепмена-Колмогорова приобретают вид Раскрывая скобки и проводя деление на Дt, получим: В пределе получается система дифференциально-разностных уравнений, реш е ние которой будут играть важную роль для практических задач. В соответствие этой системе уравнений можно поставить наглядную диагра м му интенсивностей переходов, которая аналогична диаграмме переходов для ди с кретных цепей Маркова (Рис. 2) Рис. 2 Диаграмма интенсивностей переходов для процесса размножения и г и бели. Овалам здесь соответствуют дискретные состояния, а стрелки определяют и н тенсивности потоков вероятности ( а не вероятности !) переходов от одного с о стояния к другому. Имеет место своеобразный « закон сохранения »: Разность между суммой интенсивностей, с которой система попадает в состо я ние k и суммой интенсивностей, с которой система покидает это состояние дол ж на равняться интенсивности изменения потока в это состояние (производной по вр е мени). Применение закона сохранения позволяет получать уравнения для любой по д системы Марковской цепи типа процесса «гибели-размножения». Особенно э ф фективным оказывается построение решений в стационарном, установившемся режиме, когда можно полагать что вероятности в произвольный, достаточно отд а ленный момент времени, остаются постоянными. Приравнивая производную по времени нулю, получаем систему разностных уравнений Полагая, что интенсивности л -1 =л -2 = л -3 =…0; м 0 = м -1 = м -2 = м -3 =…=0, второе уравнение выписывать отдельно далее не потребуется. Итак, стационарный режим в цепи Маркова будет описываться системой разностных уравнений и условием нормировки для вероятностей Нетрудно видеть, что эти уравнения легко выводятся из закона сохранения и н тенсивностей вероятностей. В стационарном режиме разность потоков равна нулю и полученные выше уравнения приобретают смысл уравнений равновесия или бала н са, как их и называют. . Интенсивность потока вероятностей в состояние k равна интенсивности п о тока из этого состояния. Решать уравнение баланса можно, сначала определив при k =0 значение . Затем, построив систему уравнений для k =1, можно получить . Далее получаем Из условия нормировки: . Система, описываемая полученными выше выражениями, будет иметь стаци о нарные вероятности состояний, когда она эргодическая. Это условие может быть выражено через соотношение интенсивностей. Необходимо и достаточно, чтобы существовало некоторое значение k , начиная с которого выполнялось неравенс т во . Для большинства реальных систем массового обслуживания это неравенство выполняется. Классификация систем массового обслуживания. Используется трех -, четырех -, шести – компонентное символическое обозн а чение системы массового обслуживания, предложенное Кендаллом ( Candall ) и развитое в работах Г.П.Барашина. a / b / c : d / e / f a – распределение поступающего потока запросов. b – закон распределения времени обслуживания. Типовые условные обозначения: М – экспоненциальное (Марковское) распределение, D – детерминированное распределение, E k – эрланговское распределение k -го порядка, HM k – гиперэкспоненциальное, HE k – гиперэрланговское распределение порядка k , GI – произвольное распределение независимых промежутков между заявками, G – произвольное распределение длительностей обсл у живания. c – структура системы обслуживания (обычно число серверов). d – дисциплина обслуживания (параметры после двоеточия иногда опускают). Обычно используется сокращенное символическое обозначение, например FF вместо FIFO , LF , PR и т.п. e – максимальное число запросов, воспринимаемое системой, может употре б ляться символ . f – максимальное число запросов к системе обслуживания. В некоторых публикациях последними символами отражают качественные х а рактеристики системы обслуживания. Некоторые общие результаты и основы м а тематического аппарата, необходимого для анализа можно получить, рассматр и вая системы G / G / m . Формула Литтла ( Little ). Рассмотрим временную диаграмму работы системы массового обслуживания (рис. 3), отразив на ней последовательность поступления требований, помещение требований в оч е редь и обработки серверами системы. Временная диаграмма работы системы массового обслужив а ния. В общем случае ясно, что с увеличением числа требований растет время ож и дания. Установим соотношение между средним числом требований в системе, и н тенсивностью потока и среднего времени пребывания в системе. Обозначим число поступающих в промежутке времени (0 , t ) требований как функцию времени б ( t ). Число исходящих из системы заявок (обслуженных) на этом интервале обозначим д(t). На рисунке 4 показаны примеры функциональных зависимостей этих двух сл у чайных процессов от времени. Рис. 4 Зависимость между средним числом требований в системе, интенсивностью потока и средним времени пребывания в системе. Число требований, н а ходящихся в системе в момент t будет равно: . Площадь между двумя рассматриваемыми кривыми от 0 до t - дает общее время, проведенное всеми заявками в системе за время t. Обозначим эту накопленную величину г(t) . Если интенсивность входного потока равна л, а средняя интенсивность за время t: ,то время, проведенное одной заявкой в системе, усредненное по всем заявкам б у дет равно: . Наконец, определим среднее число требований в системе в промежутке (0,t): . Из последних трех уравнений следует, что: , (где ). Если в СМО существует стационарный режим, то при t
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Отец обращается к сыну, вступающему в переходный возраст:
- Сынок, пришло время поговорить о твоем будущем: кем ты хочешь стать, когда выпьешь?
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Модели систем массового обслуживания. Классификация систем массового обслуживания", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru