рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

2. Имитационные методы моделирования

2. Имитационные методы моделирования - раздел Промышленность, Лекция 1 Введение С Точки Зрения Философии, Моделирование П...

Лекция 1

Введение

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

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

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

 

1. Аналитические методы моделирования

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

 

2. Имитационные методы моделирования

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

 

4. Проблемы применения имитационного моделирования

Применение имитационного моделирования целесообразно при наличии определенного условия. Эти условия определяет Р. Шеннон:

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

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

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

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

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

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

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

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

 

 

3. Математические модели систем

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

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

,

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

- совокупность внутренних параметров системы,

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

F - закон функционирования системы.

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

,

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

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

.

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

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

,

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

Простейшую систему автоматического управления можно представить в следующем виде:

 
 


x(t) h'(t) y(t)

 

Разность между заданными yзад(t) и действительным y(t) законами изменения управляемой величины есть ошибка управления h'(t)=yзад(t)-y(t). Если предписанный закон изменния управляемой величины соответствует закону изменения входного (задающего) воздействия, т.е. x(t)=y(t), то h'(t)=x(t)-y(t).Принцип обратной связи (основной принцип систем автоматического управления): приведение в соответствие выходной переменной y(t) ее заданному значению используется информация об отклонении h'(t) между ними. Задачей системы автоматического управления является изменение выходных сигналов согласно заданному закону с определенной точностью (с допустимой ошибкой).

2. Дискретно-детерминированный подход реализуется с помощью математического аппарата теории автоматов. Система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. Математической моделью при этом подходе является конечный автомат, характеризующийся конечным множеством X входных сигналов, конечным множеством Y выходных сигналов, конечным множеством Z внутренних состояний, начальным состоянием Z0 Z; функцией переходов g(z,x); функцией выходов v(z,x). Автомат функционирует в дискретном автоматном времени, моментами которого являются такты (примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния).

Работа конечного автомата происходит по следующей схеме: в каждом t-м такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который он реагирует переходом в (t+1)-м такте в новое состояние z(t+1) и выдачей некоторого выходного сигнала. Например, автомат первого рода (автомат Мили) описывается следующим образом:

z(t+1)=g[z(t),x(t)], t=0,1,2,...;

y(t)=v[z(t),x(t)], t=0,1,2,...;

для автомата второго рода:

z(t+1)=g[z(t),x(t)], t=0,1,2,...;

y(t)=v[z(t),x(t-1)], t=1,2,3...;

Автомат, для которого функция выходов не зависит от входной переменной x(t), называется автоматом Мура:

y(t)=v[z(t)], t=0,1,2,...

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

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

Простейший табличный способ задания конечного автомата основан на использовании таблиц переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы - его состояниям. При этом обычно первый слева столбец соответствует начальному состоянию z0. На пересечении i-й строки и k-го столбца таблицы переходов помещается соответствующее значение g (zk, xi) функции переходов, а в таблице выходов - соответствующее значение v (zk, xi) функции выходов. Для конечного автомата Мура обе таблицы можно совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием zk автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию, согласно, выходной сигнал v (zi).

Описание работы конечного автомата Мили таблицами переходов g и выходов v иллюстрируется табл. 1., а описание конечного автомата Мура - таблицей переходов (табл. 2).

Таблица 1

xi   zk
z0 z1 ... zk
Переходы
x1 g(z0,x1) g(z1,x1) ... g(zk,x1)
x2 g(z0,x2) g(z1,x2) ... g(zk,x2)
... ... ... ... ...
xk g(z0,xk) g(z1,xk) ... g(zk,xk)
  Выходы
x1 v(z0,x1) v(z1,x1) ... v(zk,x1)
x2 v(z0,x2) v(z1,x2) ... v(zk,x2)
... ... ... ... ...
xk v(z0,xk) v(z1,xk) ... v(zk,xk)

 

Таблица 2

xi   v(zk)
v(z0) v(z1) ... v(zk)
z0 z1 ... zk
Переходы
x1 g(z0,x1) g(z1,x1) ... g(zk,x1)
x2 g(z0,x2) g(z1,x2) ... g(zk,x2)
... ... ... ... ...
xk g(z0,xk) g(z1,xk) ... g(zk,xk)

 

Примеры табличного способа задания конечного автомата Мили приведены в табл. 3, а для автомата Мура в табл. 4.

Таблица 1

