Тема 7: Моделирование случайных процессов в системах массового обслуживания.

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

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

Рассмотрим некоторые проблемы, возникающие в этой задаче. На входе этой задачи случайный процесс – приход покупателей в магазин. Промежутки между приходами любой последовательной пары покупателей – независимые случайные величины, распределенные по некоторому закону. Реальный характер этого закона может быть установлен лишь путем многочисленных наблюдений. В качестве простейшей модели можно выбрать равномерное распределение в диапазоне времени от 0 до Т – максимально возможного времени между приходами покупателей. Однако на практике равномерное распределение маловероятно. Реальная функция распределения имеет максимум при t=τ и очень быстро убывает с ростом t. Ее график будет иметь вид

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

, λ R, n N

Функция p_n(t) имеет максимум

Кроме того,

Т. е. эта функция действительно является плотностью распределения некоторой случайной величины.

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

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

Рассмотрим таблицу.

В колонке А записаны случайные числа – промежутки между приходами покупателей в минутах.

В колонке В также записаны случайные числа – длительности обслуживания покупателей.

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

В колонке D записаны моменты начала обслуживания покупателей.

В колонке Е – моменты конца обслуживания.

В колонке F – длительности времени, проведенного покупателем в магазине

В колонке G – время, проведенное покупателями в очереди в ожидании продавца.

В колонке Н – время, проведенное продавцом в ожидании покупателей.

Таблицу удобно заполнять по горизонтали, переходя от строки к строке и пользуясь формулами:

С₁=0, С_i+1=C_i+A_i+1

D₁=0, D_i+1=max(C_i+1, E_i)

E_i=D_i+B_i

F_i=E_i-C_i

G₁=0, G_i+1=F_i+1-B_i+1

H₁=0, H_i+1=A_i+1-E_i

Данная таблица позволяет ответить на вопросы:

1) Каково среднее время G ожидания покупателем в очереди.

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

2) Найти среднее время Н ожидания продавцом покупателей.

Решается так же, как и предыдущее.

3) Найти функции распределения случайных величин G и H.

Построим данную таблицу для какого-либо большого числа строк n. Найдем максимальное значение g_max в столбце G. Разделим отрезок [0, g_max ] на М равных частей. Посчитаем количество элементов, попавших в каждый из отрезков. В первый отрезок попало п₁ чисел, во второй – п₂ и т.д. найдем также частоты попадания в отрезок элементов столбца G . По полученным данным построим гистограмму

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