Главная страница
Навигация по странице:

  • Успешно изучив тему, Вы: получите представление о

  • Вопрос 1. Понятие марковского процесса.

  • Вопрос 2. Классификация марковских процессов.

  • Вопрос 4. Дискретные цепи Маркова.

  • Моделирование систем лекция. Моделирование систем. Литература по теме Тема Модели на основе метода статистических испытаний


    Скачать 2.59 Mb.
    НазваниеЛитература по теме Тема Модели на основе метода статистических испытаний
    АнкорМоделирование систем лекция
    Дата17.08.2022
    Размер2.59 Mb.
    Формат файлаpdf
    Имя файлаМоделирование систем.pdf
    ТипЛитература
    #647642
    страница4 из 13
    1   2   3   4   5   6   7   8   9   ...   13
    Тема 4. Марковские процессы. Модели систем массового
    обслуживания
    Цели изучения темы:
     познакомиться с понятием марковского процесса;
     познакомиться с математическим аппаратом моделирования дискретно протекающих марковских процессов.
    Задачи изучения темы:
     изучить способ математического описания марковских процессов;
     научиться определять характеристики марковских процессов с дискретным временем и дискретным множеством состояний.
    Успешно изучив тему, Вы:
    получите представление о:
     сущности марковских процессов и их классификации;
     как формулируются задачи в терминах марковского процесса;
     способах построения математической модели и нахождения с ее помощью значений нужных показателей;
    будете знать:
     как описать протекающие процессы с помощью графа состояний и переходов;
     как найти вектор вероятностей состояния процесса на определенном шаге;
     как вычислить предельные вероятности процесса.
    Вопросы темы:
    1. Понятие марковского процесса.
    2. Классификация марковских процессов.
    3. Граф состояний и переходов.
    4. Дискретные цепи Маркова.
    5. Уравнения Колмогорова.
    6. Процессы гибели и размножения.
    7. Оптимизация показателей многоканальной СМО с отказами.
    8. Модель системы массового обслуживания с неограниченной очередью. Формула Хинчина – Полачека.

    50
    Вопрос 1. Понятие марковского процесса.
    Постановка многих задач анализа и, в особенности, проектирования систем связаны с необходимостью проведения оценивания количественных показателей протекающих в системе процессов. Часто поведение этих развивающихся во времени процессов в силу действия различных случайных факторов не удается исследовать во всех деталях. Следствием этого является невозможность в отличие от
    детерминированных систем однозначно предсказать поведение системы в какой-то момент в будущем. Такие системы и процессы, как это уже было определено ранее, носят название стохастических. Их анализ целесообразно проводить, рассматривая их как случайные процессы, ход и исход которых зависят от ряда случайных факторов, сопровождающих их развитие.
    Для нахождения числовых значений нужных параметров применяются как аналитические, так и имитационные модели. В настоящей и следующей теме будет рассмотрен подход на основе аналитических моделей. Построение аналитической модели в случае стохастических процессов означает необходимость построения некоторой вероятностной модели явления, в которой будут учтены обусловливающие его развитие случайные факторы.
    Для математического описания многих случайных процессов может быть применен аппарат, разработанный в теории вероятностей для так называемых марковских случайных процессов.
    Случайный процесс, протекающий в системе S, называется
    марковским (или процессом без последействия), если он обладает следующим свойством: для каждого момента времени t
    0
    вероятность любого состояния системы в будущем (при t>t
    0
    ) зависит только от ее состояния в настоящем (при t= t
    0
    ) и не зависит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлом).
    Другими словами, в марковском случайном процессе будущее развитие зависит только от его настоящего состояния и не зависит от
    «предыстории» процесса.
    Вопрос 2. Классификация марковских процессов.
    Марковские случайные процессы делятся на классы. Основными классифицирующими признаками являются:
     множество состояний, в которых может находиться система;
     моменты времени, в которых происходит изменение состояния системы.

    51
    Случайный процесс называется процессом с дискретными
    состояниями, если возможные состояния системы S
    1
    , S
    2
    , S
    3
    ,... можно перечислить (перенумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) переходит из одного состояния в другое.
    Кроме процессов с дискретными состояниями существуют случайные процессы с непрерывными состояниями: для этих процессов характерен постепенный, плавный переход из состояния в состояние. Например, процесс изменения напряжения в осветительной сети представляет собой случайный процесс с непрерывными состояниями.
    Если переходы системы из состояния в состояние возможны только в определенные моменты времени t
    1
    , t
    2
    , t
    3
    ,…, то марковский процесс относится к процессам с дискретным временем. В противном случае имеет место процесс с непрерывным временем.
    Вопрос 3. Граф состояний и переходов.
    Анализ случайных процессов с дискретными состояниями обычно проводится с помощью графа состояний и переходов (ГСП).
    Пусть имеется система S с n дискретными состояниями:
    S1, S2, S3,…, Sn.
    Каждое состояние изображается окружностью или прямоугольником (вершина), а возможные переходы из состояния в состояние («перескоки») – стрелками (дугами), соединяющими эти вершины (рис. 8а).
    Рис. 8. Пример неразмеченного (а) и размеченного (б) ГСП

    52
    Заметим, что стрелками можно отмечать только непосредственные переходы из состояния в состояние; если система может перейти из состояния S
    1
    в S
    5
    только через S
    2
    , то стрелками отмечаются только переходы S
    1
    –S
    2
    и S
    2
    –S
    5
    , но не S
    1
    –S
    5
    Удобно также пользоваться размеченным графом, который графически изображает не только возможные состояния системы и возможные переходы из состояния в состояние, но также и значения вероятностей перехода (рис. 8б), о которых речь будет идти ниже.
    Вопрос 4. Дискретные цепи Маркова.
    Пусть система S может находиться в состояниях:
    S1, S2, S3, …, Sn,
    и изменения состояния системы возможны только в моменты:
    t1, t2, t3, …, tn.
    Будем называть эти моменты шагами, или этапами процесса и рассматривать протекающий в системе S случайный процесс как функцию целочисленного аргумента m = 1, 2,..., k,..., обозначающего номер шага.
    Указанный случайный процесс состоит в том, что в последовательные моменты времени t
    1
    , t
    2
    ,..., t
    k
    ,... система S оказывается в тех или иных состояниях. Процесс, происходящий в системе, можно представить как последовательность (цепочку) событий, например:
    (0)
    (1)
    ( )
    ( )
    1 2
    ,
    ,...
    ,...,
    i
    n
    i
    n
    S
    S
    S
    S
    ,
    называемую марковской цепью, где для каждого шага вероятность перехода из любого состояния S
    i
    в любое S
    j
    не зависит от того, когда и как система пришла в состояние S
    i
    Марковскую цепь можно описать с помощью вероятностей состояний, в которых находится система на каком-то шаге. Пусть в любой момент времени (после любого шага) система может пребывать в одном из состояний:
    S1, S2, S3, …,.Sn,

    53 т.е., в результате шага k осуществится одно из полной группы несовместных событий:
    ( )
    ( )
    ( )
    ( )
    1 2
    ,
    ,....
    ,...,
    k
    k
    k
    k
    i
    n
    S
    S
    S
    S
    .
    Обозначив вероятности этих событий для k -го шага через
    ( )
    ( )
    ( )
    ( )
    1 1
    2 2
    ( )
    (
    ),
    ( )
    (
    ), ... ( )
    (
    ),... ( )
    (
    )
    k
    k
    k
    k
    i
    i
    i
    n
    p k
    p S
    p k
    p S
    p k
    p S
    p k
    p S




    ,
    легко видеть, что для каждого шага k
    1 2
    ( )
    ( ) ... ( ) ...
    ( ) 1
    i
    n
    p k
    p k
    p k
    p k


     

    ,
    поскольку
    ( ),
    1,
    i
    p k i
    n

    , представляют собой вероятности появления полной группы событий.
    Вероятности
    ( ),
    1,
    i
    p k i
    n

    называются вероятностями состояния.
    Для любого шага (момента времени t
    1
    ,t
    2
    ,..., t
    k
    ,... или номера
    1,2,...,k,...) существуют некоторые вероятности перехода системы из любого состояния в любое другое (некоторые из них равны нулю, если непосредственный переход за один шаг невозможен), а также вероятность задержки системы в данном состоянии. Эти вероятности называются переходными вероятностями марковской цепи.
    Если значения переходных вероятностей не зависят от номера шага, то марковская цепь называется однородной, или стационарной.
    В противном случае марковская цепь является неоднородной, или
    нестационарной.
    Если из состояния S
    i
    не исходит ни одной стрелки (переход из него ни в какое другое состояние невозможен, например, S
    3
    графа рис. 8), соответствующая вероятность задержки Р
    ii
    равна единице.
    Графу системы, содержащему n вершин, можно поставить в соответствие матрицу n×n, элементами которой являются вероятности переходов pij между вершинами графа, называемую матрицей
    вероятностей переходов:
    11 12 1
    1 21 22 2
    2 1
    2 1
    2
    (
    )
    j
    n
    j
    n
    ij
    i
    i
    ij
    in
    n
    n
    nj
    nn
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P
    P









     











    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    K
    .
    (9)

    54
    Элементы матрицы переходов, означающие вероятности переходов в системе за один шаг, удовлетворяют условиям:
    0 1
    ij
    p


    .
    (10)
    1 1
    n
    ij
    j
    p



    .
    (11)
    Условие (10) выражает ограничение, накладываемое на значение вероятности, а условие (11) означает, что система S обязательно либо переходит из какого-то состояния Si в другое состояние, либо остается в состоянии Si (иначе говоря, события S
    1
    (k),
    S
    2
    (k)
    ,…,S
    i
    (k)
    ,…,S
    n
    (k)
    образуют
    полную группу событий).
    Обычно на графе вероятности перехода системы из одного состояния в то же самое не отмечаются, так как каждая из них дополняет до единицы сумму переходных вероятностей, соответствующих всем стрелкам, исходящим из данного состояния. Например, для графа рис.
    8б значения переходных вероятностей P
    ii будут равны:
    11 12 13 1 (
    )
    P
    P
    P
     

    22 23 24 25 1 (
    )
    P
    P
    P
    P
     


    33 1
    P
    44 45 1
    P
    P
     
    55 53 1
    P
    P
     
    .
    При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы.

    55
    Имея размеченный ГСП (или, что равносильно, матрицу переходных вероятностей) и зная начальное состояние системы, можно найти вероятности состояний р
    1
    (k), р
    2
    (k),... р
    n
    (k) после любого (k-го) шага. Они находятся с помощью следующих рекуррентных соотношений:
    1
    ( )
    (
    1)
    (
    1,..., )
    n
    i
    j
    ji
    j
    p k
    p k
    P
    i
    n





    ,
    (12)
    или в матричной форме
    (k)
    (k-1)
    p =p
    ×P
    ,
    (13)
    где
    p
    (k)
    ,
    p
    (k-1)
    – матрицы-строки вероятностей состояний после k-го и (k-
    1)-го шагов соответственно;
    P– матрица переходных вероятностей.
    Предположим, что в начальный момент (перед первым шагом) система находится в каком-то определенном состоянии, например, S
    m
    Тогда для начального момента (0) будем иметь:
    р1(0) = 0, р2(0) = 0,..., рm(0) = 1,..., рn(0) = 0,
    т.е. вероятности всех состояний равны нулю, кроме вероятности начального состояния S
    m
    , равной единице.
    Найдем вероятности состояний после первого шага. Мы знаем, что перед первым шагом система заведомо находится в состоянии S
    m
    . Значит, за первый шаг она перейдет в состояния S
    1
    , S
    2
    ,..., S
    m
    ,..., S
    n
    с вероятностями
    Pm1, Pm2,..., Pmm,..., Pmn.
    находящимися в m-ой строке матрицы переходных вероятностей.
    Таким образом, вероятности состояний после первого шага будут:
    1 1
    2 2
    (1)
    ,
    (1)
    , ...,
    (1)
    , ...,
    (1)
    m
    m
    m
    mm
    n
    mn
    p
    P
    p
    P
    p
    P
    p
    P




    .
    (14)
    Найдем вероятности состояний после второго шага:
    (2)
    1 2
    (
    (2),
    (2),...,
    (2),...,
    (2))
    i
    n
    p
    p
    p
    p
    p

    .

    56
    Вычислим их по формуле полной вероятности с гипотезами:
     после первого шага система была в состоянии S
    1
    ;
     после первого шага система была в состоянии S
    2
    ;
    ………………………………………………………
     после первого шага система была в состоянии S
    i
    ;
    ………………………………………………………
     после первого шага система была в состоянии S
    n
    Вероятности гипотез известны (14), условные вероятности перехода в состояние S
    i
    – при каждой гипотезе тоже известны и записаны в матрице переходных вероятностей. По формуле полной вероятности получим:
    1 1
    11 2
    21 1
    2 1
    12 2
    22 2
    1 1
    2 2
    1 1
    2 2
    (2)
    (1)
    (1)
    (1)
    (2)
    (1)
    (1)
    (1)
    (2)
    (1)
    (1)
    (1)
    (2)
    (1)
    (1)
    (1)
    n
    n
    n
    n
    i
    i
    i
    n
    ni
    n
    n
    n
    n
    nn
    p
    p
    P
    p
    P
    p
    P
    p
    p
    P
    p
    P
    p
    P
    p
    p
    P
    p
    P
    p
    P
    p
    p
    P
    p
    P
    p
    P


     




     

    



     





     
    
    K
    K
    (15)
    Или n
    i j
    ji j=1
    p (2)=
    p (1)P , (
    1,..., )
    i
    n


    .
    (16)
    Данное выражение может быть записано в векторно-матричной форме:
    (2)
    (1)
    p
    p
    P


    .
    (17)
    В формулах (15) – (16) суммирование распространяется формально на все состояния S
    1
    , S
    2
    ,..., S
    m
    ,..., S
    n
    ; фактически учитывать надо только те из них, для которых переходные вероятности Pij отличны от нуля, т.е. те состояния, из которых может совершиться переход в состояние S
    l
    (или задержка в нем).

    57
    Таким образом, вероятности состояний после второго шага известны. Очевидно, после третьего шага они определяются аналогично:
    1
    (3)
    (2)
    (
    1,..., )
    n
    i
    j
    ji
    j
    p
    p
    P
    i
    n




    ,
    (18) и вообще после k-то шага:
    1
    ( )
    (
    1)
    (
    1,..., )
    n
    i
    j
    ji
    j
    p k
    p k
    P
    i
    n





    ,
    (19)
    или в матричной форме
    ( )
    ( -1)
    k
    k
    p
    p
    P


    .
    (20)
    Таким образом, вероятности p i
    (k)
    состояний после k-го шага определяются рекуррентной формулой (20) через вероятности состояний после (к – 1)-го шага; последние, в свою очередь, – через вероятности состояний после (к – 2)-го шага, и т.д.
    Например, пусть требуется найти вероятность перехода системы из состояния S1 в состояние S2 за 3 шага для графа на рис. 9.
    Рис. 9. Пример ГСП

    58
    Из условия следует, что p
    1
    (0)=1,p
    2
    (0)=0,p
    3
    (0)=0. Находим вероятности состояния после первого шага:
    1
    (1)
    0, 7
    p

    2
    (1)
    0,1
    p

    3
    (1)
    0, 2
    p

    .
    Вероятности состояния после второго шага:
    1 1
    11 2
    21 3
    31
    (2)
    (1)
    (1)
    (1)
    0,7 0,7 0,1 0, 4 0, 2 0, 2 0,57
    p
    p
    p
    p
    p
    p
    p










    2 1
    12 2
    22 3
    32
    (2)
    (1)
    (1)
    (1)
    0,7 0,1 0,1 0,0 0, 2 0,5 0,17
    p
    p
    p
    p
    p
    p
    p










    3 1
    13 2
    23 3
    33
    (2)
    (1)
    (1)
    (1)
    0,7 0, 2 0,1 0,6 0, 2 0,3 0, 26
    p
    p
    p
    p
    p
    p
    p










    .
    Вероятность состояния S2 после третьего шага P
    2
    (3)
    :
    2 1
    12 2
    22 3
    32
    (3)
    (2)
    (2)
    (2)
    0,57 0,1 0,17 0, 0 0, 26 0,5 0,187
    p
    p
    p
    p
    p
    p
    p










    .
    Если обозначить через P
    (m)
    матрицу, элементами которой являются вероятности переходов из Si в Sj за m шагов p ij
    (m)
    , то справедлива формула:
    ( )
    m
    m
    P
    P

    ,
    (21)
    где
    1   2   3   4   5   6   7   8   9   ...   13


    написать администратору сайта