xi   zk
z0 z1 z2
Переходы
x1 z2 z0 z0
x2 z0 z2 z1
  Выходы
x1 y1 y1 y2
x2 y1 y2 y1

 

Таблица 2

xi   y
y1 y1 y3 y2 Y3
z0 z1 z2 z3 Z4
x1 z1 z4 z4 z2 Z2
x2 z3 z1 z1 z0 Z0

При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xk вызывает переход из состояния zi в состояние zj , то на графе автомата дуга, соединяющая вершину zi с вершиной zj , обозначается xk. Дуги графа отмечаются соответствующими выходными сигналами.

При решении задач моделирования систем часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица С=||cij||, строки которой соответствуют исходным состояниям, а столбцы - состоянием перехода. Элемент cij = xk/ys, в случае автомата Мили соответствует входному сигналу xk , вызывающему переход из состояния zi в состояние zj , и выходному сигналу ys , выдаваемому при этом переходе. Для автомата Мили, рассмотренного выше, матрица соединений имеет вид:

Если переход из состояния zi в состояние zj происходит под действием нескольких сигналов, элемент матрицы cij представляет собой множество пар "вход-выход" для этого перехода, соединенных знаком дизъюнкции.

Для автомата Мура элемент cij - равен множеству входных сигналов на переходе (zi,zj).

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

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

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

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

ui

yi

wi

П

 

Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий и задается последовательностью {tn }={0<= t1<= t2 ... <= tn <=...}, где tn - момент наступления n-го события (неотрицательное вещественное число).

Потоком неоднородных событий называется последовательность {tn,fn }, где fn - набор признаков события (приоритет, принадлежность к какому-либо источнику и т.д.)

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

Поток событий называется ординарным, если вероятность того, что на малый интервал времени , примыкающий к моменту времени t, попадает больше одного события P>1(t, ) пренебрежительно мала по сравнению с вероятностью того, что на этот же интервал времени попадает ровно одно событие P1(t, ). Для любого интервала верно следующее:

P0(t, )+ P1(t, )+ P>1(t, )=1

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

P0(t, )+ P1(t, )=1, P>1(t, )=0().

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

Рассмотрим на оси времени ординарный поток событий и найдем среднее число событий, наступающих на интервале времени :

0·P0(t, )+1·P1(t, )= P1(t, )

Тогда среднее число событий ординарного потока в единицу времени (интенсивность потока):

Для стационарного потока интенсивность постоянна.

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

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

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

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

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

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

где - вероятность нахождения системы в состоянии zn(t) Î Z в момент времени t, т.е. когда в ней имеется n заявок.

Эти уравнения следуют из того, что вероятность нахождения в системе n заявок в момент времени (t+Dt) равна вероятности нахождения в системе n заявок в момент t, умноженной на вероятность того, что за время Dt в систему не поступит ни одной заявки и ни одна заявка не будет обслужена, плюс вероятность нахождения в системе (n-1) заявок в момент времени t, умноженная на вероятность того, что за время Dt поступит одна заявка и ни одна заявка обслужена не будет, плюс вероятность нахождения в системе (n+1) заявок в момент t, умноженная на вероятность того, что за время Dt одна заявак покинет систему и не поступит ни одной заявки. Вероятность того, что за время Dt не поступит ни одной заявки и ни одна заявка не покинет систему, равна . Член, содержащий (Dt)2, при составлении дифференциального уравнения опускается. Следовательно, можно записать . Относительно остальных двух членов первого уравнения заметим, что

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

найдем выражение для математического ожидания числа заявок, находящихся в накопителе, и среднего времени ожидания заявок в накопителе для стационарного состояния r=l/m<1. Приравняв нулю производные по времени и исключив, таким образом, t из уравнений, получим систему алгебраических уравнений

Пусть в первом уравнении n=1. Тогда (1+r)p1= p2+rp0 . Подставив сюда значение p1 из второго уравнения, находим p2=r2p0. Повторяя эти операции, получаем pn=rnp0 , причем так как это сумма вероятностей того, что в системе нет ни одной заявки, имеется одна заявка, две заявки и т.д. Сумма этих вероятностей должна быть равна единице, так как рассматриваются все возможные состояния системы. Поэтому

Или , откуда . Следовательно,

Математическое ожидание числа заявок, находящихся в системе (приборе),

.

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

.

При этом

.

Следовательно,

.

Математическое ожидание числа заявок, находящихся в накопителе,

.

