Математическое моделирование. Документ Microsoft Word. исследование и оптимизация свойств локальных информационных систем
 Скачать 1.67 Mb.
|
|
Тема 8. Основы имитационного моделирования Цели изучения темы: · изучить сущность имитационного моделирования систем и процессов. Задачи изучения темы: · изучить принципы построения имитационных моделей; · изучить способы имитации случайных величин и событий; · изучить методы обработки результатов имитационного моделирования. Успешно изучив тему, Вы: получите представление о: · когда применяется и как реализуются имитационные модели; · как имитируется в программной модели параллельное протекание реальных процессов; · способах преобразования описаний в исполнительные компьютерные программы; будете знать: · какие алгоритмы используются для имитации случайных величин с заданным законом распределения; · как реализуется имитация в программе случайного события с заданной вероятностью; · как найти математическое ожидание и дисперсию показателя на основе полученных с помощью модели данных. Вопросы темы: 1. Концепции имитационного моделирования. 2. Имитация случайных величин с заданными законами распределения. 3. Обработка результатов запусков программной модели. Вопрос 1. Концепции имитационного моделирования. Ранее нами была рассмотрена модель марковских процессов, которую можно с успехом применять для решения многих практических задач оценивания показателей системы с помощью аналитических выражений. Однако условия марковости процесса соблюдаются далеко не всегда. Кроме того, получение аналитических выражений для расчета показателей часто представляет большую трудность. Альтернативным подходом к решению задач оценки показателей является исследование системы на основе имитационной модели, с помощью которой можно получить результаты для случаев произвольных распределений временных интервалов и других случайных величин. Такую модель можно построить с помощью специальной моделирующей системы, что ускоряет процесс создания, улучшает характеристики конечного результата (программной модели) и имеет ряд других достоинств. Поведение (процесс функционирования) динамической дискретной системы можно рассматривать как последовательность состояний  в моменты времени  . При этом факты смены состояния системой рассматриваются как события. В основу идеи имитационного моделирования положен принцип, согласно которому на ЭВМ осуществляется воспроизведение (имитация) процесса функционирования исследуемой системы в контексте смены ее состояний в результате происходящих в ней событий. В процессе проведения имитации собираются данные о состоянии системы или отдельных ее элементов в определенные моменты времени, что позволяет в конце процесса моделирования провести агрегирование и обработку собранных данных и получить значения нужных исследователю показателей.Пусть, например, нам необходимо исследовать работу уже рассматривавшейся выше СМО с очередью и одним обслуживающим прибором (рис. 15.). Заявки, образующие входящий поток, поступают в систему в случайные моменты времени. Если обслуживающий прибор (канал) свободен, заявка принимается на обслуживание, которое продолжается некоторое время (его величина является, как правило, также случайной), после чего она уходит из системы (выходящий поток). Если в момент прихода заявки канал занят, заявка попадает в очередь ждущих заявок. Решая задачу нахождения показателей системы, для описания состояния процесса достаточно использовать один параметр  , который означает число заявок в системе в момент времени . Имитацию процесса обслуживания заявки в можно провести, определяя моменты ожидаемого изменения состояния (наступления события), связанных с изменением состояния . В данном случае, это моменты поступления очередной заявки в систему и моменты окончания обслуживания заявки, находящейся в обслуживающем приборе. Моменты наступления будущих событий могут быть найдены на основе рекуррентных выражений с помощью функций распределения интервалов времени путём проведения случайных испытаний аналогично тому, как это производилось в методе статистических испытаний. Это позволяет построить алгоритм имитации, состоящий из повторения следующей совокупности шагов:· находится момент наступления ближайшего события, событие с минимальным временем — наиболее раннее событие; · стрелки модельных часов передвигаются на этот момент времени; · определяется тип происшедшего события; · в зависимости от типа события модифицируются значения переменных, описывающих состояние системы (в данном случае, число находящихся в системе заявок), и определяются следующие моменты наступления событий. Логика построения мехнизма моделирования показана на рис. 23.  Рис. 23. Блок-схема имитации работы одноканальной СМО с очередью В процессе выполнения алгоритма производится накопление значений существенных параметров моделируемой системы. По окончании моделирования осуществляется статистическая обработка полученных величин и выдача результатов. Описанный алгоритм носит название событийного алгоритма. Альтернативным способом построения алгоритма имитационного моделирования является перемещение по временной оси с фиксированным интервалом (шагом). После каждого перехода на новую временную отметку проводится сканирование всех протекающих в моделируемой системе процессов и выявление всех свершившихся на данный момент существенных событий. Такой алгоритм носит название пошагового алгоритма. Преимуществом пошагового алгоритма является простота его программной реализации. Вместе с тем, в условиях, когда наступление событий, обусловленных разными процессами, происходит с сильно отличающимися интервалами, то значительное время моделирования оказывается затраченным впустую (например, при моделировании производственного процесса на предприятии, работающем в односменном режиме, все вечернее и ночное время программная модель не будет выполнять никакой содержательной работы). Поэтому большинство программных реализаций имитационных моделей использует событийный алгоритм имитации. Имитационное моделирование представляет собой процесс, реализуемый с помощью средств вычислительной техники, что позволяет автоматизировать решение таких задач как: а) Создание или модификация имитационной модели. б) Проведение модельных экспериментов и интерпретация получаемых результатов. В случаях разработки сложных моделей, предназначенных для проведения большого объема экспериментов, для решения этих задач используются моделирующие комплексы (системы). Имитационное моделирование как информационная технология включает несколько основных этапов. На этапе структурного анализа процессов проводится формализация реального процесса, его декомпозиция на подпроцессы, которые могут также подвергаться декомпозиции. Задачи, решаемые на этом этапе, соответствуют задачам создания модели деловых процессов, вместе с тем, в зависимости от применяемых средств моделирования результат может потребовать преобразования формы представления в вид, наиболее полно соответствующий задачам, решаемым на дальнейших шагах. Описание модели в вербальном, графическом или полуформализованном виде должно быть представлено на специальном (формальном) языке для ввода в моделирующую систему. При этом могут применяться: · Ручной способ. Описание составляется на языке какой-либо системы моделирования, например, GPSS, Pilgrim или алгоритмическом языке, например, Visual Basic (размер результирующего текста в последнем случае будет многократно превосходить размер текста на языке специальных систем). · Автоматизированный способ. Текст на формальном языке получается в результате автоматической генерации описания, которое строится в интерактивном режиме с помощью высокоуровневого графического конструктора. Такой конструктор, которым оснащена, в частности, система Pilgrim, позволяет фактически совместить этап разработки программной модели с этапом системного анализа. Созданное формальное описание далее преобразуется в компьютерную программу, способную воспроизводить реальные процессы. Преобразование, которое обычно представляет собой трансляцию и редактирование связей, осуществляется в некоторой программной среде, может проводиться в двух режимах. · Интерпретация. В этом режиме специальная программа-интерпретатор осуществляет всю процедуру имитации, непосредственно выполняя инструкции формального описания. Примером системы, где предусмотрен режим интерпретации, является система GPSS. · Компиляция. В этом режиме на основе формального описания создается отдельная программа (исполнительный модуль), который может запускаться независимо от программной среды, в которой он был создан. Примером системы, где предусмотрен режим интерпретации, является система Pilgrim. Целью следующего этапа является обоснование модели, заключающегося в демонстрации пригодности модели для получения нужных показателей, т.е., обеспечение необходимых точности и надежности получаемых на ее основе результатов. Основной, последний этап моделирования сводится к проведению машинных экспериментов с программной моделью, сбору, накоплению, обработке и анализу собранных данных. Вопрос 2. Имитация случайных величин с заданными законами распределения. Значительную роль в программных средствах и системах имитационного моделирования играют методы и процедуры получения случайных величин, подчиняющихся тому или иному закону распределения. Рассмотрим основные из этих методов, а также приемы обработки результатов, получаемых с помощью имитационных моделей. Метод обратной функции. Пусть непрерывная случайная величина задана законом распределения:  где – плотность распределения вероятностей, - функция распределения вероятностей. Тогда случайная величина .  распределена равномерно на интервале (0,1). Отсюда следует, что искомое значение y может быть определено из уравнения:  которое эквивалентно уравнению:  где y – значение случайной величины , x – значение случайной величины . Решение уравнения можно записать в общем виде через обратную функцию  : Основной недостаток метода заключается в том, что интеграл не всегда является берущимся, а уравнение не всегда решается аналитическими методами. Имитация величины, распределенной по показательному закону. Для ряда весьма важных случаев решение уравнения для нахождения значения случайной величины можно найти. В частности, в соответствии с методом обратной функции существует преобразование, позволяющее вычислить значения случайной величины η, распределенной по показательному закону, который особенно часто используется для исследования систем массового обслуживания и определения показателей надежности систем. Функция плотности для показательного закона имеет вид:  Воспользуемся методом обратной функции, вычислим интеграл и получим уравнение вида  или  Тогда  и, прологарифмировав и разрешив уравнение через y, будем иметь: Получая значение х с помощью датчика равномерно распределенных на интервале (0,1) случайных чисел, можно получить значения y в соответствии с полученным выражением. Программа на языке С++: float expont(float m ) { return(m*(-log(rundum()) ) ); } Имитация случайного числа по данным наблюдения. Довольно часто значения случайной величины доступны в виде данных наблюдения, которые можно непосредственно использовать для модельных экспериментов без аппроксимации теоретическим распределением. Предположим, что в банке регистрировалось число обращений k его клиентов за получением обслуживания в часовом интервале, на основе чего получены частоты fk появлений в течение часа к клиентов:
Вычислим значение  и дополним таблицу строкой со значениями  :
и строкой , в первой ячейке которой будет записано значение , а в оставшихся – значения  :
Если считать, что значения хранятся в массиве P[9] (с индексом первого элемента равным 1), то построенный на основе метода обратной функции алгоритм получения случайной величины k для данного примера можно записать в таком виде: a=x k=0 ЦИКЛ-ПОКА a ≤ P[k+1] И k≤8 k=k+1 ВСЕ-ЦИКЛ где x – значение псевдослучайного числа, равномерно распределенного на интервале 0,1. Приводимый ниже текст программы на языке С++ обеспечивает генерацию случайной величины с произвольными значениями, которые задаются элементами массива vals. Массив nums задает значения частот появления значений (обозначены в примере какfk). Аргумент parts – число значений случайной величины (в примере - 9). float partval(int parts, int nums[], float vals[]) { int i; float sum, bleft,rnd=rundum(); for (i=0,sum=0; i for (i=0, bleft=0; i =bleft; bleft+=(float)nums[i]/sum, i++) ; return(vals[i-1]); } Вопрос 3. Обработка результатов запусков программной модели. В процессе имитационного моделирования формируется большое количество реализаций, являющихся исходным статистическим материалом для нахождения приближенных значений (оценок) показателей эффективности. Основные результаты моделирования включают, как правило, функцию распределения (наиболее информативное описание) какого-то состояния системы или процесса (события, явления) и/или числовые характеристики, такие как оценка вероятности, математическое ожидание и дисперсия случайной величины. Оценка вероятности. В качестве оценки вероятности используется частота  где m - число случаев наступления события А в экспериментах, N- число проведенных экспериментов. Для получения оценки вероятности обычно организуют на программном уровне два счетчика, в которых накапливаются: · общее количество проведенных экспериментов N; · общее количество экспериментов с положительным исходом m. Закон распределения. В ряде случаев в качестве характеристики исследуемой системы выступает закон распределения (плотности распределения). Его приближенно можно представить с помощью гистограммы. Для этого интервал изменения случайной величины разбивается на отрезки, каждому из них сопоставляется счетчик, где накапливаются mi – количество попаданий значений этой величины . На основании полученных значений счетчиков для можно построить гистограмму - набор прямоугольников с высотами  . Практический прием сбора данных и построения графика вместе с текстом компьютерной программы будет рассмотрен далее.Оценка математического ожидания. Оценку математического ожидания получают как среднее арифметическое значение случайной величины yi:  Для получения суммы в программных моделях обычно используется переменная, значение которой получает приращение после каждого проведенного испытания. Оценка дисперсии Оценка дисперсии получается с помощью формулы:  Выводы: 1. Применение метода статистических испытаний дает хорошие результаты в случаях, когда требуется найти статические характеристики системы. Для моделей динамических систем и, в первую очередь, для стохастических моделей мощным инструментом решения задач является имитационное моделирование, воспроизводящее с помощью ЭВМ протекание реальных процессов. 2. Для реализации программных моделей применяются стандартные механизмы имитации событий. В случае, когда необходимо добиться наиболее быстрого выполнения алгоритма обычно применяется событийный алгоритм имитации. 3. Создание имитационных моделей требует выполнения ряда задач в определенной последовательности. Непосредственная реализация программы может осуществляться на основе интерпретации или компиляции. Каждый из этих вариантов имеет свои достоинства и недостатки, выбор подхода обусловлен требованиями конкретной задачи. 4. В имитационных моделях стохастических систем широко используются случайные величины, распределенные по определенным законам. Для получения таких величин используются различные методы и приемы, одним из наиболее распространенных является метод обратной функции. 5. Данные, полученные в результате прогона имитационных моделей, необходимо обрабатывать. В зависимости от типа результатов используются свои методы обработки. Типичными случаями обработки данных запусков стохастических моделей являются получение средних значений и дисперсии какого-либо показателя, для вычисления которых по собранным данным применяются соответствующие математические выражения. Вопросы для самопроверки: 1. Что такое имитационное моделирование? 2. Для решения каких задач используется имитационное моделирование? 3. Что такое пошаговый алгоритм имитации протекания процессов? 4. Что такое событийный алгоритм имитации протекания процессов? 5. Каковы сравнительные достоинства и недостатки пошагового и событийного алгоритмов? 6. Из какие основных этапов состоит процесс моделирования? 7. В чем заключается задача этапа структурного анализа процессов? 8. Какие способы используются для формализации содержательного описания модели? 9. Какие способы используются для получения программного кода по формальному описанию модели? 10. Как реализуется метод обратной функции для имитации случайной величины, распределенной по показательному закону? 11. Как оценить величину вероятности наступления события по результатам моделирования? 12. Как оценить математическое ожидание случайной величины по результатам моделирования? 13. Как оценить дисперсию случайной величины по результатам моделирования? Литература по теме: 1. Емельянов А.А., Власова Е.А., Дума Р.В. Имитационное моделирование экономических процессов / Под ред. А.А. Емельянова. – М.: Финансы и статистика, 2009. – 480 с. |