Простейшие потоки марковские процессы и цепи решение. Потоки событий марковские случайные процессы потоки событий. Эргодические и поглощающие цепи

Потоки событий Это последовательность событий происходящих одно за другим в определенные интервалы времени. T - средняя величина времени между соседними событиями Если T=const, то события в потоке распределены равномерно. - интенсивность потока, т. е. среднее число событий, происходящих в единицу времени.

Потоки событий Стационарный Количество событий, попадающих на любой произвольный интервал времени не зависит от положения на числовой оси, а зависит только от его ширины Без последействия Для любых двух непересекающихся временных интервалов количество событий, попадающих на один из них, не зависит от того, сколько событий произошло на другом интервале Регулярный Противоположный потоку без последействия (с последействием)

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

Экономическое применение Современные финансово – банковские операции предполагают погашение задолженности в рассрочку, периодическое поступление доходов от инвестиций. Такого рода последовательность, или ряд платежей, можно назвать потоком платежей. Поток платежей все члены которого – положительные величины, а временные интервалы между платежами одинаковы, называют финансовой рентой. Рентой является последовательность получения процентов по облигациям, платежи по потребительскому кредиту, выплаты в рассрочку страховых премий. Характеристики потока платежей: интервал между двумя соседними платежами, вероятности выплаты платежа, широко применяются в различных финансовых расчетах. Без них невозможно разработать план последовательного погашения задолженности, измерить финансовую эффективность проекта, осуществить сравнение или безубыточное изменение условий контрактов.

Задача Для анализа изменения с течением времени размера текущего фонда банка, занимающегося выдачей долгосрочных ссуд, важно обладать информацией о процессе поступления в банк выплат по займам. Наблюдение за банком в предшествующем периоде показало, что число поступающих в банк выплат за любой промежуток времени не зависит от момента времени с которого начался отсчет промежутка времени, а зависит только от его продолжительности. Ожидаемое число выплат в банк за неделю равно 2. Исследуем, какова вероятность поступления в банк за месяц 7 выплат и найдем вероятность того, что интервал времени между двумя соседними выплатами меньше 2 дней.

Решение По условию задачи поток выплат можно считать простейшим с интенсивностью =2 (за неделю). Следовательно, число выплат, поступивших за промежуток времени =4 недели (1 месяц), распределено по закону Пуассона. Интервалы времени между двумя последовательными выплатами в простейшем потоке имеют показательный закон распределения.

Решение Пусть X() - дискретная случайная величина, представляющая собой число выплат, поступивших за промежуток времени. Она распределена по закону Пуассона. M(X)=D(X)= Тогда - вероятность того, что за промежуток времени в потоке наступят точно m событий равна Следовательно, при интенсивности потока выплат =2 вероятность поступления в банк за месяц (=4) 7 выплат (m=7) равна

