Теория марковских случайных процессов. Основные понятия марковских процессов
Теория массового обслуживания составляет один из разделов теории вероятностей. В этой теории рассматриваются вероятностные задачи и математические модели (до этого нами рассматривались детерминированные математические модели). Напомним, что:
Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позицийполной определенности в настоящем и будущем.
Вероятностная математическая модель учитывает влияние случайных факторов на поведение объекта (системы, процесса) и, следовательно, оценивает будущее с позиций вероятности тех или иных событий.
Т.е. здесь как, например, в теории игр задачи рассматриваются в условиях неопределенности .
Рассмотрим сначала некоторые понятия, которые характеризуют «стохастическую неопределенность», когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность называют еще «благоприятной», «доброкачественной».
Понятие случайного процесса
Строго говоря, случайные возмущения присущи любому процессу. Проще привести примеры случайного, чем «неслучайного» процесса. Даже, например, процесс хода часов (вроде бы это строгая выверенная работа – «работает как часы») подвержен случайным изменениям (уход вперед, отставание, остановка). Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.
Пусть имеется некоторая система 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 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.
МАРКОВСКИЙ ПРОЦЕСС
Процесс без последействия, - случайный процесс ,
эволюция к-рого после любого заданного значения временного параметра 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
Аналогично, функция
удовлетворяет при 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 русским ученым А.А. Марковым.
Для системы массового обслуживания характерен случайный процесс. Изучение случайного процесса, протекающего в системе, выражение его математически и является предметом теории массового обслуживания.
Математический анализ работы системы массового обслуживания значительно облегчается, если случайный процесс этой работы является марковским. Процесс, протекающий в системе, называется марковским, если в любой момент времени вероятность любого состояния системы в будущем зависит только от состояния системы в текущий момент и не зависит от того, каким образом система пришла в это состояние. При исследовании экономических систем наибольшее применение имеют марковские случайные процессы с дискретными и непрерывными состояниями.
Случайный процесс называется процессом с дискретными состояниями, если все его возможные состояния можно заранее перечислить, а сам процесс состоит в том, что время от времени система скачком переходит из одного состояния в другое.
Случайный процесс называется процессом с непрерывным состоянием, если для него характерен плавный, постепенный переход из состояния в состояние.
Также можно выделить марковские процессы с дискретным и непрерывным временем. В первом случае переходы системы из одного состояния в другое возможны только в строго определенные, заранее фиксированные моменты времени. Во втором случае переход системы из состояния в состояние возможен в любой, заранее неизвестный, случайный момент. Если вероятность перехода не зависит от времени, то марковский процесс называют однородным.
В исследовании систем массового обслуживания большое значение имеют случайные марковские процессы с дискретными состояниями и непрерывным временем.
Исследование марковских процессов сводится к изучению матриц переходных вероятностей (). Каждый элемент такой матрицы (поток событий) представляет собой вероятность перехода из заданного состояния (которому соответствует строка) к следующему состоянию (которому соответствует столбец). В этой матрице предусмотрены все возможные переходы данного множества состояний. Следовательно, процессы, которые можно описывать и моделировать с помощью матриц переходных вероятностей, должны обладать зависимостью вероятности конкретного состояния от непосредственно предшествующего состояния. Так выстраивается цепь Маркова. При этом цепью Маркова первого порядка называется процесс, для которого каждое конкретное состояние зависит только от его предшествующего состояния. Цепью Маркова второго и более высоких порядков называется процесс, в котором текущее состояние зависит от двух и более предшествующих.
Ниже представлены два примера матриц переходных вероятностей.
Матрицы переходных вероятностей можно изобразить графами переходных состояний, как показано на рисунке.
Пример
Предприятие выпускает продукт, насытивший рынок. Если предприятие от реализации продукта в текущем месяце получит прибыль (П), то с вероятностью 0,7 получит прибыль и в следующем месяце, а с вероятностью 0,3 – убыток. Если в текущем месяце предприятие получит убыток (У), то с вероятностью 0,4 в следующем месяце оно получит прибыль, а с вероятностью 0,6 – убыток (вероятностные оценки получены в результате опроса экспертов). Рассчитать вероятностную оценку получения прибыли от реализации товара через два месяца работы предприятия.
В матричной форме эта информация будет выражена следующим образом (что соответствует примеру матрицы 1):
Первая итерация – построение матрицы двухступенчатых переходов.
Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно снова получит прибыль, равна
Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно получит убыток, равна
Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно получит прибыль, равна
Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно вновь получит убыток, равна
В результате расчетов получаем матрицу двухступенчатых переходов:
Результат достигается перемножением матрицы т,на матрицу с такими же значениями вероятностей:
Для проведения этих процедур в среде Excel необходимо выполнить следующие действия:
- 1) формировать матрицу;
- 2) вызывать функцию МУМНОЖ;
- 3) указывать первый массив – матрицу;
- 4) указывать второй массив (эта же матрица или другая);
- 5) ОК;
- 6) выделить зону новой матрицы;
- 7) F2;
- 8) Ctrl+Shift+Enter;
- 9) получить новую матрицу.
Вторая итерация – построение матрицы трехступенчатых переходов. Аналогично рассчитываются вероятности получения прибыли или убытка на следующем шаге и рассчитывается матрица трехступенчатых переходов, она имеет следующий вид:
Таким образом, в ближайшие два месяца работы предприятия вероятность получения прибыли от выпуска продукта выше, по сравнению с вероятностью получения убытка. Однако следует заметить, что вероятность получения прибыли падает, поэтому предприятию необходимо осуществить разработку нового продукта для замены производимого продукта.
Структура и классификация систем массового обслуживания
Системы массового обслуживания
Нередко возникает необходимость в решении вероятностных задач, связанных с системами массового обслуживания (СМО), примерами которых могут быть:
Билетные кассы;
Ремонтные мастерские;
Торговые, транспортные, энергетические системы;
Системы связи;
Общность таких систем выявляется в единстве математических методов и моделей, применяемых при исследовании их деятельности.
Рис. 4.1. Основные сферы применения ТМО
На вход в СМО поступает поток требований на обслуживание. Например, клиенты или пациенты, поломки в оборудовании, телефонные вызовы. Требования поступают нерегулярно, в случайные моменты времени. Случайный характер носит и продолжительность обслуживания. Это создает нерегулярность в работе СМО, служит причиной ее перегрузок и недогрузок.
Системы массового обслуживания обладают различной структурой, но обычно в них можно выделить четыре основных элемента :
1. Входящий поток требований.
2. Накопитель (очередь).
3. Приборы (каналы обслуживания).
4. Выходящий поток.
Рис. 4.2. Общая схема систем массового обслуживания
Рис. 4.3. Модель работы системы
(стрелками показаны моменты поступления требований в
систему, прямоугольниками – время обслуживания)
На рис.4.3 а представлена модель работы системы с регулярным потоком требований. Поскольку известен промежуток между поступлениями требований, то время обслуживания выбрано так, чтобы полностью загрузить систему. Для системы со стохастическим потоком требований ситуация совершенно иная – требования приходят в различные моменты времени и время обслуживания тоже является случайной величиной, которое может быть описано неким законом распределения (рис.4.3 б).
В зависимости от правил образования очереди различают следующие СМО:
1) системы с отказами , в которых при занятости всех каналов обслуживания заявка покидает систему необслуженной;
2) системы с неограниченной очередью , в которых заявка встает в очередь, если в момент ее поступления все каналы обслуживания были заняты;
3) системы с ожиданием и ограниченной очередью , в которых время ожидания ограниченно какими-либо условиями или существуют ограничения на число заявок, стоящих в очереди.
Рассмотрим характеристики входящего потока требований.
Поток требований называется стационарным , если вероятность попадания того или иного числа событий на участок времени определенной длины зависит только от длины этого участка.
Поток событий называется потоком без последствий , если число событий, попадающих на некоторый участок времени, не зависит от числа событий, попадающих на другие.
Поток событий называется ординарным , если невозможно одновременное поступление двух или более событий.
Поток требований называется пуассоновским (или простейшим), если он обладает тремя свойствами: стационарен, ординарен и не имеет последствий. Название связано с тем, что при выполнении указанных условий число событий, попадающих на любой фиксированный интервал времени, будет распределен по закону Пуассона.
Интенсивностью потока заявок λ называется среднее число заявок, поступающих из потока за единицу времени.
Для стационарного потока интенсивность постоянна. Если τ – среднее значение интервала времени между двумя соседними заявками, то В случае пуассоновского потока вероятность поступления на обслуживание m заявок за промежуток времени t определяется по закону Пуассона:
Время между соседними заявками распределено по экспоненциальному закону с плотностью вероятности
Время обслуживания является случайной величиной и подчиняется показательному закону распределения с плотностью вероятности 
где μ – интенсивность потока обслуживания, т.е. среднее число заявок, обслуживаемых в единицу времени,
Отношение интенсивности входящего потока к интенсивности потока обслуживания называется загрузкой системы
Система массового обслуживания представляет собой систему дискретного типа с конечным или счетным множеством состояний, а переход системы из одного состояния в другое происходит скачком, когда осуществляется какое-нибудь событие.
Процесс называется процессом с дискретными состояниями , если его возможные состояния можно заранее перенумеровать, и переход системы из состояния в состояние происходит практически мгновенно.
Такие процессы бывают двух типов: с дискретным или непрерывным временем.
В случае дискретного времени переходы из состояния в состояние могут происходить в строго определенные моменты времени. Процессы с непрерывным временем отличаются тем, что переход системы в новое состояние возможен в любой момент времени.
Случайным процессом называется соответствие, при котором каждому значению аргумента (в данном случае – моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае – состояние СМО). Случайной величиной называется величина, которая в результате опыта может принять одно, но неизвестное заранее, какое именно, числовое значение из данного числового множества.
Поэтому для решения задач теории массового обслуживания необходимо этот случайный процесс изучить, т.е. построить и проанализировать его математическую модель.
Случайный процесс называется марковским , если для любого момента времени вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент и не зависят от того, когда и как система пришла в это состояние.
Переходы системы из состояния в состояние происходит под действием каких-то потоков (поток заявок, поток отказов). Если все потоки событий, приводящие систему в новое состояние, – простейшие пуассоновские, то процесс, протекающий в системе, будет марковским, так как простейший поток не обладает последствием: в нем будущее не зависит от прошлого.
Очень удобно описывать появление случайных событий в виде вероятностей переходов из одного состояния системы в другое, так как при этом считается, что, перейдя в одно из состояний, система не должна далее учитывать обстоятельства того, как она попала в это состояние.
Случайный процесс называется марковским процессом (или процессом без последействия ), если для каждого момента времени t вероятность любого состояния системы в будущем зависит только от ее состояния в настоящем и не зависит от того, как система пришла в это состояние.
Итак, марковский процесс удобно задавать графом переходов из состояния в состояние. Мы рассмотрим два варианта описания марковских процессов с дискретным и непрерывным временем .
В первом случае переход из одного состояния в другое происходит в заранее известные моменты времени такты (1, 2, 3, 4, ). Переход осуществляется на каждом такте, то есть исследователя интересует только последовательность состояний, которую проходит случайный процесс в своем развитии, и не интересует, когда конкретно происходил каждый из переходов.
Во втором случае исследователя интересует и цепочка меняющих друг друга состояний, и моменты времени, в которые происходили такие переходы.
И еще. Если вероятность перехода не зависит от времени, то марковскую цепь называют однородной .
Марковский процесс с дискретным временем
Итак, модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.1 .
Каждый переход характеризуется вероятностью перехода P ij . Вероятность P ij показывает, как часто после попадания в i -е состояние осуществляется затем переход в j -е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.
Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие состояния должна быть всегда равна 1 (см. рис. 33.2 ).
(переходы из i-го состояния являются
полной группой случайных событий)
Например, полностью граф может выглядеть так, как показано на рис. 33.3 .
 |
