Разработка марковской моделисистемы с дискретным

Этапы:

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

n построение размеченного графа переходов;

n формирование матрицы интенсивностей переходов;

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

Процессы однородные и неоднородные

Процесс называется однородным, если вероятности (плотности вероятностей) от времени не зависят. Иначе процесс называется неоднородным.

Если по истечении достаточно большого промежутка времени вероятности состояний стремятся к предельным значениям p ₁, …, p_n, не зависящим от начальных вероятностей p ₁(0), …, p_n (0) и от текущего момента времени t, то говорят, что случайный процесс обладает эргодическим свойством.

– стационарные вероятности

Процессы с эргодическим свойством

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

n Матрица является разложимой, если она может быть приведена к одному из следующих видов:

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

n Матрица является периодической, если она может быть приведена к виду:

Случайный процесс в этом случае будет по очереди переходить изсостояний, соответствующих B, в состояния, соответствующие С.

10. Имитационное моделирование. История, принципы, примеры.

Сложилось в середине XXвека

Работы Р. Шеннона и Т. Д. Шрайбера

Сейчас это основной метод исследования сложных систем

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

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

Если статистическое моделирование выполняется с использованиемимитационной модели, то такое моделирование называется имитационным.

Следует иметь в виду, что статистическое моделирование не обязательно является имитационным.

Временн а я диаграмма – графическое представление последовательности событий, происходящих в системе. Для построения временн ы хдиаграмм необходимо достаточно четко представлять взаимосвязьсобытий внутри системы.

Имитационное моделирование обычно проводится на ЭВМ всоответствии с программой, реализующей заданное конкретное логико-алгоритмическое описание. При этом несколько часов, недель или летработы исследуемой системы могут быть промоделированы на ЭВМ занесколько минут. В большинстве случаев модель является не точныманалогом системы, а скорее её символическим отображением. Однако

такая модель позволяет производить измерения, которые невозможнопроизвести каким-либо другим способом.

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

Рассмотрим принципы имитационного моделирования на примере

простейшей базовой модели в виде одноканальной системы массового обслуживания с однородным потоком заявок (рис.6.1), в которую поступает случайный поток заявок с интервалами между соседними заявками, распределёнными по закону A (t), а длительность обслуживания заявок в приборе распределена по закону B (t).

Процесс функционирования такой системы может быть представлен

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

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

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

1. «процесс поступления заявок» - получено с помощью задания случайного интервала по правилу A (t)

2. процесс обслуживания в приборе», представленный в виде длительностей обслуживания bi t, которых вырабатываются с помощью генератора случайных величин B (t), и моментов завершения обслуживания ti заявок в приборе, определяемых по обслуживания заявок в приборе

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

Точность полученных числовых моментов распределения и качествогистограмм существенно зависит от количества значений N времени пребывания заявок, на основе которых они рассчитываются: чем больше N,тем точнее результаты расчета. Значение N может составлять от нескольких тысяч до десятков миллионов. Конкретное значение N зависит отмногих факторов, влияющих на скорость сходимости результатов к истинному значению, основными среди которых при моделировании систем и

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

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

Таким образом, имитационная модель представляет собой алгоритм

реализации временной диаграммы функционирования исследуемой

системы. Наличие встроенных в большинство алгоритмических языков

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

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

Второй подход, который может быть предложен для реализации

временной диаграммы, – пошаговое построение диаграммы. Для этого

следует сформировать переменную для модельного времени и выбрать шаг  t его изменения. В каждый такой момент времени необходимо проверять, какое событие (поступление в систему или завершение обслуживания заявки) произошло в системе за предыдущий интервал  t.

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

Недостатки такого подхода очевидны. Во-первых, проблематичным

является выбор длины интервала  t. С одной стороны, интервал  t

должен быть как можно меньше для уменьшения методической погрешности моделирования, с другой стороны, интервал  t должен быть

как можно больше для уменьшения времени моделирования.

Наиболее эффективным подходом признан подход с переменным

шагом продвижения модельного времени, который реализуется в соответствии с принципом «до ближайшего события». Принцип «продвижения модельного времени до ближайшего события» заключается в следующем. По всем процессам, параллельно протекающим в исследуемой системе, в каждый момент времени формируются моменты наступления «ближайшего события в будущем». Затем модельное время продвигается до момента наступления ближайшего из всех возможных событий. В зависи-

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

пуста. Затем формируется новый момент наступления этого же события.ность событий в имитационной модели, используются системные часы, хранящие значение текущего модельного времени. Изменение значения модельного времени осуществляется в соответствии с принципом «пересчёта времени до ближайшего события». Например, если текущее значение модельного времени равно 25, а очередные события должны наступить в моменты времени 31, 44 и 56, то значение модельного времени увеличивается сразу на 6 единиц и «продвигается» до значения 31. Важно помнить, единицы времени

выбираются исходя из требований пользователя к точности моделирова-

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

Кроме рассмотренной службы времени в имитационной модели

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

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

· выработка (генерирование) случайных величин:

o равномерно распределенных;

o с заданным законом распределения;

· формирование потоков заявок и имитация обслуживания;

· организация очередей заявок;

· организация службы времени;

· сбор и статистическая обработка результатов моделирования.

Этапы имитационного моделирования:

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

n декомпозиция системы на компоненты производится с учетом структуры проектируемого или изучаемого объекта;

n в качестве законов поведения, могут использоваться экспериментальные данные, полученные в результате натурных экспериментов;

n а поведение системы во времени иллюстрируется заданными динамическими образами.

n Вместо расчёта вероятностных величин рассчитываются ситуации конкретных значений случайных параметров

n То есть имитируется поведение случайных параметров

n Адекватность и достоверность полученных результатов во многом зависят от адекватности имитирования этих параметров