Математическая постановка задачи

Введение

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

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

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

Система массового обслуживания – это, прежде всего, система, где люди работают с людьми, притом в больших количествах. Поэтому проводить анализ таких систем крайне сложно и трудозатратно т.к. вести учёт обслуживания больших масс людей очень проблематично, а порой и невозможно. Статистическое моделирование позволяет смоделировать работу системы массового обслуживания, в каких угодно масштабах и временных рамках, предоставляя удобную для анализа модель работы системы. Использование случайных чисел в расчётах позволяет получать каждый раз новую модель. Анализ нескольких моделей одной системы предоставляет широкие возможности по улучшению системы.

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

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

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

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

 

1.Математическая  постановка задачи

Смоделировать работу системы  массового обслуживания, поступление  требований в которой  подчинено пуассоновскому закону распределения со средним  λ=5 клиент/час. Время обслуживания заявки равно 0.4 с вероятностью 0.5 и 0.6 с вероятностью 0.5. Моделирование закончить с поступлением 5 заявки. При моделировании использовать следующие случайные числа

0.345500

0.487110

0.811154

0.891254

0.429090

0.230243

0.595449

0.542293

0.420822

0.697501

 

2. Решение задачи

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

Теорию потока однородных событий, которая легла в основу теории массового обслуживания, разработал советский математик А. Я. Хинчин.[

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

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

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

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

Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых, с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.

К примеру, пусть сказано: «заявки  в среднем приходят в количестве 5 штук в час». Это означает, что  времена между приходом двух соседних заявок случайны, например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис. 1, но в сумме они дают в среднем 1 (обратите внимание, что в примере это не точно 1, а 1.1 — но зато в другой час эта сумма, например, может быть равной 0.9); и только за достаточно большое время среднее этих чисел станет близким к одному часу.

Рис.  1. Случайный процесс прихода заявок в СМО

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

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

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

Перечислим некоторые основные понятия СМО.

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

Очереди характеризуются правилами стояния в очереди (дисциплиной обслуживания), количеством мест в очереди (сколько клиентов максимум может находиться в очереди), структурой очереди (связь между местами в очереди). Бывают ограниченные и неограниченные очереди. Перечислим важнейшие дисциплины обслуживания. FIFO (First In, First Out — первым пришел, первым ушел): если заявка первой пришла в очередь, то она первой уйдет на обслуживание. LIFO (Last In, First Out — последним пришел, первым ушел): если заявка последней пришла в очередь, то она первой уйдет на обслуживание (пример — патроны в рожке автомата). SF (Short Forward — короткие вперед): в первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.

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

Пусть имеется два магазина. В  магазине № 1 обслуживание осуществляется в порядке очереди, то есть здесь  реализована дисциплина обслуживания FIFO (см. рис. 2.).

Рис. 2. Организация очереди по дисциплине FIFO

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

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

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

    для  х = 0, 1, …  ,

где р(х) — вероятность поступления х заявок в единицу времени;

х    —число заявок в единицу времени;

λ     — среднее число заявок в единицу времени (темп поступления заявок);

е = 2,7183 (основание натурального логарифма).

Соответствующие значения вероятностей р(х) нетрудно определить с помощью таблицы пуассоновского распределения. Например, если средний темп поступления заявок равен двум клиентам в час, то вероятность не поступления в систему в течение часа ни одной заявки равна 0,13; вероятность появления одной заявки -0,27; двух — также около 0,27; три заявки могут появиться с вероятностью 0,18; четыре — с вероятностью около 0,9 и т.д. Вероятность того, что за час в систему поступят 9 и более заявок близка нулю.

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

 

Судить о результатах  работы СМО можно по показателям. Наиболее популярные из них:

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

Процесс моделирования начинаем с того, что генерируем время поступления первого клиента (заявки).

R=0.345500

T₁=Т₀+P₁=0-(1/5)*ln(0.345500)=0.21

I событие.

Т_тек=0.21- время поступления первой заявки.

Сгенерируем время поступления  второй заявки

R=0.487110

Т₂=Т_тек+Р₂=0.21-(1/5)*ln(0.487110)=0.35

Так как в начальный  момент времени система простаивала, то определим время простоя:

T_{простоя}=T_тек-T₀=0.21

Сгенерируем время обслуживания первой заявки

R=0.811154

R>0.5 => q=q2=0.6

   Определим время  окончания обслуживания первой  заявки

T_ок.1 = T_тек + q=0.21+0.6=0.81

II событие

Т_тек=0.35- время поступления второй заявки.

Сгенерируем время поступления  третей заявки:

R= 0.891254

T₃ = T_тек. + P₃ = 0.35 –(1/5) *ln(0.891254)  = 0.37

Так как система работает, ставим заявку в очередь и увеличиваем длину очереди:

Q = 0 + 1 = 1 ( при

III событие.

T_тек = 0.37 – время поступления третей заявки.

Сгенерируем время поступления  четвертой заявки:

R= 0.429090

T₄ = T_тек. + P₄ = 0.38 – (1/5)* ln 0.429090=0.54

Так как система работает, ставим заявку в очередь и увеличиваем длину очереди: