Граф состояний. Вероятности состояний

СЕВАСТОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

М.М. Гхашим, Т.В.Чернэуцану

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

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

Учебное пособие

Утверждено

ученым советом института

Севастополь

Гхашим М.М., Т.В.Чернэуцану

Марковские случайные процессы иОсновы теории массового обслуживания:учеб.-метод. пособие. – Севастополь: СевГУ, 2015.

В данном пособии рассмотрены два основных раздела: « », « », Каждый из разделов включает в себя основные вопросы теории, разбор типовых примеров, задания для самостоятельной работы с ответами к ним.

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

Рецензенты:

к.ф.-м..,

к.т.н, доцент

нк.ф.-м.н доцент

Издание СевГУ, 2015

ОГЛАВЛЕНИЕ

Глава первая. МАРКОВСКИЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ

Граф состояний. Вероятности состояний…………………………..

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

Стационарный режим для цепи Маркова………………………….

Решение типовых задач…………………………………………………….

Задачи для самостоятельного решения………………………………….

Глава вторая. ОСНОВЫ ТЕОРИИ МАССОВАОБСЛУЖИВАНИЯ

Введение………………………………………………………………..

§ 2. Основные компоненты моделей массового обслуживания………

Случайный поток со счетным множеством состояний…………….

Поток событий. Простейший поток и его свойства………………..

Нестационарный пуассоновский поток……………………………..

Потоки Пальма и Эрланга…………………………………………….

Решение типовых задач……………………………………………………..

Задачи для самостоятельного решения………………………………….

Глава первая

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

Граф состояний. Вероятности состояний.

Рассмотрим случайный процесс, который протекает в физической системе S. Этот процесс называется процессом с дискретными состояниями, если в любой момент времени t множество его состояний конечно или счетно; другими словами, если его сечение в любой момент времени t характеризируется дискретной случайной величиной X(t). Обозначим эти дискретные состояния

s₁, s₂, …, s_i, …

Рассмотрим возможности системы S переходить из состояния s_i в состояние s_j непосредственно или через другие состояния. Для изображения этих действий удобно пользоваться ориентированным графом состояний, т.е. схемой, состоящей из совокупности точек (вершин) и соединяющих некоторые из них ориентированных отрезков (стрелок). Вершины графа будут соответствовать состояниям системы, мы будем изображать их прямоугольниками, в которые вписываются состояния; стрелка, ведущая из вершины s_i в вершину s_j, будет обозначать возможность перехода системы S из состояния s_i в состояние s_j непосредственно, минуя другие состояния.

Нередко кроме стрелок, связывающих различные состояния s_i, s_j (i ≠ j), проставляют также обратные стрелки, возвращающие систему из состояния в то же состояние s_i. Переход по такой стрелке означает задержку системы в состоянии s_i.

Пример 1. Система S представляет собой техническое устройство (ТУ), а его возможные состояния: s₁ – ТУ работает исправно; s₂ – ТУ неисправно, но это не обнаружено; s₃ – неисправность обнаружена, ведется поиск ее источника; s₄ – источник неисправности найден, ведется ремонт ТУ; s₅ – проводится послеремонтный осмотр (после этого осмотра, если ТУ восстановлено в прежнем виде, оно возвращается в состояние s₁, если нет – признается негодным и списывается); s₆ – ТУ списано за негодностью; s₇ – ведется профилактический осмотр ТУ (если обнаружена неисправность, ТУ направляется в ремонт). Составим граф состояний этой системы

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

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

Если система S может непосредственно перейти из состояния s_i в состояние s_j, то состояние s_j называется соседним по отношению к состоянию s_i. Если система может непосредственно перейти из состояния s_i в состояние s_j и из состояния s_j в состояние s_i, то эти состояния называются соседними.

На рисунке состояние s₁ является источником, состояние s₅ является поглощающим, а состояния s₂, s₃ и s₂, s₄ – соседними.

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

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

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

Подмножество состояний V называется транзитивным, если система S может войти в это подмножество и выйти из него, т.е. из любого состояния можно (за то или иное число перескоков) выйти из этого подмножества.

Определение. Вероятностью i-того состояния системы S в момент времени t называется вероятность события, состоящего в том, что в момент времени t система будет находиться в состоянии s_i:

p_i(t) = P{S(t) = s_i},

где S(t) – случайное состояние системы S в момент времени t.

Очевидно, что для системы с дискретными состояниями s₁, s₂, …, s_i, … в любой момент времени t сумма вероятностей состояний равна единице,:

как сумма вероятностей полной группы несовместных событий.