Решение Пусть непрерывная случайная величина T - промежуток времени между двумя любыми соседними выплатами (событиями простейшего потока). Она имеет показательный закон распределения. M(T)=1/ , D(T)=1/ 2 Тогда вероятность P(T

Задачи для самостоятельного решения 1. Обычно студент приходит на остановку ровно в 8 часов утра и, сев в первый пришедший автобус, идущий в направлении университета, вовремя прибывает на занятия, которые начинаются ровно в 9 утра. Интервалы движения автобуса составляют в среднем 10 минут, а время в пути автобуса равно 30 минутам. Пусть поток автобусов является простейшим. Найдите вероятность того, что студент все же опоздает на занятия.

Задачи для самостоятельного решения 2. Поток заявок, поступающих в некоторую систему массового обслуживания, достаточно моделируется простейшим. При изучении опытных данных рассматривалось 200 выбранных наудачу промежутков времени длиной в 2 мин. Оказалось, что число тех из них, в которых не было зарегистрировано ни одной заявки, равно 27. Найти математическое ожидание и среднее квадратическое отклонение числа заявок за 1 час.

Основные понятия Под системой S будем понимать всякое целостное множество взаимосвязанных элементов, которое нельзя расчленить на независимые подмножества. Если система S с течением времени t изменяет свои состояния S(t) случайным образом, то говорят, что в системе S протекает случайный процесс. В любой момент времени система пребывает только в одном из состояний, то есть для любого момента времени t найдется единственное состояние Si такое, что S(t) = Si. Множество состояний может быть дискретно (техническое состояние объекта: исправен - неисправен, загружен - находится в простое; численность персонала; количество объектов, ожидающих обслуживания в очереди) или непрерывно (доход, объем производства).

Основные понятия В случае дискретного множества состояний система меняет свои состояния скачком (мгновенно). В случае же непрерывного множества состояний переход системы происходит непрерывно (плавно). В зависимости от времени пребывания системы в каждом состоянии различают процессы с дискретным временем (искусственная числовая сетка времени) и с непрерывным временем (физическое время, переход системы из одного состояния в другое может осуществляться в любой момент времени). Случайный процесс, протекающий в системе S, называется Марковским, если он обладает свойством отсутствия последствия, состоящим в том, что для каждого момента времени t 0 вероятность любого состояния S(t) системы S в будущем (при t>t 0) зависит только от ее состояния S(t 0) в настоящем (при t=t 0) и не зависит от того, как и сколько времени развивался этот процесс в прошлом (при t>t 0).

А. А. Марков (1856 - 1922) Андрей Андреевич Марков - старший - выдающийся русский математик, разработавший основы теории случайных процессов без последействия, которые в математике называют Марковскими процессами в его честь. А. А. Марков - старший известен также как давший вероятностное обоснование метода наименьших квадратов (МНК), приведший одно из доказательств предельной теоремы теории вероятностей и многое другое.

Виды Марковских процессов Дискретные состояния и дискретное время (цепь Маркова) Непрерывные состояния и дискретное время (Марковские последовательности) Дискретные состояния и непрерывное время (непрерывная Марковская цепь) Непрерывные состояния и непрерывное время. На практике большинство задач по Марковским процессам описываются с помощью Марковских цепей с дискретным или непрерывным временем.

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

Задание Марковской цепи множеством состояний S = {s 1, …, sn}, событием является переход из одного состояния в другое в результате случайного испытания вектором начальных вероятностей (начальным распределением) p(0) = {p(0)(1), …, p(0)(n)}, определяющим вероятности p(0)(i) того, что в начальный момент времени t = 0 процесс находился в состоянии si матрицей переходных вероятностей P = {pij}, характеризующей вероятность перехода процесса с текущим состоянием si в следующее состояние sj, при этом сумма вероятностей переходов из одного состояния равна 1

Виды Марковских цепей Марковская цепь называется однородной, если переходные вероятности от времени не зависят, то есть от шага k к шагу (k+1) не меняются. Разложимые Марковские цепи содержат невозвратные состояния, называемые поглощающими. Из поглощающего состояния нельзя перейти ни в какое другое. На графе поглощающему состоянию соответствует вершина, из которой не выходит ни одна дуга. Эргодические Марковские цепи описываются сильно связанным графом. В такой системе возможен переход из любого состояния в любое состояние за конечное число шагов.

Цель моделирования - определить вероятность системы находится в j-ом состоянии после k-го шага. Обозначим эту вероятность - однородная Марковская цепь - неоднородная Марковская цепь

Задача № 1 Некоторая совокупность рабочих семей поделена на три группы: 1 – семьи, не имеющие автомашины и не намеревающиеся ее приобрести; 2 – семьи, не имеющие автомашины, но собирающиеся ее приобрести, и, наконец, 3 – семьи, имеющие автомашину. Статистические обследования дали возможность оценить вероятность перехода семей из одной группы на протяжении года в другую. При этом матрица перехода оказалась такой:

Задача № 1 Найти: а)вероятность того, что семья, не имевшая машины и не собиравшаяся ее приобрести, будет находиться в той же ситуации через 2 года; б) вероятность того, что семья, не имевшая автомашины и намеревающаяся ее приобрести, будет иметь автомашину через 2 года. (выполнить решение пункта (б) данной задачи самостоятельно)

Решение задачи № 1 а) Дано: т. е. вектор начальных вероятностей p(0)=(1, 0, 0) (сейчас система в состоянии 1) Найти: (через 2 года в состоянии 1) Найдем вероятности системы оказаться в каждом из состояний через 1 год (умножение вектора начальных вероятностей на 1 столбец матрицы переходных вероятностей) (умножение вектора начальных вероятностей на 2 столбец матрицы переходных вероятностей) (умножение вектора начальных вероятностей на 3 столбец матрицы переходных вероятностей)

