9789

нове вычислений по методу Монте-Карло лежит случайный выбор числе из за-

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

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

помощью аналитической модели проводится N «розыгрышей» случайного яв-

ления в модели объекта имитации (заранее заданным числом N раз). При этом вектор параметров модели X не меняется (фиксирован) и на модели определя-

ются значения компонент вектора откликов Y. Так же, как в реальности, кон-

кретная j-ая реализация случайного процесса (из-за случайного характера алго-

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

стемы при одних и тех же значениях вектора параметров модели X, из-за слу-

чайного характера алгоритма сложной системы получают выборку значений откликов Yi, i 1, N . Усредняя выборку значений Yi , находят вектор ма-

тематических ожиданий значений компонент этого вектора N Y Y1 ,Y2 ,...,Yn и дисперсию y S компонент вектора откликов при фиксированных значе-

ниях вектора параметров {X}. Число экспериментов N определяется из необхо-

димой точности оценки Y. Задавшись точностью вычислений , по таблицам нормального распределения для доверительной вероятности =1- находят требуемое число экспериментов N, обеспечивающее оценку среднего Y с веро-

ятностью ошибки .

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

Основные вопросы, рассматриваемые на лекции:

Дискретная модель случайной величины, равномерно распределенной на отрезке [0,1]. Имитационное моделирование простого события. Имитационное

31

моделирование полной группы несовместных событий. Имитационное моделирование дискретной случайной величины. Моделирование экономических процессов в виде СМО. Элементы теории массового обслуживания. Основные понятия. Классификация систем массового обслуживания. Понятие марковского случайного процесса. Потоки событий.

Уравнения Колмогорова. Предельные вероятности состояний. Процесс гибели и размножения. Размеченный граф состояний процесса гибели и размножения.

Системы массового обслуживания с отказами. Системы массового обслуживания с ожиданием. Моделирование систем массового обслуживания.

Моделирование случайного потока событий. Расчет показателей СМО методом Монте-Карло.

Элементы теории массового обслуживания

Термин «дискретно-событийное моделирование» исторически возник для описания моделей, описывающих системы обслуживания потоков объектов не-

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

туристов у стойки регистрации на рейс, междугородних переговоров и т.д.

Именно такие системы получили название систем массового обслуживания

(СМО) – это системы, на вход которых подается случайный поток однотипных заявок (событий), обрабатываемых одним или несколькими однотипными кана-

лами (устройствами). Теория систем массового обслуживания начала разви-

ваться в начале ХХ века. Иохансен в 1907 году сформулировал основные пред-

положения новой теории. В 1909 году Эрланг (шведский математик) с помо-

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

живания телефонных вызовов от числа поступающих на телефонную станцию вызовов. В СССР основные положения теории СМО были описаны в моногра-

фии «Теория очередей» А.Я. Хинчина.

Примерами СМО могут служить телефонные системы, ремонтные мастер-

ские, билетные кассы, магазины, …

32

СМО состоит из определенного числа обслуживающих единиц (приборов,

устройств, пунктов, …), которые называются каналами обслуживания (рабочие

точки, продавцы, вычислительные машины, …).

Заявки поступают в СМО обычно не регулярно, а случайно, образуя так

называемый случайный поток заявок (требований).

Предметом теории массового обслуживания является построение матема-

тических моделей, связывающих заданные условия работы СМО (число кана-

лов, их производительность, …).

Процесс работы СМО представляет собой случайный процесс – процесс изменения во времени состояния какой-либо системы в соответствии с вероят-

ностными закономерностями.

Процесс называется процессом с дискретным состоянием, если его воз-

можные состояния S1, S2, …, Sn можно заранее перечислить, а переход из одного состояния в другое происходит мгновенно.

Случайный процесс называется марковским (случайным процессом без по-

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

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

зоваться геометрической схемой – графом состояний.

Пример. Построить граф состояний следующего случайного процесса:

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

продолжающийся заранее неизвестное случайное время.

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

лефонной станции, поток покупателей и т.п.).

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

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

делий на конвейере).

Поток событий называется стационарным, если его вероятностные харак-

теристики не зависят от времени.

Рассмотрим математическое описание марковского процесса с дискретным состоянием и непрерывным временем на нашем примере. Будем полагать, что все переходы системы из состояния Si в Sj происходит под воздействием про-

стейших потоков событий с интенсивностями ij.

Граф состояний с проставленными у стрелок интенсивностями будет называть размеченным. Вероятностью i-того состояния называется вероятность pi(t) того, что в момент t система будет находиться в состоянии Si. Очевидно,

что для любого момента времени t сумма вероятностей всех состояний будет

n

равна 1: pi t 1 .

i 1

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

вероятностями состояний.

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

ти в любое другое состояние, что предельные вероятности существуют.

34

Предельная вероятность состояния Si. имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии.

Предельные вероятности системы можно найти из системы уравнений, со-

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

Слева в уравнении стоит предельная вероятность данного состояния pi,

умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа – сумма произведений интенсивностей всех потоков, вхо-

дящих в i–е состояние, на вероятность тех состояний, из которых эти потоки исходят.

Раздел 7. Моделирование непрерывных процессов при помощи

разностных уравнений.

Основные вопросы, рассматриваемые на лекции: Метод обратной функции имитационного моделирования непрерывной случайной величины.

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

35

случайных величин с произвольным распределением. Моделирование непрерывных процессов при помощи разностных уравнений.

Краткие теоретические сведения.

Для осуществления моделирования непрерывной переменной, представ-

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

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

Большинство современных вычислительных средств включают стандартную процедуру генерации случайных чисел R, распределенных равномерно на от-

резке [0;1].

Пусть нам требуется величина с иным законом распределения. Нам потре-

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

вестна функция плотности вероятности (в точности или с неизвестным мас-

штабным коэффициентом, который можно найти из условия нормировки),

функцию распределения отыщем как ее первообразную F(x) p(x) dx при усло-

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

Теперь получим при помощи генератора случайных чисел значение R, а

значение рассматриваемой переменной найдем по формуле x F 1 (R) (следует обратить внимание, что обратные функции стандартных распределений встрое-

ны в Microsoft Excel). Такая случайная величина будет распределена по задан-

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

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

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

эффициенты этой зависимости методом наименьших квадратов. Затем при по-

мощи полученного выражения можно найти значения величины в те моменты

36

времени, когда она неизвестна.

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

dxdt f (x, y,t) . Здесь x – величина, динамика которой описывается данным урав-

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

мость.

Если найти аналитическое решение этого уравнения невозможно или не-

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

ную разностной схемой. Задав некоторый шаг по времени h, приближенно

выразим значение величины x на следующем шаге через значения величин на предыдущем x(t h) x(t) h f (x(t), y(t),t) . Естественно, что при этом необходимо знать или предполагать значение x в некоторый начальный момент времени,

значения же y считаются известными или находятся из других соотношений,

входящих в данную модель.

Раздел 8. Обработка результатов имитационного моделирования.

Надежность методов имитационного моделирования.

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

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

Краткие теоретические сведения.

Решения, принимаемые исследователем по результатам имитационного

37

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

ных условий:

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

стью;

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

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

Оценка качества имитационной модели Оценка качества модели является завершающим этапом ее разработки и

преследует две цели:

• проверить соответствие модели ее предназначению (целям исследова-

ния);

• оценить достоверность и статистические характеристики результатов,

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

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

ется двумя основными факторами:

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

сания исследуемой системы;

• методической ошибкой, присущей данному математическому методу При имитационном моделировании на достоверность результатов влияет

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

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

чиков СЧ, которые могут вносить «искажения» в поведение модели;

•наличие нестационарного режима работы модели;

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

ках одной модели;

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

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

•наличие модели рабочей нагрузки, качество которой зависит, в свою оче-

редь, от тех же факторов.

38

Пригодность имитационной модели для решения задач исследования ха-

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

ми целевыми свойствами. Основными из них являются:

•адекватность;

•устойчивость;

•чувствительность.

Оценка адекватности модели

В общем случае под адекватностью понимают степень соответствия моде-

ли тому реальному явлению или объекту, для описания которого она строится.

Вместе с тем, создаваемая модель ориентирована, как правило, на исследо-

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

ни это утверждение справедливо относительно моделей проектируемых систем

(т.е. в ситуациях, когда реальная система вообще не существует).

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

собами. Наиболее распространенные из них:

•по средним значениям откликов модели и системы;

•по дисперсиям отклонений откликов модели от среднего значения откли-

ков системы;

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

ли от откликов системы.

В результате N0 опытов на реальной системе получают множество значе-

ний (выборку) У*. Выполнив NM экспериментов на модели, также получают множество значений наблюдаемой переменной Y.

Затем вычисляются оценки математического ожидания и дисперсии откли-

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

39

потезы является t-статистика (распределение Стьюдента). Ее значение, вычис-

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

взятым из справочной таблицы. Если выполняется неравенство tn<tкр, то гипоте-

за принимается.

Оценка устойчивости

Устойчивость модели – это ее способность сохранять адекватность при ис-

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

Универсальной процедуры проверки устойчивости модели не существует.

Разработчик вынужден прибегать к методам «для данного случая», частичным тестам и здравому смыслу. Часто бывает полезна апостериорная проверка. Она состоит в сравнении результатов моделирования и результатов измерений на системе после внесения в нее изменений. Если результаты моделирования при-

емлемы, уверенность в устойчивости модели возрастает.

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

Устойчивость результатов моделирования может быть также оценена ме-

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

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

тезы об устойчивости результатов может быть использован критерий Уилкок-

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

Оценка чувствительности

Очевидно, что устойчивость является положительным свойством модели.

Однако если изменение входных воздействий или параметров модели (в неко-

тором заданном диапазоне) не отражается на значениях выходных параметров,

то польза от такой модели невелика (ее можно назвать «бесчувственной»). В

40