Дипломная работа на тему "Понятие и классификация систем массового обслуживания"

ГлавнаяЭкономико-математическое моделирование → Понятие и классификация систем массового обслуживания




Не нашли то, что вам нужно?
Посмотрите вашу тему в базе готовых дипломных и курсовых работ:

(Результаты откроются в новом окне)

Текст дипломной работы "Понятие и классификация систем массового обслуживания":


Содержание

Введение........................................................................................................... 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

Заказать написание дипломной - rosdiplomnaya.com

Новый банк готовых оригинальных дипломных работ предлагает вам приобрести любые работы по необходимой вам теме. Высококлассное выполнение дипломных работ на заказ в Туле и в других городах России.

Заключение.................................................................................................... 53

Список использованных источников............................................................ 54


Введение

Темой моей дипломной работы является исследование системы массового обслуживания. В своем изначальном состоянии рассматриваемая мной СМО представляет собой один из классических случаев, а конкретно M/M/2/5 по принятому обозначению Кэндалла. После исследования системы были сделаны выводы о неэффективности ее работы. Были предложены методы оптимизации работы СМО, но с этими изменениями система перестает быть классической. Основная проблема при исследовании систем массового обслуживания заключается в том, что в реальности они могут быть исследованы с использованием классической теории массового обслуживания только в редких случаях. Потоки входящих и исходящих заявок могут оказаться не простейшими, следовательно, нахождение предельных вероятностей состояний с использованием системы дифференциальных уравнений Колмогорова невозможно, в системе могут присутствовать приоритетные классы, тогда расчет основных показателей СМО также невозможен.

Для оптимизации работы СМО была введена система из двух приоритетных классов и увеличено число обслуживающих каналов. В таком случае целесообразно применить методы имитационного моделирования, например метод Монте-Карло. Основная идея метода заключается в том, что вместо неизвестной случайной величины принимается ее математическое ожидание в достаточно большой серии испытаний. Производится разыгрывание случайной величины (в данном случае это интенсивности входящего и исходящего потоков) изначально равномерно распределенной. Затем осуществляется переход от равномерного распределения к показательному распределению, посредством формул перехода. Была написана программа на языке Visual Basic, реализующая этот метод.


1 Марковские цепи с конечным числом состояний и дискретным временем

Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S1, S2,…, Sn, а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t1, t2, t3, называемые шагами.

Если система переходит из одного состояния в другое случайно, то говорят, что имеет место случайный процесс с дискретным временем.

Случайный процесс называется марковским, если вероятность перехода из любого состояния Si в любое состояние Sj не зависит от того, как и когда система S попала в состояние Si (т. е. в системе S отсутствует последствие). В таком случае говорят, что функционирование системы S описывается дискретной цепью Маркова.

Переходы системы S в различные состояния удобно изображать с помощью графа состояний (рис. 1).

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1 – Пример размеченного графа состояний

Вершины графа S1, S2, S3 обозначают возможные состояния системы. Стрелка, направленная из вершины Si в вершину Sj обозначает переход Рисунок убран из работы и доступен только в оригинальном файле.; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i-той вершине графа, обозначает, что система остается в состоянии Si с вероятностью, стоящей у стрелки.

Графу системы, содержащему n вершин, можно поставить в соответствие матрицу NxN, элементами которой являются вероятности переходов pij между вершинами графа. Например, граф на рис. 1 описывается матрицей P:

Рисунок убран из работы и доступен только в оригинальном файле.

называемой матрицей вероятностей переходов. Элементы матрицы pij удовлетворяют условиям:

Рисунок убран из работы и доступен только в оригинальном файле. (1)

Рисунок убран из работы и доступен только в оригинальном файле. (2)

Элементы матрицы pij – дают вероятности переходов в системе за один шаг. Переход

Si – Sj за два шага можно рассматривать как происходящий на первом шаге из Si в некоторое промежуточное состояние Sk и на втором шаге из Sk в Si. Таким образом, для элементов матрицы вероятностей переходов из Si в Sj за два шага получим:

Рисунок убран из работы и доступен только в оригинальном файле.

