Краткая теории

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

В ходе решения данной задачи требуется дать ответ на вопросы типа: какова функция распределения вероятностей времени ожидания клиента в очереди? Времени простоя системы в ожидании клиентов? Если сами эти функции определять сложно, то каковы их наиболее важные характеристики (т.е. математическое ожидание, дисперсия и т.д.)?

Основа этой задачи ¾ случайный процесс прихода клиентов в систему обслуживания. Промежутки между приходами любой последовательной пары клиентов ¾ независимые случайные события, распределенные по некоторому закону. Реальный характер этого закона может быть установлен лишь путем многочисленных наблюдений; в качестве простейшей модельной функции плотности вероятности можно взять равновероятное распределение в диапазоне времени от 0 до некоторого T ¾ максимально возможного промежутка между приходами двух последовательных покупателей. При этом распределении вероятность того, что между приходами двух покупателей пройдет 1 минута, 3 минуты или 8 минут одинакова (если T > 8 мин).

Такое распределение, конечно, малореалистично; реально для большинства процессов массового обслуживания функция распределения растет от t = 0, имеет при некотором значении t = t максимум и быстро спадает при больших t, т.е. имеет вид, изображенный на рисунке 7.6.

f (t)

t t

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

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

(4.1)

где l ¾ некоторая константа, n ¾ произвольное целое. Функции (4.1) имеют максимум при t = n/l и нормированы.

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

Для примера в таблице в колонке A записаны случайные числа ¾ промежутки между приходами клиентов (в минутах), в колонке B ¾ случайные числа ¾ длительности обслуживания (в минутах). Для определенности взято a _max = 10 и b _max = 5. Из этой короткой таблицы, разумеется, невозможно установить, каковы законы распределения приняты для величин A и B. Остальные колонки предусмотрены для удобства анализа; входящие в них числа находятся путем элементарного расчета. В колонке C представлено условное время прихода клиента, D ¾ момент начала обслуживания, E ¾ конца обслуживания, F ¾ длительность времени, проведенного клиентом в системе в целом, G ¾ в очереди в ожидании обслуживания, H ¾ время, проведенное системой в ожидании клиентов (если их нет). Таблицу удобно заполнять по горизонтали, переходя от строчки к строчке. Приведем для удобства соответствующие формулы (в них i = 1, 2, 3,...):

c ₁ = 0, c _i+1 = c _i + a _i+1, d ₁ = 0, d _i+1 = max(c _i+1, e _i) (4.2)

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

(4.3)

Таким образом, при данных случайных наборах чисел в колонках A и B, и клиентам приходилось стоять в очереди (колонка G), и системе простаивать в ожидании клиента (колонка H).

№ п/п	A	B	C	D	E	F	G	H

Какие вопросы возникают в первую очередь при моделировании систем такого вида? Во-первых, какое среднее время приходится стоять в очереди? Ответить на него кажется несложно: найти

(4.4)

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

Более сложный вопрос ¾ каково распределение случайных величин G и H при заданных распределениях случайных величин A и B? Качественный ответ на него можно попытаться получить построив соответствующие гистограммы по результатам моделирования. Затем делается некоторая гипотеза о виде распределения и используются один или несколько статистических критериев проверки достоверности этой гипотезы.

Располагая функцией распределения (пусть даже эмпирической, но достаточно надежной), можно ответить на любой вопрос о характере процесса ожидания в очереди. Например: какова вероятность прождать дольше m минут? Ответ будет получен, если найти отношение площади криволинейной трапеции, ограниченной графиком плотности распределения, прямыми x = m и y =0, к площади всей фигуры.

Контрольные вопросы

1. Что такое «случайный процесс»?

2. Каковы принципы компьютерного генерирования равномерно распределенных случайных чисел?

3. Как можно получить последовательность случайных чисел с пуассоновским законом распределения?

4. Что такое «система массового обслуживания»? Приведите примеры.

5. В чем заключается метод Монте-Карло вычисления площадей плоских фигур? Объемов тел?

6. Какие примеры случайных процессов Вы можете привести?

Рекомендации.

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

2. Одна из центральных задач при моделировании случайных процессов — нахождение характеристик случайных величин, являющихся объектом моделирования. Главная такая характеристика — функция распределения. Ее вид можно качественно оценить по гистограмме, построенной в ходе моделирования, а гипотезу о функциональной форме проверить с помощью одного из стандартных критериев, используемых в математической статистике (например, критерия c ²). Однако это не всегда целесообразно, особенно если в задаче требуется определить лишь некоторые характеристики случайной величины — чаще всего среднее значение и дисперсию. Их можно найти без моделирования самой функции распределения. При этом статистическая оценка достоверности результатов является обязательной.

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

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