Имитационное моделирование

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

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

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

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

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

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

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

G=F(X,Y)

Где G – результат действия системы; X – переменные и параметры, которыми мы можем управлять; Y – переменные, которыми мы не можем управлять; F – функциональная зависимость, определяющая величину G.

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

Такое чрезмерное упрощение полезно лишь тем, что оно явно показывает зависимость функционирования системы как от контролируемых, так и от неконтролируемых параметров и переменных.

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

Перевести переменные величины в константы;

Исключить некоторые переменные или объединить их;

Предположить линейную зависимость между исследуемыми величинами;

Ввести более жесткие предположения и ограничения.

Имитационное моделирование во многом является искусством. Однако можно сформулировать следующие полезные на практике указания, согласно которым надлежит:

Разложить общую задачу исследования системы на ряд более простых задач;

Четко сформулировать цели исследования;

Подыскать аналогию;

Рассмотреть численный пример, соответствующий данной задаче;

Выбрать определенную систему обозначений;

Записать очевидные соотношения.

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

1. Простой и понятной пользователю,

2. Целенаправленной,

3. Надежной в смысле гарантии от абсурдных ответов,

4. Удобной в общении и управлении,

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

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

3.2.2. Метод статистических испытаний

В основе метода статистических испытаний (метода Монте – Карло) лежит моделирование на ЭВМ статистического эксперимента и регистрации числовых характеристик, получаемых в эксперименте.

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

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

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

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

р1(А)=m/n,

где n - число опытов; m - количество наступлений события А в n опытах.

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

m_x=(1/n) ∑x_k

^k=1

Как известно, оценкой s² дисперсии случайной величины Х может служить:

_n

S²=(1/(n-1)) ∑(x_k – m_x)²

^k=1

Непосредственное вычисление S² по этой формуле неудобно, так как m_x изменяется в процессе накопления значений x_k, что требует запоминания всех n значений x_k. Поэтому для вычисления оценки S² удобнее пользоваться формулой

_{n n}

S²=(1/(n-1)) ∑x_k² – (1/n(n-1))(Σx_k)²

^{k=1 k=1}

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

_n

K_xy=(1/(n-1)) ∑(x_k – m_x) (y-m_y)

^k=1

Его можно преобразовать к виду:

_{n n}

K_xy=(1/(n-1)) ∑x_ky_k – (1/n(n-1))Σx_kΣx_k)²,

^{k=1 k=1}

Требующему запоминания трех величин: Σx_k, Σy_k, Σx_ky_k

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

r_xy=K_xy/(s_xs_y)

Где s_x,s_y - средние квадратические отклонения величин Х и У.

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

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

|b-m_x| <ε

А вероятность α того, что неравенство выполняется, достоверностью ее.

α =p(|b-m_x| <ε)

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

Пусть целью моделирования будет вычисление вероятности p появления некоторого случайного события А, определяемого состояниями исследуемой системы. В каждой и n реализаций процесса на модели рассматриваемое событие может наступить или не наступить; другими словами количество ξ наступлений события А является случайной величиной, принимающей значение x₁=1 с вероятностью p, и x₂=0 с вероятностью (1-p).

Математическое ожидание и дисперсия случайной величины ξ равны

M(ξ)=x₁p+x₂(1-p)

D(ξ)=[x₁- M(ξ)]²p+[x₂- M(ξ)]²(1-p)=p(1-p)

В качестве оценки для искомой вероятности p принимается частота m/n наступления события А при n реализациях. Частоту m/n можно представить в виде

_n

m/n=(1/n) ∑ ξ _k

^k=1

Где ξ_k - количество наступлений события А в реализации с номером k, (осреднение по реализациям).

Тогда математическое ожидание и дисперсию частоты m/n

M(m/n)=p, D(m/n)=p(1-p)/n

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

ε= t_α D(m/n)= t_α p(1-p)/n

Отсюда можно определить количество реализаций n, необходимых для получения оценки m/n с точностью ε и достоверностью α

α	0.60	0.85	0.95	0.99
tα	0.84	1.44	1.96	2.58

n= t_α²p(1-p)/(ε²)