В общем случае перехода Рисунок убран из работы и доступен только в оригинальном файле. за m шагов для элементов Рисунок убран из работы и доступен только в оригинальном файле. матрицы вероятностей переходов справедлива формула:

Рисунок убран из работы и доступен только в оригинальном файле. (3)

Получим два эквивалентных выражения для Рисунок убран из работы и доступен только в оригинальном файле.:

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле.

Пусть система S описывается матрицей вероятностей переходов Р:

Рисунок убран из работы и доступен только в оригинальном файле.

Если обозначить через Р(m) матрицу, элементами которой являются рi вероятности переходов из Si в Sj за m шагов, то справедлива формула

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

где матрица Рm получается умножением матрицы P саму на себя m раз.

Исходное состояние системы характеризуется вектором состояния системы Q(qi) (называемым также стохастическим вектором).

Рисунок убран из работы и доступен только в оригинальном файле.

где qj - вероятность того, что исходным состоянием системы является Sj состояние. Аналогично (1) и (2) справедливы соотношения

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Обозначим через

Рисунок убран из работы и доступен только в оригинальном файле.

вектор состояния системы после m шагов, где qj – вероятность того, что после m шагов система находится в Si состоянии. Тогда справедлива формула

Рисунок убран из работы и доступен только в оригинальном файле.

Если вероятности переходов Pij остаются постоянными, то такие марковские цепи называются стационарными. В противном случае марковская цепь называется нестационарной.

 
2. Марковские цепи с конечным числом состояний и непрерывным временем

Если система S может переходить в другое состояние случайным образом в произвольный момент времени, то говорят о случайном процессе с непрерывным временем. В отсутствии последействия такой процесс называется непрерывной марковской цепью. При этом вероятности переходов Рисунок убран из работы и доступен только в оригинальном файле. для любых i и j в любой момент времени равны нулю (в силу непрерывности времени). По этой причине вместо вероятности перехода Рисунок убран из работы и доступен только в оригинальном файле. вводится величина Рисунок убран из работы и доступен только в оригинальном файле.- плотность вероятности перехода из состояния Рисунок убран из работы и доступен только в оригинальном файле. в состояние Рисунок убран из работы и доступен только в оригинальном файле., определяемая как предел:

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Если величины Рисунок убран из работы и доступен только в оригинальном файле. не зависят от t, то марковский процесс называется однородным. Если за время Рисунок убран из работы и доступен только в оригинальном файле. система может изменить свое состояние не более чем один раз, то говорят, что случайный процесс является ординарным. Величину Рисунок убран из работы и доступен только в оригинальном файле. называют интенсивностью перехода системы из Si в Sj. На графе состояний системы численные значения Рисунок убран из работы и доступен только в оригинальном файле. ставят рядом со стрелками, показывающими переходы в вершины графа.

Зная интенсивности переходов можно найти величины p1(t), p2(t),…, pn(t) – вероятности нахождения системы S в состояниях S1, S2,…, Sn соответственно. При этом выполняется условие:

Рисунок убран из работы и доступен только в оригинальном файле.

Распределение вероятностей состояний системы, которое можно характеризовать вектором Рисунок убран из работы и доступен только в оригинальном файле., называется стационарным, если оно не зависит от времени, т. е. все компоненты вектора Рисунок убран из работы и доступен только в оригинальном файле. являются константами.

Состояния Si и Sj называются сообщающимися, если возможны переходы Рисунок убран из работы и доступен только в оригинальном файле..

Состояние Si называется существенным, если всякое Sj, достижимое из Si, является сообщающимся с Si. Состояние Si называется несущественным, если оно не является существенным.

Если существуют предельные вероятности состояний системы:

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

не зависящие от начального состояния системы, то говорят, что при Рисунок убран из работы и доступен только в оригинальном файле. в системе устанавливается стационарный режим.

Система, в которой существуют предельные (финальные) вероятности состояний системы, называется эргодической, а протекающий в ней случайный процесс эргодическим.

Теорема 1. Если Si – несущественное состояние, то Рисунок убран из работы и доступен только в оригинальном файле. т. е. при Рисунок убран из работы и доступен только в оригинальном файле. система выходит из любого несущественного состояния.