Решение задачи № 1 Получим вектор вероятностей через 1 год В нашем случае это 1 -ая строка матрицы переходных вероятностей Найдем вероятности системы оказаться в 1 состоянии через 2 года (умножение вектора вероятностей через 1 год, т. е. 1 -ой строки матрицы переходных вероятностей на 1 -ый столбец матрицы переходных вероятностей)

Решение задачи № 1 Вычисления: Ответ: вероятность того, что семья, не имевшая машины и не собиравшаяся ее приобрести, будет находиться в той же ситуации через 2 года равна 0, 64

Задача № 2 Предположим, что некая фирма осуществляет доставку оборудования по Москве: в северный округ (обозначим А), южный (В) и центральный (С). Фирма имеет группу курьеров, которая обслуживает эти районы. Понятно, что для осуществления следующей доставки курьер едет в тот район, который на данный момент ему ближе. Статистически было определено следующее: после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях – в В и в 40 случаях – в С; после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях – в В и в 20 случаях – в С; после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях – в В и в 20 случаях – в С. Таким образом, район следующей доставки определяется только предыдущей доставкой.

Задача № 2 Если курьер стартует из центрального округа, какова вероятность того, что осуществив две доставки, он будет в южном округе? Выполните решение задачи самостоятельно: Составьте матрицу переходных вероятностей Нарисуйте граф данного процесса Вычислите искомую вероятность

Предельные вероятности Для эргодических цепей при достаточно большом времени функционирования (t стремится к бесконечности) наступает стационарный режим, при котором вероятности состояний системы не зависят от времени и не зависят от распределения вероятностей в начальный момент времени. Такие вероятности называются предельными (или финальными, стационарными) вероятностями состояний, они показывает среднее относительное время пребывания системы в определенном состоянии. Например, если предельная вероятность i-го состояния pi=0. 5, то это означает, что в среднем половину времени система находится в i-ом состоянии.

Предельные вероятности Пусть xi – предельные вероятности (i=1. . n), где n – число состояний. Тогда xi являются единственным решением системы линейных уравнений. В данную систему входят уравнения:

Пример Матрица переходных вероятностей (число состояний n=2) и графическое изображение Марковского процесса: Предельные вероятности x 1 и x 2 можно найти, решив систему

Задача № 3 Две машины А и В сдаются в аренду по одной и той же цене. Эти машины имеют следующие матрицы переходных вероятностей: где 1 – состояние, когда машина работает хорошо; 2 – состояние, когда машина требует регулировки. Определить вероятности для обеих машин. Какую машину стоит арендовать?

Задача № 4 Посетитель банка с намерением получить кредит проходит ряд проверок (состояний): е 1 – оформление документов; е 2 – кредитная история; е 3 – возвратность; е 4 – платежеспособность. По результатам проверки возможны два исхода: отказ в выдаче кредита (е 6) и получение кредита (е 5).

Задача № 4 Требуется: a) описать данный процесс как Марковскую цепь и построить переходную матрицу (выполнить самостоятельно); б) найти среднее время получения положительного и отрицательного результата (решение в Excel).

СМО – система, подразумевающая наличие в ней 2х процессов: поступления заявок и обслуживания заявок.

Условно схема представляется в виде

И Накопитель К

Обслуживающий прибор

Процесс поступления заявок – процесс по времени.

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

С любой СМО связаны 3 потока:

1) входной поток. Последовательность моментов времени поступления заявок

2) выходной поток. Последовательность моментов времени ухода обслужившихся заявок.

3) поток обслуживаний. Последовательность моментов времени окончания ослуживания заявок в предположении что обслуживание осуществляется непрерывно.

Поток характеризуется интенсивностью – среднее число событий в единицу времени.

Поток наз-ся регулярным , если интервалы времени между событиями в нём одинаковы. Нерегулярный – если интервалы времени м\ду событиями – случайные величины.

Поток рекуррентный , если интервалы времени между событиями – случайные величины, распределённые по одному и томуже закону.

