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

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

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

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

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

 

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

 

Утверждено

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

 

Севастополь

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

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

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