Теорема 2. Чтобы система с конечным числом состояний имела единственное предельное распределение вероятностей состояний, необходимо и достаточно, чтобы все ее существенные состояния сообщались между собой.

Если случайный процесс, происходящий в системе с дискретными состояниями является непрерывной марковской цепью, то для вероятностей p1(t), р2(t),…, pn(t) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. При составлении уравнений удобно пользоваться графом состояний системы. В левой части каждого из них стоит производная вероятности какого-то (j-го) состояния. В правой части – сумма произведений вероятностей всех состояний, из которых возможен переход в данное состояние, на интенсивности соответствующих потоков, минус суммарная интенсивность всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния.

 
3 Процессы рождения и гибели

Так называется широкий класс случайных процессов, происходящих в системе, размеченный граф состояний которой изображен на рис. 3.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 2 – Граф состояний для процессов гибели и размножения

Здесь величины Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,…, Рисунок убран из работы и доступен только в оригинальном файле. – интенсивности переходов системы из состояния в состояние слева направо, можно интерпретировать как интенсивности рождения (возникновения заявок) в системе. Аналогично, величины Рисунок убран из работы и доступен только в оригинальном файле.,Рисунок убран из работы и доступен только в оригинальном файле.,…,Рисунок убран из работы и доступен только в оригинальном файле. – интенсивности переходов системы из состояния в состояние справа налево, можно интерпретировать как интенсивности гибели (выполнения заявок) в системе.

Поскольку все состояния являются сообщающимися и существенными, существует (в силу теоремы 2) предельное (финальное) распределение вероятностей состояний. Получим формулы для финальных вероятностей состояний системы.

В стационарных условиях для каждого состояния поток, входящий в данное состояние должен равняться потоку, исходящему из данного состояния. Таким образом, имеем:

Для состояния S0:

Рисунок убран из работы и доступен только в оригинальном файле.

Следовательно:

Рисунок убран из работы и доступен только в оригинальном файле.

Для состояния S1:

Рисунок убран из работы и доступен только в оригинальном файле.

Следовательно:

Рисунок убран из работы и доступен только в оригинальном файле.

С учетом того, что Рисунок убран из работы и доступен только в оригинальном файле.:

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле.

Аналогично получаем уравнения для остальных состояний системы. В результате получим систему уравнений:

Рисунок убран из работы и доступен только в оригинальном файле.

Решение этой системы будет иметь вид:

Рисунок убран из работы и доступен только в оригинальном файле. (4)

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,…, Рисунок убран из работы и доступен только в оригинальном файле. (5)

 
4. Основные понятия и классификация систем массового обслуживания

Заявкой (или требованием) называется спрос на удовлетворение какой-либо потребности (далее потребности предполагаются однотипными). Выполнение заявки называется обслуживанием заявки.

Системой массового обслуживания (СМО) называется любая система для выполнения заявок, поступающих в неё в случайные моменты времени.

Поступление заявки в СМО называется событием. Последовательность событий, заключающихся в поступлении заявок в СМО, называется входящим потоком заявок. Последовательность событий, заключающихся в выполнении заявок в СМО, называется выходящим потоком заявок.

Поток заявок называется простейшим, если он удовлетворяет следующим условиям:

1) отсутствие последействия, т. е. заявки поступают независимо друг от друга;

2) стационарность, т. е. вероятность поступления данного числа заявок на любом временном отрезке [t1; t2] зависит лишь от величины этого отрезка и не зависит от значения t1, что позволяет говорить о среднем числе заявок за единицу времени, λ, называемом интенсивностью потока заявок;

3) ординарность, т. е. в любой момент времени в СМО поступает лишь одна заявка, а поступление одновременно двух и более заявок пренебрежимо мало.

Для простейшего потока вероятность pi(t) поступления в СМО ровно i заявок за время t вычисляется по формуле:

Рисунок убран из работы и доступен только в оригинальном файле. (6)

т. е. вероятности распределены по закону Пуассона с параметром λt. По этой причине простейший поток называется также пуассоновским потоком.

