11. Типовые графы состояний системы. Циклический процесс. Примеры объектных систем.

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

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

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

Среднее время пребывания системы в i-том состоянии:

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

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

1. Метод вложенных цепей Маркова.

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

Частным случаем вложенных цепей маркова является полумарковский случайный процесс. Полумарковский процесс – это процесс, обладающий конечным или счетным числом состояний, при этом заданы вероятности перехода системы из одного состояния в другое, а также задано распределение времени пребывания процесса в каждом состоянии, например в виде функции распределения F(t) или плотности распределения f(t).

2. Метод псевдосостояний.

Идея: все состояния процесса/объекта, переходы из которых совершаются под воздействием немарковских потоков, заменяются эквивалентным набором фиктивных псевдосостояний, переходы между которыми являются марковскими. В результате получается новая статистически эквивалентная система, которую можно исследовать с помощью аппарата теории марковских цепей.

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

Произвольный поток можно аппроксимировать потоком Эрланга k-того порядка:

Пример задачи на тему “метод псевдосостояний”:

13. Теория массового обслуживания и ее место при построении и исследовании вероятностных моделей объектов. Основные понятия и определения.

Для современных вычислительных машин и систем характерна работа в режиме решения потока случайных по своим характеристикам задач, поступающих в общем случае в отдельные моменты времени. Такой режим работы характерен для работы системы “процессор-основная память” (случаен поток команд, выбираемых УУ процессора из памяти), системы внешнего ЗУ (случайно время доступа к хранящейся в памяти информации) и т.д.

1. Есть каналы обслуживания (обычно несколько) – линии связи, рабочие места, продавцы/кассиры, процессоры и пр.

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

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

4. Может случиться, что у объекта нет свободных ресурсов – тогда новая заявка либо получает отказ, либо попадает в очередь на обслуживание.

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

К условиям можно отнести: количество каналов обслуживания, их производительность, правила работы и др. К показателям эффективности можно отнести: среднее число занятых каналов, среднее число заявок, находящихся в очереди, среднее время обслуживания и пр.

В марковском процессе все потоки – простейшие.

Теория массового обслуживания (ТМО) строит и исследует два типа моделей:

1. СМО – система массового обслуживания (динамическая система, предназначенная для эффективного обслуживания случайного потока заявок в условиях ограниченности ресурсов).

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

ТМО пытается решить 2 типа задач:

1. Прямая задача ТМО (задача анализа) – определение характеристик объекта при заданной структуре объекта и параметрах компонент.

2. Обратная задача ТМО (задача синтеза) – определение структуры объекта, параметров компонент структуры для получения требуемых значений характеристик (многократное решение задачи 1).