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

Введение

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

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

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

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

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

– вероятность отказа обслуживания заявки ();

– среднее число занятых каналов ();

– среднее число заявок в СМО ();

– среднее время пребывания заявки в системе ();

– среднее число заявок в очереди ();

– среднее время пребывания заявки в очереди ();

– среднее число заявок, обслуживаемых в единицу времени;

– среднее время ожидания обслуживания;

– вероятность того, что число заявок в очереди превысит определенное значение и т.п.

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

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

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

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

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

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

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

        Описание поведения системы;

        Построение теорий и гипотез, которые могут объяснить наблюдаемое поведение;

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

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

1.        Концептуальный: разработка концептуальной схемы и подготовка области исходных данных;

2.        Математический: разработка математических моделей и обоснование методов моделирования;

3.        Программный: выбор средств моделирования и разработка программных моделей;

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

Виды имитационного моделирования

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

        Дискретно-событийное моделирование — подход к моделированию, предлагающий абстрагироваться от непрерывной природы событий и рассматривать только основные события моделируемой системы, такие как: «ожидание», «обработка заказа», «движение с грузом», «разгрузка» и другие. Дискретно-событийное моделирование наиболее развито и имеет огромную сферу приложений — от логистики и систем массового обслуживания до транспортных и производственных систем. Этот вид моделирования наиболее подходит для моделирования производственных процессов. Основан Джеффри Гордоном в 1960-х годах.

        Системная динамика — парадигма моделирования, где для исследуемой системы строятся графические диаграммы причинных связей и глобальных влияний одних параметров на другие во времени, а затем созданная на основе этих диаграмм модель имитируется на компьютере. По сути, такой вид моделирования более всех других парадигм помогает понять суть происходящего выявления причинно-следственных связей между объектами и явлениями. Метод основан Джеем Форрестером в 1950 годах.

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

Фаза валидации.

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

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

Фаза проектирования.

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

Фаза верификации.

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

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

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

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

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

Рассмотрим ряд приемуществ и недостатков имитационного моделирования:

Преимущества

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

2. В ходе моделирования возможно "сжатие" времени: годы практической эксплуатации реальной системы можно промоделировать в течение нескольких секунд или минут.

3. Моделирование не требует прерывания текущей деятельности реальной системы.

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

5. Моделирование можно использовать в качестве средства обучения персонала работе с реальной системой.

6. Моделирование обеспечивает более реалистичное воспроизведение системы, чем математический анализ.

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

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

9. Имитационное моделирование отвечает на вопросы типа "а что, если...".

Недостатки

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

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

804

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

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

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

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

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

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

-                     в первой – под имитационной моделью понимается математическая модель в классическом смысле;

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

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

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

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

Этапы процесса построения математической модели сложной системы:

1.        Формулируются основные вопросы о поведении системы, ответы на которые мы хотим получить с помощью модели.

2.        Из множества законов, управляющих поведением системы, выбираются те, влияние которых существенно при поиске ответов на поставленные вопросы.

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

Критерием адекватности модели служит практика.

Трудности при построении математической модели сложной системы:

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

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

-           Возможность сопоставления модели и оригинала при таком подходе имеется лишь в начале.

Эти трудности и обуславливают применение имитационного моделирования.

Оно реализуется по следующим этапам:

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

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

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

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

5.        Формализованным образом задаются необходимые феноменологические свойства системы и отдельных ее частей.

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1.

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

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

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

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

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

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

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

Например, для графа состояний, приведенного на рис.1, уравнения Колмогорова имеют вид:

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

Метод Монте-Карло  как разновидность имитационного моделирования.

Интегрирование методом Монте-Карло

Численное интегрирование функции детерминистическим методом

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

Для определения этой площади можно воспользоваться одним из обычных численных методов интегрирования: разбить отрезок на подотрезки, подсчитать площадь под графиком функции на каждом из них и сложить. Предположим, что для функции, представленной на рисунке 2, достаточно разбиения на 25 отрезков и, следовательно, вычисления 25 значений функции. Представим теперь, мы имеем дело с n-мерной функцией. Тогда нам необходимо 25n отрезков и столько же вычислений значения функции. При размерности функции больше 10 задача становится огромной. Поскольку пространства большой размерности встречаются, в частности, в задачах теории струн, а также многих других физических задачах, где имеются системы со многими степенями свободы, необходимо иметь метод решения, вычислительная сложность которого бы не столь сильно зависела от размерности. Именно таким свойством обладает метод Монте-Карло.

Обычный алгоритм Монте-Карло интегрирования

Предположим, требуется вычислить определённый интеграл

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

Таким образом, искомый интеграл выражается как
.

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

Итак, бросаем точек, равномерно распределённых на , для каждой точки вычисляем . Затем вычисляем выборочное среднее: .

В итоге получаем оценку интеграла:

Точность оценки зависит только от количества точек .

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