Численные методы моделирования смо

Моделирование СМО как Марковского процесса.

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

Графу состояний трехканальной СМО можно сопоставить следующую матрицу интенсивностей переходов Марковского процесса.

Рис. 5. Матрица интенсивностей переходов для СМО.

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

Будем для определенности считать, что строки и столбцы матрицы нумеруются с 0. Тогда l_ij — интенсивность перехода в состояние j при условии, что система находится в состоянии i. Логично задать начальное состояние системы i=0 (нет заявок). Тогда, если i — номер текущего состояния, алгоритм моделирования произвольного Марковского процесса работает следующим образом:

1. Установить текущее состояние i = 0, обнулить счетчик модельного времени T и счетчики времени пребывания в k-том состоянии T_k, k = 0, …m-1, а также счетчик числа обслуженных заявок N.

2. Для каждого состояния j = 0, … m – 1 генерируется случайная величина – время до перехода из текущего состояния i в состояние j. Это время рассчитывается по формуле

где u – случайное число с равномерным законом распределения на интервале [0, 1). Это генератор случайных чисел с экспоненциальным законом распределения с интенсивностью l_ij , построенный по методу обратной функции.

3. Среди полученных времен t_ij находим минимальное. Другими словами находим индекс j такой, что для него время t_ij минимально при изменении 0 ≤ j ≤ m-1. Найденное минимальное время определяет действительное время пребывания системы в текущем состоянии i и показывает новое действительное состояние системы j.

4. Увеличиваем счетчик модельного времени T и счетчик времени пребывания системы в состоянии i на величину t_ij .

T = T + t_ij: T_i = T_i + t_ij;

5. Если j < i, то увеличить число в счетчике обслуженных заявок N на единицу.

6. Если N меньше заданного числа обслуженных заявок, то перейти в следующее состояние j. ( i = j ), а затем перейти к п.2.

Если N равно заданному числу заявок – СТОП.

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

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

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

Для случаев с конечным количеством состояний m накапливать модельное время необязательно — ведь T равно сумме всех T_i.

Очевидно, что для случая СМО возможен переход процесса из текущего состояния i только в два соседних состояния: j = i + 1 и j = i – 1. Это позволяет упростить алгоритм моделирования. Рассмотрим два более простых алгоритма моделирования на примере СМО с бесконечной очередью.

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

Решение 1.

Заметим, что матрица интенсивностей переходов для СМО – трехдиагональная (рисунок 4). В такой матрице все отличные от нуля элементы размещены на двух диагоналях, прилегающих к главной. Таким образом, если j = i + 1, то переход происходит к элементу j, лежащему выше главной диагонали (интенсивность равна l). Если j = i – 1, то переход происходит к элементу j , лежащему ниже главной диагонали.

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

Необходимо вычислять случайное время перехода из текущего состояния i только в два соседних состояния: j = i + 1 и j = i – 1. Переходы в другие состояния невозможны.

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

Решение 2. Ввести искусственные ограничения на длину очереди и решить конечную задачу, подобрав в эксперименте достаточно большую (например, 40 или 100) максимальную длину очереди. В процессе моделирования необходимо проверять, что бы очередь ограниченной длины полностью не заполнялась. Тогда результаты моделирования СМО с конечной очередью будут полностью соответствовать системе с бесконечной очередью. Если последнее состояние в очереди достигается, необходимо увеличить ее длину.

Характеристики СМО, полученные в результате моделирования Марковского процесса необходимо сравнить с характеристиками, полученными в результате аналитического расчета.