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

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

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

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

 

Персонал

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

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

Время	Событие
10:00	Клиент №55 пришел и встал в очередь
10:15	Клиент №56 пришел и встал в очередь
10:17	Клиент №54 закончил обслуживаться и ушел
10:17	Клиент №55 начал  обслуживаться

Следующий этап заключается в анализе статистики, собранной и представленной моделью. Если средний размер очереди клиентов превышает выбранный предел в 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. Определяют показатели качества функционирования системы путем обработки накопленных результатов моделирования методами математической статистики.

 

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