Раздел 2.
СПОСОБ ФОРМИРОВАНИЯ ПОТОКА ЗАЯВОК И ИХ
ОБСЛУЖИВАНИЯ ПРИ МОДЕЛИРОВАНИИ СМО С
ДИСКРЕТНЫМ ПРЕДСТАВЛЕНИИ ВРЕМЕНИ
2.1. Анализ методов формирования моделей потоков заявок
При моделировании СМО необходимо реализовать две процедуры: формирование последовательности случайных чисел (обычно с равномерным распределением в диапазоне 0-1) и формирование потоков заявок (обслуживания) с заданным законом распределения.
Известны три основных метода получения такой случайной последовательности [13, 70]:
1 - аппаратный;
2 - табличный;
3 - алгоритмический.
Первый метод использует физический случайный процесс (внутриламповый шум, радиоактивный распад, атмосферный шум и т.д.) - генератор шума, который может управлять цифровым импульсным генератором, формирующем последовательность случайных чисел [13, 81].
Пример системы аппаратной реализации генераторов случайных потоков при моделировании систем массового обслуживания приведен в [9]. Эти методы обладают универсальностью в отношении заданий значений параметров потоков и их вероятностных характеристик.
Табличный метод широко применялся до появления быстродействующих ЭВМ. Таблицы формировались экспериментальным методом.
Наиболее широкое распространение в настоящее время имеет алгоритмический метод [81], осуществляющий определенную арифметическую процедуру. К ним относят алгоритмы: серединных квадрантов, конгруэнтные, генератор Лемера и др.
Вторая процедура - формирование потока поступления (обслуживания) заявок СМО с заданным законом распределения может быть реализована несколькими способами (графический, аналитический, численный).
Для формирования возможных значений случайных величин с заданным законом распределения, исходными данными служат случайные величины, имеющие, как правило, либо равномерное, либо нормальное распределение в интервале (0,1). Возможные значения xi случайной величины ?, имеющей такие распределения должны быть преобразованы в возможные значения yi случайной величины ?, закон распределения которой задан.
Для выбора способа реализации второй процедуры проанализируем имеющиеся в литературе алгоритмы формирования потока заявок с заданным распределением.
В работе [52] рассмотрен графический способ. Его реализация представлена на рис. 2.1. Fисх.(x) - функция исходного потока распределения случайных величин, а Fтеор.(y) - необходимая функция распределения случайных величин.
Путем перемещения линии MN производится определение точек получаемого закона распределения, в зависимости от исходного закона. Отклонения исходной функции отражаются на результирующем графике. На рис.2.1 показано получение только двух точек результирующей функции распределения.
. Преимущество графического метода заключается в том, что с его помощью можно сформировать последовательность случайных величин практически любого закона распределения из нормального или равномерного.
Несмотря на простоту графического метода формирования потоков случайных распределений, и возможность получения практически заданных законов распределения из одного из заданных, данный метод обладает большим количеством недостатков, основными из которых являются небольшая точность получения случайных величин, трудоемкость построения для необходимого количества точек, и невозможность применения алгоритмических моделей при использовании данного метода.
Рис. 2.1. Графический способ получения потока случайных величин заданного закона распределения.
Сущность аналитического, или прямого метода преобразования случайных чисел показано в [13]. Идея построения соответствующих алгоритмов вытекает из следующей теоремы: если случайная величина ? имеет плотность распределения f(y), то распределение случайной величины
(2.1)
является равномерным в интервале (0,1).
На основании этой теоремы можно получить следующее правило. Чтобы получить число, принадлежащее совокупности случайных чисел {yi}, имеющих функцию плотности f(y), необходимо разрешить относительно yi уравнение
. (2.2)
Для обоснования данного правила рассмотрим случайную величину ?, имеющую равномерное распределение в интервале (0,1), и случайную величину ? , связанную с ? соотношением (2.1).
Предположим, что f(y) на одном интервале не обращается в тождественно в нуль. Тогда ? является, согласно (2.1), монотонно возрастающей функцией ? . В свою очередь величина ? , соответственно, может быть выражена как функция от ? :
? = ? (?). (2.3)
Легко видеть, что обратная функция
(2.4)
в данном случае выражается соотношением (2.1). Имея это в виду, получим плотность распределения случайной величины ? . Функция распределения F? (y) равна вероятности того, что ? < y:
. (2.5)
Подставим в (2.5) вместо ? его значение из (2.3)
. (2.6)
Поскольку функция монотонно возрастает, то неравенство
эквивалентно неравенству
.
Поэтому,
. (2.7)
Вероятность, фигурирующую в соотношении (2.7), можно вычислить, так как функция плотности случайной величины известна: принято, что ? имеет равномерное распределение в интервале (0,1). Поэтому
, (2.8)
или
. (2.9)
Подставляя в (2.9) вместо его выражение из (2.1) и (2.4), получим
. (2.10)
Последнее соотношение показывает, что случайная величина имеет функцию плотности .
Соотношение (2.10) в ряде случаев может быть непосредственно использовано для получения последовательности случайных чисел показательного закона распределения.
Если требуется получить случайные числа с показательным законом распределения , (), (2.11)
то в силу соотношения (2.11) получим
. (2.12)
(где - случайное число, имеющее равномерное распределение в интервале (0,1)), или, после вычисления интеграла, . (2.13)
Разрешая это уравнение относительно , имеем . (2.14)
Учитывая, что случайная величина