Метод ступенчатой аппроксимации

Так как законы распределения вероятности событий могут быть различной формы, а не только равновероятными, то необходимо уметь превращать равномерный ГСЧ в генератор случайных чисел с заданным произвольным законом распределения. На рис. 21.3 это соответствует двум первым блокам метода статистического моделирования. Для этого непрерывный закон распределения вероятности события дискретизируем, превратим в дискретный.

Обозначим: h_i — высота i-го столбца, f(x) — распределение вероятности (показывает насколько вероятно некоторое событие x). Значение h_i операцией нормировки необходимо перевести в единицы вероятности появления значений x из интервала x_i < x ≤ x_{i + 1}: P_i = h_i/(h₁ + h₂ + … + h_i + … + h_n).

Операция нормировки обеспечивает сумму вероятностей всех n событий равную 1:

На рис. 24.2 показаны графически переход от произвольного непрерывного закона распределения к дискретному (рис. 24.2, а), отображение получаемых вероятностей на интервал r_рр[0; 1] и генерация случайных событий с использованием эталонного равномерно распределенного ГСЧ (рис. 24.2, б).

Рис. 24.2. Иллюстрация метода ступенчатой аппроксимации

Заметим, что внутри интервала x_i < x ≤x_{i + 1} значение x теперь не различимо, одинаково. Метод огрубляет изначальную постановку задачи, переходя от непрерывного закона распределения к дискретному. Поэтому следует учитывать количество разбиений n из условий точности представления.

На рис. 24.3 показан фрагмент алгоритма, реализующего описанный метод. Алгоритм генерирует случайное число, равномерно распределенное от 0 до 1. Затем, сравнивая границы отрезков, расположенных на интервале от 0 до 1, представляющих собой вероятности P выпадения тех или иных случайных величин X, определяет в цикле, какое из случайных событий i в результате этого выпадает.

Рис. 24.3. Блок-схема алгоритма, реализующего метод ступенчатой аппроксимации

Заметим, что внутри интервала x_i < x ≤ x_{i + 1} значение x теперь не различимо, одинаково. Метод огрубляет изначальную постановку задачи, переходя от непрерывного закона распределения к дискретному. Поэтому следует учитывать количество разбиений n из условий точности представления.

40. Пример моделирования случайного изменения состояния системы.

41. Общие сведения о системе массового обслуживания.

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

1. системы с потерями, в которых требования, не нашедшие в момент поступления ни одного свободного прибора, теряются;

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

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

Выбор требования из очереди на обслуживание производится с помощью так называемой дисциплины обслуживания. Их примерами являются FCFS/FIFO (пришедший первым обслуживается первым), LCFS/LIFO (пришедший последним обслуживается первым), random (англ.)(случайный выбор). В системах с ожиданием накопитель в общем случае может иметь сложную структуру.

42. Виды систем массового обслуживания.

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

43. Потоки событий.

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

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

Однородный поток можно изобразить последовательностью точек на оси, соответствующей времени:

t₁ t₂ t_n

t

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

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

Стационарность потока событий означает, что плотность потока постоянна, отсутствуют промежутки времени, в течение которых событий больше чем обычно. Классический пример – “час пик” на транспорте.

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

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

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

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

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

Если поток событий стационарен, ординарен и без последействий, то такой поток называется простейшим (пуассоновским)потоком.

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

Мгновенной плотностьюпотока событий называется предел отношения среднего числа событий, приходящегося на элементарный отрезок времени (t, t + Dt), к длине этого участка, которая стремиться к нулю.

Пример. В бюро обслуживания в среднем поступает 12 заявок в час. Считая поток заказов простейшим, определить вероятность того, что: а) за 1 минуту не поступит ни одного заказа, б) за 10 минут поступит не более трех заказов.

Сначала найдем плотность (интенсивность) потока, выразив ее в количестве заявок в минуту. Очевидно, эта величина равна .

Далее находим вероятность того, что за время t = 1 мин не поступит ни одной заявки по формуле:

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

44. Методика моделирования систем массового обслужи­вания для простейшего случая.

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

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

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

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

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

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

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

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

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

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