На практике часто определяющим при выборе числа реализаций является допустимый расход времени ЭВМ. В этом случае возможны два варианта оценки точности моделирования:

-для заданных количества реализаций n, достоверности α и полученной оценки вероятности Р вычислить точность ε;

- для заданных количества реализаций n,точности ε и полученной оценки вероятности Р, вычислить достоверность α.

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

Пусть случайная величина Х имеет среднее значение a и дисперсию s². В реализации с номером k она принимает значение x_k. В качестве оценки для среднего значения используется среднее арифметическое.

_n

m_x=(1/n) ∑x_k

^k=1

По центральной предельной теореме при больших значениях n среднее арифметическое будет иметь нормальное распределение с математическим ожиданием a и дисперсией s²/n. Поэтому точность

ε= t_αs n

3.2.3. Формирование случайных чисел на ЭВМ

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

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

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

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

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

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

F(x)={ 1/(b-a) a<x<b

^{0 вне этого интервала}

Математическое ожидание и среднее квадратическое отклонение соответственно равны:

M_x=(a+b)/2, S_x=(b-a)/(2 ₃)

Программные способы формирования случайной последовательности чисел, как правило используют рекуррентную формулу вида x_k+1=f(x_k). Полученные таким образом случайные числа не являются случайными, но отвечают установленным критериям случайности. Поэтому их называют "псевдослучайными" числами.

Большинства программ получения псевдослучайных чисел используют метод:

x_k+1=(x_ka+c)mod m,

С помощью которого получаются равномерно распределенные целые числа в пределах от 0 до m-1. для n -разрядных целых двоичных чисел m обычно равно 2ⁿ, а x₀, а и с – целые числа из той же области. Рекомендуются следующие правила по выбору x₀, а и с.

-x₀ – может быть произвольным.

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

а – простое число;

a(mod8)=5

m<a<m- m

-в качестве с следует выбирать нечетное число, такое, что

c/m=1/2-(1/6) ₃ =0.21132

библиотечная функция rand() (прототип в файле <stdlib.h>) генерирует последовательность целых псевдослучайных чисел равномерно распределенных в интервале (0, 32767). Посредством функции srand() можно установить или восстановить исходное число последовательности псевдослучайных чисел.

Если целочисленное Х находится в пределах от 0 до m, то дробь x_k/m попадает в интервал (0,1).

Можно использовать директиву define

Define RND (float)rand()/32768.0

Переход от стандартного интервала (0,1) к произвольному (а,в) осуществляется по формуле

y=a+(b-a)x

Где y принадлежит равномерному распределению на интервале (a,b), а х – равномерному распределению на (0,1)

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

_{2 2}

F(x)=1(s 2x)n^{-(x-m) /2s}

Где m -математическое ожидание, s - среднее квадратическое отклонение величины Х.

Для получения последовательности случайных чисел x_k, имеющих нормальное распределение воспользуемся центральной предельной теоремой и построим x_k в виде сумм последовательных случайных чисел, имеющих равномерное распределение в интервале (0,1).

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

₁₂

y= ∑q_k-6, x=a+sy

^k=1

q_k принадлежит равномерному распределению на интервале (0,1), а у - нормальному на интервале (0,1) и х тоже нормальному, но на интервале (а,s).

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

Идея построения такой операции вытекает из теоремы: если величина У имеет плотность распределения f(y), то распределение случайной величины

X= dy

Является равномерным в интервале (0,1).

Тогда, чтобы получить число, принадлежащее совокупности случайных чисел {y_k}, необходимо разрешить относительно y уравнение:

dy=x_k

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

f(y)=λe^-λy (y>0)

Получим для верхнего предела интегрирования у_к

Где у_к -случайное число, имеющее равномерное распределение в интервале (0,1) или, после вычисления интеграла

λ-e^-λy=x_k

Разрешая это уравнение относительно _Уk, имеем

y_k=(-1/λ)ln(1-x_k)

Учитывая, что случайная величина 1-x_k, имеет также равномерный закон распределения в интервале (0,1), соотношение можно записать

y_k=(-1/λ)ln(x_k)

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