Поток наз-ся однородным , если он х-ся только множеством {ti} наступивших событий. Неоднородный – если он описывается множеством {ti,fi}, где ti – моменты времени наступления событий, fi – признак заявки.

Сами СМО подразделяются на СМО с отказами и СМО с очередями . СМО с очередями подразделяется на с ограниченной очередью и с неограниченной очередью. Частный случай – ограниченное время ожидания в очереди.

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

1) FIFO (first in – first out) – в порядке поступления;

2) LIFO (last in – first out) – первой обслуживается поступившая последней;

3) SIRO (service in random order) – в случайном порядке;

4) – приоритетные системы. (абсолютный и относительный приоритеты. При относительном заявки выстраиваются по значению приоритета – вначале высокие, потом ниже.)

Для краткой характеристики СМО Д.Кендалл ввел символику (нотацию)

m - число обслуживающих каналов;

n – количество мест ожидания (емкость накопителя).

k – кол-во источников.

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

А и В могут принимать значения:

D – детерминированное распределение;

М – показательное;

Е r – распределение Эрланга;

H r - гиперпоказательное;

G – распределение общего вида.

При этом подразумевается, что потоки являются рекуррентными , т.е. интервалы между событиями независимы и имеют одинаковое распределение. Обязательными в нотации являются первых 3 позиции. По умолчанию если n отсутствует имеем систему с отказами, если отсутствует k, то по умолчанию – один источник.

9. Простейший поток, его свойства и значение при исследовании смо.

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

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

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

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

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

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

вероятность того, что за интервал времени τ произойдет ровно m событий.

Условие отсутствие последствия (заявки поступают независимо друг от друга) наиболее существенно для простейшего потока.

пуассоновского распределения.

Вероятность того, что за не произойдет не одного события

Вероятность, что за времяпроизойдет хотя бы одно событие

Иногда удобней анализировать систему, рассматривая интервалы между событиями T:

Это показательный закон с интенсивностью .

Математическое ожидание и среднее квадратичное для T:

Свойство отсутствие последействия позволяет использовать для исследования простейшего потока аппарат Марковских цепей.

Введем состояния системы следующим образом – считаем систему, находящейся в состоянии S, если в момент времени t в системе находится S заявок.

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

(S=0, 1, 2…)

Разлагая в ряд, получим:

Вероятность получения хотя бы одной заявки

Аналогичные соотношения можно получить, рассматривая процесс обслуживания заявок.

Простейшие или близкие к ним потоки часто встречаются на практике.

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

При вероятностном просеивании простейшего потока получается простейший поток

10. Непрерывно-стохастические модели (Q -схемы). Одноканальная СМО с блокировкой. Построение графа состояний .

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

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

В СМО можно выделить два стохастических процесса:

Поступление заявок на обслуживание;

Обслуживание заявок.

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

Входной поток: множество моментов времени поступления в систему заявок;

Поток обслуживания: множество моментов окончания обработки системой заявок.

В общем случае СМО элементарного вида может быть представлено следующим образом

Обслуживающий прибор

И – источник;

О – очередь;

К – канал обслуживания.

Одноканальная СМО с блокировкой . Система M / M / 1/ n

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

Считаем, что теперь входной поток пуассоновский с интенсивностью, а поток обслуживания – пуассоновский с интенсивностью.

Как и прежде, дисциплина обслуживания FIFO с блокировкой источника.

Состояние – число заявок в системе.

Всего возможно n +3 состояния: от 0 до n +2 .

Обозначим
- вероятность прихода за
i заявок;

- вероятность обслуживания за
i заявок.

ввиду ординарное

Аналогично

+
=

1-
+

Система уравнений:
и
- вероятности состояний.

при
получим

Ввиду стационарности потоков имеем:

и
,

Аналогично для остальных строк системы.

Окончательно имеем:

Получена система алгебраических уравнений.

Преобразуем её, начиная со второго и заканчивая предпоследним - новое уравнение получаем сложением старого с новым предыдущим.

В результате новое предпоследнее будет совпадать со старым последним уравнением:

i=0, 1,….n+1

Обозначим

,

Используем уравнеие нормировки

;

;

Это сумма геометрической прогрессии:

Cреднее время обсл. заявки

