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

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

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

Когда событий много и они следуют друг за другом, то они образуют поток . Заметим, что события при этом должны быть однородными, то есть похожими чем-то друг на друга. Например, появление водителей на АЗС, желающих заправить свой автомобиль. То есть, однородные события образуют некий ряд. При этом считается, что статистическая характеристика этого явления (интенсивность потока событий) задана. Интенсивность потока событий указывает, сколько в среднем происходит таких событий за единицу времени. Но когда именно произойдет каждое конкретное событие надо определить методами моделирования. Важно, что, когда мы сгенерируем, например, за 200 часов 1000 событий, их количество будет равно примерно величине средней интенсивности появления событий 1000/200 = 5 событий в час, что является статистической величиной, характеризующей этот поток в целом.

Интенсивность потока в некотором смысле является математическим ожиданием количества событий в единицу времени. Но реально может так оказаться, что в один час появится 4 события, в другой — 6, хотя в среднем получается 5 событий в час, поэтому одной величины для характеристики потока недостаточно. Второй величиной, характеризующей насколько велик разброс событий относительно математического ожидания, является, как и ранее, дисперсия. Собственно именно эта величина определяет случайность появления события, слабую предсказуемость момента его появления. Про эту величину мы расскажем в следующей лекции.

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

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

Интенсивность потока λ — это среднее число событий в единицу времени. Интенсивность потока можно рассчитать экспериментально по формуле: λ = N /T н , где N — число событий, произошедших за время наблюдения T н .

Если интервал между событиями τ j равен константе или определен какой-либо формулой в виде: t j = f (t j – 1) , то поток называется детерминированным . Иначе поток называется случайным .

Случайные потоки бывают:

• ординарные : вероятность одновременного появления двух и более событий равна нулю;
• стационарные : частота появления событий λ (t ) = const(t ) ;
• без последействия : вероятность появления случайного события не зависит от момента совершения предыдущих событий.

Пуассоновский поток

За эталон потока в моделировании принято брать пуассоновский поток .

Пуассоновский поток — это ординарный поток без последействия.

Как ранее было указано, вероятность того, что за интервал времени (t 0 , t 0 + τ ) произойдет m событий, определяется из закона Пуассона:

где a — параметр Пуассона.

Если λ (t ) = const(t ) , то это стационарный поток Пуассона (простейший). В этом случае a = λ · t . Если λ = var(t ) , то это нестационарный поток Пуассона .

Для простейшего потока вероятность появления m событий за время τ равна:

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

Рис. 28.2 иллюстрирует зависимость P 0 от времени. Очевидно, что чем больше время наблюдения, тем вероятность непоявления ни одного события меньше. Кроме того, чем более значение λ , тем круче идет график, то есть быстрее убывает вероятность. Это соответствует тому, что если интенсивность появления событий велика, то вероятность непоявления события быстро уменьшается со временем наблюдения.

Вероятность появления хотя бы одного события (P ХБ1С ) вычисляется так:

так как P ХБ1С + P 0 = 1 (либо появится хотя бы одно событие, либо не появится ни одного, — другого не дано).

Из графика на рис. 28.3 видно, что вероятность появления хотя бы одного события стремится со временем к единице, то есть при соответствующем длительном наблюдении события таковое обязательно рано или поздно произойдет. Чем дольше мы наблюдаем за событием (чем более t ), тем больше вероятность того, что событие произойдет — график функции монотонно возрастает.

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

Если увеличивать λ , то при наблюдении за событием в течение одного и того же времени τ , вероятность наступления события возрастает (см. рис. 28.4 ). Очевидно, что график исходит из 0, так как если время наблюдения бесконечно мало, то вероятность того, что событие произойдет за это время, ничтожна. И наоборот, если время наблюдения бесконечно велико, то событие обязательно произойдет хотя бы один раз, значит, график стремится к значению вероятности равной 1.

Изучая закон, можно определить, что: m x = 1/λ , σ = 1/λ , то есть для простейшего потока m x = σ . Равенство математического ожидания среднеквадратичному отклонению означает, что данный поток — поток без последействия. Дисперсия (точнее, среднеквадратичное отклонение) такого потока велика. Физически это означает, что время появления события (расстояние между событиями) плохо предсказуемо, случайно, находится в интервале m x – σ < τ j < m x + σ . Хотя ясно, что в среднем оно примерно равно: τ j = m x = T н /N . Событие может появиться в любой момент времени, но в пределах разброса этого момента τ j относительно m x на [–σ ; +σ ] (величину последействия). На рис. 28.5 показаны возможные положения события 2 относительно оси времени при заданном σ . В данном случае говорят, что первое событие не влияет на второе, второе на третье и так далее, то есть последействие отсутствует.