Функция распределения F(t) случайного интервала времени T между двумя последовательными заявками по определению равна Рисунок убран из работы и доступен только в оригинальном файле.. Но Рисунок убран из работы и доступен только в оригинальном файле., где Рисунок убран из работы и доступен только в оригинальном файле. – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t, т. е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (6) при i = 0. Таким образом:

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. (7)

Плотность вероятности f(t) случайной величины T определяется формулой:

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

Математическое ожидание, дисперсия и среднее квадратическое отклонение случайной величины T равны соответственно:

Рисунок убран из работы и доступен только в оригинальном файле.

Каналом обслуживания называется устройство в СМО, обслуживающее заявку. СМО, содержащее один канал обслуживания, называется одноканальной, а содержащее более одного канала обслуживания – многоканальной.

Если заявка, поступающая в СМО, может получить отказ в обслуживании (в силу занятости всех каналов обслуживания) и в случае отказа вынуждена покинуть СМО, то такая СМО называется СМО с отказами.

Если в случае отказа в обслуживании заявки могут вставать в очередь, то такие СМО называются СМО с очередью (или с ожиданием). При этом различают СМО с ограниченной и неограниченной очередью. Очередь может быть ограничена как по количеству мест, так и по времени ожидания. Различают СМО открытого и замкнутого типа. В СМО открытого типа поток заявок не зависит от СМО. В СМО замкнутого типа обслуживается ограниченный круг клиентов, а число заявок может существенно зависеть от состояния СМО (например, бригада слесарей – наладчиков, обслуживающих станки на заводе).

СМО могут также различаться по дисциплине обслуживания.

Если в СМО нет приоритета, то заявки отбираются из очереди в канал по различным правилам.

-   Первым пришел – первым обслужен (FCFS – First Came – First Served)

-   Последним пришел – первым обслужен (LCFS – Last Came – First Served)

-   Первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE)

-   Первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT)

-   Первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT)

-   Первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT)

Приоритеты бывают двух типов – абсолютный и относительный.

Если требование в процессе обслуживания может быть удалено из канала и возвращено в очередь (либо вовсе покидает СМО) при поступлении требования с более высоким приоритетом, то система работает с абсолютным приоритетом. Если обслуживание любого требования, находящегося в канале не может быть прервано, то СМО работает с относительным приоритетом. Существуют также приоритеты, осуществляемые с помощью конкретного правила или набора правил. Примером может служить приоритет, изменяющийся с течением времени.

СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.

Рисунок убран из работы и доступен только в оригинальном файле. – число каналов в СМО;

Рисунок убран из работы и доступен только в оригинальном файле. – интенсивность поступления в СМО заявок;

Рисунок убран из работы и доступен только в оригинальном файле. – интенсивность обслуживания заявок;

Рисунок убран из работы и доступен только в оригинальном файле. – коэффициент загрузки СМО;

Рисунок убран из работы и доступен только в оригинальном файле. – число мест в очереди;

Рисунок убран из работы и доступен только в оригинальном файле. – вероятность отказа в обслуживании поступившей в СМО заявки;

Рисунок убран из работы и доступен только в оригинальном файле. – вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО);

При этом:

Рисунок убран из работы и доступен только в оригинальном файле. (8)

А – среднее число заявок, обслуживаемых в СМО в единицу времени (абсолютная пропускная способность СМО)

Рисунок убран из работы и доступен только в оригинальном файле. (9)

Рисунок убран из работы и доступен только в оригинальном файле. – среднее число заявок, находящихся в СМО

Рисунок убран из работы и доступен только в оригинальном файле. – среднее число каналов в СМО, занятых обслуживанием заявок. В тоже время это Рисунок убран из работы и доступен только в оригинальном файле. – среднее число заявок, обслуживаемых в СМО за единицу времени. Величина Рисунок убран из работы и доступен только в оригинальном файле. определяется как математическое ожидание случайного числа занятых обслуживанием n каналов.

Рисунок убран из работы и доступен только в оригинальном файле., (10)

где Рисунок убран из работы и доступен только в оригинальном файле. – вероятность нахождения системы в Sk состоянии.

Рисунок убран из работы и доступен только в оригинальном файле. – коэффициент занятости каналов

