Марковская цепь с непрерывным временем

Лекция 1. Цель и задачи дисциплины

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

Целью преподавания дисциплины «Имитационное моделирование» является усвоение студентами главных понятий и методов имитационного моделирования, нужных в профессиональной деятельности эксперта в области применения математических способов в экономике.

Введение

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

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

Компьютерное ИМ предполагает исполнение последовательности последовательных действий.

1) Описание настоящей совокупности с выделением структуры, динамического сотрудничества элементов, состояний системы и факторов неопределённости, в которых она может пребывать.

2) Создание блоковой схемы объекта с указанием состояний его возможных переходов и элементов между ними.

3) Построение моделирующей программы на особом языке ИМ либо неспециализированном языке программирования.

4) Проигрывание разных вероятных обстановок на модели.

5) программы и Верификация модели на базе анализа взятых их сравнения и результатов с теорией процесса и (либо) информацией о функционировании настоящего объекта.

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

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

Способ Монте-Карло (МК)

ИМ можно считать развитием способа МК, созданного в 50-х годах прошлого века. Главная мысль этого способа пребывает в применении выборок чтобы получить оценки искомых черт изучаемых объектов. Задача, наряду с этим, формулируется так, дабы метод ответа применял случайные числа соответствующих законов распределения. Оказалось, что возможно так формализовать детерминированную задачу (вычисление определенных интегралов, к примеру), дабы решить ее посредством выборок случайных чисел. Покажем это на примере. Пускай требуется отыскать площадь фигуры, ограниченной заданными линиями.

Пускай плоская фигура g образовывает часть фигуры G. На фигуру G кинута случайная точка. Тогда возможность попадания ее нa фигуру g равна отношению площади g к площади фигуры G : (геометрическая возможность). Следовательно, в случае если известна площадь , то . Используем данный подход для определения площадей фигур, заданных уравнениями границ.

Пример 1. Отыскать площадь фигуры, ограниченной линиями .

Выстроим указанные линии. Из Рис. 1 видно, что фигура, площадь которой нужно отыскать всецело попадает в прямоугольник с основанием равным 6 и площадью 4 и высотой .

Рис. 1.

Формируем nслучайных точек в этого прямоугольника.

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

.

Возможность попадания одной точки на фигуру g приближенно равна (и тем правильнее, чем больше n) отношению числа точек попавших на фигуру к полному числу точек. и, тогда искомая площадь . Иначе, площадь фигуры равна определенному интегралу . Относительная погрешность способа МК . Повысить точность возможно повышением числа точек либо (и) повторением расчета с последующим сглаживанием.

Пример 2. Отыскать площадь фигуры, ограниченной линиями . Отыщем точки пересечения данных линий и выстроим график. Из чертежа видно, что фигура, площадь которой нужно отыскать всецело попадает в прямоугольник с основанием равным 6 и площадью 4 и высотой .

Формируем nслучайных точек в этого прямоугольника.

. Программа для подсчета, подобна приведенной и нет необходимости ее приводить.

Возможность попадания одной точки на фигуру g равна и тогда искомая площадь . Площадь фигуры равна определенному интегралу . Относительная погрешность способа МК в этом примере .

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

Марковская цепь с постоянным временем

Имеется некая совокупность с k состояниями. Переходы между состояниями происходят мгновенно в случайные моменты времени. Возможности переходов из любого состояния Si в любое второе Sj являются функциями от времени pij(t). В случае если случайный процесс, протекающий в совокупности, владеет свойством отсутствия последействия, то говорят, что задана Марковская цепь с постоянным временем [2]. Интенсивностью перехода из состояния Si в состояние Sj именуется предел , где -возможность перехода на промежутке времени .

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

,

Составим размеченный граф состояний данной Марковской цепи (Рис. 3). Разумеется, что эта цепь регулярна и имеет финальное распределение возможностей состояний, совпадающее со стационарным распределением.

2. Отыскать стационарное распределение возможностей состояний.

3. Выполнить моделирование совокупности и сравнить полученные результаты моделирования с результатами, взятыми в пункте 2.

Ответ.

1. Составим граф состояний.

2

S2
S1

3

3 1 4 4

S3

Рис. 3.

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

Запишем уравнения для возможностей состояний.

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

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

.

При достижении стационарного состояния возможности станут постоянными размерами и их производные будут равны нулю. Тогда из совокупности

совместно с очевидным условием ,

отыщем стационарное распределение возможностей состояний

Моделирование процесса, протекающего в данной совокупности.