По смыслу P равно r (см. лекцию 23. Моделирование случайного события. Моделирование полной группы несовместных событий), поэтому, выражая τ из формулы (*) , окончательно для определения интервалов между двумя случайными событиями имеем:

τ = –1/λ · Ln(r ) ,

где r — равномерно распределенное от 0 до 1 случайное число, которое берут из ГСЧ, τ — интервал между случайными событиями (случайная величина τ j ).

Пример 1 . Рассмотрим поток изделий, приходящих на технологическую операцию. Изделия приходят случайным образом — в среднем восемь штук за сутки (интенсивность потока λ = 8/24 [ед/час] ). Необходимо промоделировать этот процесс в течение T н = 100 часов . m = 1/λ = 24/8 = 3 , то есть в среднем одна деталь за три часа. Заметим, что σ = 3 . На рис. 28.6 представлен алгоритм, генерирующий поток случайных событий.

На рис. 28.7 показан результат работы алгоритма — моменты времени, когда детали приходили на операцию. Как видно, всего за период T н = 100 производственный узел обработал N = 33 изделия. Если запустить алгоритм снова, то N может оказаться равным, например, 34, 35 или 32. Но в среднем, за K прогонов алгоритма N будет равно 33.33… Если посчитать расстояния между событиями t сi и моментами времени, определяемыми как 3 · i , то в среднем величина будет равна σ = 3 .

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

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

Допустим, что M k = 10 , σ = 4 (то есть, в среднем в 68 случаях из 100 приходит от 6 до 14 вагонов в составе поезда) и их число распределено по нормальному закону. В место, отмеченное (*) в предыдущем алгоритме (см. рис. 28.6 ), нужно вставить фрагмент, показанный на рис. 28.8 .

Пример 2 . Очень полезным в производстве является решение следующей задачи. Каково среднее время суточного простоя оборудования технологического узла, если узел обрабатывает каждое изделие случайное время, заданное интенсивностью потока случайных событий λ 2 ? При этом экспериментально установлено, что привозят изделия на обработку тоже в случайные моменты времени, заданные потоком λ 1 партиями по 8 штук, причем размер партии колеблется случайно по нормальному закону с m = 8 , σ = 2 (см. лекцию 25). До начала моделирования T = 0 на складе изделий не было. Необходимо промоделировать этот процесс в течение T н = 100 часов.

На рис. 28.9 представлен алгоритм, генерирующий случайным образом поток прихода партий изделий на обработку и поток случайных событий — выхода партий изделий с обработки.

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

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

T пр. ср. = 24 · (t 1 пр. + t 2 пр. + t 3 пр. + t 4 пр. + … + t N пр.)/T н .

Задание 1 . Меняя величину σ , установите зависимость T пр. ср. (σ ) . Задавая стоимость за простой узла 100 евро/час, установите годовые потери предприятия от нерегулярности в работе поставщиков. Предложите формулировку пункта договора предприятия с поставщиками «Величина штрафа за задержку поставки изделий».

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

Моделирование нестационарных потоков событий

В ряде случаев интенсивность потока может меняться со временем λ (t ) . Такой поток называется нестационарным . Например, среднее количество за час машин скорой помощи, покидающих станцию по вызовам населения большого города, в течение суток может быть различным. Известно, например, что наибольшее количество вызовов падает на интервалы с 23 до 01 часа ночи и с 05 до 07 утра, тогда как в остальные часы оно вдвое меньше (см. рис. 28.11 ).

В этом случае распределение λ (t ) может быть задано либо графиком, либо формулой, либо таблицей. А в алгоритме, показанном на рис. 28.6 , в место, помеченное (**), нужно будет вставить фрагмент, показанный на рис. 28.12 .

Потоки событий Это последовательность событий происходящих одно за другим в определенные интервалы времени. 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).

Рассмотрим некоторую физическую систему S={S 1 ,S 2 ,…S n }, которая переходит из состояния в состояние под влиянием каких-то случайных событий (вызовы, отказы, выстрелы). Будем себе это представлять так, будто события, переводящие систему из состояния в состояние, представляют собой какие-то потоки событий.

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

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

Пример. Техническая система S состоит из двух узлов I и II, каждый из которых независимо от другого может отказывать. Поток отказов первого узла пуассоновский с интенсивностью I , второго также пуассоновский с интенсивностью II . Каждый узел сразу после отказа начинает ремонтироваться (восстанавливаться). Поток восстановлений (окончаний ремонта узла) для обоих узлов - пуассоновский с интенсивностью. Составить граф состояний системы и написать уравнение Колмогорова. Состояния системы: S 11 - оба узла исправны; S 21 - первый узел ремонтируется, второй исправен; S 12, S 22 .

