Цели и задачи имитационного моделирования и исследования

СОДЕРЖАНИЕ

 

 

ВВЕДЕНИЕ

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

Цель должна быть достигнута посредством  решения таких задач:

- изучить теоретические основы  систем массового обслуживания, структуру функционирования СМО;

- провести анализ системы массового  обслуживания на примере заказа  такси;

- построить сеть Петри изучаемой  СМО.

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

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

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

 

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

1.1. Цели и задачи имитационного моделирования и исследования

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

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

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

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

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

Имитация как метод решения нетривиальных задач получила начальное развитие в связи с созданием ЭВМ в 1950-х — 1960-х годах.

Можно выделить разновидности имитации:

• Метод Монте-Карло (метод статистических испытаний);
• Метод имитационного моделирования (статистическое моделирование)[10].

1.2 Основные классы СМО

Основными классами системы массового обслуживания являются:

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

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

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

Системы с очередью делятся на системы с неограниченным и с ограниченным ожиданием.

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

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

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

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

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

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

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

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

- среднее  число заявок в очереди;

- среднее  число заявок в системе (в очереди  и под обслуживанием);

- среднее  время ожидания заявки в очереди;

- среднее  время пребывания заявки в  системе (в очереди и под обслуживанием);

и другие характеристики ожидания.

Для СМО с ограниченным ожиданием интерес представляют обе группы характеристик: как абсолютная и относительная пропускная способности, так и характеристики ожидания [5].

1.3. Классификация систем массового обслуживания

Системы, в которых в случайные моменты времени возникают заявки на обслуживание и имеются устройства для обслуживания этих заявок, называются системами массового обслуживания (СМО) [3].

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

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

Если в СМО одновременно может обслуживаться несколько заявок,

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

одноканальной.

Как одноканальные СМО, так и многоканальные СМО делятся на

СМО с отказами и СМО с очередью (ожиданием).

В СМО с отказами заявка, поступившая в момент, когда все каналы

обслуживания заняты, получает «отказ» в обслуживании и покидает СМО.

В СМО с очередью заявка, поступившая в момент, когда все каналы

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

СМО с очередью различаются по принципу построения очереди.

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

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

этом используется:

1. Случайный  выбор заявки из очереди;

2. Выбор  заявки из очереди в зависимости  от её приоритета;

3. Выбор  заявки в зависимости от порядка  её поступления в очередь.

В третьем случае заявки из очереди могут обслуживаться, как по схеме:

«Первым пришел - первым обслуживаешься», так и по схеме: «Последним

пришел - первым обслуживаешься».

СМО с очередью делятся также на СМО с неограниченным ожиданием и СМО с ограниченным ожиданием.

В СМО с неограниченным ожиданием каждая заявка, поступившая

в СМО, рано или поздно будет обслужена.

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

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

времени пребывания в очереди, покидает СМО [4].

 

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

Для моделирования СМО необходимо иметь следующие исходные данные:

-основные параметры;

-граф состояний.

Результатами моделирования СМО являются вероятности ее состояний, через которые выражаются все показатели ее эффективности.

Основные параметры для моделирования СМО включают:

-характеристики входящего потока  заявок на обслуживание;

-характеристики механизма обслуживания.

Рассмотрим характеристики потока заявок.

Поток заявок - последовательность заявок, поступающих на обслуживание.

Интенсивность потока заявок λ - среднее число заявок, поступающих в СМО в единицу времени.

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

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

Стационарность означает неизменность интенсивности поступления заявок с течением времени.

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

Отсутствие последействия заключается в том, что число заявок, поступивших в СМО за один интервал времени, не влияет на количество заявок, полученных за другой интервал времени.

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

Рассмотрим характеристики механизма обслуживания.

Механизм обслуживания характеризуется:

- числом  n каналов обслуживания;

- производительностью канала, или интенсивностью обслуживания μ

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

- дисциплиной очереди (например, объемом очереди m, порядком отбора из очереди в механизм обслуживания и т.п.).

Граф состояний описывает функционирование системы обслуживания как переходы из одного состояния в другое под действием потока заявок и их обслуживания.

Для построения графа состояний СМО необходимо:

- составить перечень всех возможных состояний СМО;

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

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

Вычисление вероятностей состояний СМО

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

Рисунок 1.1 Граф состояния СМО

Число состояний в графе на единицу больше, чем суммарное число каналов обслуживания и мест в очереди.

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

где Pi - вероятность того, что система находится в состоянии  Si, i=

λi(i-1) или λi(i+1) - интенсивность перехода, или среднее число переходов системы в единицу времени из состояния Si в состояние Si+1 или Si-1.

Используя эту систему уравнений, а также уравнения

i=1,

Вероятность Pi любого i-ого (i= ) состояния можно вычислить по следующему общему правилу:  вероятность нулевого состояния рассчитывается как