Рисунок убран из работы и доступен только в оригинальном файле. – среднее время ожидания заявки в очереди

Рисунок убран из работы и доступен только в оригинальном файле. – интенсивность ухода заявок из очереди

Рисунок убран из работы и доступен только в оригинальном файле. – среднее число заявок в очереди. Определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

Рисунок убран из работы и доступен только в оригинальном файле. (11)

Здесь Рисунок убран из работы и доступен только в оригинальном файле. – вероятность нахождения в очереди i заявок;

Рисунок убран из работы и доступен только в оригинальном файле. – среднее время пребывания заявки с СМО

Рисунок убран из работы и доступен только в оригинальном файле. – среднее время пребывания заявки в очереди

Для открытых СМО справедливы соотношения:

Рисунок убран из работы и доступен только в оригинальном файле. (12)

Рисунок убран из работы и доступен только в оригинальном файле. (13)

Эти соотношения называются формулами Литтла и применяются только для стационарных потоков заявок и обслуживания.

Рассмотрим некоторые конкретные типы СМО. При этом будет предполагаться, что плотность распределения промежутка времени между двумя последовательными событиями в СМО имеет показательное распределение (7), а все потоки являются простейшими.

 
5. Основ ные типы открытых систем массового обслуживания 5.1 Одноканальная система массового обслуживания с отказами

Размеченный граф состояний одноканальной СМО представлен на рисунке 3.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 3 – Граф состояний одноканальной СМО

Здесь Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле. – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы So обозначает, что канал свободен, а S1 – что канал занят обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеет вид:

Рисунок убран из работы и доступен только в оригинальном файле.

где po(t) и p1(t) – вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей po и p1 получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:

Рисунок убран из работы и доступен только в оригинальном файле. (14)

Рисунок убран из работы и доступен только в оригинальном файле. (15)

Вероятность p0 по своему смыслу есть вероятность обслуживания заявки pобс, т. к. канал является свободным, а вероятность р1 по своему смыслу является вероятностью отказа в обслуживании поступающей в СМО заявки ротк, т. к. канал занят обслуживанием предыдущей заявки.

5.2 Многоканальная система массового обслуживания с отказами

Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна Рисунок убран из работы и доступен только в оригинальном файле., а интенсивность обслуживания заявки каждым каналом равна Рисунок убран из работы и доступен только в оригинальном файле.. Размеченный граф состояний системы изображён на рисунке 4.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 4 – Граф состояний многоканальной СМО с отказами

Состояние S0 означает, что все каналы свободны, состояние Sk (k = 1, n) означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью Рисунок убран из работы и доступен только в оригинальном файле. независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина Рисунок убран из работы и доступен только в оригинальном файле. характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).

Сравнивая графы на рис. 3 и на рис. 5 легко увидеть, что многоканальная СМО с отказами является частным случаем системы рождения и гибели, если в последней принять Рисунок убран из работы и доступен только в оригинальном файле. и

Рисунок убран из работы и доступен только в оригинальном файле. (16)

При этом для нахождения финальных вероятностей можно воспользоваться формулами (4) и (5). С учётом (16) получим из них:

Рисунок убран из работы и доступен только в оригинальном файле. (17)

Рисунок убран из работы и доступен только в оригинальном файле. (18)

Формулы (17) и (18) называются формулами Эрланга – основателя теории массового обслуживания.

Вероятность отказа в обслуживании заявки ротк равна вероятности того, что все каналы заняты, т. е. система находится в состоянии Sn. Таким образом,

Рисунок убран из работы и доступен только в оригинальном файле. (19)

Относительную пропускную способность СМО найдём из (8) и (19):

Рисунок убран из работы и доступен только в оригинальном файле. (20)

Абсолютную пропускную способность найдём из (9) и (20):

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число занятых обслуживанием каналов можно найти по формуле (10), однако сделаем это проще. Так как каждый занятый канал в единицу времени обслуживает в среднем Рисунок убран из работы и доступен только в оригинальном файле. заявок, то Рисунок убран из работы и доступен только в оригинальном файле. можно найти по формуле:

Рисунок убран из работы и доступен только в оригинальном файле.