t=0 p 11 =1 p 21 =p 22 =p 12 =0

p 11 +p 12 +p 21 +p 22 =1.

Предельные вероятности состояний для непрерывной марковской цепи

Пусть имеется физическая система S={S 1 ,S 2 ,…S n }, в которой протекает марковский случайный процесс с непрерывным временем (непрерывная цепь Маркова). Предположим, что ij =const, т.е. все потоки событий простейшие (стационарные пуассоновские). Записав систему дифференциальных уравнений Колмогорова для вероятностей состояний и проинтегрировав эти уравнения при заданных начальных условиях, мы получим p 1 (t), p 2 (t),… p n (t), при любом t. Поставим следующий вопрос, что будет происходить с системой S при t. Будут ли функции p i (t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными вероятностями состояний. Можно доказать теорему: если число состояний S конечно и из каждого состояния можно перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы. Предположим, что поставленное условие выполнено и предельные вероятности существуют (i=1,2,…n), .

Таким образом, при t в системе S устанавливается некоторый предельный стационарный режим. Смысл этой вероятности: она представляет собой не что иное, как среднее относительное время пребывания системы в данном состоянии. Для вычисления p i в системе уравнений Колмогорова, описывающих вероятности состояний, нужно положить все левые части (производные) равными 0. Систему получающихся линейных алгебраических уравнений надо решать совместно с уравнением.

Схема гибели и размножения

Мы знаем, что имея в распоряжении размеченный граф состояний, можно легко написать уравнения Колмогорова для вероятностей состояний, а также написать и решить алгебраические уравнения для финальных вероятностей. Для некоторых случаев удается последние уравнения решить заранее, в буквенном виде. В частности, это удается сделать, если граф состояний системы представляет собой так называемую «схему гибели и размножения».

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 , ..., S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний -- правым и левым, а крайние состояния (S 0 , S n) -- только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состояний (их существование вытекает из того, что из каждого состояния можно перейти в каждое другое, и число состояний конечно). Для первого состояния S 0 имеем:

Для второго состояния S 1:

В силу (8.1) последнее равенство приводится к виду

где k принимает все значения от 0 до n. Итак, финальные вероятности р 0 , p 1 ,..., р n удовлетворяют уравнениям

кроме того, надо учесть нормировочное условие

p 0 + р 1 + р 2 +…+ р n =1 (8.3)

Решим эту систему уравнений. Из первого уравнения (8.2) выразим р 1 через р 0 .

Из второго, с учетом (8.4), получим:

из третьего, с учетом (8.5),

и вообще, для любого k (от 1 до N):

Обратим внимание на формулу (8.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе -- произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).

Таким образом, все вероятности состояний p 1 , р 2 , …, p n выражены через одну из них (p 0). Подставим эти выражения в нормировочное условие (8.3). Получим, вынося за скобку p 0:

отсюда получим выражение для р 0 .

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (8.4) -- (8.7)). Заметим, что коэффициенты при p 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (8.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.

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

Задачи теории массового обслуживания. Классификация систем массового обслуживания и их основные характеристики

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

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

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

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

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

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

Процесс называется процессом с дискретными состояниями, если его возможные состояния 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 хотя бы одного события потока равна согласно

Цель лекции: освоение понятий поток событий, простейший поток событий, Марковский процесс.

1.Поток событий. Свойства потоков событий. Простейший поток событий. Формула Пуассона.

2. Процесс обслуживания как Марковский процесс.

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

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

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

Поток вызовов на телефонной станции;

Поток сбоев компьютера;

Поток выстрелов, направляемых на цель, и т.д.

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

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

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

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

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

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

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

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

Параметром потока называется предел

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

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

Для стационарного потока его параметр не зависит от времени .

Для стационарного и ординарного потока λ=μ.

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

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

где - интенсивность потока;

Количество событий, появляющихся за время .

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

F(t)=P(zt),

P(z>t) равносильна вероятности того, что в промежутке длиной t не поступит не одного вызова.

F(t)=P(z>t)=1- (t)=1-

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

Свойства и характеристики простейшего потока:

а) для простейшего потока математическое ожидание и среднеквадратическое отклонение величины промежутка z равны между собой MZ= σz=1/λ;

б) Математическое ожидание и дисперсия числа вызовов i за промежуток времени t равны между собой Mi=Di= λt.

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