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

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

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КУРСОВАЯ РАБОТА

по дисциплине «Компьютерное моделирование»

на тему: Построение алгоритмов функционирования дискретно-событийной модели системы

Самара 2024

РЕФЕРАТ

Курсовая работа содержит 35 страниц, 3 рисунка, 13 источников.

Ключевые слова: АЛГОРИТМ, ДИСКРЕТНО-СОБЫТИЙНОЕ МОДЕЛИРОВАНИЕ, ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ, МОДЕЛЬ, МОДЕЛИРОВАНИЕ, ПРИНЦИПЫ, СИСТЕМЫ.

Объект работы - дискретно-событийная модель системы.

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

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

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

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

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

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

Область применения: результаты работы могут быть рекомендованы при изучении дискретно-событийного моделирования.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

1 ПОНЯТИЕ МОДЕЛИ. КЛАССИФИКАЦИЯ СИСТЕМ И МОДЕЛЕЙ 6

1.1 Основные понятия

1.2 Классификация систем и моделей

2 ПРИНЦИПЫ СИСТЕМНОГО И ИМИТАЦИОННОЕ ПОДХОДА

В МОДЕЛИРОВАНИИ СИСТЕМ

2.1 Основные подходы к построению математических моделей систем

2.2 Принципы системного подхода в моделировании систем

2.3 Имитационное моделирование. Метод статистического моделирования

3 ДИСКРЕТНО-СОБЫТИЙНЫЕ СИСТЕМЫ И МОДЕЛИ. СХЕМА

АЛГОРИТМА МОДЕЛИРОВАНИЯ СТОХАСТИЧЕСКИХ ДИСКРЕТНО-СОБЫТИЙНЫХ СИСТЕМ алгоритм моделирование дискретный

3.1 Дискретно-событийные системы и компоненты дискретно-событийной имитационной модели

3.2 Организация компонентов дискретно-событийной имитационной модели

3.3 Схема алгоритма моделирования стохастических дискретно-событийных систем

3.3 Примеры дискретно-событийного моделирования

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

Объект работы - дискретно-событийная модель системы.

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

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

В соответствии с целью определены следующие задачи:

- изучить понятие модели, классификации систем и моделей;

- охарактеризовать принципы системного и имитационного подхода в моделировании систем;

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

алгоритма моделирования стохастических дискретно-событийных систем.

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

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

Теоретической и методологической основой написания работы послужили труды таких ученых, как В.В. Афонина, А.В. Дигрис, Ю. А. Кораблева, А.В. Петрова и других.

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

1. ПОНЯТИЕ МОДЕЛИ. КЛАССИФИКАЦИЯ СИСТЕМ И МОДЕЛЕЙ

1.1 Основные понятия

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

Моделирование - замена исследуемой системы другой аналогичной системой, в которой отражаются существенные свойства моделируемой системы [2, c,34].

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

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

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

Известны 4 случая применения моделей:

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

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

- модель как инструмент прогнозирования;

- модель как процедура организации эксперимента позволяет проводить эксперименты в таких ситуациях, когда на реальном объекте это невозможно [2, c. 35].

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

Рисунок 1.1- Классификация мыслительных моделей

1. В основе гипотетической модели лежит некоторая гипотеза о реальном объекте. Такие модели применяют в тех случаях, когда знаний об объекте недостаточно для построения формальной модели [3, c, 48].

Аналоговые модели основаны на применении аналогий различного уровня.

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

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

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

3. Аналитические модели - математические модели, которые представлены аналитическими математическими объектами (дифференциальные уравнения или их системы, интегральные уравнения т.д.)

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

Имитационная модель - совокупность описания статических свойств системы, а также динамики изменения состояния и взаимосвязей элементов системы во времени под влиянием факторов внешней среды и внутренней логики функционирования системы. ИМ задается совокупностью моделирующих алгоритмов, воспроизводящих (копирующих) с заданной степенью детализации развитие физических процессов, происходящих в исследуемой системе, т.е. задающих модель поведения [10, c. 18].

Дискретно-событийное моделирование (англ. discrete-event simulation, DES)- это вид имитационного моделирования. В дискретно-событийном моделировании функционирование системы представляется как хронологическая последовательность событий.

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

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

1.2 Классификация систем и моделей

В зависимости от различных признаков системы и модели относятся к тем или иным классам [7, c, 55].

Системы: статические - фактор времени не учитывается; динамические - время играет существенную роль, система функционирует во времени.

При описании динамических систем используется понятие состояние системы. Состояние системы описывается набором переменных состояния (z1,z2,…zn). Математически, состояние системы можно интерпретировать в виде К-мерного пространства (фазовое пространство).

Движение (функционирование) системы можно проиллюстрировать некоторой кривой - траекторией движения.

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

Y=F(x,z,t),	(1.1)

где x - вектор входных параметров X=(X1,X2,…Xn);

z - вектор состояний Z=(Z1,Z2,…Zn);

y - вектор выходных параметров Y=(Y1,Y2,…Yn).

Динамические системы: непрерывные - состояние непрерывных систем меняется постоянно с течением времени; дискретные - изменение состояний происходит в отдельные (выделенные) моменты времени.

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

Исследования таких моделей сводятся к решению таких уравнений или систем таких уравнений.

Решение стремятся произвести аналитическими методами. Иногда аналитическое решение задачи получить не удается и тогда используют численные методы (методы приближенного или точного решения математических задач оптимизации, сводящиеся к выполнению конечного числа элементарных операций над числами). Это означает, что модель дискретизируется, т.е. непрерывная система заменяется дискретной [7, c.58].

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

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

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

.

2. ПРИНЦИПЫ СИСТЕМНОГО И ИМИТАЦИОННОЕ ПОДХОДА В МОДЕЛИРОВАНИИ СИСТЕМ

2.1 Основные подходы к построению математических моделей систем

Под математической моделью объекта (реальной системы) понимают конечное подмножество входных воздействий на систему, воздействий внешней среды, совокупности внутренних (собственных) параметров системы вместе с математическими связями между ними и совокупностью выходных характеристик системы [9, c.38].

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

Соответственно этим подходам были разработаны типовые математические схемы создания моделей [9, c.40

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

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

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

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

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

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

2.2 Принципы системного подхода в моделировании систем

Моделирование является одним из наиболее важных методов научного исследования и экспериментирования [12, c. 64]

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

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

- подсистема является функционально независимой частью объекта. Она связана с другими подсистемами, обменивается с ними информацией и энергией;

- для каждой подсистемы могут быть определены функции или свойства, не совпадающие со свойствами всей системы;

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

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

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

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

В связи с системным подходом к построению моделей используется понятие инфраструктуры, описывающей взаимосвязи системы с ее окружением (средой) [8, c. 42].

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

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

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

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

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

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

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



2.3 Имитационное моделирование. Метод статистического моделирования

Имитационное (программное) моделирование - при котором логико-математическая модель исследуемой системы представляет собой алгоритм функционирования системы, программно-реализуемый на компьютере [1, c.55].

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

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

Имитационное моделирование, при котором воспроизводятся случайные явления, называется статистическим имитационным моделированием. Случайные факторы при построении компьютерной модели имитируются при помощи случайных чисел, формируемых ЭВМ. Таким образом, под статистическим имитационным моделированием понимают построение имитационной модели существующего или гипотетического (предполагаемого, разрабатываемого) объекта, учитывающей случайные явления, и проведение экспериментов на этой модели. Статистическое имитационное моделирование базируется на численном статистическом методе решения математическим задач, называемых методом Монте-Карло [11,c. 12].

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

Метод Монте-Карло является основным принципом моделирования систем, содержащих стохастические или вероятностные элементы. Его зарождение связано с работой фон Неймана и Улана в конце 40-х годов XX-ого века, когда они ввели термин «Монте-Карло» и применили этот метод к решению задач ядерных излучений. Применение метода оказалось настолько успешным, что он получил распространение и в других областях науки и техники, включая экономические науки.

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

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

В общем случае объектом-оригиналом может быть любая естественная или искусственная система, предназначенная для выполнения определенного вида работ или решения определенного класса задач. Она состоит из компонентов С0, называемых также элементами или подсистемами, имеет некоторое множество параметров P0 и характеризуется определенными свойствами S0. Система проявляет эти свойства под влиянием внешних воздействий X0 и в результате физических процессов A0, определяющих принципы ее функционирования. Количественной мерой свойств системы служит Y0 являются частными показателями эффективности системы. Показатель эффективности -это числовая характеристика системы, которая оцениваетмножество характеристик Y0. Элементы множества характеристик Y0i степень приспособленности системы к выполнению поставленных перед ней задач, т.е. качество ее функционирования [13, c. 32].

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

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

3. ДИСКРЕТНО-СОБЫТИЙНЫЕ СИСТЕМЫ И МОДЕЛИ.

СХЕМА АЛГОРИТМА МОДЕЛИРОВАНИЯ СТОХАСТИЧЕСКИХ ДИСКРЕТНО-СОБЫТИЙНЫХ СИСТЕМ

3.1 Дискретно-событийные системы и компоненты дискретно-событийной имитационной модели

Дискретно-событийное моделирование - это вид имитационного моделирования. В дискретно-событийном моделировании функционирование системы представляется как хронологическая последовательность событий. Событие происходит в определенный момент времени и знаменует собой изменение состояния системы [6, c. 33].

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

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

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

- состояние системы - совокупность переменных состояния, необходимых для описания системы в определенный момент времени;

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

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

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

- программа инициализации - подпрограмма, устанавливающая в исходное состояние имитационную модель в момент времени, равный 0;

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

- программа обработки событий - подпрограмма, обновляющая состояние системы, когда происходит событие определенного типа (для каждого типа событий существует отдельная программа обработки событий);

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

- генератор отчетов - подпрограмма, которая считывает оценки (со статистических счетчиков) критериев оценки работы и выдает отчет по окончании моделирования;

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

- условие завершения. Условием завершения могут выступать: возникновение заданного события (например, достижение 10 мин времени ожидания в очереди) [6, c.34].

Логические отношения (поток управления) между данными компонентами показаны на рис. 3.1.

Рисунок 3.1- Поток управления в механизме продвижения времени от события к событию

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

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

Если следующим должно произойти событие типа 2, часы имитационного времени переводятся на время возникновения события типа i, и управление возвращается основной программе [4, c.72].

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

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

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

Если время прекращения моделирования еще не настало, управление снова передается основной программе, и цикл «основная программа -синхронизирующая программа -основная программа -программа обработки событий -проверка условия прекращения имитации» повторяется до тех пор, пока условие останова не будет выполнено[4, c.73].

3.2 Организация компонентов дискретно-событийной имитационной модели

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

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

Существует альтернативный подход к имитационному моделированию, именуемый процессным подходом. При этом моделирование рассматривается с точки зрения отдельных объектов, участвующих в нем, и разработанный код описывает «опыт» отдельного «типичного» объекта по мере его «перемещения» по системе [5, c. 66].

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

3.3 Схема алгоритма моделирования стохастических дискретно-событийных систем

Схему моделирования дискретно-событийной системы можно представить в следующем виде [6, c.57]:

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

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

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

Рисунок 3.2- Схема алгоритма моделирования стохастических дискретно-событийных систем

При дискретной имитации функционирования системы считается, что ее состояние может изменяться только в моменты времени совершения событий. Между этими моментами времени состояние системы и ее компонентов полагается неизменным. Для получения картины поведения системы во времени в модели организуется продвижение имитационного времени от одного события к другому при обязательном учете возможности параллельного выполнения в реальной системе нескольких действий сразу. Очевидно, что в алгоритмических реализациях моделей систем этот параллелизм действий может быть реализован лишь за счет последовательного обслуживания событий или действий, одновременно возникающих в разных компонентах реальной системы. Когда имитация одновременно появившихся событий в системе будет завершена и будут определены моменты совершения следующих событий, начала или завершения следующих действий или процессов, тогда производится сдвиг модельного времени до момента совершения ближайшего по времени события. По способу организации квазипараллелизма действий в имитационной модели различают четыре методологических подхода к построению дискретных моделей систем: событийный подход; подход, ориентированный на действия, называемый часто подходом сканирования активностей; транзактный подход и процессорно-ориентированный подход. Рассмотрим эти подходы подробнее [6, c.58].

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

Перед началом имитации управляющая программа моделирования устанавливает начальные состояния моделей компонентов системы и задает начальные параметры, определяющие условия совершения событий и времени, затем управление передается на программу проверки выполнимости условий совершения событий. В процедурах поверки появления события реализуется зависимость выполнения соответствующего этому событию действия от конкретной ситуации, имеющей место в реальной системе. Имена тех событий, для которых эти условия выполнены, заносятся в список инициализируемых, т.е. совершившихся, событий. Если этот список содержит хотя бы одно событие, то начинается последовательное выполнение процедур обслуживания событий, каждая из которых реализует алгоритм, имитирующий соответствующее действие компонента системы. В большинстве случаев имитация действия происходит путем временной задержки ф, равной времени совершения этого действия компонентом в реальной системе. Завершается работа алгоритма имитации действия оператором, который модифицирует значение момента совершения этого действия в будущем и возвращает управление на выполнение следующей по порядку процедуры обслуживания событий, имя которой определяется управляющей программой моделирования [6, c. 60].

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

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

3.3 Примеры дискретно-событийного моделирования

Дискретно-событийное моделирование используется для построения модели, отражающей развитие системы во времени, когда состояния переменных меняются мгновенно в конкретные моменты времени. (Говоря математическим языком, система может меняться только в исчислимое количество моментов времени.) В такие моменты времени происходят события, при этом событие определяется как мгновенное возникновение, которое может изменить состояние системы. Хотя теоретически дискретно-событийное моделирование можно осуществлять с помощью вычислений вручную, количество данных, которые должны сохраняться и обрабатываться при моделировании большинства реальных систем, диктует необходимость применения вычислительных машин [6, c. 72].

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

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

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

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

Для построения дискретно-событийной модели необходимо определить все основные события, при которых может измениться состояние системы, и сгруппировать их в классы по способу (алгоритму) реализации (свершения). Каждое событие должно характеризоваться, кроме класса, набором параметров (атрибутов), используемых в модели, и временем свершения (или интервалом свершения, отсчитываемого, как правило, от текущего момента ) [6, c.73].

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

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

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

Сбор данных ведется в любом месте программы моделирования в соответствии с разработанным алгоритмом.

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

Имитационная модель системы представляет собой набор процедур, моделирующих действия, и процедур проверки выполнимости условий начала или завершения действий. Условия начала или окончания действий проверяются после очередного продвижения имитационного времени. Для того чтобы могло быть выполнено каждое действие в модели, проверка условий (сканирование) производится для всего множества действий при каждом продвижении имитационного времени [1, c.58].

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

Шаг 1. Устанавливаются начальные состояния компонентов системы и исходные значения параметров, определяющих инициализацию событий, устанавливается начальное значение модельного времени t=to .

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

Шаг 3. Если список пустой, то переход к шагу 4, иначе передается управление на выполнение процедуры обслуживания первого события из списка, Модифицируется время совершения данного события в будущем tj=t+j , и оно исключается из списка. Переход к шагу 2.

Шаг 4. В списке запланированных событий находится событие, имеющее минимальное время инициализации j , и корректируется модальное время, которое полагается равным этому моменту времени.

Шаг 5. Проверяется условие окончания имитационного моделирования, если оно не выполняется, то переход к шагу 2.

Шаг 6. Оформляются результаты моделирования.

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

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

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

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

ЗАКЛЮЧЕНИЕ

Выполнение данной работы позволяет сделать следующие выводы.

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

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

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

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

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

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

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

Можно имитировать поведение тех объектов, реальные эксперименты с которыми дороги, невозможны или опасны.

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

...