Процесс работы СМО представляет собой случайный процесс. Под случайным (вероятностным или стохастическим) процессом понимается процесс изменения во времени состояния какой-либо системы в соответствии с вероятностными закономерностями.

Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3… можно заранее перечислить, а переходы системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.

Процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем.

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

Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров, пройденных автомобилем до данного момента. Пусть в момент t0 счетчик показывает S0. Вероятность того, что в момент t>t0 счетчик покажет то или иное число километров (точнее соответствующее число рублей) S1 зависит от S0, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t0.

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

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

Рисунок 1 - Граф состояний

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

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

Примерами могут быть:

• - поток вызовов на телефонной станции;
• - поток включений приборов в бытовой электросети;
• - поток грузовых составов, поступающих на железнодорожную станцию:
• - поток неисправностей (сбоев) вычислительной машины;
• - поток выстрелов, направляемых на цель.

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

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

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока есть величина постоянная: .

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени и _ число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически не имеет последствия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последствия (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).

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

Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последствия.

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

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

Рисунок 2 - Поток событий

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

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

В частности, вероятность того, что за время ф не произойдет ни одного события (m = 0), равна

Найдем распределение интервала времени T между произвольными двумя соседними событиями простейшего потока.

В соответствии с формулой вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна

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

Плотность вероятности случайной величины есть производная ее функции распределения:

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

и обратно по величине интенсивности потока л.

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

Иначе говоря, для интервала времени Т между двумя последовательными соседними событиями потока, имеющего показательное распределение, любые сведения о том, сколько времени протекал этот интервал, не влияют на закон распределения оставшейся части.

Для простейшего потока с интенсивностью л вероятность попадания на элементарный (малый) отрезок времени?t хотя бы одного события потока равна согласно

Федеральное агентство по образованию РФ

ФГОУ СПО «Перевозский строительный колледж»

Курсовая работа

по дисциплине «Математические методы»

на тему «СМО с ограниченным временем ожидания. Замкнутые СМО»

Введение.......................................................................................................... 2

1. Основы теории массового обслуживания.................................................. 3

1.1 Понятие случайного процесса.................................................................. 3

1.2 Марковский случайный процесс.............................................................. 4

1.3 Потоки событий......................................................................................... 6

1.4 Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний......................................................................................................... 9

1.5 Задачи теории массового обслуживания............................................... 13

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

2. Системы массового обслуживания с ожиданием..................................... 16

2.1 Одноканальная СМО с ожиданием........................................................ 16

2.2 Многоканальная СМО с ожиданием...................................................... 25

3. Замкнутые СМО........................................................................................ 37

Решение задачи............................................................................................. 45

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

Список литературы....................................................................................... 51

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

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

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

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

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

Теория массового обслуживания составляет один из разделов теории вероятностей. В этой теории рассматриваются вероятностные задачи и математические модели (до этого нами рассматривались детерминированные математические модели). Напомним, что:

Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позиций полной определенности в настоящем и будущем.

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

Т.е. здесь как, например, в теории игр задачи рассматриваются в условиях неопределенности .

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

Строго говоря, случайные возмущения присущи любому процессу. Проще привести примеры случайного, чем «неслучайного» процесса. Даже, например, процесс хода часов (вроде бы это строгая выверенная работа – «работает как часы») подвержен случайным изменениям (уход вперед, отставание, остановка). Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.

Пусть имеется некоторая система S (техническое устройство, группа таких устройств, технологическая система – станок, участок, цех, предприятие, отрасль промышленности и т.д.). В системе S протекает случайный процесс , если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем, заранее неизвестным случайным образом.

Примеры:

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

2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.

Случайный процесс, протекающий в системе, называется Марковским , если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.

Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы знаем характеристики состояния системы в настоящем и все, что было при t <t 0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет при t >t 0 ? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое время система S окажется в состоянии S 1 или останется в состоянии S 0 и т.д.

Пример . Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t 0 количество сохранившихся (не сбитых) самолетов соответственно – x 0 , y 0 . Нас интересует вероятность того, что в момент времени численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента t 0 самолеты.

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

В исследовании операций большое значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем.

Процесс называется процессом с дискретным состоянием , если его возможные состояния S 1 , S 2 , … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

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