5.3 Одноканальная система массового обслуживания с ограниченной длиной очереди

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 5.

--------------------------------------------------
--------------------------------------------------

S0

|
--------------------------------------------------------- --------------------------------------------------   |
--------------------------------------------------------- -------------------------------------------------- Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 5 – Граф состояний одноканальной СМО с ограниченной очередью

Состояния СМО представляются следующим образом:

S0 – канал обслуживания свободен,

S1 – канал обслуживания занят, но очереди нет,

S2 – канал обслуживания занят, в очереди одна заявка,

Sk+1 – канал обслуживания занят, в очереди k заявок,

Sm+1 – канал обслуживания занят, все m мест в очереди заняты.

Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рисунок 5 является частным случаем системы рождения и гибели, представленной на рисунке 2, если в последней принять Рисунок убран из работы и доступен только в оригинальном файле. и

Рисунок убран из работы и доступен только в оригинальном файле. (21)

Рисунок убран из работы и доступен только в оригинальном файле. (22)

Рисунок убран из работы и доступен только в оригинальном файле. (23)

Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (4) и (5) с учётом (21). В результате получим:

При р = 1 формулы (22), (23) принимают вид

При m = 0 (очереди нет) формулы (22), (23) переходят в формулы (14) и (15) для одноканальной СМО с отказами.

Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии Sm+1, т. е. вероятность отказа в обслуживании заявки равна:

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле.

Относительная пропускная способность СМО равна:

Рисунок убран из работы и доступен только в оригинальном файле.

Абсолютная пропускная способность равна:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число заявок, стоящих в очереди Lоч, находится по формуле

Рисунок убран из работы и доступен только в оригинальном файле.

и может быть записано в виде:

Рисунок убран из работы и доступен только в оригинальном файле. (24)

При Рисунок убран из работы и доступен только в оригинальном файле. формула (24) принимает вид:

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. – среднее число заявок, находящихся в СМО, находится по формуле(10)

Рисунок убран из работы и доступен только в оригинальном файле.

и может быть записано в виде:

Рисунок убран из работы и доступен только в оригинальном файле. (25)

При Рисунок убран из работы и доступен только в оригинальном файле., из (25) получим:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее время пребывания заявки в СМО и в очереди находится по формулам (12) и (13) соответственно.

 
5.4 Одноканальная система массового обслуживания с неограниченной очередью

Примером такой СМО может служить директор предприятия, вынужденный рано или поздно решать вопросы, относящиеся к его компетенции, или, например, очередь в булочной с одним кассиром. Граф такой СМО изображён на рисунке 6.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 6 – Граф состояний одноканальной СМО с неограниченной очередью

Все характеристики такой СМО можно получить из формул предыдущего раздела, полагая в них Рисунок убран из работы и доступен только в оригинальном файле.. При этом необходимо различать два существенно разных случая: а) Рисунок убран из работы и доступен только в оригинальном файле.; б) Рисунок убран из работы и доступен только в оригинальном файле.. В первом случае, как это видно из формул (22), (23), р0 = 0 и pk = 0 (при всех конечных значениях k). Это означает, что при Рисунок убран из работы и доступен только в оригинальном файле. очередь неограниченно возрастает, т. е. этот случай практического интереса не представляет.

Рассмотрим случай, когда Рисунок убран из работы и доступен только в оригинальном файле.. Формулы (22) и (23) при этом запишутся в виде:

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле.

Поскольку в СМО отсутствует ограничение на длину очереди, то любая заявка может быть обслужена, т. е. относительная пропускная способность равна:

Рисунок убран из работы и доступен только в оригинальном файле.

Абсолютная пропускная способность равна:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число заявок в очереди получим из формулы (24) при Рисунок убран из работы и доступен только в оригинальном файле.:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число обслуживаемых заявок есть:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число заявок, находящихся в СМО:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее время пребывания заявки в СМО и в очереди определяются формулами (12) и (13).

5.5 Многоканальная система массового обслуживания с ограниченной очередью

