Лекция_11_С
.docДля изучения процессов с дискретными состояниями пользуются так называемым графом состояний, в котором состояния системы обозначаются прямоугольниками или кружочками, а возможные переходы из состояния в состояние − ориентированными дугами графа.
-
Рассмотрим марковский процесс с дискретным состоянием и дискретным временем.
Пусть имеется физическая система , которая может находиться в состояниях , , …, , причем переход системы из состояния в состояние осуществляется скачками только в моменты времени , , …, , …, для которых разности равны постоянному числу — шагу, для простоты принимаемому за единицу времени. Такие марковские процессы называются марковскими цепями.
Определение. Вероятностью состояния называется вероятность системы находиться в состоянии после -го шага.
Очевидно, что для каждого шага
.
Будем считать, что вероятности перехода системы из состояния в состояние (они называются переходными вероятностями) одинаковые для всех шагов (такая цепь называется однородной).
Введем так называемую матрицу вероятностей перехода
. (1)
Элементы матрицы неотрицательны, но могут равняться 0: , если переход системы из состояния в состояние невозможен. Сумма элементов любой строки матрицы равна 1. Такие матрицы называются стохастическими.
1. Вероятности перехода из состояния в состояние за шагов определяются матрицей
,
где , откуда следует, что
,
. (2)
2. Теорема Маркова. Если при некотором все элементы матрицы положительны, то существуют такие положительные числа , , …, , что независимо от начального состояния системы имеют место равенства
, причем
. (3)
Вектор называется предельным распределением, а числа — предельными вероятностями состояний.
Предельное распределение можно найти как собственный вектор матрицы ( транспонированная), соответствующий собственному значению .
Пример 2. Задана матрица вероятностей перехода цепи Маркова из состояния в состояние за один шаг. Найти матрицу перехода из состояния в состояние за два шага и вероятность появления цепочки состояний —— за два шага. Выяснить, можно ли к матрице применить теорему Маркова. Если да, найти предельное распределение.
Решение. Матрицу получаем по формуле (2)
.
Вероятность появления цепочки состояний —— за два шага равна , т.е. такой последовательности состояний наблюдаться не может.
Матрица получилась положительной, а это означает, что предельные вероятности существуют. Найдем вектор как собственный вектор матрицы
из матричного уравнения
(4)
при , т.е.
или из системы
Эта система равносильна системе
Решая ее, например методом Жордана-Гаусса, получим
~~, откуда
А с учетом (3)
,
т.е. в стационарном режиме система в среднем всего времени находится в состоянии , — в состоянии и — в состоянии .
-
Рассмотрим марковский процесс с дискретным состоянием и непрерывным временем временем.
Для таких процессов рисуется граф состояний, вершины которого соответствуют состояниям S0, S1,…,Sn, а дуги − переходам из одного состояния в другое. Как правило, переход из одного состояния в другое происходит под действием простейшего потока событий с интенсивностью . Граф, дугам которого приписаны интенсивности , называется размеченным.
− вероятность того, что в момент времени система находиться в состоянии .
Для вероятностей имеет место условие нормировки:
(1)
и система уравнений Колмогорова:
(2)
Гдеберётся по всем состояниям , дуги из которых идут в состояния . Во второй сумме берутся все состояния, в которые идут дуги из состояния .
Особый интерес представляет случай, когда система может перейти в стационарный режим.
, − это предельные вероятности, получающиеся при . Их находят из системы:
(3)
Среди системы уравнений (3) одно лишнее (любое), его следует отбросить и добавить условие (1). Доказано, что если число состояний конечно и из каждого состояния можно перейти в любое другое, то предельные вероятности существуют.
Пример:
Найти предельные вероятности для системы, размеченный граф которой имеет вид.
,
,
,
.
С учетом условия нормировки получаем систему
Отбрасываем третье из уравнений, получаем:
§ 4 Процессы гибели и размножения
описывают изменение численности биологических популяций.
Граф состояний процесса гибели и размножения имеет вид
т.к. переход из любого состояния может осуществляться только в состояния с соседними номерами.
,
, т.к. , то остается
,
и далее аналогично
,
…………………..
,
.
Получаем систему
из которой с учетом условия нормировки получаем окончательно
и далее из системы находим , ,…, .
Пример. Дан граф процесса гибели и размножения.
Найдите предельные вероятности состояний.
Решение. ,
,
,
.
Отбрасываем последнее уравнение, добавляем условие нормировки и получаем систему
или
Окончательно
§ 5. Некоторые задачи теории массового обслуживания
Системы массового обслуживания СМО − системы, предназначенные для многократного использования при решении однотипных задач. Каждая система состоит из определенного количества обслуживающих единиц − каналов.
Будем рассматривать многоканальные СМО с отказами (т.е. такие, в которых в случае занятости всех каналов заявка покидает систему необслуженной). Для них введем следующие показатели.
1. интенсивность потока заявок, т.е. среднее количество заявок, поступающих за единицу времени;
2. — абсолютная пропускная способность СМО, т.е. среднее число заявок, рассматриваемых в единицу времени.
3. — относительная пропускная способность, т.е. средняя доля пришедших заявок, обслуживаемых системой.
4. — вероятность отказа, т.е. того, что заявка покинет систему необслуженной.
5. — среднее число занятых каналов для многоканальной системы.
6. — интенсивность обслуживания, т.е. количество заявок, обслуживаемых одним каналом за единицу времени.
7. — среднее время обслуживания, т.е. .
Итак, имеется каналов, на которые поступает поток заявок с интенсивностью . Поток обслуживания каждого канала имеет интенсивность . Найдем предельные вероятности состояний системы и показатели ее эффективности.
Система имеет следующие состояния , , , …, , …, , пронумерованные по числу заявок, находящихся в системе, т.е. — состояние системы, когда в ней находятся заявок (занято каналов).
Граф состояний соответствует процессу гибели и размножения.
Переход в соседнее состояние с большим номером всегда происходит под действием простейшего потока с интенсивностью , а вот переход из состояния в состояние происходит под действием потока интенсивности , так как освободиться может любой из занятых каналов.
Формула для предельной вероятности состояния примет вид
, (1)
где — так называемая интенсивность нагрузки канала, а
, , …, , …, . (2)
Найдем показатели эффективности СМО.
Вероятность отказа системы есть предельная вероятность того, что все каналов будут заняты, т.е.
.
Относительная пропускная способность — вероятность того, что заявка будет обслужена
.
Абсолютная пропускная способность
.
Среднее число занятых каналов , т.е. математическое ожидание числа занятых каналов
или иначе .
Далее разбирайте задачи к практическому занятию и используйте методички (см. список литературы).