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

Оглавление

Введение

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

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

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

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

Второй раздел курсовой работы посвящен практическому заданию. Выполнение расчетного раздела предполагает решение трех расчетных заданий в соответствии с вариантом (№18).

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

Раздел 1. Имитационное моделирование

1.1 Понятие, цели  и область применения имитационного моделирования

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

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

Имитационное  моделирование экономических процессов  – разновидность экономико-математического  моделирования. Однако этот вид моделирования  в значительной степени базируется на компьютерных технологиях. Многие моделирующие системы, идеологически разработанные в 1970-1980-х гг., претерпели эволюцию вместе с компьютерной техникой и операционными системами (эффективно используются в настоящее время на новых компьютерных платформах). Кроме того, в конце 1990-х гг. появились принципиально новые моделирующие системы, концепции которых не могли возникнуть раньше – при использовании ЭВМ и операционных систем 1970-1980-х гг.

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

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

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

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

Цель имитационного  моделирования состоит в воспроизведении  поведения исследуемой системы  на основе результатов анализа наиболее существенных взаимосвязей между ее элементами или другими словами — разработке симулятора (англ. simulation modeling) исследуемой предметной области для проведения различных экспериментов.

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

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

• бизнес процессы;
• боевые действия;
• динамика населения;
• дорожное движение;
• ИТ-инфраструктура;
• математическое моделирование исторических процессов;
• логистика;
• пешеходная динамика;
• производство;
• рынок и конкуренция;
• сервисные центры;
• цепочки поставок;
• уличное движение;
• управление проектами;
• экономика здравоохранения;
• экосистемы и прочее.

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

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

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

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

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

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

На рисунке 1 представлены этапы построения модели.

Рис. 1. Этапы процесса моделирования

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

1.2 Простейшие задачи, решаемые при помощи имитационного моделирования

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

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

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

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

В данной  работе рассмотрим несколько примеров таких задач.

1. Максимизация прибыли поставщика сервиса для мобильной связи.³

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

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

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

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

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

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

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

2. Минимизация количества обслуживающего персонала парикмахерского салона.

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

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

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

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

Приход   Ожидание   Обслуживание   Уход клиента

клиента   в очереди

Персонал

Рис. 3 – Имитационная модель

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

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

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

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

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

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

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

Рис.4 Структура модели простой СМО

Генераторы заявок имитируют  события прихода новых клиентов, которые для модели все одинаковы за исключением того, что каждый из клиентов будет иметь свою собственную историю обслуживания и ожидания в очередях. Поэтому имитирующие клиентов заявки могут хранить такую историю – моменты времени входа в систему (порождения), начала и конца обслуживания и т.п. Очереди имитируют реальные очереди людей. Обслуживающие приборы имитируют работу менеджеров и кассира. Ясно, что оценки качества обслуживания в операционном зале банка не важны ни расположение обслуживаемого персонала, ни даже вид работы, которую выполняет конкретный служащий. С точки зрения поставленной задачи (анализа эффективности) важно только время обслуживания, и этим отличаются различные обслуживающие приборы в этой модели. Т.к. время обслуживания случайно, приборы просто задерживают заявки на некоторый случайный период времени. Блок «Выход заявки из системы» получает заявки и может подсчитать интегральные временные характеристики, описывающие историю обслуживания заявок в системе.

1.3 Моделирование систем массового обслуживания с использованием метода Монте-Карло.

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

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

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

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

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

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

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

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

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

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

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

Для решения  задачи статистического моделирования функционирования СМО должны быть заданы следующие исходные данные:

• описание СМО (тип, параметры, критерии эффективности работы системы);
• параметры закона распределения периодичности поступления требований в систему;
• параметры закона распределения времени пребывания  требования в очереди (для СМО с ожиданием);
• параметры закона распределения времени обслуживания требований в системе.

Решение задачи статистического моделирования функционирования СМО складывается из следующих этапов.

1. Вырабатывают  равномерно распределенное случайное число ξ_i

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

• интервал времени между поступлениями требований в систему (∆t_Ti);
• время ухода заявки из очереди (для СМО с ограниченной  длиной очереди);
• длительность времени обслуживания требования каналами (∆t_Oi)

3. Определяют  моменты наступления событий: 

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

4. Моделируют функционирование СМО в целом и накапливают статистические данные о процессе обслуживания.

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

6. Определяют  показатели качества функционирования  СМО путем обработки результатов моделирования методами математической статистики.

Методику решения задачи рассмотрим на примере моделирования СМО с отказами.

Пусть система  имеет два однотипных канала, работающих с отказами, причем моменты времени окончания обслуживания на первом канале обозначим через t_i, на втором канале - через t_2i. Закон распределения интервала времени между смежными поступающими требованиями задан плотностью распределения f₁(t_T). Продолжительность обслуживания также является случайной величиной с плотностью распределения f₂(t₀).

Процедура решения  задачи будет выглядеть следующим образом:

1. Вырабатывают равномерно распределенное случайное число ξ_i
2. Равномерно распределенное случайное число преобразуют в величины с заданным законом распределения, используя формулы для моделирования случайных величин. Определяют реализацию случайного интервала времени (∆t_Ti) между поступлениями требований в систему.
3. Вычисляют момент поступления заявки на обслуживание: t_i=t_i-1 +∆t_Ti
4. Сравнивают моменты окончания обслуживания предшествующих заявок на первом t_1(i-1) и втором t_(2i-1)каналах.
5. Сравнивают момент поступления заявки /,- с минимальным моментом окончания обслуживания (допустим, что t_1(i-1) < t_2(i-1)):

а) если [t_i - t_1(i-1)] < 0, то заявка получает отказ и вырабатывают новый момент поступления заявки описанным способом;

б) если [t_i - t_1(i-1)] ≥0, то происходит обслуживание.

6. При выполнении условия 5 б) определяют время обслуживания i-й заявки на первом канале ∆t_1i путем преобразования случайной величины ξ_i в величину (время обслуживания i-й заявки) с заданным законом распределения.
7. Вычисляют момент окончания обслуживания i-й заявки на первом канале t_1i = [t_1(i-1) + ∆t_1i].
8. Устанавливают новый момент поступления заявки, и вычислительная процедура повторяется в соответствии с изложенным.
9. В ходе моделирования СМО накапливаются статистические данные о процессе обслуживания.
10. Определяют показатели качества функционирования системы путем обработки накопленных результатов моделирования методами математической статистики.

Проведем классификацию  задач решаемых имитационным моделированием.