Курсовая работа
Инвариантность стационарного распределения трехузловой сети массового обслуживания
Исполнитель
Студентка группы М-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; (заявка, поступающая в -ый узел, вытесняет заявку с прибора и начинает обслуживаться, вытесненная заявка идет в начало очереди).
В курсовой работе для открытой марковской сети массового обслуживания составим уравнения равновесия, найдем стационарные вероятности, установим условия эргодичности. Для не марковского случая составим дифференциально-разностное уравнение в частных производных для процесса, дополненного остаточными временами, найдем решение данного уравнения. Сравним марковский и немарковский случай. Сделаем вывод.
Теоретические сведения
Марковские процессы
Пусть Т и Х - некоторые подмножества числовой прямой 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. Если промежутки времени между моментами поступления заявок независимы и имеют показательное распределение с параметром 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. Говорят, что обслуживание задано, если для любого
Определение 2. Обслуживание называется рекуррентным, если 
Определение 3. Рекуррентное обслуживание с
(показательным) обслуживанием с параметром m. Если
Т. е. время обслуживания любой заявки неслучайно (и равно b единиц времени), то обслуживание называют детерминированным или регулярным.
Марковский случай
Описание модели
1
Сеть массового обслуживания
Дана открытая марковская сеть массового обслуживания, состоящая из трех подсистем. Состояние сети в момент времени t определяется вектором
число заявок в i-ой подсистеме в момент времени t. Входящий поток является пуассоновским потоком с параметром 
. Времена обслуживания заявок в i-ой системе массового обслуживания распределены по показательному закону с параметром 
, зависящим от текущего числа заявок в i-ой системе, i=1,2,3.
Заявки поступают из общего потока заявок во второй узел и первый узел с вероятностями и 
соответственно. После обслуживания во втором узле заявки поступают на третий узел. А после обслуживания на первом узле заявки поступают с вероятностью 
в третий узел либо с вероятностью 
в первый узел, либо с вероятностью в третий узел. После обслуживания на 3 узле заявки уходят из системы.
Уравнения равновесия
Предположим, что существует стационарное распределение 
. Составим уравнение равновесия.
P 
P 
+ 
P 
+
+ 
P 
+ 
P 
+
+ 
P 
+ 
P 
+
+ 
P 
Условия эргодичности
Для исследования эргодичности применим эргодическую теорему Фостера (теорема 1 из 1.1)
Теорема (Эргодическая теорема Фостера).
Регулярная Марковская цепь с непрерывным временем и счетным числом состояний эргодична, если она неприводима и система уравнений
имеет нетривиальное решение 
такое, что 
При этом существует единственное стационарное распределение, которое совпадает с эргодическим.
Рассмотрим условия этой теоремы.
Регулярность следует из того, что 
. Неприводимость следует из того, что все состояния сообщаются с нулевым, то есть в любое состояние 
можно перейти из нулевого (0,0,0) путем поступления, перехода, обслуживания заявок.
В качестве нетривиального решения системы уравнений из теоремы Фостера возьмем 
. Тогда для эргодичности потребуется, чтобы
Тогда получим,
Условие (1) и есть искомое условие эргодичности. Если это условие будет выполнятся, то будет существовать единственное стационарное распределение, совпадающее с эргодическим.
Немарковский случай
Описание модели
Дана модель открытой сети массового обслуживания, точно такая как марковском случае Только предполагается, что длительность обслуживания отдельного требования распределена по произвольному закону. Пусть 
- произ. функция распределения времени обслуживания 
-той заявки в 
-том узле, при этом предполагаем, что выполняется следующее требование:
.
Состояние сети в момент времени t определяется вектором
, где
- остаточное время обслуживания заявки, первой подсистемой, стоящей в 
-ой позиции.
- остаточное время обслуживания заявки, второй подсистемой, стоящей в -ой позиции.
остаточное время обслуживания заявки, третьей подсистемой, стоящей в 
-ой позиции.
| |||
 | |||
Система LCFS PR.
Заявка, поступающая в 
-ый узел, вытесняет заявку с прибора и начинает обслуживаться. Вытесненная заявка идет в начало очереди.
-
не Марковский процесс.
Рассматривается следующий процесс
- остаточное время обслуживания заявки, первой подсистемой, стоящей в -ой позиции.
Список литературы
1. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966. - 431с.
2. Ширяев А.Н. Вероятность. - М.: Наука, 1980. - 575с.
3. Буриков А.Д., Малинковский Ю.В., Маталыцкий М.А. Теория массового обслуживания: Учебное пособие по спецкурсу. - Гродно, 1984. - 108с. (ГрГу).
4. Феллер В. Введение в теорию вероятностей и её приложения: в 2-х т. М.: Мир, 1967, - т.1,-498с.
5. Кениг Д., Штоян Д. Методы теории массового обслуживания. - М.: Радио и связь, 1981. - 127с.
Курсовая работа
Инвариантность стационарного распределения трехузловой сети массового обслуживания
Исполнитель
Студентка группы М-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; (заявка, поступающая в -ый узел, вытесняет заявку с прибора и начинает обслуживаться, вытесненная заявка идет в начало очереди).
В курсовой работе для открытой марковской сети массового обслуживания составим уравнения равновесия, найдем стационарные вероятности, установим условия эргодичности. Для не марковского случая составим дифференциально-разностное уравнение в частных производных для процесса, дополненного остаточными временами, найдем решение данного уравнения. Сравним марковский и немарковский случай. Сделаем вывод.
Теоретические сведения
Марковские процессы
Пусть Т и Х - некоторые подмножества числовой прямой 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. Если промежутки времени между моментами поступления заявок независимы и имеют показательное распределение с параметром 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. Говорят, что обслуживание задано, если для любого
Определение 2. Обслуживание называется рекуррентным, если
Определение 3. Рекуррентное обслуживание с
(показательным) обслуживанием с параметром m. Если
Т. е. время обслуживания любой заявки неслучайно (и равно b единиц времени), то обслуживание называют детерминированным или регулярным.
Классификация систем массового обслуживания
Классификация систем массового обслуживания чаще всего производят по следующим признакам:
входящий поток заявок;
совместное распределение времен обслуживания заявок;
число обслуживающих приборов (каналов, линий);
дисциплина обслуживания, организация очереди и процесса обслуживания.
Существуют следующие типы систем. В системах с потерями заявки, которые при поступлении не находят ни одного свободного прибора, теряются. Для систем с ожиданием возможно ожидание любого числа требований, которые не могут быть обслужены сразу. Для систем с ограниченным числом мест для ожидания ожидать может только число заявок, меньше некоторого фиксированного числа 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 - количество мест для ожидания заявок в очереди.
Дата: 2019-07-24, просмотров: 183.