Пусть на вход СМО, имеющей Рисунок убран из работы и доступен только в оригинальном файле. каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью Рисунок убран из работы и доступен только в оригинальном файле.. Интенсивность обслуживания заявки каждым каналом равна Рисунок убран из работы и доступен только в оригинальном файле., а максимальное число мест в очереди равно Рисунок убран из работы и доступен только в оригинальном файле..

Граф такой системы представлен на рисунке 7.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 7 – Граф состояний многоканальной СМО с ограниченной очередью

Рисунок убран из работы и доступен только в оригинальном файле. – все каналы свободны, очереди нет;

Рисунок убран из работы и доступен только в оригинальном файле. – заняты l каналов (l = 1, n), очереди нет;

Рисунок убран из работы и доступен только в оригинальном файле.- заняты все n каналов, в очереди находится i заявок (i = 1, m).

Сравнение графов на рисунке 2 и рисунке 7 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле.

Выражения для финальных вероятностей легко найти из формул (4) и (5). В результате получим:

Рисунок убран из работы и доступен только в оригинальном файле. (26)

Рисунок убран из работы и доступен только в оригинальном файле.

Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т. е. в системе находятся либо n, либо (n+1),…, либо (n + m – 1) заявок. Т. к. эти события несовместны, то вероятность образования очереди pоч равна сумме соответствующих вероятностей Рисунок убран из работы и доступен только в оригинальном файле.:

Рисунок убран из работы и доступен только в оригинальном файле. (27)

Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т. е.:

Рисунок убран из работы и доступен только в оригинальном файле.

Относительная пропускная способность равна:

Рисунок убран из работы и доступен только в оригинальном файле.

Абсолютная пропускная способность:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число заявок, находящихся в очереди, определяется по формуле (11) и может быть записано в виде:

Рисунок убран из работы и доступен только в оригинальном файле. (28)

Среднее число заявок, обслуживаемых в СМО, может быть записано в виде:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число заявок, находящихся в СМО:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее время пребывания заявки в СМО и в очереди определяется формулами (12) и (13).

5.6 Многоканальная система массового обслуживания с неограниченной очередью

Граф такой СМО изображен на рисунке 8 и получается из графа на рисунке 7 при Рисунок убран из работы и доступен только в оригинальном файле..

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 8 – Граф состояний многоканальной СМО с неограниченной очередью

Формулы для финальных вероятностей можно получить из формул для n-канальной СМО с ограниченной очередью при Рисунок убран из работы и доступен только в оригинальном файле.. При этом следует иметь в виду, что при Рисунок убран из работы и доступен только в оригинальном файле. вероятность р0 = р1=…= pn = 0, т. е. очередь неограниченно возрастает. Следовательно, этот случай практического интереса не представляет и ниже рассматривается лишь случай Рисунок убран из работы и доступен только в оригинальном файле.. При Рисунок убран из работы и доступен только в оригинальном файле. из (26) получим:

Рисунок убран из работы и доступен только в оригинальном файле.

Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:

Рисунок убран из работы и доступен только в оригинальном файле.

Из (27) получим выражение для вероятности образования очереди заявок:

Рисунок убран из работы и доступен только в оригинальном файле.

Поскольку очередь не ограничена, то вероятность отказа в обслуживании заявки:

Рисунок убран из работы и доступен только в оригинальном файле.

Относительная пропускная способность:

Рисунок убран из работы и доступен только в оригинальном файле.

Абсолютная пропускная способность:

Рисунок убран из работы и доступен только в оригинальном файле.

Из формулы (28) при Рисунок убран из работы и доступен только в оригинальном файле. получим выражение для среднего числа заявок в очереди:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число обслуживаемых заявок определяется формулой:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее время пребывания в СМО и в очереди определяется формулами (12) и (13).

5.7 Многоканальная система массового обслуживания с ограниченной очередью и ограниченным временем ожидания в очереди

Отличие такой СМО от СМО, рассмотренной в подразделе 5.5, состоит в том, что время ожидания обслуживания, когда заявка находится в очереди, считается случайной величиной, распределённой по показательному закону с параметром Рисунок убран из работы и доступен только в оригинальном файле., где Рисунок убран из работы и доступен только в оригинальном файле. – среднее время ожидания заявки в очереди, а Рисунок убран из работы и доступен только в оригинальном файле. – имеет смысл интенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке 9.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 9 – Граф многоканальной СМО с ограниченной очередью и ограниченным временем ожидания в очереди