Пример . Технологическая система (участок) S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможны следующие состояния системы:

S 0 - оба станка исправны;

S 1 - первый станок ремонтируется, второй исправен;

S 2 - второй станок ремонтируется, первый исправен;

S 3 - оба станка ремонтируются.

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

При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом состояний . Вершины графа – состояния системы. Дуги графа – возможные переходы из состояния в состояние. Для нашего примера граф состояний приведен на рис. 1.

Рис. 1. Граф состояний системы

Примечание. Переход из состояния S 0 в S 3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.

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

В предыдущем примере – это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.

Поток событий можно наглядно изобразить рядом точек на оси времени O t – рис. 2.

Рис. 2. Изображение потока событий на оси времени

Положение каждой точки случайно, и здесь изображена лишь какая-то одна реализация потока.

Интенсивность потока событий ( ) – это среднее число событий, приходящееся на единицу времени.

Рассмотрим некоторые свойства (виды) потоков событий.

Поток событий называется стационарным , если его вероятностные характеристики не зависят от времени.

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами:

1) стационарен;

2) ординарен;

3) не имеет последствий.

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

Для простейшего потока с интенсивностью интервал T между соседними событиями имеет так называемое показательное (экспоненциальное) распределение с плотностью:

где - параметр показательного закона.

Для случайной величины T , имеющей показательное распределение, математическое ожидание есть величина, обратная параметру, а среднее квадратичное отклонение равно математическому ожиданию:

Рассматривая Марковские процессы с дискретными состояниями и непрерывным временем, подразумевается, что все переходы системы S из состояния в состояние происходят под действием простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.). Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в системе, будет Марковским.

Итак, на систему, находящуюся в состоянии , действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния в состояние (на графе состояний по стрелке ).

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

Рис. 3. Размеченный граф состояний системы

На этом рисунке - интенсивности потока отказов; - интенсивности потока восстановлений.

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

Пусть система находится в состоянии S 0 . В состояние S 1 ее переводит поток отказов первого станка. Его интенсивность равна:

где - среднее время безотказной работы первого станка.

Из состояния S 1 в S 0 систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна:

где - среднее время ремонта первого станка.

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

Пусть рассматриваемая система S имеет -возможных состояний . Вероятность -го состояния - это вероятность того, что в момент времени , система будет находиться в состоянии . Очевидно, что для любого момента времени сумма всех вероятностей состояний равна единице:

Для нахождения всех вероятностей состояний как функций времени составляются и решаются уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний. Правило составления этих уравнений приведем здесь без доказательств. Но прежде, чем его приводить, объясним понятие финальной вероятности состояния .

Что будет происходить с вероятностями состояний при ? Будут ли стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний .

где - конечное число состояний системы.

Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:

Финальная вероятность состояния – это по–существу среднее относительное время пребывания системы в этом состоянии.

Например, система S имеет три состояния S 1 , S 2 и S 3 . Их финальные вероятности равны соответственно 0,2; 0,3 и 0,5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии S 1 , 3/10 – в состоянии S 2 и 5/10 – в состоянии S 3 .

Правило составления системы уравнений Колмогорова : в каждом уравнении системы в левой его части стоит финальная вероятность данного состояния , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния , а в правой его части – сумма произведений интенсивностей всех потоков, входящих в -е состояние , на вероятности тех состояний, из которых эти потоки исходят.

Пользуясь этим правилом, напишем систему уравнений для нашего примера :

.

Эту систему четырех уравнений с четырьмя неизвестными , казалось бы, можно вполне решить. Но эти уравнения однородны (не имеют свободного члена), и, значит, определяют неизвестные только с точностью до произвольного множителя. Однако можно воспользоваться нормировочным условием: и с его помощью решить систему. При этом одно (любое) из уравнений можно отбросить (оно вытекает как следствие из остальных).

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

Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:

.

