![]() |
|||||||||||||||
Главная Рефераты по коммуникации и связи Рефераты по косметологии Рефераты по криминалистике Рефераты по криминологии Рефераты по науке и технике Рефераты по кулинарии Рефераты по культурологии Рефераты по зарубежной литературе Рефераты по логике Рефераты по логистике Рефераты по маркетингу Рефераты по международному публичному праву Рефераты по международному частному праву Рефераты по международным отношениям Рефераты по культуре и искусству Рефераты по менеджменту Рефераты по металлургии Рефераты по налогообложению Рефераты по оккультизму и уфологии Рефераты по педагогике Рефераты по политологии Рефераты по праву Биографии Рефераты по предпринимательству Рефераты по психологии Рефераты по радиоэлектронике Рефераты по риторике Рефераты по социологии Рефераты по статистике Рефераты по страхованию Рефераты по строительству Рефераты по схемотехнике Рефераты по таможенной системе Сочинения по литературе и русскому языку Рефераты по теории государства и права Рефераты по теории организации Рефераты по теплотехнике Рефераты по технологии Рефераты по товароведению Рефераты по транспорту Рефераты по трудовому праву Рефераты по туризму Рефераты по уголовному праву и процессу Рефераты по управлению |
Курсовая работа: Инвариантность стационарного распределения трехузловой сети массового обслуживанияКурсовая работа: Инвариантность стационарного распределения трехузловой сети массового обслуживанияМИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Учреждение образования “Гомельский Государственный университет имени Франциска Скорины" Математический факультет Кафедра математического анализа
Курсовая работа Инвариантность стационарного распределения трехузловой сети массового обслуживания Исполнитель Студентка группы М-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. Случайный процесс Другими словами, марковский процесс это такой случайный процесс, у которого при фиксированном настоящем будущее не зависит от прошлого. Если Х={i} конечно или счётно, то марковский процесс называют цепью Маркова. Если вероятности
не зависят от s, а зависят от t, то цепь Маркова называется однородной. Цепь Маркова с T={0,1,2,... } называют цепью с дискретным временем, цепь Маркова c
называют цепью с непрерывным временем. Обозначим
Вероятностями перехода за 1 шаг Определение 2. Цепь Маркова называется эргодической, если при
Если все Набор Определение 3. Распределение вероятностей
Определение 4. Однородная марковская цепь называется
неприводимой, если для любых двух состояний i и j, Определение 5. Однородная марковская цепь называется
эргодической, если для любых начальных распределений абсолютное распределение
Теорема (Эргодическая теорема Фостера). Регулярная Марковская цепь с непрерывным временем и счетным числом состояний эргодична, если она неприводима и система уравнений
имеет нетривиальное решение При этом существует единственное стационарное распределение, которое совпадает с эргодическим. 1.2 Простейший потокЕсли у рекуррентного потока
то такой поток называется простейшим или пуассоновским потоком. Определение 1. Если промежутки времени между моментами поступления заявок независимы и имеют показательное распределение с параметром l, то поток заявок называется простейшим или пуассоновским с параметром l. Для простейшего потока вероятность поступления k заявок в промежутке времени [0,t) равна:
Определение 2. Поток
заявок называется стационарным, если для любых попарно непересекающихся
интервалов времени Определение 3. Поток заявок называется потоком без последействия, если вероятность поступления k заявок в течение промежутка времени [T,T+t) не зависит от того, сколько требований и каким образом поступало до момента Т. Определение 4. Поток
заявок называется ординарным, если для Определение 5. Простейшим потоком называется стационарный ординарный поток без последействия. Определение 6. Стационарный поток, для которого вероятность поступления k заявок за время t равна:
называется простейшим или пуассоновским потоком с параметром l. В силу (1) среднее число заявок, поступающих за время t, равно lt. Значит l - среднее число заявок, поступающих в единицу времени. Поэтому l называют интенсивностью пуассоновского потока. 1.3 Время обслуживанияРассмотрим работу обслуживающего прибора (канала, линии). В
общем случае длительности обслуживания заявок представляют из себя
неотрицательные величины.
Определение 1. Говорят, что обслуживание задано, если для любого
Определение 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 может быть описано марковским процессом 1) числом заявок в системе в момент t; 2) моментами поступления заявок после момента t; 3) моментами окончаний обслуживания заявок после момента t. В силу того, что входной поток простейший, моменты поступления
заявок после момента t не зависят от предыстории
системы до момента t. Аналогично, поскольку
времена обслуживания показательно распределены, из-за “отсутствия памяти” у
показательного распределения моменты окончания обслуживания заявок после момента
t не зависят от предыстории системы до момента t. Поэтому вероятностное поведение 1.6 Марковские сети массового обслуживанияСеть массового обслуживания представляет собой совокупность
систем массового обслуживания, в которой циркулируют заявки, переходящие из
одной системы в другую. Предположим, что сеть состоит из n
систем массового обслуживания (СМО) Под состоянием сети в момент времени t будем понимать вектор:
где Сети массового обслуживания разделяют на два типа: замкнутые
и открытые (разомкнутые). В замкнутой сети обслуживания постоянное число заявок
Традиционный подход в описании моделей сетей массового обслуживания зависит от ряда предположений из теории стохастических процессов, например: Переходы заявок между СМО сети описываются неприводимой цепью Маркова. Заявки стохастически независимы. Существует стационарный режим, работа сети может быть описана стационарным стохастическими процессами. Времена обслуживания заявок в СМО сети распределены по показательному закону. 1.7 Нахождение стационарных вероятностей состояний открытой марковской сети массового обслуживанияПусть входящий в открытую марковскую сеть массового
обслуживания поток заявок описывается чистым процессом размножения с
интенсивностью , причем в i-ую систему
массового обслуживания входящая заявка поступает с вероятностью Дисциплины обслуживания заявок в системе сети FIFO. Переходы
заявок между системами, а также уход заявки из сети описывается неприводимой
цепью Маркова. Заявка, завершающая обслуживание в системе В этом случае многомерный процесс N (t), определяющий состояние сети, является многомерным аналогом процесса размножения и гибели. Предположим, что существует стационарное распределение
принимает все возможные значения. Тогда, аналогично как и для одномерного процесса размножения и гибели, можно показать, что стационарное распределение единственно и удовлетворяет системе уравнений равновесия (баланса), которая представляет собой систему линейных разностных уравнений:
Для упрощения системы (1) введем величины Поэтому Из (2) получим Соотношение (2) иногда называют законом сохранения потока заявок. Оно говорит о том, что интенсивность входящего потока заявок в i-тую СМО, i=1,...,n, в стационарном режиме равна интенсивности входящего потока заявок из этой системы. Теорема1. (Джексона) Стационарное распределение может быть найдено в виде: 1.8 Нахождение решения для немарковского случаяСоставив и решив систему дифференциально-разностных уравнений, найдется вид функции распределения
для случайного процесса Так что нахождение функций
решит поставленную задачу. 2. Марковский случай2.1 Описание модели
2.2 Сеть массового обслуживанияДана открытая марковская сеть массового обслуживания, состоящая из трех подсистем. Состояние сети в момент времени t определяется вектором
число заявок в i-ой
подсистеме в момент времени t. Входящий поток является
пуассоновским потоком с параметром Заявки поступают из общего потока заявок во второй узел и
первый узел с вероятностями 2.3 Уравнения равновесияПредположим, что существует стационарное распределение P
+ + + 2.4 Нахождение стационарных вероятностейДля того, чтобы найти решение уравнения равновесия
Таким образом, нам необходимо найти Из системы
Матрица перехода имеет вид: Тогда, получим где Io - нулевой вектор. Итак, стационарное распределение найдено с точностью до постоянного множителя P (Io). 2.5 Условия эргодичностиДля исследования эргодичности применим эргодическую теорему Фостера (теорема 1 из 1.1) Теорема (Эргодическая теорема Фостера). Регулярная Марковская цепь с непрерывным временем и счетным числом состояний эргодична, если она неприводима и система уравнений
имеет нетривиальное решение При этом существует единственное стационарное распределение, которое совпадает с эргодическим. Рассмотрим условия этой теоремы. Регулярность следует из того, что В качестве нетривиального решения системы уравнений из
теоремы Фостера возьмем Тогда получим, Условие (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-действительно решение этого уравнения. И таким образом Список литературы1. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966. - 431с. 2. Ширяев А.Н. Вероятность. - М.: Наука, 1980. - 575с. 3. Буриков А.Д., Малинковский Ю.В., Маталыцкий М.А. Теория массового обслуживания: Учебное пособие по спецкурсу. - Гродно, 1984. - 108с. (ГрГу). 4. Феллер В. Введение в теорию вероятностей и её приложения: в 2-х т. М.: Мир, 1967, - т.1,-498с. 5. Кениг Д., Штоян Д. Методы теории массового обслуживания. - М.: Радио и связь, 1981. - 127с. |
||||||||||||||
|