Модели систем массового обслуживания. Классификация систем массового обслуживания (стр. 1 из 2)
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
кафедра сетей и устройств телекоммуникаций
РЕФЕРАТ
На тему:
«Модели систем массового обслуживания. Классификация систем массового обслуживания»
МИНСК, 2008
Математическое введение в теорию цепей Маркова. (Markov’schain )
Дискретные цепи Маркова. Будем говорить, что задана дискретная цепь Маркова, если для последовательности случайных величин выполняется равенство
.Это означает, что поток случайных величин определяется только вероятностью перехода от предыдущего значения случайной величины к последующему. Зная начальное распределение вероятностей, можно найти распределение на любом шаге. Величины inможно интерпретировать как номера состояний некоторой динамической системы с дискретным множеством состояний (типа конечного автомата). Если вероятности переходов не зависят от номера шага, то такая цепь Маркова называется однородной и ее определение задается набором вероятностей
.Для однородной Марковской цепи можно определить вероятности перехода из состояния i в состояние j за m шагов
Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния. Состояние i называется поглощающим, если для него pii =1.
Состояние называется возвратным, если вероятность попадания в него за конечное число шагов равна единице. В другом случае состояние относится к невозвратным. Возвратное состояние может быть периодическим и апериодическим в зависимости от наличия кратных шагов возврата. Введем вероятности возврата в состояние i через n шагов после ухода из этого состояния:
Они позволяют определить среднее число шагов или, иначе говоря, среднее время возврата:
.Состояние называется возвратным нулевым, если среднее время возвращения в него равно бесконечности, и возвратным ненулевым, если это время конечно. Известны две важные теоремы:
Теорема 1.
Состояния неприводимой цепи Маркова либо все невозвратные, либо все возвратные нулевые, либо все возвратные ненулевые. В случае периодической цепи все состояния имеют один и тот же период.
Вторая теорема рассматривает вероятности достижения состояний в стационарном (то есть не зависящем от начального распределения вероятностей) режиме. Соответствующее распределение вероятностей также называют стационарным. Нахождение стационарного распределения вероятностей достижения состояний одна из основных задач теории телетрафика.
Теорема 2.
Для неприводимой и апериодической цепи Маркова всегда существуют предельные вероятности, не зависящие от начального распределения вероятностей. Более того, имеет место одна из следующих двух возможностей:
А) все состояния цепи невозвратные или все возвратные нулевые, и тогда все предельные вероятности равны нулю и стационарного состояния не существует;
Б) все состояния возвратные ненулевые и тогда существует стационарное распределение вероятностей:
Состояние называется эргодическим, если оно апериодично и возвратно ненулевое. Если все состояния цепи Маркова эргодичны, то вся цепь называется эргодической. Предельные вероятности эргодической цепи Маркова называют вероятностями состояния равновесия, имея в виду, что зависимость от начального распределения вероятностей полностью отсутствует.
Цепь Маркова с конечным числом состояний (конечная цепь), удобно изображать в виде ориентированного графа, называемого диаграммой переходов. Вершины графа ассоциируются с состояниями, а ребра с вероятностями переходов.
Вычисления вероятностей достижения состояний производится прямыми методами или с помощью z-преобразования.
Цепь Маркова.
Введем матрицу вероятностей переходов и вектор-строку вероятностей на шаге n
.Распределение вероятностей на произвольном шаге тогда будет подчиняться матричному соотношению:
.Оно позволяет рекуррентно вычислять все вероятности состояний. Для нахождения предельного распределения (стационарного) нужно решить уравнение:
Его можно решать как систему линейных алгебраических уравнений, если цепь конечна.
Для примера (рис. 1) имеем:
.и решение матричного уравнения сводится к решению системы трёх уравнений:
Коэффициенты первого уравнения в этой системе дополняют до единицы сумму коэффициентов второго и третьего уравнений; это свидетельствует о линейной зависимости между ними. Поэтому для решения системы уравнений нужно ввести дополнительное нормирующее условие. В данном примере:
.Решая систему полученных уравнений, имеем:
Уравнение для вероятности достижения состояния в переходном режиме решить значительно труднее. Некоторого упрощения можно достигнуть, используя z – преобразование. Применим его к уравнению для переходных вероятностей
.Обозначая соответствующие преобразования, получим:
Все полученные здесь математические результаты относились к однородным Марковским процессам, где вероятности переходов не зависят от времени. В более общем случае такая зависимость имеет место.
Рассмотрим вероятности перехода системы из состояния i на m-том шаге в состояние j на n-том шаге для n > m.
Можно показать, что эти вероятности связаны между собой, так называемым уравнениями Чепмена-Колмогорова.(Chapman - Kolmogorov)
.Для однородных цепей Маркова эти уравнения упрощаются так как
.И сводятся к анализируемым выше.
Случайный процесс X(t) с дискретным множеством значений образует непрерывную цепь Маркова, если
.Будущие состояния зависят от прошлого только через текущее состояние. Для непрерывный цепей Маркова основным также является уравнение Чепмена –Колмогорова, для однородной цепи имеющее вид:
.Здесь матрица H(t)= [ pij(t)] - матрица вероятностей перехода из состояния i в состояние j в момент времени t , а матрица Q называется матрицей интенсивностей переходов. Ее элементы имеют следующий смысл: если в момент времени t система находилась в состоянии Ei , то вероятность перехода в течение промежутка времени (t,t+Δt) в произвольное состояние Ej задается величиной qij(t)Δt + o(Δt), а вероятность ухода из состояния Ei величиной -qiiΔt + o(Δt).
Таким образом, интенсивности переходов можно вычислять как соответствующие пределы при стремлении к нулю длительности временного интервала.
Наиболее важным для дальнейшего использования является класс непрерывных цепей Маркова называемых «процессами гибели - размножения» (Birth – deathprocess). Для таких систем из состояния k возможны переходы только в состояния k, k-1 и k+1 в следующие моменты времени:
· в момент t объем популяции был равен k и в течение времени (t,t+Δt) не произошло изменения состояния
· в момент t объем популяции был равен k-1 и в течение времени (t,t+Δt) родился один член популяции
· в момент времени t объем популяции был равен k+1 и в течение времени (t,t+Δt) погиб один член популяции
Рис. 1. Возможные переходы в состояние Ек.
Будем искать вероятность того, что в момент времени t объем популяции равен k , обозначив его Pk(t). Можно записать соотношения для вероятности достижения состояния k в момент времени t+Δt:
.Определим граничные и нормирующие условия:
Выразим вероятности переходов за интервал Δt через интенсивности
Вер(+1)=λkΔt+o(Δt) ; Вер(-1)=μkΔt+o(Δt).
Вероятность нуля рождений 1- λkΔt+o(Δt) , а нуля гибелей 1- μkΔt+o(Δt).
Таким образом, вероятность того, что состояние k сохранится неизменным, будет равно произведению [1- λkΔt+o(Δt)][ 1- μkΔt+o(Δt)].
Тогда уравнения Чепмена-Колмогорова приобретают вид