Реализация марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние (см. рис. 33.4 ). Цепь на рис. 33.4 является случайной последовательностью и может иметь также и другие варианты реализации.
по марковскому графу, изображенному на рис. 33.3
Чтобы определить, в какое новое состояние перейдет процесс из текущего i -го состояния, достаточно разбить интервал на подынтервалы величиной P i 1 , P i 2 , P i 3 , (P i 1 + P i 2 + P i 3 + = 1 ), см. рис. 33.5 . Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале случайное число r рр и определить, в какой из интервалов оно попадает (см. лекцию 23).
состояния марковской цепи в j-е с использованием
генератора случайных чисел
После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной процедуры для нового состояния. Результатом работы модели является марковская цепь (см. рис. 33.4 ) .
Пример. Имитация стрельбы из пушки по цели . Для того, чтобы проимитировать стрельбу из пушки по цели, построим модель марковского случайного процесса.
Определим следующие три состояния: S 0 цель не повреждена; S 1 цель повреждена; S 2 цель разрушена. Зададим вектор начальных вероятностей:
| S 0 | S 1 | S 2 | |
| P 0 | 0.8 | 0.2 | 0 |
Значение P 0 для каждого из состояний показывает, какова вероятность каждого из состояний объекта до начала стрельбы.
Зададим матрицу перехода состояний (см. табл. 33.1).
| Таблица 33.1. Матрица вероятностей перехода дискретного марковского процесса |
|||||||||||||||||||
| В S 0 | В S 1 | В S 2 | Сумма вероятностей переходов |
|
| Из S 0 | 0.45 | 0.40 | 0.15 | 0.45 + 0.40 + 0.15 = 1 |
| Из S 1 | 0 | 0.45 | 0.55 | 0 + 0.45 + 0.55 = 1 |
| Из S 2 | 0 | 0 | 1 | 0 + 0 + 1 = 1 |
Матрица задает вероятность перехода из каждого состояния в каждое. Заметим, что вероятности заданы так, что сумма вероятностей перехода из некоторого состояния в остальные всегда равна единице (куда-то система должна перейти обязательно).
Наглядно модель марковского процесса можно представить себе в виде следующего графа (см. рис. 33.6 ).
моделирующий стрельбу из пушки по цели
Используя модель и метод статистического моделирования, попытаемся решить следующую задачу: определить среднее количество снарядов, необходимое для полного разрушения цели.
Проимитируем, используя таблицу случайных чисел, процесс стрельбы. Пусть начальное состояние будет S 0 . Возьмем последовательность из таблицы случайных чисел: 0.31, 0.53, 0.23, 0.42, 0.63, 0.21, (случайные числа можно взять, например, из этой таблицы).
0.31
: цель находится в состоянии
S
0
и остается в состоянии
S
0
, так как
0 < 0.31
< 0.45;
0.53
: цель находится в состоянии
S
0
и переходит в состояние
S
1
,
так как
0.45 < 0.53
< 0.45 + 0.40;
0.23
: цель находится в состоянии
S
1
и остается в состоянии
S
1
,
так как
0 < 0.23
< 0.45;
0.42
: цель находится в состоянии
S
1
и остается в состоянии
S
1
,
так как
0 < 0.42
< 0.45;
0.63
: цель находится в состоянии
S
1
и переходит в состояние
S
2
,
так как
0.45 < 0.63
< 0.45 + 0.55.
Так как достигнуто состояние S 2 (далее цель переходит из S 2 в состояние S 2 с вероятностью 1), то цель поражена. Для этого в данном эксперименте потребовалось 5 снарядов.
На рис. 33.7 приведена временная диаграмма, которая получается во время описанного процесса моделирования. Диаграмма показывает, как во времени происходит процесс изменения состояний. Такт моделирования для данного случая имеет фиксированную величину. Нам важен сам факт перехода (в какое состояние переходит система) и не важно, когда это происходит.
 |
в марковском графе (пример имитации)
Процедура уничтожения цели совершена за 5 тактов, то есть марковская цепь этой реализации выглядит следующим образом: S 0 S 0 S 1 S 1 S 1 S 2 . Конечно, ответом задачи это число быть не может, так как в разных реализациях получатся разные ответы. А ответ у задачи может быть только один.
Повторяя данную имитацию, можно получить, например, еще такие реализации (это зависит от того, какие конкретно случайные числа выпадут): 4 (S 0 S 0 S 1 S 1 S 2 ); 11 (S 0 S 0 S 0 S 0 S 0 S 1 S 1 S 1 S 1 S 1 S 1 S 2 ); 5 (S 1 S 1 S 1 S 1 S 1 S 2 ); 6 (S 0 S 0 S 1 S 1 S 1 S 1 S 2 ); 4 (S 1 S 1 S 1 S 1 S 2 ); 6 (S 0 S 0 S 1 S 1 S 1 S 1 S 2 ); 5 (S 0 S 0 S 1 S 1 S 1 S 2 ). Всего уничтожено 8 целей. Среднее число циклов в процедуре стрельбы составило: (5 + 4 + 11 + 5 + 6 + 4 + 6 + 5)/8 = 5.75 или, округляя, 6. Именно столько снарядов, в среднем, рекомендуется иметь в боевом запасе пушки для уничтожения цели при таких вероятностях попаданий.
Теперь следует определить точность. Именно точность может нам показать, насколько следует доверять данному ответу. Для этого проследим, как сходится последовательность случайных (приближенных) ответов к правильному (точному) результату. Напомним, что, согласно центральной предельной теореме (см. лекцию 25 , лекцию 21), сумма случайных величин есть величина неслучайная, поэтому для получения статистически достоверного ответа необходимо следить за средним числом снарядов, получаемых в ряде случайных реализаций.
На первом этапе вычислений средний ответ составил 5 снарядов, на втором этапе средний ответ составил (5 + 4)/2 = 4.5 снаряда, на третьем (5 + 4 + 11)/3 = 6.7. Далее ряд средних величин, по мере накопления статистики, выглядит следующим образом: 6.3, 6.2, 5.8, 5.9, 5.8. Если изобразить этот ряд в виде графика средней величины выпущенных снарядов, необходимых для поражения цели, в зависимости от номера эксперимента, то обнаружится, что данный ряд сходится к некоторой величине, которая и является ответом (см. рис. 33.8 ).
Визуально мы можем наблюдать, что график «успокаивается», разброс между вычисляемой текущей величиной и ее теоретическим значением со временем уменьшается, стремясь к статистически точному результату. То есть в некоторый момент график входит в некоторую «трубку», размер которой и определяет точность ответа.
Алгоритм имитации будет иметь следующий вид (см. рис. 33.9).
Еще раз заметим, что в вышерассмотренном случае нам безразлично, в какие моменты времени будет происходить переход. Переходы идут такт за тактом. Если важно указать, в какой именно момент времени произойдет переход, сколько времени система пробудет в каждом из состояний, требуется применить модель с непрерывным временем.
Марковские случайные процессы с непрерывным временем
Итак, снова модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.10 .
 |
