Алгоритм имитационного моделирования цепи Маркова

Задано:

a) матрица переходных вероятностей P;

b) номер стартового состояния j ₀;

c) число временных шагов исследования процесса t_k;

d) число статистических экспериментов N.

Требуется: вычислить оценки вероятностей нахождения процесса в различных состояниях X [ j ] в момент времени t = t_k.

Алгоритм

1. Создаем два массива X и Y длиной n. Заполняем массив X нулями. полагаем t_k =1.

2. Полагаем t =0 и помещаем 1 в позицию j ₀  массива Y, остальные элементы этого массива – нули.

3. Выполняем основной шаг алгоритма – определяем номер очередного состояния j. Прибавляем 1 к элементу Y [ j ]. Увеличиваем t на 1.

4. Повторяем шаг 3 до тех пор, пока .

5. Пересчитываем X:= X + Y.

6. Повторяем шаги 2 – 5 N раз.

7. Вычисляем значения X [ j ] = X [ j ] / N, j =1,.. n, которые являются оценками среднего числа пребываний процесса в j -м состоянии.

8. Вычисляем сумму  и величины , которые представляют собой оценки вероятностей пребывания процесса в каждом состоянии. Выводим время  и вектор X на печать и на график.

9. Повторяем шаги 1-7 для всех , .

 

Основной шаг алгоритма

Пусть в момент времени t система находится в состоянии S_k. Определим номер состояния, в которое система перейдет в момент t +1. Выделим k – ю строку матрицы P:

p_k = [ p_{k 1}, p_{k 2} ,…, p_kn ],

С помощью датчика случайных чисел генерируем случайное число r (t),  с равномерным законом распределения.Тогда номер состояния j определится условием:

Иными словами, j – это номер элемента строки p_k, для которого сумма  при возрастании j от 1 до n впервые не меньше r (t).

Исходные данные к работе

 

Таблица	mмах 1/с		5	10	7	1	2	4	0.1	1.2	8	5	12	10	7	0.2	2	4	8	15	0.5	1.2	2.5	8	10.5	8	15
	Трудоемкости, С,	С7	-	-	2	2	2	3	-	-	-	-	1	1	1	-	-	5	6	3	8	-	-	-	-	7	3
		С6	2	3	7	3	6	3	6	2	7	1	9	3	8	1	3	2	3	6	7	6	1	5	8	2	6
		С5	7	8	4	3	7	3	9	3	8	2	9	6	7	6	7	1	2	6	7	8	1	5	8	3	6
		С4	7	6	6	4	6	4	7	5	8	4	7	6	6	6	9	3	4	7	6	8	3	6	7	3	8
			10	9	3	5	5	4	5	7	6	6	3	6	9	9	6	3	4	7	6	4	5	6	7	4	2
		С	5	4	5	2	4	3	3	9	3	8	5	8	9	5	3	8	7	8	1	3	5	7	1	5	7
		С	3	4	2	1	3	2	1	6	2	5	1	2	1	2	3	5	6	5	1	2	6	4	1	5	7
	Вероятности перехода Рk ´10	Р10	1	2	3	3	1	2	-	-	-	-	2	8	7	3	5	4	4	1	2	-	-	-	-	5	3
		Р9	3	2	1	1	1	1	5	6	5	1	1	9	7	1	5	2	2	2	2	3	3	2	1	5	4
		Р8	3	2	3	3	5	2	5	1	5	4	2	3	1	2	6	3	3	1	3	2	3	4	3	4	3
		Р7	2	5	1	2	1	5	2	5	2	5	5	3	3	1	1	3	4	2	6	2	3	3	3	4	2
		Р6	5	3	3	3	5	1	5	5	3	2	3	2	4	7	3	5	1	6	2	3	3	2	3	4	3
		Р5	5	3	2	4	2	2	3	4	3	2	4	3	5	4	3	3	7	3	4	3	4	3	2	4	3
		Р4	4	1	7	8	2	2	3	4	5	3	3	3	5	3	5	6	5	1	1	6	1	3	4	1	1
		Р3	7	2	5	3	3	4	3	4	2	5	4	3	2	1	2	4	2	1	6	2	6	3	4	6	7
		Р2	3	5	2	3	2	3	4	4	5	4	2	3	1	5	2	3	1	5	1	7	1	3	2	4	1
		Р1	3	4	2	3	2	3	3	4	2	3	5	2	5	2	3	1	3	4	5	2	8	4	4	3	4
	Схема,вход		A1	А2	Б1	Б2	В1	В2	Г1	Г2	Д1	Д2	Е1	Е2	Е3	А1	А2	Б1	Б2	В1	В2	Г1	Г2	Д1	Д2	Е1	Е2
	№ вар		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

 