Т.е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S 0 (оба станка исправны), 20% - в состоянии S 1 (первый станок ремонтируется, второй работает), 27% - в состоянии S 2 (второй станок ремонтируется, первый работает), 13% - в состоянии S 3 (оба станка ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.

Пусть система S в состоянии S 0 (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии S 1 – доход 3 условные единицы, в состоянии S 2 – доход 5 условных единиц, в состоянии S 3 – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен: условных единиц.

Станок 1 ремонтируется долю времени, равную: . Станок 2 ремонтируется долю времени, равную: . Возникает задача оптимизации . Пусть мы можем уменьшить среднее время ремонта первого или второго станка (или обоих), но это нам обойдется в определенную сумму. Спрашивается, окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? Нужно будет решить систему четырех уравнений с четырьмя неизвестными.

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

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

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

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

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

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

Первое деление (по наличию очередей):

1. СМО с отказами;

2. СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

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

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

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

Классификация СМО далеко не ограничивается приведенными разновидностями, но этого достаточно.

Рассмотрим простейшую СМО с ожиданием - одноканальную систему (n - 1), в которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (т.е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

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

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

Канал свободен;

Канал занят, очереди нет;

Канал занят, одна заявка стоит в очереди;

Канал занят, k-1 заявок стоят в очереди;

Канал занят, т-заявок стоят в очереди.

ГСП показан на рис. 4. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны , а справа налево - . Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево - поток «освобождений» занятого канала, имеющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

Рис. 4. Одноканальная СМО с ожиданием

Изображенная на рис. 4 схема представляет собой схему размножения и гибели. Напишем выражения для предельных вероятностей состояний:

(5)

или с использованием: :

(6)

Последняя строка в (6) содержит геометрическую прогрессию с первым членом 1 и знаменателем р, откуда получаем:

(7)

в связи с чем предельные вероятности принимают вид:

(8).

Выражение (7) справедливо только при < 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:

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

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

(9).

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

(10).

Средняя длина очереди. Найдем среднее число -заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины R-числа заявок, находящихся в очереди:

С вероятностьюв очереди стоит одна заявка, с вероятностью- две заявки, вообще с вероятностьюв очереди стоят k-1 заявок, и т.д., откуда:

(11).

Поскольку , сумму в (11) можно трактовать как производную по от суммы геометрической прогрессии:

Подставляя данное выражение в (11) и используя из (8), окончательно получаем:

(12).

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

.

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

(13).

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

Если же k=m+1, т.е. когда вновь приходящая заявка застает канал обслуживания занятым и m-заявок в очереди (вероятность этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:

если подставить сюда выражения для вероятностей (8), получим:

(14).

Здесь использованы соотношения (11), (12) (производная геометрической прогрессии), а также из (8). Сравнивая это выражение с (12), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.

(15).

Среднее время пребывания заявки в системе. Обозначим - матожидание случайной величины - время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди и среднего времени обслуживания . Если загрузка системы составляет 100%, очевидно, , в противном же случае:

.

Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).

Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно (m = 3). Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность =1 (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.

Определить:

вероятность отказа;

относительную и абсолютную пропускную способности АЗС;

среднее число машин, ожидающих заправки;

среднее число машин, находящихся на АЗС (включая обслуживаемую);

среднее время ожидания машины в очереди;

среднее время пребывания машины на АЗС (включая обслуживание).

Иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.

Находим вначале приведенную интенсивность потока заявок: =1/1,25=0,8; =1/0,8=1,25.

По формулам (8):

Вероятность отказа 0,297.

Относительная пропускная способность СМО: q=1-=0,703.

Абсолютная пропускная способность СМО: A==0,703 машины в мин.

Среднее число машин в очереди находим по формуле (12):

т.е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.

Прибавляя к этой величине среднее число машин, находящихся под обслуживанием:

получаем среднее число машин, связанных с АЗС.

Среднее время ожидания машины в очереди по формуле (15):

Прибавляя к этой величине , получим среднее время, которое машина проводит на АЗС:

Системы с неограниченным ожиданием. В таких системах значение т не ограничено и, следовательно, основные характеристики могут быть получены путем предельного перехода в ранее полученных выражениях (5), (6) и т.п.

Заметим, что при этом знаменатель в последней формуле (6) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится, когда прогрессия бесконечно убывающая, т.е. при <1.

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

Если, то соотношения (8) принимают вид:

(16).

При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q=1, .

Среднее число заявок в очереди получим из (12) при :

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

.

Среднее время ожиданияполучим из формулы (14) при:

.

Наконец, среднее время пребывания заявки в СМО есть:

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

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты -каналов, остальные нет;

Заняты все -каналов, свободных нет;

есть очередь:

Заняты все n-каналов; одна заявка стоит в очереди;

Заняты все n-каналов, r-заявок в очереди;

Заняты все n-каналов, r-заявок в очереди.

ГСП приведен на рис. 17. У каждой стрелки проставлены соответствующие интенсивности потоков событий. По стрелкам слева направо систему переводит всегда один и тот же поток заявок с интенсивностью , по стрелкам справа налево систему переводит поток обслуживании, интенсивность которого равна , умноженному на число занятых каналов.

Рис. 17. Многоканальная СМО с ожиданием

Граф типичен для процессов размножения и гибели, для которой решение ранее получено. Напишем выражения для предельных вероятностей состояний, используя обозначение : (здесь используется выражение для суммы геометрической прогрессии со знаменателем ).

Таким образом, все вероятности состояний найдены.

Определим характеристики эффективности системы.

Вероятность отказа. Поступившая заявка получает отказ, если заняты все n-каналов и все m-мест в очереди:

(18)

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

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

(19)

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

Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем -заявок в единицу времени, а СМО в целом обслуживает в среднем А-заявок в единицу времени. Разделив одно на другое, получим:

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

(20)

Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (11), (12) - (14)), используя соотношение для нее, получаем:

Среднее число заявок в системе:

Среднее время ожидания заявки в очереди. Рассмотрим ряд ситуаций, различающихся тем, в каком состоянии застанет систему вновь пришедшая заявка и сколько времени ей придется ждать обслуживания.

Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все n-каналов, а очереди нет, ей придется ждать в среднем время, равное (потому что «поток освобождений» -каналов имеет интенсивность ). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени (по на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди -заявок, ей придется ждать в среднем в течение времени . Если вновь пришедшая заявка застанет в очереди уже m-заявок, то она вообще не будет ждать (но и не будет обслужена). Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:

(21)

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (20) только множителем , т. е.

.

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

.

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

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

Вероятности состояний получим из формул предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при >1. Допустив, что <1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:

Среднее число заявок в очереди получим при из (20):

,

а среднее время ожидания - из (21):

.

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

.

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

Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью =0,8 (машин в минуту). Среднее время обслуживания одной машины:

В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.

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

и т. д.

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

Вероятность отсутствия очереди у АЗС будет:

Среднее число машин в очереди:

Среднее число машин на АЗС:

Среднее время ожидания в очереди:

Среднее время пребывания машины на АЗС:

СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом m-заявок, одновременно находящихся в очереди). В такой СМО заявка, разраставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).

Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.

Предположим, что имеется n-канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значением, таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью:

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

нет очереди:

Все каналы свободны;

Занят один канал;

Заняты два канала;

Заняты все n-каналов;

есть очередь:

Заняты все n-каналов, одна заявка стоит в очереди;

Заняты все n-каналов, r-заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 23.

Рис. 23. СМО с ограниченным временем ожидания

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна .

Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения , запишем:

(24)

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

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

Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок . Это следует из того, что ряд для в знаменателе формулы (24) сходится при любых положительных значениях и .

Для СМО с «нетерпеливыми» заявками понятие «вероятность отказа» не имеет смысла - каждая заявка становится в очередь, но может и не дождаться обслуживания, уйдя раньше времени.

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

На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа -заявок в очереди в среднем будет уходить, не дождавшись обслуживания, -заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться -заявок. Относительная пропускная способность СМО будет составлять:

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

(26)

Среднее число заявок в очереди. Соотношение (26) позволяет вычислить среднее число заявок в очереди , не суммируя бесконечного ряда (25). Из (26) получаем:

а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0, 1, 2,..., n с вероятностями ,:

В заключение заметим, что если в формулах (24) перейти к пределу при (или, что то же, при ), то при получатся формулы (22), т. е. «нетерпеливые» заявки станут «терпеливыми».

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

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

Пусть n - число каналов обслуживания, s - число потенциальных заявок, n <s , - интенсивность потока заявок каждого потенциального требования, μ - интенсивность обслуживания:

Вероятность простоя системы определяется формулой

Р 0 = .

Финальные вероятности состояний системы:

P k = при k = при .