Среднее время ожидания заявок в накопителе

.

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

 

4. Статистическое моделирование

 

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

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

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

2 области применения: 1) изучение стохастических систем; 2) решение детерминированных задач.

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

Теоретическая основа метода статистического моделирования является пре дельнее теоремы теории вероятностей. Их значение - гарантируют высокое качество статистических оценок при числе испытаний N ® ¥. Часто приемлемые результаты могут быть получены при достаточно небольших N.

Неравенство Чебышева. Для неотрицательной случайной величины X и любого K>0 выполняется неравенство:

P(X>=K)=<M(X)/K

Теорема Бернулли. Если проводится N независимых испытаний, в каждом из которых некоторое событие А осуществляется с вероятностью p, то относительная частота появления события m/N при N ® ¥ сходится по вероятности к p, т.е. при любом e>0

, где m - число положительных исходов испытания.

Теорема Пуассона.

, где pi - вероятность осуществления события А в i-м испытании.

 

Обобщенная теорема Чебышева.

, Xi - i-ая случайная величина

Теорема Маркова. Обобщенная теорема Чебышева справедлива и для зависимых случайных величин, если

Центральная предельная теорема. Если X1 , X2,..., Xn - независимые одинаково распределенные случайные величины, имеющие математическое ожидание M(Xi)=a и дисперсию s2, то при N ® ¥ закон распределения суммы неограниченно приближается к нормальному:

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

Пример 1. Входное воздействие - , воздействие внешней среды - - случайные величины с известными функциями распределения.

Необходимо определить математическое ожидание величины y:

Схема алгоритма (ген. - генерация):

 

 
 

 


Пример 2. Необходимо найти площадь фигуры:

 

 

Пример 3. Проводится s=10 независимых выстрелов по мишени, причем вероятность попадания при одном выстреле задана и равна p. Требуется оценить вероятность того, что число попаданий в мишень будет четным.

Аналитическое решение этой задачи:

Схема алгоритма (статистическое моделирование):

 

 

 
 

 

 


Генерация последовательности случайных чисел

Существует три способа генерации случайных чисел:

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

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

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

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

Непрерывная случайная величина имеет равномерное распределение в интервале (a,b), если ее функции плотности и распределения соответственно примут вид

Для получения случайных чисел на ЭВМ используются алгоритмы, поэтому такие последовтельности, являющиеся по сути детерминированными, называются псевдослучайными. ЭВМ оперирует n-разрядными числами, поэтому поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0,1) используют дискретную последовательность 2n случайных чисел того же интервала - закон распределения такой дискретной последовательности называется квазиравномерны распределением.

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

1. Последовательность должна состоять из квазиравномернло распределенных чисел.

2. Числа должны быть независимыми.

3. Последовательности случайных чисел должны быть воспроизводимыми.

4. Последовательности должны иметь неповторяющиеся числа.

5. Последовательности должны получаться с минимальными затратами вычислительных ресурсов.

Наибольшее применение в практике моделирования на ЭВМ для генерации последовательностей псевдослучайных числе находят алгоритмы вида:

xi+1=Ф(xi),

представляющие собой реккурентные соотношения первого порядка.

Пример. x0 = 0,2152 , (x0)2=0,04631104 , x1 = 0,6311 , (x1)2=0,39828721, x2=0,8287 и т.д.

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

x0 = 0,4500 , (x0)2=0,20250000, x1 = 0,2500 , (x1)2=0,06250000, x2=0,2500 и т.д.

Широкое применение получили конгруэнтные процедуры генерации псевдослучайных последовательностей.

Два целых числа a и b конгруэнтны (сравнимы) по модулю m, где m - целое число, тогда и только тогда, когда существует такое целое число k, что a-b=km.

1984º4 (mod 10), 5008º8 (mod 103).

Большинство конгруэнтных процедур генерации случайных чисел основаны на следующей формуле:

где - неотрицательные целые числа.

По целым числам последовательности {Xi} можно построить последовательность {xi}={Xi/M} рациональных чисел из единичного интервала (0,1).

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

Методы улучшения качества последовательностей случайных чисел:

1. Использование рекуррентных формул порядка r:

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

2. Метод возмущений:

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

1. Необходимо реализовать случайное событие А, наступающее с заданной вероятностью p. Определим А как событие, состоящее в том, что выбранное значение xi равномерно распределенной на интервале (0,1) случайной величины удовлетворяет неравенству:

xi =<p.