Исходные данные представлены в виде таблицы и набора схем. По указанному преподавателем номеру варианта в таблице выбирается соответствующая строка. Второй столбец таблицы указывает код схемы и стартовое состояние (например, Г1 – схема Г, старт происходит из состояния S 1). Далее указаны вероятности перехода между состояниями в десятых долях (т.е. указанное в таблице значение  означает, что ). Этими вероятностями помечены дуги на схеме. Некоторые дуги не помечены – соответствующие вероятности определяются из условия, что сумма вероятностей на дугах, отходящих от каждого узла, равна единице. Следующая группа столбцов задает трудоемкости отдельных процессов  в секундах. В последнем столбце указаны величины  (1/с), которая используется в лабораторной работе №3

 

 

 

Б

 

 

P4

В

 

Г

P5

 

Д

 

Е

Контрольные вопросы

1 Дайте определение дискретной цепи Маркова.

2 Какими свойствами обладают матрица переходных вероятностей?

3 Как рассчитываются вероятности нахождения однородной цепи Маркова в определенном состоянии через нужное число тактов?

4 Что такое начальное состояние цепи?

5 Дайте определение однородной цепи Маркова?

Лабораторная работа № 2. Моделирование динамики систем на основе
цепей Маркова с дискретным временем (часть 2)

 

Цели работы

- освоить основные положения теории конечных цепей Маркова (ЦМ) с дискретным временем.

- научиться составлять ЦМ для моделирования вычислительных систем и анализа динамики их функционирования.

- провести расчет характеристик производительности вычислительных систем с использованием пакета MathCad.

Содержание работы

1. Изучить теоретический материал по ЦМ по учебному пособию
[1] или лекциям.

2. Для системы заданной в Лабораторной работе №1, провести следующие вычисления.

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

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

2.3.  На основе матрицы  вычислить среднюю трудоемкость вычислительного процесса .

2.4. Получить оценку строки матрицы , соответствующей заданному стартовому состоянию с помощью модификации программы, составленной в Лабораторной работе №1. Модификация алгоритма заключается в следующем.

1. Выполнение шага 3 прекращается, если очередное состояние  относится к эргодическому множеству: .

2. Исключается шаг 8. на печать выводится результат шага 7.

3. Расчет ведется только для максимального значения , .

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

2.6. Оценить предельные вероятности пребывания процесса в множестве эргодических состояний.

Оформление отчета по работе

Отчет по лабораторной работе должен содержать:

· титульный лист с указанием всех исполнителей и номера группы;

· исходные данные по ЦМ – граф состояний и матрицы переходных вероятностей ; , ;

· матрицу средних значений  и оценку средней трудоемкости процесса ;

· оценку строки матрицы , полученную путем имитационного моделирования;

· матрицу дисперсий  и оценку среднеквадратичного отклонения трудоемкости s_Q;

· листинг модифицированной программы имитационного моделирования ЦМ с подсчетом среднего числа пребываний процесса в различных состояниях;

· оценки предельных вероятностей пребывания процесса в состояниях эргодического множества:

а) путем прямого возведения матрицы  в высокую степень,

б) путем спектрального разложения матрицы.

 

Контрольные вопросы

1 Как определить какие состояния будут невозвратными?

2 Дайте определения невозвратных и эргодических состояний?

3 Как определить число среднее число пребываний цепи  в каком-то невозвратном состоянии?

4 Как имитационно смоделировать фундаментальную матрицу?

5 Что такое трудоемкость процесса исполняемого цепью Маркова?

6 Что такое предельное состояние цепи Маркова?

7 Сформулируйте основные шаги алгоритма нахождения предельного состояния.

Лабораторная работа № 3. Моделирование динамики систем на основе
цепей Маркова с непрерывным временем

 

Цели работы

- освоить основные положения теории конечных цепей Маркова (ЦМ) с непрерывнымвременем.

- научиться составлять и исследовать модели вычислительных систем на основе этой теории.

Содержание работы

· изучить теоретический материал по учебникам [1], [2], [3] или лекциям.

· создать ЦМ с непрерывным временем на базе модели, рассмотренной в Лабораторных работах №1 и №2. Для этого:

· по заданному номеру варианта из таблицы в Лабораторной работе №1, взять величину  и для всех дуг графа цепи Маркова рассчитать плотности вероятностей переходов .

· составить матрицу p (формула (3.42)).

· составить уравнение Колмогорова в матричной и компонентной формах для определения динамики изменения вектора вероятностей . Задать начальные условия исходя из заданного стартового состояния системы.

· решить уравнение Колмогорова с заданными начальными условиями с помощью пакета MathCad. Решение вести до получения установившихся значений вектора . Оценить временную шкалу решения исходя из величины . Сравнить график решения с аналогичным графиком, полученным в Лабораторной работе №1, п. 3.

·  Вычислить установившиеся значения вектора  путем решения системы линейных уравнений, полученных из уравнения Колмогорова при  с учетом условия . Сравнить решение с результатом п. 3.

Оформление отчета по работе

Отчет по лабораторной работе должен содержать:

