Значимые выборки

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

Пусть рассчитывается интеграл следующей структуры:

(19)

где g(x), f(x) – заданные функции;

G_x – область интегрирования.

Не обязательно, чтобы функции g(x), f(x) и область G_x были заданы явно, например, аналитически. Процедуры их определения могут быть очень сложными. Кроме того, в реальной задаче интеграл может быть k-кратным (то есть х – это вектор; dx = dx₁…dx_k).

В (19) функция f(x) может интерпретироваться как плотность вероятности. При необходимости ее нужно перенормировать:

, (19а)

где ; .

Тогда значение интеграла можно интерпретировать как среднее значение функции g(x) при заданном распределении случайной величины х:

.

В частном случае интеграл I действительно (изначально) может отображать среднее значение заданной функции g(x) наблюдаемой случайной переменной х, имеющей известную плотность распределения f(x).

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

Для простоты рассмотрим одномерный случай.

В первой схеме разыгрывают последовательность равномерно распределенных в области G_x случайных значений переменной х: х₁, х₂, …, х_п. Несмещенная выборочная оценка интеграл в этом случае будет иметь вид:

, (20)

где DG – объем области интегрирования.

Наиболее "естественно" такая схема выглядит в случае, если просто интегрируется функция g(x) - без весового коэффициента f(x). В этом случае в (20) сомножитель f(x_i) исключается (равен 1).

Во второй схеме также разыгрывают последовательность случайных значений переменной х: х₁, х₂, …, х_п, однако розыгрыш реализуют иначе – в предположении что случайная переменная х подчиняется распределению с плотностью распределения f(x) – см. п.1.3.

Несмещенная выборочная оценка интеграл в этом случае будет иметь вид:

(21)

Именно эта вторая схема и является реализацией метода значимых выборок.

Суть понятия "значимая выборка" заключается в том, что при определении последовательности значений х₁, х₂, …, х_п мы выбираем эти значения не "на равных правах" (на основе равномерного распределения). Выбираются, по преимуществу, "более значимые (более вероятные)" значения – в смысле заданного распределения f(x).

Метод значимых выборок можно обобщить следующим образом.

Пусть необходимо рассчитать интеграл

. (22)

Переопределим подынтегральную функцию следующим образом:

, (23)

где f(x) специально подобранная функция, которую можно интерпретировать как плотность распределения, то есть:

;

g*(x) = g(x)/f(x).

Тем самым мы сводим задачу к предыдущей и можем реализовать схему метода значимых выборок, оперируя "искусственной" плотностью распределения f(x).

По определению

I = E[g*(x)].

и, следовательно,

(24)

Если подобрать плотность f(x) соответствующим образом, то можно значительно уменьшить дисперсию выборочного среднего (24). Действительно, учтем, что в имитационном эксперименте (24) наблюдаемой является величина g* = g/f, то есть частное от деления двух других случайных коррелированных величин (так как они зависят от общей случайной переменной x). Следовательно, если обеспечить положительную корреляцию величин g и f, то можно значительно понизить дисперсию величины g*. Не приводя точных расчетных формул, покажем это на грубых оценках.

Предположим, что отношение g/f конечно, то есть g₁* £ g/f £ g₂*. Тогда

Var[g*] £ (g₂* - g₁*)²/4.

Следовательно, если функция f будет примерно пропорциональна g, разброс отношения g/f будет небольшим, то есть значения g₁* и g₂* будут близки. В пределе, если положить f = g/I, где I – истинное значение интеграла, получим g₁* = g₂* и, следовательно, Var[g*] = 0. Естественно, что такой предел недостижим, поскольку значение интеграла априори неизвестно, но можно констатировать, что в методе значимых выборок существует принципиальная возможность значительного уменьшения погрешности расчета интеграла.

4. Некоторые типы систем массового обслуживания
(для проведения имитационных экспериментов)

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

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

В основном мы рассмотрим простейшие стационарные пуассоновские модели (п.4.1), дополнительно – одну более сложную модель (п. 4.2)[10].

Классификацию СМО будем проводить, пользуясь расширенными обозначениями Кендалла (a/b/c):(d/e/f) (см. п.1.2). Конкретные значения параметров а и b (типы входного и выходного потоков) будем обозначать так:

М – пуассоновский (марковский) поток. Это значит, что временные интервалы Dt_з между входными заявками и время обслуживания заявки Dt_о в одном канале обслуживания распределены экспоненциально;

D – интервалы Dt_з и Dt_о имеют фиксированные значения (детерминированы);

E_з – поток Эрланга k-го порядка. Это значит, что интервалы Dt_з и Dt_о имеют гамма-распределение;

GI – произвольный тип распределения интервалов Dt_з;

G – произвольный тип распределения интервалов Dt_о.

Для дисциплины очереди (параметр d) будем использовать следующие обозначения:

FCFS – первым пришел первым обслуживаешься;

LCFS – последним пришел первым обслуживаешься;

SIRO – случайный отбор клиентов;

GD – произвольный тип дисциплины.