- •Набережные Челны 1999
- •2. Теория массового обслуживания
- •2.1 Задачи теории массового обслуживания
- •2.2. Классификация систем массового обслуживания и их основные характеристики
- •2.4. Многоканальная смо с отказами
- •2.5. Одноканальная смо с ожиданием
- •2.8. Многоканальная смо с ожиданием
- •2.9. Смо с ограниченным временем ожидания
- •2.10. Замкнутые системы массового обслуживания
- •2.11. Системы массового обслуживния с не пуассоновскими потоками событий
- •3.3. Оценка количества испытаний,
- •3.4. Генерирование, равномерно
- •3.6. Имитация случайных величин
- •3.7. Имитация случайных потоков
- •3.8. Имитация процессов функционирования
Министерство образования РФ
Камский политехнический институт
И.Х.Садыков
Математическое моделирование систем массового обслуживания
Учебное пособие
Набережные Челны 1999
УДК 519.22
С 14
И. X. Садыков. Математическое моделирование систем массового обслуживания: Учебное пособие для студентов специальности 2102,1502 по разделу "Модели систем массового обслуживания" дисциплин "Исследование операций" и "Математическое моделирование". Набережные Челны: Изд-во КамПИ, 1999. 115с.
ISBN 5-230-29436-1
Ил. 31; Библиогр. 10 назв.
Рецензент кафедра прикладной математики Казанского государственного технического университета.
Печатается по решению научно-методического совета Камского политехнического института от 14 декабря 1999 года
ISBN 5-230-29436-1
© Камский политехнический
институт, 1999 год © Садыков И. X., 1999 год
1. МОДЕЛИРОВАНИЕ ОПЕРАЦИИ ПО СХЕМЕ МАРКОВСКИХ СЛУЧАЙНЫХ ПРОЦЕССОВ
1.1. МАРКОВСКИЙ СЛУЧАЙНЫЙ ПРОЦЕСС С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ
Многие операции, которые приходится анализировать под углом зрения выбора оптимального решения, развиваются как случайные процессы, ход и исход которых зависят от ряда случайных факторов, сопровождающих эти операции.
Для того чтобы вычислить числовые параметры, характеризующие эффективность таких операций, нужно построить некоторую вероятностную модель явления, учитывающую сопровождающие его случайные факторы.
Для математического описания многих операций, развивающихся в форме случайного процесса, может быть с успехом применен математический аппарат, разработанный в теории вероятностей для так называемых марковских случайных процессов.
Поясним понятие марковского случайного процесса.
Пусть имеется некоторая система S , состояние которой меняется с течением времени (под системой S может пониматься различное техническое устройство, ремонтная мастерская, заправочная станция, вычислительная машина и т.д.).
Если состояние системы S меняется во времени случайным, заранее непредсказуемым образом, говорят, что в системе S протекает случайный процесс.
Примерами случайных процессов могут быть:
процесс функционирования ЭВМ;
процесс обслуживания клиентов парикмахерской, ремонтной мастерской или заправочной станцией;
процесс выполнения плана снабжения группы предприятий и т.д.
Конкретное протекание каждого из таких процесс зависит от ряда случайных, заранее непредсказуемых факторов, таких как:
поступление заказов на ЭВМ, вид этих заказов и случайные выходы ЭВМ из строя;
случайный характер потока заявок (требований), поступающих со стороны клиентов;
случайные перебои в выполнении плана снабжения и т.д.
Случайный процесс, протекающий в системе S, называется марковским процессом (или "процессом без последействия"), если он обладает следующим свойством.
Для каждого момента времени to вероятность любого состояния системы в будущем (при
t >to) зависит только от ее состояния в настоящем (при t — t0) и независит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлым).
Другими словами, в марковском случайном процессе будущее развитие его зависит только от настоящего состояния и не зависит от "предистории" процесса.
Рассмотрим пример. Пусть система S представляет собой техническое устройство, которое уже проработало некоторое время, соответственным образом "износилось" и пришло в некоторое состояние, характеризующееся определенной степенью изношенности S . Нас интересует, как будет работать система в будущем. Ясно, что, по крайней мере, в первом приближении характеристики работы системы в будущем (частота отказов, потребность в ремонте) зависят от состояния устройства в настоящий момент и не зависят от того, когда и как устройство достигло своего настоящего состояния.
На практике часто встречаются случайные процессы, которые, с той или другой степенью приближения, можно считать марковскими.
Теория марковских случайных процессов является в настоящее время очень обширным разделом теории вероятностей с широким спектром различных приложений.
Марковские случайные процессы делятся на классы по некоторым признакам, в зависимости от того, как и в какие моменты времени система S может менять свои состояния.
Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы:
S1,S2,S3...
можно перечислить (пронумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.
Кроме процессов с дискретными состояниями, существуют случайные процессы с непрерывными состояниями: для этих процессов характерен постепенный, плавный переход из состояния в состояние. Например, процесс изменения напряжения в осветительной сети представляет собой случайный процесс с непрерывными состояниями.
Здесь мы будем рассматривать только случайные процессы с дискретными состояниями.
При анализе случайных процессов с дискретными состояниями очень удобно пользоваться геометрической схемой - так называемым графом состояний. Граф состояний геометрически изображает возможные переходы из состояния в состояние.
Пусть имеется система S с дискретными состояниями:
S1, S2,...Sn.
Будем изображать каждое состояние прямоугольником, а возможные переходы (" перескоки ") из состояния в состояния - стрелками, соединяющими эти прямоугольники (Рис.1).
Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния S1 в S3 только через S2, то стрелками отмечаются только переходы S1 —> S2 и S2 —> S3 , но не S1 —> S3.
Пример 1. Система S- автомашина, которая может находиться в одном из пяти возможных состояний: S1 - исправно работает;
S 2 - неисправна, ожидает осмотра;
S 3 - осматривается;
S 4 -ремонтируется;
S5 - списана.
Граф состояний этой системы показан на Рис. 1
Рис.1
Пример 2. Техническое устройство S состоит из двух узлов: 1 и 2, каждый из которых может в ходе работы устройства отказать (выйти из строя). Построить граф состояний предполагая, что ремонт узлов в ходе процесса не производится.
Пример 3. Техническое устройство S состоит из двух узлов: 1 и 2, каждый из которых может в ходе работы устройства отказать. Отказавший узел немедленно начинает восстанавливаться и обязательно восстановиться. Построить граф состояний.
1.2. МАРКОВСКИЙ ПРОЦЕСС С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ И НЕПРЕРЫВНЫМ ВРЕМЕНЕМ. УРАВНЕНИЯ КОЛМОГОРОВА ДЛЯ ВЕРОЯТНОСТЕЙ СОСТОЯНИЙ
Способы математического описания марковского случайного процесса, протекающего в системе с дискретными со стояниями, зависят от того, в какие моменты времени - заранее известные или случайные - могут происходить переходы ("перескоки") системы из состояния в состояние.
Случайный процесс называется процессом с дискретным временем, если переходы системы из состояния в состояние возможны только в строго определенные, заранее
фиксированные моменты времени: t1,t2,.... В промежутке времени между этими моментами система S сохраняет свое состояние.
Здесь марковский процесс с дискретным временем не рассматривается.
На практике значительно чаще встречаются ситуации, когда переходы системы из состояния в состояние происходят не в фиксированные, а в случайные моменты времени, которые заранее указать невозможно - переход может осуществиться, вообще говоря, в любой момент. Например, выход из строя (отказ) любого элемента аппаратуры может произойти в любой момент времени; окончание ремонта (восстановление) этого элемента также может произойти в заранее не фиксированный момент и т.д.
Для описания таких процессов в ряде случаев может быть с успехом применена схема марковского случайного процесса с дискретными состояниями и непрерывным временем, который для кратности называется непрерывной цепью Маркова.
Покажем, как выражаются вероятности состояний для такого процесса.
Пусть имеется ряд дискретных состояний:
S1,S2,...,Sn;
переход (перескок) системы S из состояния в состояние может осуществляться в любой момент времени.
Обозначим Pt (t) - вероятность того, что в момент t
система S будет находиться в состоянии Si (i = 1,п) . Очевидно, для любого момента t сумма вероятностей состояний равна единице:
так как события, состоящие в том, что в момент t система находится в состояниях S1,S2,...,Sn,
несовместны и образуют полную группу.
Поставим задачу - определить для любого t вероятности состояний:
P1(t),P2(t),...,Pn(t)
Для того, чтобы найти эти вероятности, необходимо знать характеристики процесса перехода системы из одного состояния в другое состояние.
Рис.2
Пусть система S в момент времени t находится в состоянии Si. Рассмотрим элементарный промежуток времени Δt, примыкающий к моменту t (Рис,2).
Назовем плотностью вероятности перехода λij предел отношения вероятности перехода системы за время At из состояния Si в состояние Sj к длине промежутка Δt:
(1.2)
где Pij(Δt) - вероятность того, что система, находившаяся в момент t в состоянии Si, за время Δt перейдет из него в состояние Sj (плотность вероятностей перехода определяется только для j ≠ i).
Из формулы (1.2) следует, что при малом Δt вероятность перехода Pij(Δt) (с точностью до бесконечно малых высших порядков) равна λij(Δt), т.е.
Если все плотности вероятностей перехода λij не зависят от t, марковский процесс называется однородным; если эти плотности представляют собой какие-то функции времени λij(Δt), процесс называется неоднородным. При пользовании сокращенным названием "непрерывная марковская цепь" мы также будем различать однородные и неоднородные цепи.
Предположим, что нам известны плотности вероятностей перехода λij для всех пар состояний Si, Sj ,.
Построим граф состояний системы S и около каждой стрелки проставим соответствующую плотность вероятности перехода (Рис.3).
Рис.3
Такой граф, с проставленными у стрелок плотностями вероятностей перехода, называют размеченным графом состояний.
Оказывается, зная размеченный граф состояний, можно определить вероятности состояний:
P1(t),P2(t),...,Pn(t) (1.3)
как функции времени. А именно, эти вероятности удовлетворяют определенного вида дифференциальным уравнениям, так называемым уравнениям Колмогорова. Решив эти уравнения, получим вероятности (1.3).
Продемонстрируем методику вывода уравнений Колмогорова для вероятностей состояний на конкретном примере.
Пусть система S имеет четыре возможных состояния:
S1, S2, S3, S4;
размеченный граф состояний системы показан на рис.4.
Поставим себе задачу: найти одну из вероятностей состояний, например, Р1 (t). Это есть вероятность того, что в момент t система будет находиться в состоянии S1.
Придадим t малое приращение Δt и найдем вероятность того, что в момент t + Δt система будет находиться состоянии S1.
Это событие может произойти двумя способами:
- в момент t система уже была в состоянии S1, а за время Δt не вышла из этого состояния или
- в момент t система уже была в состоянии S 3, а за время Δt перешла из него в S1.
Вероятность первого варианта найдем как произведение вероятности Р1 (t) того, что в момент t система была в состоянии S1, на условную вероятность того, что, будучи в состоянии S1, система за время Δt не перейдет из него в S2 . Эта условная вероятность (с точностью до бесконечно малых высших порядков) равна 1-λ12Δt.
Аналогично, вероятность второго варианта равна вероятности того, что в момент t система была в состоянии S 3, умноженной на условную вероятность перехода за время Δt в состояние S1:
P3(t)∙λ31Δt
Применяя правило сложения вероятностей, получим:
P1(t + Δt) = P1(t)( 1-λ12Δt ) + P3(t) ∙λ31Δt
Раскроем скобки в первой части, перенесем Р1 (t) в левую и разделим обе части равенства на Δt; получим:
Перейдем к пределу при Δt стремление к нулю:
Левая часть есть не что иное, как производная функции P1(t):
(1.4)
Таким образом, выведено дифференциальное уравнение, которому должна удовлетворять функция Р1(t).
Аналогичные дифференциальные уравнения могут быть выведены и для остальных вероятностей состояния:
P2(t), P3(t), P4(t).
Рассмотрим второе состояние S2 и найдем P2(t + Δt) - вероятность того, что в момент (t + Δt) система S будет находиться в состоянии S2. Это событие может произойти следующими способами:
- в момент t система уже была в состоянии S2 , а за время Δt не перешла из него ни в S3, ни в S4;
или
- в момент t система уже была в состоянии S1, а за время Δt перешла из него в S2 ;
или
- в момент t система уже была в состоянии S4 , а за время Δt перешла из него в S2 ;
Вероятность первого варианта вычисляется так: P2(t) умножается на условную вероятность того, что система за Δt не перейдет ни в S3, ни в S4 .
Так как события, состоящие в переходе за время Δt из S2 в S3 и из S2 в S4, несовместны, то вероятность того, что осуществится один из этих переходов, равна сумма их вероятностей, т.е. λ23Δt + λ24Δt (с точностью до бесконечно малых высших порядков). Вероятность того, что не осуществится ни один из этих переходов, равна
1 – λ23Δt – λ24Δt. Отсюда вероятность первого варианта:
P2(t)( 1 - λ23Δt - λ24 Δt )
Прибавляя сюда вероятности второго и третьего вариантов, получим:
Перенося Р2 (t) в левую часть, деля на Δt и переходя к пределу, получим дифференциальное уравнение для Р2(t):
(1.5)
Рассуждая аналогично для состояний S3, S4, получим в результате систему дифференциальных уравнений, составленных по типу (1.4) и (1.5). Отбросив в них для кратности аргумент у функций Р1,Р2,Р3,Р4 и перепишем эту систему в виде:
(1.6)
Это уравнения для вероятностей состояний и называются уравнениями Колмогорова.
Интегрирование этой системы уравнений даст нам искомые вероятности состояний как функции времени. Начальные условия берутся в зависимости от того, какого было начальное состояние системы S. Например, если в начальный момент времени (при t = 0) система S находилась в состоянии S1, то надо принять начальные условия:
при t = 0 Р, =1, Р2 =Р3 =Р4 =0.
Заметим, что всех четырех уравнений для Р1, Р2, Р3, Р4 можно было бы и не писать; действительно,
Р1 + Р2 + Р3 + Р4 =1 для всех t, и любую из вероятностей Pi (i = 1,4) можно выразить через три остальные. Например, Р4 можно выразить через Р1,Р2,Р3 в виде
Р4 = 1-(Р1+Р2+Р3)
и поставить в остальные уравнения. Тогда специального уравнения для вероятности Р4 можно и не писать. Однако в дальнейшем будет удобнее пользоваться полной системой уравнений типа (1.6).
Обратим внимание на структуру уравнений (1.6). Все они построены по вполне определенному правилу, которое можно сформулировать следующим образом.
В левой части каждого уравнения стоит производная вероятности состояния, а правая часть содержит столько членов, сколько стрелок связано с данным состоянием. Если стрелка направлена из состояния, соответствующий член имеет знак "минус", если в состояние — знак "плюс". Каждый член равен произведению плотности вероятности перехода, соответствующей данной стрелке, умноженной на вероятность того состояния, из которого исходит стрелка.
Это правило составления дифференциальных уравнений для вероятностей состояний является общим и справедливо для любой непрерывной марковской цепи; с его помощью можно совершенно механически, без всяких рассуждений, записывать дифференциальные уравнения для вероятностей состояний непосредственно по размеченному графу состояний.
Пример. Размеченный граф состояний S имеет вид, показанный на рис.5. Написать систему дифференциальных уравнений Колмогорова и начальные условия для решения этой системы, если известно, что в начальный момент система
находится в состоянии S1.
Решение. Система уравнений Колмогорова имеет вид:
Начальные условия при t=0 P1=1, P2 = P3 = P4 = 0.
Рис.5
1.3. ПОТОК СОБЫТИЙ. ПРОСТЕЙШИЙ ПОТОК И ЕГО СВОЙСТВА
При рассмотрении случайных процессов, протекающих в системах с дискретными состояниями и непрерывным временем, часто приходится встречаться с так называемыми "потоками событий".
Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то, вообще говоря, случайные моменты времени.
Примерами могут быть:
поток вызовов на телефонной станции;
поток включений приборов в бытовой электросети;
поток автомашин, прибывающий на автозаправочную станцию;
поток заявок на обслуживание ремонтной мастерской;
поток неисправностей (сбоев) ЭВМ, и т.д.
При рассмотрении процессов, протекающих в системе с дискретными состояниями и непрерывным временем, часто бывает удобно представлять себе процесс так, как будто переходы системы из состояния в состояние происходят под действием каких-то потоков событий (поток вызовов, поток неисправностей, поток заявок на обслуживание, поток посетителей и т.д.). Поэтому имеет смысл рассмотреть подробнее потоки событий и их свойства.
Рис.6
Будем изображать поток событий последовательностью точек на оси времени t (рис.6). Пользуясь таким изображением, не надо забывать, что положение каждой точки на оси абсцисс случайно.
Поток событий называется регулярным, если события следуют одно за другим через строго определенные промежутки времени. Такой поток сравнительно редко встречается на практике, но представляет определенный интерес как предельный случай.
При исследовании операций чаще приходится встречаться с потоками событий, для которых и моменты поступления событий и промежутки времени между ними случайны.
Здесь рассмотрим потоки событий, обладающие некоторыми особо простыми свойствами. Для этого введем ряд определений.
1 .Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени длиной т (рис.7) зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.
2.Поток событий называется потоком без последействия, если для любых непересекающихся участков времени число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой (или другие, если рассматривается больше двух участков).
З.Поток событий называется ординарным, если вероятность попадания на элементарный (малый) участок двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события.
Рассмотрим подробнее эти три свойства потоков.
Стационарность потока означает то, что вероятностные характеристики такого потока не должны меняться в зависимости от времени. В частности, так называемая интенсивность (или "плотность") потока событий - среднее число появления события в единицу времени - для стационарного потока должна остаться постоянной. Это, разумеется, не значит, что фактическое число событий, появляющихся в единицу времени, всегда постоянно. В конкретной реализации поток может иметь местные сгущения и разрежения. Важно, что для стационарного потока они не носят закономерного характера, а среднее число событий, попадающих на единичный участок времени, остается постоянным для всего рассматриваемого периода.
Отсутствие последействия в потоке означает, что события, образующие поток, появляются в последовательные моменты времени независимо друг от друга. Например, поток пассажиров, входящих на станцию метро, можно считать потоком без последействия, потому что причины, обусловившие приход отдельного пассажира именно в данный момент, а не в другой, как правило, не связаны с аналогичными причинами для других пассажиров.
Поток автомашин, прибывающий на заправочную станцию, обладает свойством отсутствия последействия.
Ординарность потока означает, что события в потоке приходят поодиночке, а не парами, тройками и т.д.
Рассмотрим поток событий, обладающий всеми тремя свойствами: стационарный, без последействия, ординарный. Такой поток называется простейшим (или стационарным пуассоновским) потоком.
Простейший поток играет среди других потоков особую роль. А именно, можно доказать, что при суперпозиции (взаимном наложении) достаточно большого числа потоков, обладающих последействием (лишь бы они были стационарны и ординарны), образуется суммарный поток, который можно считать простейшим, и тем точнее, чем большее число потоков складывается.
Если поток событий не имеет последействия, ординарен, но не стационарен, он называется нестационарным пуассоновским потоком. В таком потоке интенсивность λ (среднее число событий в единицу времени) зависит от времени;
λ=λ(t)
тогда как для простейшего потока
λ = const .
Пуассоновский поток событий (как стационарный, так и нестационарный) тесно связан с известным распределением Пуассона.
А именно, число событий потока, попадающих на любой участок, распределено по закону Пуассона.
Рис.7
Поясним, что это означает. Рассмотрим на оси Ot, где наблюдается поток событий, некоторый участок времени длины τ (рис. 7 ) , начинающийся в момент t0 и заканчивающийся в момент tQ + τ . Нетрудно доказать (доказательство дается во всех курсах-теории вероятностей), что вероятность попадания на этот участок ровно т событий выражается формулой:
(1.7)
где а - среднее число событий, приходящееся на участок τ ,
Для стационарного (простейшего) пуассоновского потока величина а равна интенсивности потока, умноженной на длину интервала
a = λ τ,
т.е. не зависит от того, где на оси t начинается τ . Для нестационарного пуассоновского потока величина а выражается формулой:
и, значит, зависит от того, в какой точке t0 начинается участок т .
Рассмотрим на оси t простейший поток событий с интенсивностью λ (рис.8). Нас будет интересовать интервал времени T между соседними событиями в этом потоке. Очевидно, Т есть величина случайная, найдем ее закон распределения. Сначала найдем функцию распределения: F(t)= Р(Т < t) , т.е. вероятность того, что величина Т примет значение, меньшее, чем t.
Отложим от начала интервала Т (точки t0) отрезок t и найдем вероятность того, что интервал Т будет меньше t. Для этого нужно, чтобы на участок длины t, примыкающий к точке t0, попало хотя бы одно событие потока. Вычислим вероятность этого F(t) через вероятность противоположного события
( на участок t не попадает ни одного события потока);
F(t) = 1-Pt.
Вероятность Ро найдем по формуле (1.7), полагая т = 0 :
откуда функция распределения величины Т будет:
F(t) = 1- (t>0) (1.8)
Чтобы найти плотность распределения f(f) случайной величины Т, продифференцируем выражение (1.8) по t:
f(t) =λ (t>0). (1.9)
Закон распределения с плотностью (1.9) называется показательным (или экспоненциальным). Величина λ называется параметром показательного закона.
Найдем числовые характеристики случайной величины Т-математическое ожидание mt и дисперсию Dt. Имеем:
Интегрируя по частям, получим:
(1.10)
Дисперсию величины Т найдем через второй начальный момент
о
откуда, снова интегрируя по частям, получим:
(1.11)
Найдем среднее квадратическое отклонение случайной величины Т:
Итак, для показательного распределения математическое ожидание и среднее квадратическое отклонение равны друг другу и обратны параметру λ.
Т аким образом, исследуя структуру простейшего потока событий, пришли к заключению: промежуток времени Т между соседними событиями в простейшем потоке распределен по показательному закону ; его среднее значение и среднее квадратическое отклонение равны ,где λ - интенсивность потока.
Для нестационарного Пуассоновского потока закон распределения промежутка Т уже не будет показательным; вид этого закона будет зависеть, во-первых, от того, где на оси t расположено первое из событий, и, во-вторых, от вида зависимости λ(t), характеризующей переменную интенсивность потока. Однако если λ(t) меняется сравнительно медленно и его изменение за время между двумя событиями невелико, то закон распределения промежутка времени между событиями можно приближенно считать показательным (1.9), полагая в этой формуле величину λ равной среднему значению λ(t) на том участке, который нас интересует.
Выведем выражение для так называемого " элемента вероятности появления события".
Рассмотрим на оси t простейший поток событий с интенсивностью λ и элементарный участок Δt, прилежащий в точке t (рис.9).
Рис.9
Найдем вероятность того, что на участке At появится какое-то событие потока, т.е. участок не будет "пуст". Так как поток ординарен, вероятностью появления на участке Δt более чем одного события можно пренебречь. Обозначим P0(Δt) вероятность того, что на участке Δt не будет события, а Р1 (Δt) - вероятность того, что на нем появится одно событие. В силу ординарности потока
а вероятность P0(Δt) вычисляем по формуле (1.7):
откуда
Разлагая в ряд по степеням λΔt и пренебрегая величинами высшего порядка малости, подучим:
Отсюда
(1.12)
т.е. вероятность появления на элементарном участке времени Δt какого-то события потока приближенно равна λΔt, где λ -интенсивность потока. Эту вероятность будем называть " элементом вероятности появления события".
Очевидно, такая же формула будет справедлива и для нестационарного пуассоновского потока, с той разницей, что величину λ нужно брать равной ее значению в той точке t, к которой примыкает участок Δt:
1.4 ПУАССОНОВСКИЕ ПОТОКИ СОБЫТИЙ И НЕПРЕРЫВНЫЕ МАРКОВСКИЕ ЦЕПИ
Рассмотрим некоторую физическую систему S с дискретными состояниями S1, S2,...,Sn , которая переходит из состояния в состояние под влиянием каких-то случайных событий, например, вызовы па телефонной станции, выходы из строя (отказы) элементов аппаратуры, прибытие автомашин для заправки в автозаправочную станцию и т.д.
Будем себе это представлять так, будто события, переводящие систему из состояния в состояние, представляют собой какие-то потоки событий (потоки вызовов, потоки отказов, потоки прибытия автомашин в заправочную станцию и т.д.)
Пусть система S в момент t находится в состоянии Si и может перейти из него в состояние Sj. под влиянием какого-то пуассоновского потока событий с интенсивностью λij : как только появляется первое событие этого потока, система мгновенно переходит (перескакивает) из Si в Sj . Вероятность этого перехода за элементарный промежуток времени Δt (элемент вероятности перехода) равна λij Δt.
Таким образом, плотность вероятности перехода А - в непрерывной цепи Маркова представляет собой не что иное как интенсивностьпотока событий, переводящего систему по соответствующей стрелке.
Если все потоки событий, переводящие систему S из состояния в состояние, пуассоновские (стационарные или нестационарные - безразлично), то процесс протекающий в системе, будет марковским. Действительно, пуассоновский поток обладает отсутствием последействия,, поэтому, при заданном состоянии системы в данный момент ее переходы в другие состояния в будущем обусловлены только появлением каких-то событий в пуассоновских потоках, а вероятности появления этих событий не зависят от "предыстории" процесса.
В дальнейшем, рассматривая марковские процессы в системах с дискретными состояниями и непрерывным временем, нам удобно будет во всех случаях рассматривать переходы системы из состояния в состояние как происходящие под влиянием каких-то потоков событий, хотя бы в действительности эти события были единичными. Например, работающее техническое устройство мы будем рассматривать как находящееся под действием потока отказов, хотя фактически оно может только один раз.
Итак, рассматривается система, S, в которой переходы из состояния в состояние происходят под действием пуассоновских потоков событий с определенными интенсивностями. Проставим эти интенсивности (плотности вероятностей переходов) на графе состояний системы у соответствующих стрелок. Получим размеченный граф состояний, по которому, пользуясь правилом, сформулированном в 1.2, можно сразу записать дифференциальные уравнения Колмогорова для вероятностей состояний.
Пример. Техническая система S состоит из двух узлов: I и II; каждый из них независимо от другого может отказывать (выходить из строя). Поток отказов первого узла- пуассоновского, с интенсивностью λ1, второго - также пуассоновский, с интенсивностью λ11, . Каждый узел сразу после отказа начинает ремонтироваться (восстанавливаться). Поток восстановлений (окончаний ремонта ремонтируемого узла) для обоих узлов - пуассоновский с интенсивностью λ .
Составить граф состояний системы и написать уравнения Колмогорова для вероятностей состояний. Определить, при каких начальных условиях нужно решать эти уравнения, если в начальный момент (t = 0 ) система работает исправно.
Решение, Состояния системы:
S11- оба узла исправны,
S21 - первый узел ремонтируется, второй исправен,
S12 - первый узел исправен, второй ремонтируется,
S22 - оба узла ремонтируются.
Размеченный граф состояний системы показан на рис. 10.
Рис. 10
Интенсивности потоков событий на рис. 10 проставлены из следующих соображений. Если система S находится в состоянии S11, то на нее действуют два потока событий: поток неисправностей узла I с интенсивностью λ1 переводящий ее в состояние S21 , и поток неисправностей узла II с интенсивностью λ22 , переводящий ее в S22. Пусть теперь система находится в состоянии S21 (узел I ремонтируется, узел II - исправен). Из этого состояния система может, во-первых, вернуться в S11 (это происходит под действием потока восстановлений с интенсивностью λ ); во-вторых, - перейти в состояние S22 (когда ремонт узла 1 еще не закончен, а узел II тем временем вышел из строя); этот переход происходит под действием потока отказов узла II с интенсивностью λ11 . Интенсивности потоков у остальных стрелок проставляются аналогично.
Обозначим вероятности состояний P11, P21, P12 и P22 пользуясь правилом, сформулированным в 1.2, запишем уравнения Колмогорова для вероятностей состояний:
(1.13)
Начальные условия, при которых нужно решать эту систему:
при t=0 P11=1, P12 = P21 = P22 =0.
Заметим, что пользуюсь условием
P11 + P21 + P21 + P22 =1,
можно было бы уменьшить число уравнений на одно. Действительно, любую из вероятностей Р11,Р21,Р21,Р22 можно выразить через остальные и подставить в уравнение (1.13), а уравнение, содержащее в левой части производную этой вероятности - отбросить.
Заметим, кроме того, что уравнения (1.13) справедливы как для постоянных интенсивностей пуассоновских потоков λ1, λ11, λ так и для переменных:
λ1 = λ1(t), λ11= λ11(t), λ = λ(t).
1.5. ПРЕДЕЛЬНЫЕ ВЕРОЯТНОСТИ СОСТОЯНИЙ
Пусть имеется физическая система S с дискретными состояниями:
S1, S2,...,Sn,
в которой протекает марковский случайный процесс с непрерывным временем (непрерывная цепь Маркова).
Предположим, что все интенсивности потоков событий, переводящих систему из состояния в состояние, постоянны:
λij= const ,
другими словами, все потоки событий - простейшие (стационарные пуассоновские) потоки.
Записав систему дифференциальных уравнений Колмогорова для вероятностей состояний и проинтегрировав эти уравнения при заданных начальных условиях, получим вероятности состояний, как функции времени, т.е. п функций:
P1(t), P2(t),...,Pn(t),
при любом t дающих в сумме единицу:
Поставим следующий вопрос: что будет происходить с системой S при . Будут ли функции Р1 (t), Р2 (t),..., Рп(t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными вероятностями состояний.
Можно доказать следующее общее положение. Если число состояний системы S конечно и из каждого состояния можно перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы.
На рис.11 показан граф состояний, удовлетворяющий поставленному условию: из любого состояния система может рано или поздно перейти в любое другое. Напротив, для системы, граф состояний которой показан на рис.12, условие не выполнено. Очевидно, что если начальное состояние такой системы S1 , то, например, состояние S6 при может быть достигнуто, а если начальное состояние S2 – не может.
Предположим, что поставленное условие выполнено, и предельные вероятности существуют:
П редельные вероятности будем обозначать теми же буквами что и сами вероятности состояний, разумея под ними на этот раз не переменные величины (функции времени), а постоянные числа.
Очевидно, предельные вероятности состояний, так же как и допредельные, в сумме должны давать единицу:
Таким образом, при в системе S устанавливается некоторый предельный стационарный режим: он состоит в том, что система случайным образом меняет свои состояния, но вероятность каждого из них не зависит от времени: каждое из состояний осуществляется с некоторой постоянной вероятностью. Каков смысл этой вероятности? Она представляет собой не что иное, как среднее относительное время пребывания системы в данном состоянии. Например, если у системы S три возможных состояния: S1, S2 и S3, причем их предельные вероятности равны 0,2, 0,3, и 0,5, это означает, что после перехода к установившемуся режиму система S в среднем две десятых времени будет находиться в состоянии S1, три десятых – в состоянии S2 и половину времени - в состоянии S3.
Возникает вопрос: как вычислить предельные вероятности состояний Р1 Р2,...,Рп? Оказывается, для этого в системе дифференциальных уравнений Колмогорова, описывающих вероятности состояний, нужно положить все левые части (производные) равными нулю.
Действительно, в предельном (установившемся) режиме все вероятности состояний постоянны, значит их производные равны нулю.
Е сли все левые части уравнений Колмогорова для вероятностей состояний положить равными нулю, то система дифференциальных уравнений превратится в систему линейных алгебраических уравнений. Совместно с условием
(1.15)
(так называемым " нормировочным условием") эти уравнения дают возможность вычислить все предельные вероятности
Изложенный способ составления алгебраических уравнений для предельных вероятностей состояний сводился к следующему: сперва написать дифференциальные уравнения, а затем положить в них левые части равными нулю. Однако можно записать алгебраические уравнения для предельных вероятностей и непосредственно, не проходя через этап дифференциальных уравнений.
Чтобы в дальнейшем сразу же писать такие алгебраические уравнения, полезно запомнить следующее мнемоническое правило: " что втекает, то и вытекает", то есть для каждого состояния сумма членов, соответствующих входящим стрелкам, равна сумме членов, соответствующих выходящим; каждый член равен интенсивности потока событий, переводящего систему по данной стрелке, умноженной на вероятность того состояния, из которого выходит стрелка.
В дальнейшем мы во всех случаях будем пользоваться именно этим кратчайшим способом записи уравнений для предельных вероятностей.
Пример 1. Граф состояний системы показан на рис. 13. Написать алгебраические уравнения для предельных вероятностей состояний.
Решение. Используя вышеописанное правило, напишем алгебраические уравнения для предельных вероятностей состояний:
Пример 2. Написать алгебраические уравнения для предельных вероятностей состояний системы S, граф состояний которой дан на рис.14. Решить эти уравнения.
Решение. Пишем алгебраические уравнения для предельных вероятностей состояний:
(1.16)
Уравнения (1.16) - так называемые однородные уравнения (без свободного члена).. Как известно из алгебры, эти уравнения определяют величины Pi (i = 1,4) только с точностью до постоянного множителя. Нормировочное условие
P1+P2+P3+P4=1
совместно с уравнениями (1.16) дает возможность найти все неизвестные вероятности.
Действительно, выразим из (1.16) все неизвестные вероятности через одну из них, например, через Р1. Из первого уравнения:
Р3= 5P1
Подставляя во второе уравнение, получим:
Р2 = 2P1+10P1=12P1
Четвертое уравнение дает:
Подставляя все эти выражения вместо Р2 , Р3 , Р4 в нормировочное условие, получим
P1+12P1+5P1+6P1=1
Отсюда
24P1=1,
Таким образом, предельные вероятности состояний получены, они равны:
Это значит, что в предельном, установившемся режиме система S будет проводить в состоянии S1 в среднем одну двадцать четвертую часть времени, в состоянии S2 -половину времени, в состоянии S3, -пять двадцать четвертых и в состоянии S4 - одну четверть времени.
Заметим, что решая эту задачу, мы совсем не пользовались одним из уравнений (1.16) - третьим. Нетрудно убедиться, что оно является следствием трех остальных: складывая все четыре уравнения, получим тождественный нуль. С равным успехом, решая систему, могли бы отбросить любое из четырех уравнений (1.16).
1.6. ПРОЦЕСС "ГИБЕЛИ И РАЗМНОЖЕНИЯ"
В предыдущем параграфе убедились, что зная размеченный граф состояний системы, можно сразу написать алгебраические уравнения для предельных вероятностей состояний. Таким образом, если две непрерывные цепи Маркова имеют одинаковые графы состояний и различаются только значениями интенсивностей λij , то нет надобности находить предельные вероятности состояний для каждого из графов в отдельности: достаточно составить и решить в буквенном виде уравнения для одного из них, а затем подставить в место λij соответствующие значения. Для многих часто встречающихся форм графов линейные уравнения легко решаются в буквенном виде.
Здесь познакомимся с одной очень типичной схемой непрерывных марковских цепей - так называемой "схемой гибели и размножения".
Марковская непрерывная цепь называется "процессом гибели и размножения", если ее граф состояний имеет вид, представленный на рис.15, т.е. все состояния можно вытянуть в одну цепочку, в которой каждое из средних состояний (S2,...,Sn-1) связано прямой и обратной связью с каждым из соседних состояний, а крайние состояния (S1,Sn) только с одним соседним состоянием.
Схема гибели и размножения очень часто встречается в самых разнообразных практических задачах; поэтому имеет смысл заранее рассмотреть эту схему в общем виде и решить соответствующую систему алгебраических уравнений с тем, чтобы в дальнейшем, встречаясь с конкретными процессами, протекающими по такой схеме, не решать задачу в каждый раз заново, а пользоваться уже готовым решением.
Итак, рассмотрим случайный процесс гибели и размножения с графом состояний, представленным на рис.15
Напишем алгебраические уравнения для предельных вероятностей состояний.
Для состояния S1 имеем:
λ21P1=λ21P2 (1.17)
Для второго состояния S2 суммы членов, соответствующих входящим и выходящим стрелкам, равны:
λ23P2+ λ21P2= λ12P1+ λ32P3
Но, в силу (1.17), можно сократить справа и слева равные друг другу члены λ12P1 и λ21Р2 ; получим
λ23P2=λ32P3
и далее, совершенно аналогично
λ34P3=λ43P4
...................
Одним словом, для схемы гибели и размножения члены, соответствующие стоящим друг над другом стрелкам, равны между собой:
λk-1,kPk-1=λk,k-1Pk ,где k=2,n (1.18)
Итак, предельные вероятности состояний Pi (i = 1, п) в любой схеме гибели и размножения удовлетворяют уравнениям:
λ12P1=λ21P2,
λ23P2=λ32P3,
...…...……. (1.19)
λk-1,kPk-1=λk,k-1Pk,
........................
λn-1,nPn-1=λn,n-1Pn.
и нормировочному условию:
P1+P2+...+Pn=1 (1.20)
Будем решать эту систему следующим образом: из первого уравнения (1.19) выразим Р2 :
(1.21)
и з второго, с учетом (1.21), получим:
(1.22)
из третьего, с учетом (1.22):
и вообще
(1.23)
Обратим внимание на структуру формулы (1.23). В числителе стоит произведение всех плотностей вероятности перехода (интенсивностей) λij, состоящих у стрелок, направленных слева направо, с начала и вплоть до той, которая идет в состояние Sk ; в знаменателе - произведение всех интенсивностей λij, стоящих у стрелок, идущих справа налево, опять-таки, с начала и вплоть до стрелки, исходящей из состояния Sk . При k = п в числителе будет стоять произведение интенсивностей λij , стоящих у всех стрелок, идущих слева направо, а в знаменателе - у всех стрелок, идущих справа налево.
Итак, все вероятности Pi (i = 2, п) выражены через Р1. Поставив эти выражения (1.23) в нормировочное условие (1.20), Получим:
откуда
(1.24)
Остальные вероятности Рk (к = 2, п) выражаются через Р1 по формуле (1.23).
Таким образом, задача "гибели и размножения" решена в общем виде: найдены предельные вероятности состояний.
Пример. Прибор состоит из трех узлов; поток отказов-простейший, среднее время безотказной работы каждого узла
равно . Отказавший узел сразу же начинает ремонтироваться; среднее время ремонта (восстановления) узла равно ; закон распределения этого времени показательный (поток восстановлений - простейший). Найти среднюю производительность прибора, если при трех работающих узлах она равна 100%, при двух - 50%, а при одном и менее - прибор вообще не работает.
Решение. Состояние системы нумеруем по числу неисправных узлов:
So - все три узла исправны;
S1 - один узел отказал, два исправны;
S2 - два узла восстанавливаются, один исправен;
S3 - все три узла восстанавливаются.
Разметим граф состояний, т.е. проставим у каждой стрелки соответствующую интенсивность λij (см.рис. 17).
Т ак как поток отказов каждого узла - простейший, то промежуток времени между отказами в этом потоке распределен по показательному закону с параметром ,где - cреднее время безотказной работы узла.
П
S3
Е сли система находится в состоянии S1 , то работают два узла; общий поток отказов имеет интенсивность: Аналогично
П о стрелкам влево систему переводят ремонты (восстановления). Среднее время восстановления узла равно , значит, интенсивность потока восстановлений, действующего на один восстанавливаемый узел, равна .На два узла на три узла -
Эти значения λ12,λ21,λ31 и проставлены на рис. 17 у стрелок, ведущих влево.
П ользуясь полученным выше общим решением задачи гибели и размножения, имеем (ставя Р0 вместо Р1);
или
Пусть заданы конкретные значения:
Средняя производительность прибора в установившемся режиме равна:
ЦИКЛИЧЕСКИЙ ПРОЦЕСС
Марковский случайный процесс, протекающий в системе, называется циклическим, если состояния связаны между собой в кольцо (цикл) с односторонними переходами (рис.18).
λ23P2=λ12P1,
λ34P3=λ23P2,
...…...……. (1.25)
λk-1,kPk-1=λk,k+1Pk,
........................
λn-1,nPn-1=λn1Pn.
λn1Pn=λ12P1
и нормировочное условие
(1.26)
Из уравнений (1.25), отбросив последнее, выразим все вероятности Р2,..,,Рп через Р1:
Подставляя эти выражения в (1.26), получим:
(1.27)
Формулы (1.27), выражающие предельные вероятности состояний для циклического процесса, можно привести к более удобному и наглядному виду, если перейти от интенсивностей λij к средним временам ti пребывания системы (подряд) в состоянии Si (i = 1, п).
Действительно, пусть из состояния Si, как это имеет место в циклической схеме, исходит только одна стрелка.
П усть система S находится в состоянии Si. Найдем математическое ожидание времени Ti, которое она еще пробудет в этом состоянии. Так как процесс - марковский, закон распределения времени Ti не зависит от того, сколько времени система уже пробыла в состоянии Si; значит, он такой же, каким был бы, если бы система только что пришла в состояние Si, т.е. представляет собой не что иное, как показательный закон распределения промежутка времени Т между соседними событиями в простейшем " потоке уходов" системы из состояния Si. Параметр этого закона равен λi,i+1, а среднее время пребывания системы в состоянии Si,. (если она в нем уже находится) равно
Отсюда для всех .
Для i=n получим (в силу цикличности)
Подставляя эти выражения в формулы (1.27), после элементарных преобразований получим
(1.28)
т.е. предельные вероятности состояний в циклической схеме относятся как среднее времени пребывания системы подряд в каждом из состояний.
Пример. Электронный прибор может находиться в одном из следующих состояний:
S1 - исправна, работает;
S2 - неисправна, ведется поиск неисправности;
S3 - неисправность локализована, ведется ремонт;
S4 - ремонт закончен, ведется подготовка к пуску прибора.
Все потоки событий - простейшие. Среднее время безотказной работы (подряд) равно 0,5 (суток). Для ремонта прибор приходится останавливать в среднем на 6 часов. Поиск неисправности длится в среднем 0,5 часа. После окончания ремонта прибор готовится к пуску в среднем 1 час. Необходимо найти предельные вероятности состояний.
Решение. Граф состояний имеет вид циклической схемы (рис.19).
Определим среднее время пребывания прибора подряд в каждом состоянии:
откуда по формуле (1.28):
Таким образом, если процесс сводится к простому циклическому с односторонними переходами, предельные вероятности состояний находятся очень просто: из соотношения средних времен пребывания (подряд) в каждом из состояний.