· титульный лист с указанием всех исполнителей и номера группы;

· исходные данные по ЦМ – граф состояний с указанием плотностей вероятностей переходов ;

· матрицу p;

· уравнение Колмогорова в матричном и компонентном виде и начальные условия;

· график решения – все компоненты вектора  с разметкой временной шкалы;

· систему уравнений для вычисления установившегося значения  и ее решение.

 

Контрольные вопросы

1 Дайте определение непрерывной стационарной цепи Маркова.

2 Как составляется уравнение Колмогорова по графу цепи?

3 Как в пакете MathCad получить решение уравнения Колмогорова?

4 Что такое интенсивность непрерывной цепи Маркова?

5 Как сравнивать результаты выполнения лабораторных работ №1 и №3?

Сетевые модели

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

Большой вклад в развитие теории сетей петри внесли отечественные ученые, в частности, математики из Новосибирского научного центра во главе с В.Е. Котовым [4].

В последние годы получила распространение теория так называемых сетей петри высокого уровня, которая изложена, например, в трехтомной работе Курта Йенсена [5]. Эта разновидность сетей Петри позволяет моделировать весьма сложные дискретные динамические системы, а их описание представлено с помощью специализированного алгоритмического языка

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

Обыкновенные сети Петри

 

Формальное определение

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

Формально в терминах теории систем [4] с еть Петри (Petri Net – PN) - это набор элементов (кортеж)

.                                                             (2.1)

В этом определении

  - множество дискретных моментов времени;

 - непустое множество элементов сети, называемых позициями (местами);

 - непустое множество элементов сети, называемых переходами.

Множества позиций и переходов не пересекаются:

.

 - функцияинцидентности,

,                                      (2.2)

где  - кратность дуги.

M₀ - начальная маркировка позиций: .

Функция инцидентности может быть представлена в виде   и фактически задает два отображения:

1)   т.е. для каждой позиции указываются связанные с ней переходы (с учетом их кратности);

2)  т.е. для каждого перехода указываются связанные с ним позиции (также с учетом кратности).

Эти функции, в общем случае зависящие от времени, могут быть представлены матрицами инцидентности

 

 ,                                                (2.3)

 

 .                                                  (2.4)

 

Из вершины - позиции  ведет дуга в вершину - переход  тогда и только тогда, когда . В этом случае говорят, что  - выходной переход позиции .

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

Аналогично из каждой вершины перехода  дуга ведет в вершину - позицию , тогда и только тогда, когда . При этом говорят, что - выходная позиция перехода .

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

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

.                                                                  (2.5)

Начальная маркировка   определяет стартовое состояние сети Петри.

Динамика поведения моделируемой системы описывается в терминах функционирования сетей Петри. Как было сказано, сеть функционирует в дискретном времени  в асинхронном режиме, переходя от одной маркировки к другой.

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

,                                                                   (2.6)

т.е. если каждая входная позиция для данного перехода  содержит как минимум столько фишек, какова кратность ведущей к  дуги.

В результате срабатывания перехода  в момент времени  маркировка  сменяется маркировкой  по правилу:

,                                            (2.7)

i =1,..., n, j =1,..., m, , .

Иными словами, переход t изымает из каждой своей входной позиции число фишек, равное кратности входных дуг и посылает в каждую свою выходную позицию число фишек, равное кратности выходных дуг.

Если может сработать несколько переходов, то срабатывает один, любой из них. Функционирование сети останавливается, если при некоторой маркировке (тупиковая маркировка) ни один из ее переходов не может сработать. При одной и той же начальной маркировке сеть Петри может порождать, в силу недетерминированности ее функционирования, различные последовательности срабатывания ее переходов. Эти последовательности образуют слова в алфавите T.

множество всевозможных слов, порождаемых сетью Петри, называют языком сети Петри. Две сети Петри эквивалентны, если порождают один и тот же язык.

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

 

Графы сетей Петри

Формальное определение сети Петри, изложенное выше, полностью определяет ее функционирование.

Однако при решении конкретных инженерных задач удобнее и нагляднее графическое представление этих сетей.

Поэтому ниже функционирование сетей Петри изложено с позиции теории графов.

Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф сети Петри.

Этот граф содержит:

- позиции (места), обозначаемые кружками;

- переходы, обозначаемые планками;

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

Благодаря наличию кратных дуг сеть Петри есть мультиграф. Благодаря двум типам вершин граф называется двудольным. Поскольку дуги имеют направление, граф является ориентированным. Пример такого мультиграфа показан на рисунке 2.1.

 

 

р исунок 2.1 Пример сети Петри

 

Для сети, изображенной на этом рисунке, матрицы инцидентности имеют вид:

 ,  .

Начальная маркировка, как видно из рисунка 2.1, .

Нетрудно видеть, что матричное и графовое представления взаимно однозначно соответствуют друг другу.

В случае большой кратности дуг эту кратность можно указывать цифрами на соответствующей дуге.