Остальные обозначения имеют здесь тот же смысл, что и в подразделе.

Сравнение графов на рис. 3 и 9 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. (29)

Выражения для финальных вероятностей легко найти из формул (4) и (5) с учетом (29). В результате получим:

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле.

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

где Рисунок убран из работы и доступен только в оригинальном файле.. Вероятность образования очереди определяется формулой:

Рисунок убран из работы и доступен только в оригинальном файле.

Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т. е. вероятность отказа в обслуживании:

Рисунок убран из работы и доступен только в оригинальном файле.

Относительная пропускная способность:

Рисунок убран из работы и доступен только в оригинальном файле.

Абсолютная пропускная способность:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число заявок, находящихся в очереди, находится по формуле (11) и равно:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее число заявок, обслуживаемых в СМО, находится по формуле (10) и равно:

Рисунок убран из работы и доступен только в оригинальном файле.

Среднее время пребывания заявки в СМО складывается из среднего времени ожидания в очереди и среднего времени обслуживания заявки:

Рисунок убран из работы и доступен только в оригинальном файле.

 
6. Метод Монте-Карло 6.1 Основная идея метода

Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а: М(Х)=а.

Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое Рисунок убран из работы и доступен только в оригинальном файле. и принимают Рисунок убран из работы и доступен только в оригинальном файле. в качестве оценки (приближённого значения) a* искомого числа a:

Рисунок убран из работы и доступен только в оригинальном файле..

Поскольку метод Монте-Карло требует проведения большого числа испытаний, его часто называют методом статистических испытаний.

6.2 Разыгрывание непрерывной случайной величины

Пусть необходимо получить значения случайной величины Рисунок убран из работы и доступен только в оригинальном файле., распределенной в интервале Рисунок убран из работы и доступен только в оригинальном файле. с плотностью Рисунок убран из работы и доступен только в оригинальном файле.. Докажем, что значения Рисунок убран из работы и доступен только в оригинальном файле. можно найти из уравнения

Рисунок убран из работы и доступен только в оригинальном файле., (30)

где Рисунок убран из работы и доступен только в оригинальном файле. – случайная величина, равномерно распределенная на интервале Рисунок убран из работы и доступен только в оригинальном файле..

Т. е. выбрав очередное значение Рисунок убран из работы и доступен только в оригинальном файле. надо решить уравнение (30) и найти очередное значение Рисунок убран из работы и доступен только в оригинальном файле.. Для доказательства рассмотрим функцию:

Рисунок убран из работы и доступен только в оригинальном файле.

Имеем общие свойства плотности вероятности:

... (31)

... (32)

Из (31) и (32) следует, что ..., а производная ...

Значит, функция ... монотонно возрастает от 0 до 1. И любая прямая ..., где ..., пересекает график функции ... в единственной точке, абсциссу которой мы и принимаем за ... Таким образом, уравнение (30) всегда имеет одно и только одно решение....


Здесь опубликована для ознакомления часть дипломной работы "Понятие и классификация систем массового обслуживания". Эта работа найдена в открытых источниках Интернет. А это значит, что если попытаться её защитить, то она 100% не пройдёт проверку российских ВУЗов на плагиат и её не примет ваш руководитель дипломной работы!
Если у вас нет возможности самостоятельно написать дипломную - закажите её написание опытному автору»


Просмотров: 678

Другие дипломные работы по специальности "Экономико-математическое моделирование":

Экономико-математическая модель оптимизации распределения трудовых ресурсов

Смотреть работу >>

Математическое моделирование лизинговых операций

Смотреть работу >>

Математическое моделирование роста доходности страховой компании

Смотреть работу >>

Анализ и разработка мероприятий по повышению эффективности сельскохозяйственной деятельности организации на основе эмпирического анализа теоретического и практического материала ОАО "Смолевичский Райагросервис"

Смотреть работу >>

Проект оптимизации сводных показателей машиностроительного цеха

Смотреть работу >>