Основные понятия марковских процессов. Марковский процесс

Структура и классификация систем массового обслуживания

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

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

Билетные кассы;

Ремонтные мастерские;

Торговые, транспортные, энергетические системы;

Системы связи;

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

Рис. 4.1. Основные сферы применения ТМО

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

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

1. Входящий поток требований.

2. Накопитель (очередь).

3. Приборы (каналы обслуживания).

4. Выходящий поток.

Рис. 4.2. Общая схема систем массового обслуживания

Рис. 4.3. Модель работы системы

(стрелками показаны моменты поступления требований в

систему, прямоугольниками – время обслуживания)

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

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

1) системы с отказами , в которых при занятости всех каналов обслуживания заявка покидает систему необслуженной;

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

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

Рассмотрим характеристики входящего потока требований.

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

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



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

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

Интенсивностью потока заявок λ называется среднее число заявок, поступающих из потока за единицу времени.

Для стационарного потока интенсивность постоянна. Если τ – среднее значение интервала времени между двумя соседними заявками, то В случае пуассоновского потока вероятность поступления на обслуживание m заявок за промежуток времени t определяется по закону Пуассона:

Время между соседними заявками распределено по экспоненциальному закону с плотностью вероятности

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

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

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

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

Такие процессы бывают двух типов: с дискретным или непрерывным временем.

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

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

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

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

Переходы системы из состояния в состояние происходит под действием каких-то потоков (поток заявок, поток отказов). Если все потоки событий, приводящие систему в новое состояние, – простейшие пуассоновские, то процесс, протекающий в системе, будет марковским, так как простейший поток не обладает последствием: в нем будущее не зависит от прошлого.

МАРКОВСКИЙ ПРОЦЕСС

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

Определяющее М. п. свойство принято наз. марковским; впервые оно было сформулировано А. А. Марковым . Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское как М. п., попытку, получившую обоснование после исследований Н. Винера (N. Wiener, 1923). Основы общей теории М. п. с непрерывным временем были заложены А. Н. Колмогоровым .

Марковское свойство. Имеются существенно отличающиеся друг от друга определения М. п. Одним из наиболее распространенных является следующее. Пусть на вероятностном пространстве задан случайный процесс со значениями из измеримого пространства где Т - подмножество действительной оси Пусть N t (соответственно N t ).есть s-алгебра в порожденная величинами X(s).при где Другими словами, N t (соответственно N t ) - это совокупность событий, связанных с эволюцией процесса до момента t(начиная с t). Процесс X(t).наз. марковским процессом, если (почти наверное) для всех выполняется марковское свойство:

или, что то же самое, если для любых

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

В дальнейшем для определенности речь будет идти только о случае Формулы (1) и (2) дают ясную интерпретацию принципа независимости "прошлого" и "будущего" при известном "настоящем", но основанное на них определение М. п. оказалось недостаточно гибким в тех многочисленных ситуациях, когда приходится рассматривать не одно, а набор условий типа (1) или (2), отвечающих различным, хотя и согласованным определенным образом, мерам Такого рода соображения привели к принятию следующего определения (см. , ).

Пусть заданы:

а) где s-алгебра содержит все одноточечные множества в Е;

б) измеримое снабженное семейством s-алгебр таких, что если

в) (" ") x t =x t (w), определяющая при любых измеримое отображение

г) для каждых и вероятностная мера на s-алгебре такая, что функция измерима относительно если и

Набор наз. (необрывающимся) марковским процессом, заданным в если -почти наверное

каковы бы ни были Здесь - пространство элементарных событий, - фазовое пространство или пространство состояний, Р(s, x, t, В ) - переходная функция или вероятность перехода процесса X(t). Если Енаделено топологией, а - совокупность борелевских множеств в Е, то принято говорить, что М. п. задан в Е. Обычно в определение М. п. включают требование, чтобы и тогда истолковывается как вероятность при условии, что x s =x.