процесса с непрерывным временем
Теперь каждый переход характеризуется плотностью вероятности перехода λ ij . По определению:
При этом плотность понимают как распределение вероятности во времени.
Переход из i -го состояния в j -е происходит в случайные моменты времени, которые определяются интенсивностью перехода λ ij .
К интенсивности переходов (здесь это понятие совпадает по смыслу с распределением плотности вероятности по времени t ) переходят, когда процесс непрерывный, то есть, распределен во времени.
С интенсивностью потока (а переходы это поток событий) мы уже научились работать в лекции 28 . Зная интенсивность λ ij появления событий, порождаемых потоком, можно сымитировать случайный интервал между двумя событиями в этом потоке.
где τ ij интервал времени между нахождением системы в i -ом и j -ом состоянии.
Далее, очевидно, система из любого i -го состояния может перейти в одно из нескольких состояний j , j + 1 , j + 2 , , связанных с ним переходами λ ij , λ ij + 1 , λ ij + 2 , .
В j -е состояние она перейдет через τ ij ; в (j + 1 )-е состояние она перейдет через τ ij + 1 ; в (j + 2 )-е состояние она перейдет через τ ij + 2 и т. д.
Ясно, что система может перейти из i -го состояния только в одно из этих состояний, причем в то, переход в которое наступит раньше.
Поэтому из последовательности времен: τ ij , τ ij + 1 , τ ij + 2 и т. д. надо выбрать минимальное и определить индекс j , указывающий, в какое именно состояние произойдет переход.
Пример. Моделирование работы станка . Промоделируем работу станка (см. рис. 33.10 ), который может находиться в следующих состояниях: S 0 станок исправен, свободен (простой); S 1 станок исправен, занят (обработка); S 2 станок исправен, замена инструмента (переналадка) λ 02 < λ 21 ; S 3 станок неисправен, идет ремонт λ 13 < λ 30 .
Зададим значения параметров λ , используя экспериментальные данные, получаемые в производственных условиях: λ 01 поток на обработку (без переналадки); λ 10 поток обслуживания; λ 13 поток отказов оборудования; λ 30 поток восстановлений.
Реализация будет иметь следующий вид (см. рис. 33.11 ).
марковского процесса с визуализацией на временной
диаграмме (желтым цветом указаны запрещенные,
синим реализовавшиеся состояния)
В частности, из рис. 33.11 видно, что реализовавшаяся цепь выглядит так: S 0 S 1 S 0 Переходы произошли в следующие моменты времени: T 0 T 1 T 2 T 3 , где T 0 = 0 , T 1 = τ 01 , T 2 = τ 01 + τ 10 .
Задача . Поскольку модель строят для того, чтобы на ней можно было решить задачу, ответ которой до этого был для нас совсем не очевиден (см. лекцию 01), то сформулируем такую задачу к данному примеру. Определить долю времени в течение суток, которую занимает простой станка (посчитать по рисунку) T ср = (T + T + T + T )/N .
Алгоритм имитации будет иметь следующий вид (см. рис. 33.12 ).
марковского процесса на примере имитации работы станка
Очень часто аппарат марковских процессов используется при моделировании компьютерных игр, действий компьютерных героев.