Тогда вероятность события А будет Противоположное событие состоит в том, что xi >p, его вероятность равна 1-р.

2. Рассмотрим группу событий. Пусть А1, А2 ,..., Аs - полная группа событий, наступающих с вероятностями p1, p2 ,..., ps соответственно. Определим событие Аm как событие, состоящее в том, что выбранное значение xi случайной величины удовлетворяет неравенству

,

где

Процедура моделирования испытаний в этом случае состоит в последовательном сравнении случайных чисел xi со значениями lr. Если условие выполняется, исходом испытания оказывается событие Аm .

3. Рассмотрим независимые события А и В с вероятностями наступления рА и рВ. Возможными исходами совместных испытаний в этом случае будут события АВ, с вероятностями рАрВ, (1-рАВ, рА(1-рВ), (1-рА)(1-рВ). Для моделирования совместных испытаний можно использовать два варианта процедуры:

- Последовательное выполнение процедуры, рассмотренной в п.1.

- Определение одного из исходов АВ, по жребию с соответствующими вероятностями, т.е. процедура, рассмотренная в п.2.

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

4. События А и В являются зависимыми и наступают с вероятностями pА и pВ . Обозначим через pА(В) условную вероятность наступления события В при условии, что событие А произошло. Алгоритм модели подобного случая может быть следующим:

 

 

 
 

 

 


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

Дискретная случайная величина Y принимает значения y1<= y2<=… <= yj<=… с вероятностями p1, p2, …, pj,… составляющими дифференциальное распределение вероятностей

Y y1 y2 yj
P p1 p2 pj

При этом интегральная функция распределения

Длля получения дискретных случайных величин можно воспользоваться методом обратных функций: если X – равномерно распределенная на интервале (0,1) случайная величина, то искомую случайную величину получают при выполнении следующих действий:

Если x1< p1 , то Y= y1 , иначе,

Если x1< p1 + p2, то Y= y2 , иначе,

…………………………………..

Если x1<, то Y= ym , иначе,

……………………………………

Дискретное распределение (общий случай). Предположим, что известны частоты а, выбора из N объектов на определенном интер­вале времени, i=1,..., N. Пример таких частот для N=7 представлен в табл. 1.3. Первая строка таблицы - это номер объекта, а вторая - частота его выбора. Требуется разработать программную функцию, которая должна возвращать значение номера объекта в соответствии

Таблица 1

Значения обратных функций для получения дискретного распределения

Воспользуемся методом обратных функций. Сначала найдем сумму всех частот – получим S=291. После этого построим таблицу нормированных значений… Полученные значения находятся в четвертой строке табл. 1.. Построим график… gi-1 < pt <= gi

А С В x

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

Рис. 5. Событийный подход

 

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

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

Оба подхода имеют как достоинства, так и недостатки. К достоинствам процессно-ориентированного представления моделей следует отнести компактность и наглядность (рис. 6). Здесь стрелками показано направление развития процессов. Событийные модели обладают большей гибкостью, но они уступают процессно-ориентированным системам в простоте и наглядности составления моделей.

 

 

 

 


Рис. 6. Графическое представление примера процесса продвижения транзактов

 

Моделирование работы с материальными ресурсами.

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

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

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

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

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

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

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

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

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

 

Имитация информационных ресурсов.

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

- стартовый информационный ресурс, без которого нельзя начинать выполнение функции (например, права или разрешение на ее выполнение, инструкция по сборке принципиально нового устройства);

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

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

Оперативный информационный ресурс может описываться также разными способами - одним из них является использование операторов захвата и освобождения прибора (В GPSS - PREEMPT, RETURN).

 

 

Общие понятия сетей Петри

 

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

N = <B,D,I,O>,

где B - конечное множество позиций; D - конечное множество переходов; I - входная функция (прямая функция инцидентности), I:BXD®{0,1}; O - выходная функция (обратная функция инцидентности), O:DXB®{0,1}.

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

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

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

 

приход заявки

 

заявка ждет обслуживания

 

Канал обслуживания заявка обрабатывается

свободен (канал занят)

конец обслуживания

 

заявка ждет вывода

выход заявки

Рис. 1. Структура N-схема

Для представления динамических свойств объекта вводится функция маркировки (разметки) . Маркировка - присвоение абстрактных объектов, называемых метками (фишками), позициям:

NM = <B,D,I,O,M>.

Функционирование сети Петри отражается путем перехода от разметки к разметке. M0 - начальная разметка. Смена разметок - срабатывание одного из переходов сети. Необходимое условие срабатывания перехода :

,

где - разметка позиции .

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

,

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

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

 

 

2. Анализ сетей Петри

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

Рассмотрим свойство ограниченности. Позиция является к-ограниченной, если количество фишек в ней не может превышать целое число k: M(bi)£k, для всех MÎR(N,M) (множество достижимости). 1-ограниченная позиция называется безопасной. Сеть Петри ограниченна, если все ее позиции ограничены. Изучение данного свойства может иметь важное практическое значение при проектировании технических систем, в которых должно быть ограниченно присутствие одновременное присутствие активных процессов, например моделирование транспортных потоков или систем управления трафиком в глобальных вычислительных сетях. Такие системы должны быть обеспечены механизмами автоматической разгрузки или распределения.

Важным свойством для сетей Петри является сохранение. Сеть Петри является с начальной маркировкой М называется сохраняющей по отношению к вектору взвешивания W=(w1, w2,..., wn), n=|B|, wi >0, если для всех возможных маркировок выполняется следующее условие: å wi × M'(bi)= å wi × M(bi).

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

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

Очевидными являются задачи достижимости и покрываемости. Задача достижимости: можно ли из данной маркировки М достичь маркировки М'?. Задача покрываемости: для данной маркировки М существует ли достижимая маркировка М', такая что M'>=M.

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

– Конец работы –

Используемые теги: Имитационные, Методы, моделирования0.055

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

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

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

Еще рефераты, курсовые, дипломные работы на эту тему:

Методы решения жестких краевых задач, включая новые методы и программы на С++ для реализации приведенных методов
Стр. 8. Второй алгоритм для начала счета методом прогонки С.К.Годунова.Стр. 9. Замена метода численного интегрирования Рунге-Кутта в методе прогонки… Стр. 10. Метод половины констант. Стр. 11. Применяемые формулы… Стр. 62. 18. Вычисление вектора частного решения неоднородной системы дифференциальных уравнений. Стр. 19. Авторство.…

Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева
При прямом включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности и все элементы готовой… Полностью алгоритм прямого выбора приводится в прогр. 3. Таблица 2. Пример… Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения.Для С имеем…

Расчет площади сложной фигуры с помощью метода имитационного моделирования
Используя датчик случайных чисел разыгрываются координаты случайной точки из этого прямоугольника . Проверяем попадаете точки в заданную фигуру.… Причем для наглядности решения вполне достаточно порядка 3. Коэффициенты… А именно отдельно в виде процедур были решены задачи Файл WINDOW.C -ввод параметров процедура getpoly -сообщение об…

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

РАЗРАБОТКА МАКЕТА УЧЕБНОГО ПОСОБИЯ МЕТОД ПО ДИСЦИПЛИНЕ МОДЕЛИРОВАНИЕ И МАКЕТИРОВАНИЕ ОДЕЖДЫ Структура учебного пособия Моделирование и макетирование одежды
Учебное пособие основной источник информации Предметное и педагогическое содержание Определяет содержание обучения...

Исследование помехоустойчивого канала передачи данных методом имитационного моделирования на ЭВМ
Хотя практически всегда имеет место такая зависимость, избыточность источника стараются устранить, повысив тем самым эффективность и надежность… Реализуемая практически каждой ЭВМ функция random дает КСП с очень большим… О лучших случайных характеристиках можно также судить по графикам АКФ рисунок 2 квазислучайная последовательность…

По дисциплине Методы моделирования в гидрогеологии
Государственное образовательное учреждение... высшего профессионального образования... НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ...

По дисциплине Методы моделирования в гидрогеологии
Государственное образовательное учреждение... высшего профессионального образования... НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ...

Метод конечных разностей или метод сеток
Суть метода состоит в следующем. Область непрерывного изменения аргументов, заменяется дискретным множеством точек узлов, которое называется сеткой… Такие системы часто называют разностными схемами. И эти схемы решаются… По нашей области G построим равномерные сетки Wx и Wy с шагами hx и hy соответственно . Wx xiihx, i0,1 N, hxNa Wy…

ОПТИМИЗАЦИЯ РАЗВИТИЯ ГЕНЕРИРУЮЩИХ МОЩНОСТЕЙ НА ОСНОВЕ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ
Сущность имитационного подхода Блоки имитационной... модели...

0.035
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам