Первые два признака позволяют разделить имитационные модели на совершенно понятные (очевидные) классы.

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

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

Различают два механизма системного времени:

· задание времени с помощью постоянных временных интервалов (шагов);

· задание времени с помощью переменных временных интервалов (моделирование по особым состояниям).

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

При моделировании по особым состояниям системное время каждый раз изменяется на величину, соответствующую интервалу времени до планируемого момента наступления следующего события, т.е. события обрабатываются поочередно - каждое "в свое время". Если в реальной системе какие-либо события наступают одновременно, это фиксируется в модели. Для реализации этого механизма требуется специальная процедура, в которой отслеживаются времена наступления всех событий и из них выделяется ближайшее по времени. Такую процедуру называют календарем событий. На рис. 1, б) стрелками обозначены моменты изменения системного времени.

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

На рис. 2 приведены перечисленные способы управления системным временем.

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

Размещено на http://www.allbest.ru/

178

Рис. 2. Механизмы управления системным временем.

Метод фиксированного шага целесообразно применять в следующих случаях:

· события в системе появляются регулярно;

· число событий велико;

· все события являются для исследователя существенными (или заранее неизвестно, какие из них существенны).

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

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

Наибольшее распространение получили пять способов:

· просмотр активностей;

· составление расписания событий;

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

· управление агрегатами;

· синхронизация процессов.

Характеристика этих способов требует введения ряда понятий.

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

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

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

Под процессом понимают логически связанный набор активностей, относящихся к одному объекту. Выполнение таких активностей называют фазой процесса. Различие между понятиями "активность" и "процесс" полностью определяется степенью детализации модели. Например, смена позиций мобильным объектом в одних моделях может рассматриваться как сложный процесс, а в других -- как работа по изменению за некоторое время номера позиции. Процессы, включающие одни и те же типы работ и событий, относят к одному классу. Таким образом, моделируемую систему можно представить соответствующим числом классов процессов. Между двумя последовательными фазами (работами) некоторого процесса может иметь место любое число фаз других процессов, а их чередование в модели, собственно, и выражает суть квазипараллелизма.

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

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

Рассмотрим характеристики способов организации квазипараллелизма.

Способ просмотра активностей применяется при следующих условиях:

· все ФД компонент реальной системы различны, причем для выполнения каждого из них требуется выполнение некоторых (своих) условий;

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

· в результате ФД в системе наступают различные события;

· связи между ФД отсутствуют и они осуществляются независимо друг от друга.

В данном контексте имитационная модель состоит из двух частей:

· множества активностей (работ);

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

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

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

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

· различные компоненты выполняют одни и те же ФД;

· начало выполнения этих ФД определяется одними и теми же условиями, причем они известны исследователю и заданы алгоритмически;

· в результате ФД происходят одинаковые события независимо друг от друга;

· связи между ФД отсутствуют, а каждое ФД выполняется независимо.

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

· проверки выполнимости событий;

· обслуживания (обработки) событий.

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

Условия применимости транзактного способа организации квазипараллелизма были приведены при определении понятия "транзакт". Связь между приборами массового обслуживания устанавливается с помощью системы очередей, выбранных способов генерации, обслуживания и извлечения транзактов. Так организуется появление транзактов, управление их движением, нахождение в очереди, задержки в обслуживании, уход транзакта из системы и т.п. Событием в такой имитационной модели является момент инициализации любого транзакта. Типовыми структурными элементами модели являются источники транзактов; их поглотители; блоки, имитирующие обслуживание заявок; управляющий модуль. Имитация функционирования реальной системы производится путем выявления очередной (ближайшей по времени) заявки, ее обслуживания, обработки итогов обслуживания (появления нового транзакта; поглощения заявки; изменения возможного времени поступления следующего транзакта и т.п.), изменения системного времени до момента наступления следующего события.

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

Процессный способ организации квазипараллелизма применяется в случаях:

· все ФД компонент реальной системы различны;

· условия инициализации ФД также различны;

· в любой момент времени в компоненте может выполняться только одно ФД;

· последовательность ФД в каждом компоненте определена.

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

На рис. 3 представлена классификация способов организации квазипараллелизма.

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

Рис. 3. Классификация имитационных моделей по способу организации квазипараллелизма.

Структура типовой имитационной модели с календарем событий

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

На рис. 4 представлена структура типовой имитационной модели с календарем событий.

Такая имитационная модель состоит из трех частей:

· управляющей;

· функциональной, состоящей из функциональных модулей (ФМ);

· информационной, включающей базу (базы) данных (БД).

В свою очередь, управляющая часть содержит:

· блок управления (БУ) моделированием;

· блок диалога;

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

· календарь событий.

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

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

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

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

Календарем событий решаются следующие основные задачи:

· ранжирование по времени плановых событий, т.е. составление упорядоченной временной последовательности плановых событий с учетом вида возможного события и модуля, в котором оно может наступить (для отработки этой задачи в календаре содержится важнейший элемент -- каталог плановых событий, (рис. 5);

· вызов необходимых функциональных модулей в моменты наступления соответствующих событий;

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

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

Наименование модуля	Вид событий	Планируемое время наступления
УМ
ФМ1
ФМ2
..
ФМN

Рис. 5. Каталог плановых событий.

№ п/п	Адресат	Содержание сигнала	Признак передачи
1
2
..
М

Рис. 6. Таблица сигналов.

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

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

Функциональная часть имитационной модели состоит из функциональных модулей, являющихся основными ее элементами. Именно в них описываются и реализуются все процессы в моделируемой системе. Обычно один ФМ описывает либо отдельный процесс в системе, либо ее отдельный элемент (подсистему) -- в зависимости от выбранной схемы моделирования. Обобщенная структурная схема работы ФМ представлена на рис. 7.

Рис. 7. Обобщенная структурная схема работы типового ФМ.

На рисунке обозначены: ВС -- входной сигнал; ИС -- информационный сигнал.

В ФМ могут поступать пять видов входных сигналов:

· стартовый сигнал (сигнал о начале моделирования);

· сигнал о наступлении планового события;

· информационный сигнал;

· сигнал о прерывании моделирования;

· сигнал об окончании моделирования.

Отметим, что, какой бы сигнал ни поступил на вход ФМ, обязательно формируется выходное сообщение о том, что в ФМ данный сигнал отработан, т.е. проведены соответствующие виду входного сигнала действия: подготовка к моделированию (по ВС вида 1); обработка события (по ВС вида 2); обработка информационного сигнала (по ВС вида 3); запоминание состояния ФМ с целью дальнейшего продолжения моделирования с данного "шага" (по ВС вида 4); завершение моделирования в случае выполнения плана имитационного эксперимента (по ВС вида 5).

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

База (базы) данных представляет собой совокупность специальным образом организованных (структурированных) данных о моделируемой системе (операции), а также программных средств работы с этими данными. Как правило, информация из БД выдается в другие части имитационной модели в автоматическом режиме (в этом смысле можно говорить, что потребителями информации из БД являются пользователи-задачи). Наличие БД в имитационной модели не является обязательным и полностью определяется масштабами модели, объемами необходимой информации и требованиями по оперативности получения результатов моделирования и их достоверности. Если принято решение о включении БД в состав имитационной модели, проектирование БД не имеет каких-либо специфических особенностей и проводится по стандартной методике.

Лекция №13

Имитационные модели информационных систем

Технология моделирования случайных факторов

Генерация псевдослучайных чисел (ПСЧ)

Имитационное моделирование ИС, как правило, предполагает необходимость учета различных случайных факторов -- событий, величин, векторов (систем случайных величин), процессов.

В основе всех методов и приемов моделирования названных случайных факторов лежит использование случайных чисел, равномерно распределенных на интервале [0;1].

До появления ЭВМ в качестве генераторов случайных чисел применяли механические устройства -- колесо рулетки, специальные игральные кости и устройства, которые перемешивали фишки с номерами, вытаскиваемые вручную по одной.

По мере роста объемов применения случайных чисел для ускорения их моделирования стали обращаться к помощи электронных устройств. Самым известным из таких устройств был электронный импульсный генератор, управляемый источником шума, разработанный широко известной фирмой RAND Corporation. Фирмой в 1955 г. была выпущена книга, содержащая миллион случайных чисел, сформированных этим генератором, а также случайные числа в записи на магнитной ленте. Использовались и другие подобные генераторы -- например, основанные на преобразовании естественного случайного шума при радиоактивном распаде. Все эти генераторы обладают двумя недостатками:

§ невозможно повторно получить одну и ту же последовательность случайных чисел, что бывает необходимо при экспериментах с имитационной моделью;

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

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

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

Программные генераторы ПСЧ должны удовлетворять следующим требованиям:

§ ПСЧ должны быть равномерно распределены на интервале [0; 1] и независимы, т.е. случайные последовательности должны быть некоррелированы;

§ цикл генератора должен иметь возможно большую длину;

§ последовательность ПСЧ должна быть воспроизводима;

§ генератор должен быть быстродействующим;

§ генератор должен занимать малый объем памяти.

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

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

Мультипликативный метод

Основная формула мультипликативного генератора для расчета значения очередного ПСЧ по значению предыдущего имеет вид:

,

где а, т -- неотрицательные целые числа (их называют множитель и модуль).

Как следует из формулы, для генерации последовательности ПСЧ необходимо задать начальное значение (корень) последовательности, множитель и модуль, причем период (длина) последовательности Р зависит от разрядности ЭВМ и выбранного модуля, а статистические свойства -- от выбранного начального значения и множителя. Таким образом, следует выбирать перечисленные величины так, чтобы по возможности максимизировать длину последовательности и минимизировать корреляцию между генерируемыми ПСЧ. В специальной литературе приводятся рекомендации по выбору значений параметров метода, использование которых обеспечивает (гарантирует) получение определенного количества ПСЧ с требуемыми статистическими свойствами. Так, если для машины с двоичной системой счисления задать , , где -- число двоичных цифр (бит) в машинном слове; Т -- любое целое положительное число; V -- любое положительное нечетное число, получим последовательность ПСЧ с периодом, равным . Заметим, что в принципе возможно за счет другого выбора модуля т увеличить длину последовательности до , частично пожертвовав скоростью вычислений. Кроме того, важно, что получаемые таким образом ПСЧ оказываются нормированными, т.е. распределенными от 0 до 1. От выбора корня последовательности ее длина не зависит (при равенстве остальных параметров).

Аддитивный метод

Основная формула для генерации ПСЧ по аддитивному методу имеет вид:

,

где т -- целое число.

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

.

Смешанный метод

Данный метод несколько расширяет возможности мультипликативного генератора за счет введения так называемого коэффициента сдвига с. Формула метода имеет вид:

.

За счет выбора параметров генератора можно обеспечить максимальный период последовательности ПСЧ .

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

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

Моделирование случайных событий

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

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

Моделирование случайного события заключается в " определении ("розыгрыше") факта его наступления.

Для моделирования случайного события А, наступающего в опыте с вероятностью , достаточно одного случайного (псевдослучайного) числа R, равномерно распределенного на интервале [0;1]. В случае попадания ПСЧ R в интервал событие А считают наступившим в данном опыте; в противном случае -- не наступившим в данном опыте. На рис. 1 показаны оба исхода: при ПСЧ событие следует считать наступившим; при ПСЧ -- событие в данном испытании не наступило. Очевидно, что чем больше вероятность наступления моделируемого события, тем чаще ПСЧ, равномерно распределенные на интервале [0;1], будут попадать в интервал , что и означает факт наступления события в испытании.

Размещено на http://www.allbest.ru/

178

Рис. 1. Моделирование случайных событий.

Для моделирования одного из полной группы N случайных несовместных событий ,,…,, с вероятностями наступления соответственно, также достаточно одного ПСЧ R.

Напомним, что для таких случайных событий можно записать:

.

Факт наступления одного из событий группы определяют исходя из условия принадлежности ПСЧ R тому или иному интервалу, на который разбивают интервал [0;1]. Так, на рис. 2 для ПСЧ считают, что наступило событие А2. Если ПСЧ оказалось равным , считают, что наступило событие .

Размещено на http://www.allbest.ru/

178

Рис. 2. Моделирование полной группы несовместных событий.

Если группа событий не является полной, вводят дополнительное (фиктивное) событие , вероятность которого определяют по формуле:

.

Далее действуют по уже изложенному алгоритму для полной группы событий с одним изменением: если ПСЧ попадает в последний, -й интервал, считают, что пи одно из N событий, составляющих неполную группу, не наступило.

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

Для того чтобы провести моделирование двух зависимых случайных событий А и В, необходимо задать следующие полные и условные вероятности:

; ; ; .

Заметим, что, если вероятность наступления события В при условии, что событие А не наступило, не задана, ее можно определить по формуле:

.

Существуют два алгоритма моделирования зависимых событий. Один из них условно можно назвать "последовательным моделированием"; другой -- "моделированием после предварительных расчетов".

Последовательное моделирование

Алгоритм последовательного моделирования представлен на рис. 3.

Несомненными достоинствами данного алгоритма являются его простота и естественность, поскольку зависимые события "разыгрываются" последовательно -- так, как они наступают (или не наступают) в реальной жизни, что и является характерной особенностью большинства имитационных моделей. Вместе с тем алгоритм предусматривает троекратное обращение к датчику случайных чисел (ДСЧ), что увеличивает время моделирования.

Моделирование после предварительных расчетов

Приведенные на рис. 3 четыре исхода моделирования зависимых событий образуют полную группу несовместных событий. На этом основан алгоритм моделирования, предусматривающий предварительный расчет вероятностей каждого из исходов и "розыгрыш" факта наступления одного из них, как для любой группы несовместных событий. Рис. 4 иллюстрирует разбиение интервала [0;1] на четыре отрезка, длины которых соответствуют вероятностям исходов наступления событий.

Размещено на http://www.allbest.ru/

178

Рис. 4. Разбиение интервала [0;1] для реализации алгоритма моделирования зависимых событий "после предварительных расчетов".

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

Лекция №14

Имитационные модели информационных систем

Технология моделирования случайных факторов

Моделирование случайных величин

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

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

§ непрерывные;

§ дискретные;

§ смешанного типа.

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

Моделирование непрерывных случайных величин

Моделирование СВ заключается в определении ("розыгрыше") в нужный по ходу имитации момент времени конкретного значения СВ в соответствии с требуемым (заданным) законом распределения.

Наибольшее распространение получили три метода:

§ метод обратной функции;

§ метод исключения (Неймана);

§ метод композиций.

Метод обратной функции

Метод позволяет при моделировании СВ учесть все ее статистические свойства и основан на следующей теореме:

Если непрерывная СВ Y имеет плотность вероятности , то СВ X, определяемая преобразованием

,

имеет равномерный закон распределения на интервале [0;1].

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

.

Таким образом, получили равенство , а это и означает, что СВ X распределена равномерно в интервале [0;1].

Напомним, что в общем виде функция распределения равномерно распределенной на интервале СВ X имеет вид:



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

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

§ моделирование ПСЧ, равномерно распределенного на интервале [0;1];

§ подстановка этого ПСЧ в обратную функцию и вычисление значения СВ Y:

.

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

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

Метод исключения (Неймана)

Метод Неймана позволяет из совокупности равномерно распределенных ПСЧ , по определенным правилам выбрать совокупность значений с требуемой функцией распределения .

Алгоритм метода

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

В результате формируется плотность вероятности такая, что

.

Длина интервала определяется требуемой точностью моделирования значений СВ в рамках конкретного исследования.

Генерируется пара ПСЧ и , равномерно распределенных на интервале [0;1].

Вычисляется пара ПСЧ и по формулам:

;

,

.

На координатной плоскости пара чисел определяет точку -- например, точку на рис. 1. На рисунке обозначены: А -- прямоугольник, ограничивающий график плотности распределения моделируемой СВ; D -- область прямоугольника А, находящаяся ниже графика ; В -- область прямоугольника А, находящаяся выше графика .

Если точка принадлежит области D, считают, что получено первое требуемое значение СВ .

Генерируется следующая пара ПСЧ и равномерно распределенных на интервале [0;1], после пересчета по п. 3 задающих на координатной плоскости вторую точку -- .

Если точка принадлежит области В, переходят к моделированию следующей пары ПСЧ и т.д. до получения необходимого количества ПСЧ.

Очевидно, что в ряде случаев (при попадании изображающих точек в область В соответствующие ПСЧ с нечетными индексами не могут быть включены в требуемую выборку возможных значений моделируемой СВ, причем это будет происходить тем чаще, чем сильнее график по форме будет "отличаться" от прямоугольника А. Оценить среднее относительное число q "пустых" обращений к генератору ПСЧ можно геометрическим методом, вычислив отношение площадей соответствующих областей (В и А):

;

;

.

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

Метод композиции

Применение метода основано на теоремах теории вероятностей, доказывающих представимость одной СВ композицией двух или более СВ, имеющих относительно простые, более легко реализуемые законы распределения. Наиболее часто данным методом пользуются для генерации ПСЧ, имеющих нормальное распределение. Согласно центральной предельной теореме распределение СВ Y, задаваемой преобразованием

,

где -- равномерно распределенные на интервале [0;1] ПСЧ, при росте k неограниченно приближается к нормальному распределению со стандартными параметрами .

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

;

;

.

Напомним, что при равномерном распределении в интервале [0;1] СВ имеет параметры:

; .

Очевидно, что

,

и, как любая центрированно-нормированная СВ, имеет стандартные параметры.

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

,

где -- возможное значение СВ Y, полученное в результате сложения, центрирования и нормирования k равномерно распределенных ПСЧ .

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

Моделирование дискретных случайных величин

Дискретные случайные величины (ДСВ) достаточно часто используются при моделировании систем. Основными методами генерации возможных значений ДСВ являются:

§ метод последовательных сравнений;

§ метод интерпретации.

Метод последовательных сравнений

Алгоритм метода практически совпадает с ранее рассмотренным алгоритмом моделирования полной группы несовместных случайных событий, если считать номер события номером возможного значения ДСВ, а вероятность наступления события -- вероятностью принятия ДСВ этого возможного значения. На рис. 2 показана схема определения номера возможного значения ДСВ, полученного на очередном шаге.

Из анализа ситуации, показанной на рис. 2 для ПСЧ R, "попавшего" в интервал , следует сделать вывод, что ДСВ приняла свое второе возможное значение; а для ПСЧ -- что ДСВ приняла свое -e значение и т.д. Алгоритм последовательных сравнений можно улучшить (ускорить) за счет применения методов оптимизации перебора -- дихотомии (метода половинного деления); перебора с предварительным ранжированием вероятностей возможных значений по убыванию и т.п.

Размещено на http://www.allbest.ru/

178

Рис. 2. Моделирование ДСВ методом последовательных сравнений.

Метод интерпретации

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

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

Алгоритм метода для этого случая весьма прост:

§ моделируют n равномерно распределенных на интервале [0;1] ПСЧ;

§ подсчитывают число т тех из ПСЧ, которые меньше р;

§ это число т и считают возможным значением моделируемой ДСВ, подчиненной биномиальному закону распределения.

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

Моделирование случайных векторов

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

.

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

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

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

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

§ метод условных распределений;

§ метод исключения (Неймана);

§ метод линейных преобразований.

Метод условных распределений

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

Для плотности распределения случайного вектора X можно записать:

,

где -- плотность распределения СВ ; -- плотность условного распределения СВ X_k при условии: ; ; …; .

Для получения указанных плотностей необходимо провести интегрирование совместной плотности распределения случайного вектора в соответствующих пределах:

Порядок моделирования:

§ моделировать значение СВ по закону ;

§ моделировать значение СВ по закону ;

§ моделировать значение СВ по закону .

Тогда вектор и есть реализация искомого случайного вектора X.

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

Метод исключения (Неймана)

Метод является обобщением уже рассмотренного для СВ метода Неймана на случай п переменных. Предполагается, что все компоненты случайного вектора распределены в конечных интервалах

..

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

Алгоритм метода:

1. Генерируются ПСЧ: ; , распределенных, соответственно, на интервалах , ,…,; ;

.

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

3. Если данное условие не выполняется, переходят к первому пункту и т.д.

Возврат к п. 1 после "неудачного" моделирования п ПСЧ происходит тогда, когда точка Q окажется выше поверхности, представляющей двумерную плотность вероятности . Для случая, представленного на рисунке, в качестве (очередной) реализации двумерного случайного вектора следует взять пару ПСЧ .

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

Для одномерного случая, основным достоинством метода Неймана является его универсальность. Однако для плотностей вероятностей, поверхности которых имеют острые пики, достаточно часто будут встречаться "пустые" прогоны, когда очередные n ПСЧ бракуются. Этот недостаток тем существеннее, чем больше размерность моделируемого вектора и длиннее требуемая выборка реализаций случайного вектора. На практике такие ситуации встречаются не слишком часто, поэтому метод исключений и имеет столь широкое распространение.

Метод линейных преобразований

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

Идея метода заключается в линейном преобразовании случайного n-мерного вектора Y с независимыми (чаще всего -- нормально распределенными) компонентами в случайный вектор X с требуемыми корреляционной матрицей и вектором математических ожиданий компонент.

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

Дано: корреляционная матрица и математическое ожидание вектора X

;

.

Требуется: найти такую матрицу В, которая позволяла бы в результате преобразования

,(1)

где Y -- n-мерный вектор с независимыми нормально распределенными компонентами со стандартными параметрами, получить вектор X с требуемыми характеристиками.

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

(2)

Поскольку компоненты вектора Y независимы и имеют стандартные параметры, справедливо выражение:

Почленно перемножив сами на себя и между собой соответственно левые и правые части уравнений системы (2) и взяв от результатов перемножения математическое ожидание, получим систему уравнений вида:

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

Последовательно решая эту систему, получаем формулы для расчета элементов :

; ; ;…

Формула для расчета любого элемента матрицы преобразования имеет вид:

.

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

§ по заданной корреляционной матрице рассчитывают значения коэффициентов матрицы преобразования В;

§ генерируют, одну реализацию вектораY, компоненты которого независимы и распределены нормально со стандартными параметрами;

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

§ при необходимости два предыдущих шага алгоритма повторяют требуемое число раз (до получения нужного количества реализаций вектора X).

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

Лекция №15

Имитационные модели информационных систем

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

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

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

· сложностью исследуемого объекта-оригинала;

· точностью, предъявляемой к результатам расчетов.

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

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

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

· испытание модели;

· исследование свойств модели;

· планирование имитационного эксперимента;

· эксплуатация модели (проведение расчетов).

Охарактеризуем первые два этапа.

Рис. 1. Этапы машинного эксперимента.

Испытание имитационной модели

Испытание имитационной модели включает работы по четырем направлениям:

· задание исходной информации;

· верификацию имитационной модели;

· проверку адекватности модели;

· калибровку имитационной модели.

Задание исходной информации

Процедура задания исходной информации полностью определяется типом моделируемой системы:

· если моделируется функционирующая (существующая) система, проводят измерение характеристик ее функционирования и затем используют эти данные в качестве исходных при моделировании;