Введем переменный массив sj, элементы которого – суммарное время нахождения совокупности в данном состоянии j, время моделирования ;матрицу В – индикатор состояний (любой столбец соответствует одному состоянию). К примеру, при выборе столбца 3 совокупность будет в состоянии 2. Отметим, что в этом разделе элементы массивов нумеруются так 0,1,2,…

; .

Моделирующая программа.

Разглядим операторы программы по порядку. Задается начальное значение модельного времени t. Вводится матрица iw соответствующая начальному состоянию совокупности по индикатору состояний и строится цикл while до успехи времени моделирования tm. Определяется номер состояния k, в котором совокупность находится в текущий момент времени. В цикле вычисляем все времена , через каковые совокупность может перейти в второе состояние. Находим минимальное из этих времен . Так как цепь Марковская, то она удовлетворяет условию отсутствия последействия, и случайные времена между переходами распределены по показательному закону. Они смогут быть отысканы посредством оператора . Тут1говорит о том, что вычисляется одно значение, а ? интенсивность соответствующего перехода. Полученное время суммируется с временем, которое совокупность провела в текущем состоянии s. Определяется номер ind состояния, в которое переходит совокупность, и данный номер учитывается в индикаторе В. Отношения времени нахождения в каждом состоянии к полному времени моделирования, принимаются за оценки стационарных возможностей состояний . Для рассмотренного примера и времени моделирования возьмём

.

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

Разглядим имитационную модель совокупности массового обслуживания.

Одноканальная СМО с неограниченной очередью

Из СМО с ожиданием самой простой есть одноканальная СМО с неограниченной очередью. Такие СМО довольно часто видятся в практике: доктор, обслуживающий больных; телефон-автомат с одной будкой; ЭВМ, делающая заказы пользователей.

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

Отыскать предельные возможности состояний СМО, и характеристики эффективности ее работы.

Запишем состояния СМО (состояния пронумерованы по числу заявок в совокупности):

канал свободен,

канал занят, очереди нет,

канал занят, одна заявка в очереди,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

канал занят; заявка в очереди,

и без того потом.

Теоретически число состояний не ограничено (вечно). Граф состояний продемонстрирован на рисунке 3

. . .

. . .

Рис. 3

Существуют ли в этом случае предельные возможности состояний, поскольку число состояний совокупности вечно?

Формула для определения имеет форму:

В скобке стоит сумма нескончаемой геометрической прогрессии. В случае если знаменатель прогрессии , то сумму возможно вычислить по формуле

В случае если , то последовательность расходится, сумма растет неограниченно, СМО не имеет возможности трудиться из-за неограниченно возрастающей очереди. Предстоящие формулы честны лишь при .

Среднее число заявок в очереди одноканальной СМО и время ожидания обслуживания равняется

.

Среднее число занятых каналов — Отыщем среднее число заявок в совокупности:

,

и среднее время нахождения заявки в совокупности:

.

Пример.На ЖД сортировочную горку прибывают составы с интенсивностью состава в час.

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

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

Нас будут интересовать те состояния, при которых составы попадают на внешний путь:

один состав на горке, три в очереди на запасных дорогах станции, один на внешних дорогах,

один на горке, три на запасных дорогах, два на внешних дорогах и без того потом.

Вычислим стационарные возможности состояний СМО:

сост/час; час.; сост./час.

Сейчас отыщем возможность того, что прибывающий состав попадает на внешний путь

Так, в 41% случаев состав попадает на внешний путь.

Вычислим коэффициенты эффективности работы горки.

Среднее число составов, ожидающих в очереди (как в парке, так и вне его) —

состава, часа.

Среднее число составов в парке расформирования —

состава, часа.

Так, составу приходится более 1,5 часов находиться в очереди.

Вычислим среднее время ожидания на внешних дорогах. Составим закон распределения случайной величины ; — число составов, поставленных на внешних дорогах.

….
….

В отечественном примере:

Вычислим штраф за день:

Ш = 2 сост/час. · 24 час. · 0,41 · а = 19,66 а усл.ед.

Решим эту задачу имитационными способами. (Моделирующую программу возможно отыскать в работе [3]).

Результаты для параметров эффективности

состава, часа.

Среднее число составов в парке расформирования —

состава, часа. Величина штрафа по итогам моделирования кроме этого близка к значению, взятому выше.

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

Теория возможности. Математическая статистика. Лекция 5. Марковские случайные процессы


Также читать:

Понравилась статья? Поделиться с друзьями: