Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний.

В графе состояний каждой дуге необходимо приписать интенсивность соответствующего перехода из одного состояния в другое.

l - поток отказов.

m - поток «окончаний ремонтов».

 

m₁ l₂

 

l₁ m₂

 

l₂ l₁

 

m₂ m₁

 

Пусть рассматривается система S, имеющая n возможных состояний

S₁, S₂, … S_n.

p_i(t) – вероятность i-го состояния, вероятность того, что в момент t система будет находиться в состоянии S_i.

t

По различному графу состояний можно найти все вероятности p_i(t) как функции времени.

Для этого составляются и решаются уравнения Колмогорова – особого вида дифференциальные уравнения, в которых неизвестными функциями являются вероятности состояний.

Пример построения функций Колмогорова:

 

l₂₁ l₁₃

l₁₂

 

l₃₂

l₂₄ l₄₃

 

S – система, у которой 4 состояния S₁, S₂, S₃, S₄.

Dt – малое приращение времени.

Тогда p₁(t+Dt)= p₁(t)(1-(l₁₂+l₁₃) Dt)+ p₂(t) l₂₁Dt

(l₁₂+l₁₃) Dt– вероятность выхода S за момент время Dt из S₁ в S₂ или S₃ соответственно.

Раскроем скобки, перенесем p₁(t) в левую часть, разделим на Dt:

При Dt–>0 слева получаем в пределе производную:

Аналогично получаем остальные дифференциальные уравнения и записываем их в систему:

Правило составления уравнений Колмогорова:

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

Пусть t->∞. Если существует limp_i(t)=p_i, i= и все пределы не зависят от начального состояния системы. Тогда они называются финальными вероятностями состояний.

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

При t->∞ в системе S устанавливается предельный стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятности уже не зависят от времени. Финальную вероятность состояния S_i можно истолковать как среднее относительное время пребывания системы в этом состоянии.

Т. к. финальные вероятности p₁,p₂,…, p_n постоянны, то левые части уравнений Колмогорова полагаем равными нулю и решаем обычную систему алгебраических уравнений, дополнив ее нормировочным условием

.

Т. к. p₁,p₂,… постоянны, то их производные равны нулю. Поэтому:

Т. к. p₁+p₂+p₃+p₄=1, то можно решать однородное уравнение, найти финальные вероятности состояний системы, которые могут помочь оценить эффективность работы системы.

 

67. Схема гибели и размножения. Функциональные вероятности. Формула Литтла

 

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

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S₁, S₂,..., S_n-1) связано прямой и обратной стрелкой с каждым из соседних состояний — правым и левым, а крайние состояния (S₀, S_n) — только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа,— простейшие (для краткости будем называть и систему S и протекающий в ней процесс — простейшими).

Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состояний (их существование вытекает из того, что из каждого состояния можно перейти в каждое другое, и число состояний конечно). Для первого состояния S₀ имеем:

(8.1)

Для второго состояния S₁:

В силу (8.1) последнее равенство приводится к виду

далее, совершенно аналогично

и вообще

где k принимает все значения от 0 до n. Итак, финальные вероятности р₀, p₁,..., р_n удовлетворяют уравнениям

(8.2)

кроме того, надо учесть нормировочное условие

p₀ + р₁+ р₂+…+ р_n=1 (8.3)

Решим эту систему уравнений. Из первого уравнения (8.2) выразим р₁ через р₀.

(8.4)

Из второго, с учетом (8.4), получим:

(8.5)

из третьего, с учетом (8.5),

(8.6)

и вообще, для любого k (от 1 до N):

(8.7)

Обратим внимание на формулу (8.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S_k), а в знаменателе — произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S_k).

Таким образом, все вероятности состояний p₁, р₂, …, p_n выражены через одну из них (p₀). Подставим эти выражения в нормировочное условие (8.3). Получим, вынося за скобку p₀:

отсюда получим выражение для р₀.

(8. 8)

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р₀ (см. формулы (8.4) — (8.7)). Заметим, что коэффициенты при p₀ в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (8.8). Значит, вычисляя р₀, мы уже нашли все эти коэффициенты.

Полученные формулы очень полезны при решении простейших задач теории массового обслуживания.

Формула Литтла

Рассмотрим СМО произвольного типа: одноканальная, многоканальная, с неограниченной или ограниченной очередью.

С ней связаны два потока заявок, прибывающих в СМО и покидающих СМО.

Если в системе установился предельный стационарный режим, то оба потока имеют одинаковую интенсивность.

X(t) – число заявок, прибывших в СМО до момента t.

Y(t) – число заявок, покинувших СМО до момента t.

Обе функции случайны и меняются скачком (увеличиваются на 1 в моменты прихода или ухода заявок).

Z(t)=X(t)-Y(t) – число заявок, находящихся в СМО.

Пусть T – большой промежуток времени. Для него среднее число заявок, находящихся в СМО:

Интеграл равен сумме прямоугольников, высота которых равна 1, а основание равно времени пребывания в системе соответствующей заявки (первой, второй и т. д.).

Обозначим эти времена t₁, t₂, …

Тогда (1) |:T

- среднее число заявок, пришедших за время T.

W_сист. – среднее время пребывания заявки в системе. Тогда

L_сист=λW_сист, и

- формула Литтла (первая формула).

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

- вторая формула Литтла

L_оч – среднее число заявок в очереди.

W_оч – среднее время пребывания заявки в очереди.

68. Одноканальные СМО с неограниченной очередью.

Пусть потоки обслуживания и поступления заявок стационарны.

λ – интенсивность поступления заявок.

μ – интенсивность обслуживания заявок.

Потоки λ и μ – простейшие.

Граф состояний:

S₀ – канал свободен.

S₁ – канал занят (обслуживает заявку), очереди нет.

S₂ – канал занят, одна заявка в очереди.

S₃ – канал занят, две заявки в очереди.

…

S_k – канал занят, (k-1) заявок стоят в очереди.

…

Теоретически число состояний ничем не ограничено (∞). Таким образом – это схема гибели и размножения с бесконечным числом состояний.

Для такой системы финальные вероятности существуют не всегда (при t->∞ очередь может неограниченно возрастать), а только при r<1, когда система не перегружена.

При <1 ряд сходится.

При >1 ряд расходится и является косвенным доказательством, что финальные вероятности состояний p₀, p₁, …, p_k, … существуют только при <1.

Пусть <1:

Следовательно,

p₀=1-ρ (1)

p₁=ρp₀

p₂=ρ²p₀

_… (2)

p_k=ρ^kp₀,…

Тогда, учитывая (1),

, …,

,…. Самое вероятное число заявок = 0.

Z – случайная величина, характеризующая число заявок в системе, имеет возможные значения с вероятностями

(нулевой член = 0) – среднее число заявок в системе, выраженное через математическое ожидание

Сумма быстро убывает – геометрическая прогрессия с первым членом и знаменателем . Эта сумма равна . ,

По формуле Литтла

Найдем среднее число заявок в очереди

Число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. По правилу сложения математических ожиданий, среднее число заявок в очереди минус (среднее число заявок под обслуживанием) .

X - число заявок под обслуживанием, p^k=p^канала

X
	^k=p0, вероятность того, что канал свободен	, вероятность того, что канал занят

- средне число заявок под обслуживанием.

По формуле Литтла

 

 

70. n-канальные СМО с неограниченной очередью.

- в СМО нет ни одной заявки

- в СМО находится 1 заявка (один канал занят, остальные свободны)

…

- - // - занято, очереди нет

- 1 заявка в очереди

…

- в очереди заявок

Естественное условие существования финальных вероятностей . Если , очередь растет до бесконечности.

Пусть и финальные вероятности существуют.

- бесконечно убывающая геометрическая прогрессия

, ,

Тогда

-среднее число занятых каналов

- среднее число заявок в очереди

Пусть , тогда

- бесконечно убывающая геометрическая прогрессия.

, ,

, ,

 

 

71. n-канальные СМО с отказами.

Задача Эрланга – классическая задача ТМО, возникла из практических нужд телефонии, была решена датским математиком Эрлангом.

Постановка задачи: n – количество каналов связи (линий связи), на которые поступает поток заявок с интенсивностью . Поток обслуживаний имеет интенсивность . Потоки простейшие. Граф состояний соответствует схеме гибели и размножения.

- в СМО нет ни одной заявки

- в СМО находится 1 заявка (один канал занят, остальные свободны)

…

- - // - - // - ( занято, остальные свободны)

- - // - - // - (все каналы заняты)

чтобы из перейти в нужно, чтобы освободился 1 канал, интенсивность

чтобы из перейти в нужно, чтобы закончил обслуживание или первый канал или второй (суммарная интенсивность обслуживаний ).

Вычислим характеристики работы СМО.

Финальные вероятности существуют

(1)

, , …, , …, (2)

(1)и (2) называются формулами Эрланга.

Относительная пропускная способность .

Абсолютная пропускная способность: .

- среднее число занятых каналов.

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

 

 

72. Языки моделирования

Языки и системы моделирования упрощают построение программ-имитаторов и проведение имитационных экспериментов за счет частичной или полной автоматизации переходов от одного уровня представления модели к другому. В этом состоит основное назначение языков моделирования, именно здесь и проявляется их главное преимущество перед универсальными алгоритмическими языками.

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

Язык моделирования предоставляется пользователем как часть системы моделирования. Система моделирования – это совокупность языковых и программных средств, которая включает:

• собственно язык моделирования;

• язык управления системой моделирования– язык команд интерактивного взаимодействия с пользователем;

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

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