Возникает вопрос: всякую ли марковскую переходную функцию Р(s, x ; t, В ), заданную в измеримом пространстве можно рассматривать как переходную функцию нек-рого М. п. Ответ положителен, если, напр., Еявляется сепарабельным локально компактным пространством, а - совокупностью борелевских множеств в Е. Более того, пусть Е - полное метрич. пространство и пусть

для любого где
а - дополнение e-окрестности точки х. Тогда соответствующий М. п. можно считать непрерывным справа и имеющим пределы слева (т. е. таковыми можно выбрать его траектории). Существование же непрерывного М. п. обеспечивается условием при (см. , ). В теории М. п. основное внимание уделяется однородным (по времени) процессам. Соответствующее определение предполагает заданной систему объектов а) - г) с той разницей, что для фигурировавших в ее описании параметров sи u теперь допускается лишь значение 0. Упрощаются и обозначения:

Далее, постулируется однородность пространства W, т. е. требуется, чтобы для любых существовало такое что (w) при Благодаря этому на s-алгебре N, наименьшей из s-алгебр в W, содержащих любое событие вида задаются операторы временного сдвига q t , к-рые сохраняют операции объединения, пересечения и вычитания множеств и для к-рых

Набор наз. (необрывающимся) однородным марковским процессом, заданным в если -почти наверное

для Переходной функцией процесса X(t).считается Р(t, x, В ), причем, если нет специальных оговорок, дополнительно требуют, чтобы Полезно иметь в виду, что при проверке (4) достаточно рассматривать лишь множества вида где и что в (4) всегда F t можно заменить s-алгеброй , равной пересечению пополнений F t по всевозможным мерам Нередко в фиксируют вероятностную меру m ("начальное ") и рассматривают марковскую случайную функцию где - мера на заданная равенством

М. п. наз. прогрессивно измеримым, если при каждом t>0 функция индуцирует измеримое в где есть s-алгебра

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

Строго . Пусть в измеримом пространстве задан М. п.

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

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

(строго марковское свойство) выполняется -почти наверное на множестве W t . При проверке (5) достаточно рассматривать лишь множества вида где в этом случае С. м. п. является, напр., любой непрерывный справа феллеровский М. п. в топологич. пространстве Е. М. п. наз. феллеровским марковским процессом, если функция

непрерывна всякий раз, когда f непрерывна и ограничена.

В классе с. м. п. выделяются те или иные подклассы. Пусть марковская Р(t, x, В ), заданная в метрическом локально компактном пространстве Е, стохастически непрерывна:

для любой окрестности Uкаждой точки Тогда если операторы переводят в себя непрерывных и обращающихся в 0 в бесконечности функций, то функции Р(t, х, В ).отвечает стандартный М. п. X, т. е. непрерывный справа с. м. п., для к-рого

и - почти наверное на множестве а - неубывающие с ростом пмарковские моменты.

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

Пусть - однородный М. п. в фазовом пространстве имеющий переходную функцию и пусть существуют точка и функция такие, что при и в противном случае (если нет специальных оговорок, считают ). Новая траектория x t (w) задается лишь для ) посредством равенства a F t определяется как в множестве

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

Марковские процессы и . М. п. типа броуновского движения тесно связаны с дифференциальными уравнениями параболич. типа. Переходная р(s, x, t, у ).диффузионного процесса удовлетворяет при нек-рых дополнительных предположениях обратному и прямому дифференциальным уравнениям Колмогорова:


Функция р(s, x, t, у ).есть функция Грина уравнений (6) - (7), и первые известные способы построения диффузионных процессов были основаны на теоремах существования этой функции для дифференциальных уравнений (6) - (7). Для однородного по времени процесса L(s, x ) = L (x).на гладких функциях совпадает с характеристич. оператором М. п. (см. Переходных операторов полугруппа ).

Математич. ожидания различных функционалов от диффузионных процессов служат решениями соответствующих краевых задач для дифференциального уравнения (1). Пусть - математич. ожидание по мере Тогда функция удовлетворяет при s уравнению (6) и условию

Аналогично, функция

удовлетворяет при s уравнению

и условию и 2 ( Т, x ) = 0.

Пусть тt - момент первого достижения границы дD области траекторией процесса Тогда при нек-рых условиях функция

удовлетворяет уравнению

и принимает значения ср на множестве

Решение 1-й краевой задачи для общего линейного параболич. уравнения 2-го порядка


при довольно общих предположениях может быть записано в виде


В случае, когда Lи функции с, f не зависят от s, аналогичное (9) представление возможно и для решения линейного эллиптич. уравнения. Точнее, функция


при нек-рых предположениях есть задачи

В случае, когдгг оператор Lвырождается (del b(s, х ) = 0 ).или дD недостаточно "хорошая", граничные значения могут и не приниматься функциями (9), (10) в отдельных точках или на целых множествах. Понятие регулярной граничной точки для оператора L имеет вероятностную интерпретацию. В регулярных точках границы граничные значения достигаются функциями (9), (10). Решение задач (8), (11) позволяет изучать свойства соответствующих диффузионных процессов и функционалов от них.

Существуют методы построения М. п., не опирающиеся на построение решений уравнений (6), (7), напр. метод стохастических дифференциальных уравнений, абсолютно непрерывная замена меры и др. Это обстоятельство вместе с формулами (9), (10) позволяет вероятностным путем строить и изучать свойства краевых задач для уравнения (8), а также свойства решении соответствующего эллиптич. уравнения.

Так как решение стохастического дифференциального уравнения нечувствительно к вырождению матрицы b(s, x ), то вероятностные методы применялись для построения решений вырождающихся эллиптических и параболических дифференциальных уравнений. Распространение принципа усреднения Н. М. Крылова и Н. Н. Боголюбова на стохастические дифференциальные уравнения позволило с помощью (9) получить соответствующие результаты для эллиптических и параболических дифференциальных уравнений. Нек-рые трудные задачи исследования свойств решений уравнений такого типа с малым параметром при старшей производной оказалось возможным решить с помощью вероятностных соображений. Вероятностный смысл имеет и решение 2-й краевой задачи для уравнения (6). Постановка краевых задач для неограниченной области тесно связана с возвратностью соответствующего диффузионного процесса.

В случае однородного по времени процесса (Lне зависит от s) положительное решение уравнения с точностью до мультипликативной постоянной совпадает при нек-рых предположениях со стационарной плотностью распределения М. п. Вероятностные соображения оказываются полезными и при рассмотрении краевых задач для нелинейных параболич. уравнений. Р. 3. Хасьминский.

Лит. : Марков А. А., "Изв. физ.-мат. об-ва Казан. ун-та", 1906, т. 15, №4, с. 135-56; В а с h e l i е r L., "Ann. scient. Ecole norm, super.", 1900, v. 17, p. 21-86; Колмогоров А. Н., "Math. Ann.", 1931, Bd 104, S. 415- 458; рус. пер.-"Успехи матем. наук", 1938, в. 5, с. 5-41; Ч ж у н К а й - л а й, Однородные цепи Маркова, пер. с англ., М., 1964; Р е 1 1 е r W., "Ann. Math.", 1954, v. 60, p. 417-36; Д ы н к и н Е. Б., Ю ш к е в и ч А. А., "Теория вероятн. и ее примен.", 1956, т. 1, в. 1, с. 149-55; X а н т Дж.-А., Марковские процессы и потенциалы, пер. с англ., М., 1962; Д е л л а ш е р и К., Емкости и случайные процессы, пер. с франц., М., 1975; Д ы н к и н Е. В., Основания теории марковских процессов, М., 1959; его же, Марковские процессы, М., 1963; Г и х м а н И. И., С к о р о х о д А. В., Теория случайных процессов, т. 2, М., 1973; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, . - Теоретическая . 1966, М., 1967, с. 7-58; X а с ь м и н с к и й Р. 3., "Теория вероятн. и ее примен.", 1963, т. 8, в

    Марковский процесс - дискретный или непрерывный случайный процесс X(t) , который можно полностью задать с помощью двух величин: вероятности P(x,t) того, что случайная величина x(t) в момент времени t равна x и вероятности P(x2, t2½x1t1) того, что… … Экономико-математический словарь

    Марковский процесс - Дискретный или непрерывный случайный процесс X(t) , который можно полностью задать с помощью двух величин: вероятности P(x,t) того, что случайная величина x(t) в момент времени t равна x и вероятности P(x2, t2?x1t1) того, что если x при t = t1… … Справочник технического переводчика

    Важный специальный вид случайных процессов. Примером марковского процесса может служить распад радиоактивного вещества, где вероятность распада данного атома за малый промежуток времени не зависит от течения процесса в предшествующий период.… … Большой Энциклопедический словарь - Markovo procesas statusas T sritis automatika atitikmenys: angl. Markovprocess vok. Markovprozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus markovien, m … Automatikos terminų žodynas

    марковский процесс - Markovo vyksmas statusas T sritis fizika atitikmenys: angl. Markov process; Markovian process vok. Markow Prozeß, m; Markowscher Prozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus de Markoff, m; processus marcovien, m;… … Fizikos terminų žodynas

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

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

    Выдающееся открытие в области математики, сделанное в 1906 русским ученым А.А. Марковым.

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

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

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

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

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

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

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

Обозначим через g (t ) случайный процесс с дискретными состояниями, а возможные значенияg (t ), т.е. возможные состояния цепи, - через символыE 0 , E 1 , E 2 , … . Иногда для обозначения дискретных состояний используют числа 0, 1, 2,... из натурального ряда.

Случайный процесс g (t ) называетсяпроцессом с дискретным временем , если переходы процесса из состояния в состояние возможны только в строго определенные, заранее фиксированные моменты времениt 0 , t 1 , t 2 , … . Если переход процесса из состояния в состояние возможен в любой, заранее неизвестный момент времени, то случайный процесс называетсяпроцессом с непрерывным временем . В первом случае, очевидно, что интервалы времени между переходами являются детерминированными, а во втором - случайными величинами.

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

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

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

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

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

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

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

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

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

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

Лекция 9

Марковские процессы
Лекция 9
Марковские процессы



1

Марковские процессы

Марковские процессы
Случайный процесс, протекающий в системе, называется
марковским, если он обладает отсутствием последствия. Т.е.
если рассматривать текущее состояние процесса (t 0) - как
настоящее, совокупность возможных состояний { (s),s t} - как
прошлое, совокупность возможных состояний { (u),u t} - как
будущее, то для марковского процесса при фиксированном
настоящем будущее не зависит от прошлого, а определяется
лишь настоящим и не зависит от того, когда и как система
пришла в это состояние.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
2

Марковские процессы

Марковские процессы
Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова, впервые начавшего изучение вероятностной связи случайных величин
и создавшего теорию, которую можно назвать "динамикой
вероятностей". В дальнейшем основы этой теории явились
исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
3

Марков Андрей Андреевич Марков Андрей Андреевич Марков Андрей Андреевич

Марковские процессы
Марков Андрей Андреевич
1856-1922
Русский математик.
Написал около 70 работ по
теории
чисел,
теории
приближения функций, теории
вероятностей. Существенно расширил сферу применения закона
больших чисел и центральной
предельной теоремы. Является
основоположником теории случайных процессов.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
4

Марковские процессы

Марковские процессы
На практике марковские процессы в чистом виде обычно
не встречаются. Но имеются процессы, для которых влиянием «предыстории» можно пренебречь, и при изучении
таких процессов можно применять марковские модели. В
настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
5

Марковские процессы

Марковские процессы
Биология: процессы рождения и гибели - популяции, мутации,
эпидемии.
Физика:
радиоактивные
распады,
теория
счетчиков
элементарных частиц, процессы диффузии.
Химия:
теория
следов
в
ядерных
фотоэмульсиях,
вероятностные модели химической кинетики.
Images.jpg
Астрономия: теория флуктуационной
яркости млечного пути.
Теория массового обслуживания: телефонные станции,
ремонтные мастерские, билетные кассы, справочные бюро,
станочные и другие технологические системы, системы управления
гибких производственных систем, обработка информации серверами.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
6

Марковские процессы

Марковские процессы
Пусть в настоящий момент t0 система находится в
определенном состоянии S0. Мы знаем характеристики
состояния системы в настоящем и все, что было при t < t0
(предысторию процесса). Можем ли мы предсказать будущее,
т.е. что будет при t > t0?
В точности – нет, но какие-то вероятностные характеристики
процесса в будущем найти можно. Например, вероятность того,
что через некоторое время
система S окажется в состоянии
S1 или останется в состоянии S0 и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
7

Марковские процессы. Пример.

Марковские процессы
Марковские процессы. Пример.
Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество
«красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохранившихся (не сбитых) самолетов
соответственно – x0, y0.
Нас интересует вероятность того, что в момент времени
t 0 численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система
в момент времени t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
8

Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Марковский процесс с конечным или счетным числом
состояний и моментов времени называется дискретной
цепью Маркова. Переходы из состояния в состояние возможны только в целочисленные моменты времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
9

10. Дискретные цепи Маркова. Пример

Марковские процессы

Предположим,
что
речь
идет
о
последовательных бросаниях монеты при
игре "в орлянку"; монета бросается в
условные моменты времени t =0, 1, ... и на
каждом шаге игрок может выиграть ±1 с
одинаковой
вероятностью
1/2,
таким
образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... .
При условии, что ξ(t) = k, на следующем шаге выигрыш будет
уже равен ξ(t+1) = k ± 1, принимая значения j = k ± 1 c одинаковой вероятностью 1/2. Можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
10

11. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Обобщая этот пример, можно представить себе систему со
счетным числом возможных состояний, которая с течением
дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов
ξ(0) -> ξ(1) -> ... -> ξ(t) -> ξ(t+1) ->...-> ... .
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
11

12. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом
состояний. Вершины графа – состояния системы. Дуги графа
– возможные переходы из состояния в состояние.
Игра «в орлянку».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
12

13. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Обозначим все возможные состояния целыми i = 0, ±1, ...
Предположим, что при известном состоянии ξ(t) =i на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
P{ (t 1) j (t) i}
независимо от ее поведения в прошлом, точнее, независимо
от цепочки переходов до момента t:
P{ (t 1) j (t) i; (t 1) it 1;...; (0) i0 }
P{ (t 1) j (t) i}
Это свойство называется марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
13

14. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Число
pij P{ (t 1) j (t) i}
называется вероятностью
перехода системы из состояния i в состояние j за один шаг в
момент времени t 1.
Если переходная вероятность не зависит от t , то цепь
Маркова называется однородной.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
14

15. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Матрица P , элементами которой являются вероятности
перехода pij , называется переходной матрицей:
p11 ... p1n
P p 21 ... p 2n
p
n1 ... p nn
Она является стохастической, т.е.
pij 1 ;
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p ij 0 .
15

16. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Матрица переходов для игры «в орлянку»
...
k 2
k 2
0
k 1
1/ 2
k
0
k 1
k
k 1
k 2
0
1/ 2
0
0
1/ 2
0
1/ 2
0
1/ 2
0
0
0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
...
k 1 k 2
0
0
0
1/ 2
0
1/ 2
...
0
0
1/ 2
0
16

17. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Садовник в результате химического анализа почвы оценивает
ее состояние одним из трех чисел - хорошее (1), удовлетворительное (2) или плохое (3). В результате наблюдений на протяжении многих лет садовник заметил,
что продуктивность почвы в текущем
году зависит только от ее состояния в
предыдущем году. Поэтому вероятности
перехода почвы из одного состояния в
другое можно представить следующей
цепью Маркова с матрицей P1:
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
17

18. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Однако в результате агротехнических мероприятий садовник может изменить переходные вероятности в матрице P1.
Тогда матрица P1 заменится
на матрицу P2:
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
18

19. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Рассмотрим, как изменяются состояния процесса с течением времени. Будем рассматривать процесс в последовательные моменты времени, начиная с момента 0. Зададим начальное распределение вероятностей p(0) { p1 (0),..., pm (0)} , где m число состояний процесса, pi (0) - вероятность нахождения
процесса в состоянии i в начальный момент времени. Вероятность pi (n) называется безусловной вероятностью состояния
i в момент времени n 1.
Компоненты вектора p (n) показывают, какие из возможных состояний цепи в момент времени n являются наиболее
вероятными.
m
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
pk (n) 1
k 1
19

20. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Знание последовательности { p (n)} при n 1,... позволяет составить представление о поведении системы во времени.
В системе с 3-мя состояниями
p11 p12 p13
P p21
p
31
p22
p32
p23
p33
p2 (1) p1 (0) p12 p2 (0) p22 p3 (0) p32
p2 (n 1) p1 (n) p12 p2 (n) p22 p3 (n) p32
В общем случае:
p j (1) pk (0) pkj
p j (n 1) pk (n) pkj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
k
p(n 1) p(n) P
20

21. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Матрица
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
Шаг
{ p (n)}
n
0
1, 0, 0
n
1
0.2 , 0.5 , 0.3
n
2
0.04 , 0.35 , 0.61
n
3
0.008 , 0.195 , 0.797
n
4
0.0016 , 0.1015 , 0.8969
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
21

22. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
n
Матрица перехода за n шагов P(n) P .
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
p(2) p(0) P
2
p (2)
P(2) P 2
1, 0, 0
0.0016
0.
0.
0.0016
0.
0.
0.1015
0.0625
0.
0.1015
0.0625
0.
0.8969
0.9375
1.
0.8969
0.9375
1.
0.04 , 0.35 , 0.61
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
22

23. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Как ведут себя марковские цепи при n ?
Для однородной марковской цепи при определенных условиях выполняется следующее свойство: p (n) при n .
Вероятности 0 не зависят от начального распределения
p(0) , а определяются только матрицей P . В этом случае называется стационарным распределением, а сама цепь – эргодической. Свойство эргодичности означает, что по мере увеличения n
вероятность состояний практически перестаёт изменяться, а система переходит в стабильный режим функционирования.
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
23

24. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
0 0 1
P() 0 0 1
0 0 1
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p () (0,0,1)
24

25. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
0.1017 0.5254 0.3729
P() 0.1017 0.5254 0.3729
0.1017 0.5254 0.3729
p () (0.1017,0.5254,0.3729)
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
25

26. Марковские процессы с непрерывным временем

Марковские процессы

Процесс называется процессом с непрерывным временем, если
моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти
в любой момент.
Пример. Технологическая система S состоит из двух устройств,
каждое из которых в случайный момент времени может выйти из
строя, после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время.
Возможны следующие состояния системы:
S0 - оба устройства исправны;
S1 - первое устройство ремонтируется, второе исправно;
S2 - второе устройство ремонтируется, первое исправно;
S3 - оба устройства ремонтируются.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
26

27. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Переходы системы S из состояния в состояние происходят
практически мгновенно, в случайные моменты выхода из строя
того или иного устройства или
окончания ремонта.
Вероятностью одновременного
выхода из строя обоих устройств
можно пренебречь.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
27

28. Потоки событий

Марковские процессы
Потоки событий
Поток событий – последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени.
– это среднее число событий,
Интенсивность потока событий
приходящееся на единицу времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
28

29. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.
В частности, интенсивность
стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера, и среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
29

30. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется потоком без последствий, если для
любых двух непересекающихся участков времени и число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Другими словами, это означает, что события, образующие поток, появляются в те или иные моменты
времени независимо друг от друга и вызваны каждое своими собственными причинами.
Поток событий называется ординарным, если вероятность появления на элементарном участке t двух и более событий пренебрежимо мала по сравнению с вероятностью появления одного
события, т.е. события в нем появляются поодиночке, а не группами по нескольку сразу
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
30

31. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: 1) стационарен, 2) ординарен, 3) не имеет последствий.
Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую
роль, как и закон нормального распределения среди других
законов распределения. А именно, при наложении достаточно большого числа независимых, стационарных и ординарных
потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
31

32. Потоки событий

Марковские процессы
Потоки событий
Для простейшего потока с интенсивностью
интервал
времени T между соседними событиями имеет показательное
распределение с плотностью
p(x) e x , x 0 .
Для случайной величины T, имеющей показательное распределение, математическое ожидание есть величина, обратная параметру.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
32

33. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Рассматривая процессы с дискретными состояниями и непрерывным временем, можно считать, что все переходы системы S из состояния в состояние происходят под действием
простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.).
Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в
системе, будет марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
33

34. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Пусть на систему, находящуюся в состоянии, действует
простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния
в состояние.
- интенсивность потока событий, переводящий систему
из состояния
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
в
.
34

35. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Пусть рассматриваемая система S имеет
возможных состояний
. Вероятность p ij (t) является вероятностью перехода из состояния i в состояние j за время t.
Вероятность i - го состояния
- это вероятность того,
что в момент времени t система будет находиться в состоянии
. Очевидно, что для любого момента времени сумма
всех вероятностей состояний равна единице:
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
35

36. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Для нахождения всех вероятностей состояний
как
функций времени составляются и решаются дифференциальные уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний.
Для переходных вероятностей:
p ij (t) p ik (t) kj
k
Для безусловных вероятностей:
p j (t) p k (t) kj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
36

37. Колмогоров Андрей Николаевич

Марковские процессы
Колмогоров Андрей Николаевич
1903-1987
Великий русский
математик.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
37

38. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
- интенсивности потока отказов;
- интенсивности потока восстановлений.
Пусть система находится в состоянии
S0. В состояние S1 ее переводит поток
отказов первого устройства. Его интенсивность равна
где
- среднее время безотказной работы устройства.
Из состояния S1 в S0 систему переводит поток восстановлений
первого устройства. Его интенсивность равна
где
- среднее время ремонта первого станка.
Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем дугам графа.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
38

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

Марковские процессы

Примеры систем массового обслуживания (СМО): телефонные станции, ремонтные мастерские,
билетные
кассы,
справочные
бюро,
станочные и другие технологические системы,
системы
управления
гибких
производственных систем,
обработка информации серверами и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
39

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

Марковские процессы
Системы массового обслуживания
СМО состоит из какого – то количества обслуживающих
единиц, которые называются каналами обслуживания (это
станки, роботы, линии связи, кассиры и т.д.). Всякая СМО
предназначена для обслуживания потока заявок (требований), поступающих в случайные моменты времени.
Обслуживание заявки продолжается случайное время, после чего канал освобождается и готов к приему следующей
заявки.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
40

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

Марковские процессы
Системы массового обслуживания
Процесс работы СМО – случайный процесс с дискретными
состояниями и непрерывным временем. Состояние СМО меняется скачком в моменты появления каких - то событий
(прихода новой заявки, окончания обслуживания, момента,
когда заявка, которой надоело ждать, покидает очередь).
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
41

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

Марковские процессы
Системы массового обслуживания
Классификация систем массового обслуживания
1. СМО с отказами;
2. СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не
обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости
от того, как организована очередь – ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени
ожидания, «дисциплины обслуживания».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
42

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

Марковские процессы
Системы массового обслуживания
Предмет теории массового обслуживания – построение
математических моделей, связывающих заданные условия
работы СМО (число каналов, их производительность, правила
работы, характер потока заявок) с интересующими нас характеристиками – показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком
заявок. Ими могут быть: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
43

44.

СПАСИБО
ЗА ВНИМАНИЕ!!!
44

45. Построить граф переходов

Марковские процессы
Построить граф переходов
0.30
0.70
0.0
0.10
0.60
0.30
0.50
0.50
0.0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
Поделиться: