Подставив из первого уравнения получим

Где.

Вопрос 3.Двухступенчатые триггеры

Отсюда Функция распределения длины интервала между требованиями, имеет вид

при.

Функция плотности распределения будет

при t

Как видим это экспоненциальный закон распределения. Его основные числовые характеристики:

,

Как видно из выражения для функции распределения, вид закона распределения не зависит от положения интервала между требованиями на временной оси (стационарность) и от того, появились или нет требования раньше (отсутствие последействия). Т.е. е сли промежуток времени, распределенный по экспоненциальному закону уже длился некоторое время, то это никак не влияет на закон распределения оставшейся части промежутка - он будет таким же, как и закон распределения всего промежутка T. Этим свойством обладает только экспоненциальный закон. Для него можно показать, также, и выполнение условия ординарности.

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

Другие виды входных потоков.

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

Для него число требований, поступающих на участке времени длиной, начинающемся в точке также подчинено закону Пуассона

но значение параметра зависит и от и от

Как видим, закон распределения интервала времени между двумясоседними требованиями отличается от экспоненциального и зависит от видафункции.

Неординарный Пуассоновский поток. Сохраним стационарность и отсутствие последействия, но откажемся от ординарности следующим образом: Моменты прихода требований составляют простейший Пуассоновский поток, но в каждый из этих моментовt_i может придти группа из m требований, причем m случайно и задается распределением P(m) – вероятностью того, что в группе будет m требований. Тогда вероятность прихода в случайный момент (t_i) j требований равна:

P =

Поток с ограниченным последействием. Рассмотрим ординарный поток событий.

Здесь 1,2,3,… события, T₁, T₂ ,… интервалы времени между событиями.

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

Потоком Пальма является поток отказов элементов в техническом устройстве, если отказы наступают независимо, а отказавший элемент мгновенно заменяется новым. Поток отказов часто называют потокомвосстановлений т.к. в момент отказа происходит мгновенное восстановление элемента. Потоком с ограниченным последствием является, также, поток необслуженных заявок, покидающих систему (Теорема Пальма: если на входСМО поступает поток заявок типа Пальма и в случае занятости каналов обслуживания заявка покидает систему необслуженной (получает отказ), а время обслуживания заявок в системе подчинено экспоненциальному закону, то поток необслуженных заявок также является потоком Пальма.).

Частным случаем потока Пальма является простейший поток.

Другим частным случаем потоков Пальма являются потоки Эрланга, которые образуются «просеиванием» простейшего потока.

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

_*____*____*____*____*____*____*____*____*_____*__ Простейший поток

_*_________*_________*_________*_________*________ ПотокЭрланга 1-го порядка

_*______________*______________*_______________*___ Поток Эрланга 2-го порядка

_*___________________*___________________*__________ Поток Эрланга 3-го порядка

Интервал времени между требованиями в потоке Эрланга К-го порядка подчинён закону распределения Эрланга К-го порядка как закон распределения суммы (К+1) независимых случайных величин с экспоненциальнымзаконом распределения

f_к(t) ₌ при

с параметрами:

m_к=(к+1)_*m₀ = (к+1)* - мат. Ожидания;

D_К = (К+1)*D₀ = (К+1)* - дисперсия,

где: m₀,D₀ - параметры экспоненциального закона (закон Эрланг нулевого порядка).

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

Рассмотрим в качестве характеристики «меры случайности» коэффициент вариацииV_T=Ϭ_T/m_T, который применяется в ТВ для неотрицательных случайных величин.

Для закона распределения Эрланга К-го порядка он будет равен

V_T^(К)=Ϭ_T^(К)/m_T^(К)==

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

Кроме рассмотренных выше, на практике имеют распространение:

- Неординарные потоки (требования поступают не по одному, а группами);

- Сложные детерминированные потоки – неслучайные по сути, но со сложной функцией моментов поступления.

- Дискретные потоки. В них требования могут поступать только в определённые моменты времени. Например на транспорте – по расписанию и т.д.

Время обслуживания

Эффективность функционирования системы обслуживания, как уже говорилось ранее, определяется в частности временем обслуживания каждого требования. Длительность обслуживания в общем случае является случайной величиной, подчинённой некоторому закону распределения. В ТМО наиболее распространены следующие виды законов.

1. Показательное распределение длительности времени обслуживания.В этом случае время нахождения требования в канале обслуживания подчинено экспоненциальному закону распределения с параметром µ – среднее число заявок, обслуженных в канале за единицу времени (интенсивность обслуживания)

g(t) =t.

Мат. ожидание и дисперсия времени обслуживания заявки в канале будут:

m_(t) =; D_(t) =.

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

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

2. Эрланговское распределение длительности обслуживания. Используется при анализе СМО в тех случаях, когда процесс обслуживания можно представить как К последовательных, независимых этапов, длительность обслуживания на каждом из которых подчинена экспоненциальному закону распределения с параметром (распределение Эрланга (К-1)-го порядка).

3. Нормальное распределение. Часто встречаются ситуации, когда время обслуживания хорошо сгруппировано вокруг среднего значения и отклонения от него распределены симметрично с экспоненциально убывающей плотностью на ветвях. В таких случаях напрашивается использование нормального распределения. Однако, применять его надо с осторожностью. Дело в том, что генерация значений времени обслуживания в соответствии с нормальным законом чревата тем, что возможно появление отрицательных чисел, чего ни в коем случае быть не должно. Отрицательных чисел практически не будет, если среднее время обслуживания в 5-6 раз больше, чем С.К.О.

4. Постоянная длительность обслуживания. Применяется для приближённого расчёта СМО с сильной идеализацией процессов обслуживания.

Кроме этих законов распределения могут применяться и другие:

· с нестационарной интенсивностью обслуживания

· с неординарным потоком заявок.

· с зависимостью времени обслуживания от типа требования и др.

В этих случаях получить простые аналитические выражения для анализа СМО часто не представляется возможным. Поэтому:

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

- либо приводят немарковские модели к марковским, используя специальные приемы;

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

МАРКОВСКИЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ

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

Случайный процесс протекающий в системе называется Марковским – если для любого момента времени,вероятностные характеристики процесса в будущем (t >) зависят только от его состояния в данный момент времени (в настоящем) и не зависят от того,когда и как система пришла в это состояние в прошлом. (Например, счетчик Гейгера,регистрирующий число космических частиц).

Марковские процессы принято делить на 3 вида:

1. Марковская цепь – процесс, состояния которого дискретны (т.е. их можно перенумеровать), и время, по которому он рассматривается, также дискретно (т.е. процесс может менять свои состояния только в определенные моменты времени). Такой процесс идет (изменяется) по шагам (иначе - по тактам).

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

3. Непрерывный марковский процесс – множество состояний и время -непрерывные.

На практике Марковские процессы в чистом виде встречаются не часто. Однако нередко приходится иметь место с процессами, для которых влиянием предыстории можно пренебречь. Кроме того, если все параметры из «прошлого»,от которых зависит «будущее» включить в состоянии системы в «настоящем», то ее также можно рассматривать как Марковскую. Однако это часто приводит к значительному росту числаучитываемых переменных и невозможности получить решение задачи.

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

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

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

Например: Техническое устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя (отказать). После этого мгновенно начинается ремонт узла (восстановление),который продолжается случайное время.

Возможны следующие состояния системы:

- оба узла исправны;

- первый узел ремонтируется,второй исправен.

– второй узел ремонтируется,первый исправен

- оба узла ремонтируются.

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

- состояния

- переходы

Переходы и отсутствуют т.к. отказы и восстановления элементов происходят независимо и случайно и вероятность одновременного выхода из строя (восстановления) двух элементов бесконечно мала и ею можно пренебречь.

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

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

y AxLfPt1odeB1bKQZ9ZXDbS/XUbSTVnfEH1o94FOL9Vd5sQrWh0X5TOfiZVudTKGT+GNabE5K3d/N jw8gAs7hD4ZffVaHnJ0qdyHjRa9gGa93jCrYb3kysE8SEBWDmygBmWfyf4P8BwAA//8DAFBLAQIt ABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10u eG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5y ZWxzUEsBAi0AFAAGAAgAAAAhAIKWNQFeAgAAeAQAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9E b2MueG1sUEsBAi0AFAAGAAgAAAAhABYNpjngAAAACQEAAA8AAAAAAAAAAAAAAAAAuAQAAGRycy9k b3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAADFBQAAAAA= ">

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

Рассмотрим переходы системы из некоторого состояния в предыдущее или последующее. Фрагмент графа состояний в этом случае будет выглядеть следующим образом:

Пусть система в момент времени t находится в состоянии.

Обозначим (t)- вероятность i-ого состояния системы – вероятность того, что система в момент времени t находится в состоянии. Для любого момента времени t справедливо =1.

Определим вероятность того, что и в момент времени t+∆t система будет находиться в состоянии. Это может быть в следующих случаях:

1) Система находилась в состоянии и за время ∆ t из него не вышла. Это означает,что за время ∆ t не возникло события, переводящего систему в состояние (поток с интенсивностью) или события,переводящего её в состояние (поток с интенсивностью). Определим вероятность этого при малых ∆t.

При экспоненциальном законе распределения времени между двумя соседними требованиями, соответствующему простейшему потоку событий вероятность того, что на интервале времени ∆t не возникнет ни одного требования в потоке с интенсивностью λ₁ будет равна

,

Разлагая функцию f(t) в ряд Тейлора (t>0) получим (для t=∆t)

f(∆t)=f(0)+ (0)* ∆t + *∆ + *∆ +…=

= +(-l) *∆t+ (∆ + *(∆ +…» 1-l*∆t при ∆t®0

Аналогично для потока с интенсивностью λ₂получим.

Вероятность, что на интервале времени ∆t не возникнет ни одного требования будет равна

(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =

= 1 - - *∆t + 1 - (+)*∆t + б.м при ∆t®0

Таким образом, вероятность того, что система за время ∆t не вышла из состояния,при малых ∆t будет равна

P(/)=1 – (+)* ∆t

2) Система находилась в состоянии S_i-1 и за время перешла в состояние S_i. То есть в потоке с интенсивностью возникло хотя бы одно событие. Вероятность этого равна для простейшего потока с интенсивностью λ будет

Для нашего случая вероятность такого перехода будет равна

3) Система находилась в состоянии и за время ∆tперешла в состояние. Вероятность этого будет

Тогда вероятность, что система в момент времени (t+∆t) будет в состоянии S_iравна

+

Вычтем из обеих частей P_i(t), разделим на ∆tи, перейдя к пределу, при ∆t→0, получим

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

Данные уравнения называются уравнениями Колмогорова-Чепмена для дискретного марковского процесса.

Задав начальные условия (например, P₀(t=0)=1,P_i(t=0)=0 i≠0) и решив их, получим выражения для вероятностей состояния системы как функций времени. Аналитические решения достаточно просто получить, если число уравнений ≤ 2,3. Если их больше, то обычно решают уравнения численно- на ЭВМ (например методом Рунге-Кутта).

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

Так как в стационарном режиме все, следовательно все =0. Приравняв в системе уравнений левые части 0 и, дополнив их уравнением =1 получим систему линейных алгебраических уравнений, решив которую найдём значения финальных вероятностей.

Пример. Пусть в нашей системе интенсивности отказов и восстановления элементов следующие

Отказы 1эл:

2эл:

Ремонт 1эл:

2эл:

P₀+P₁+P₂+P₃=1

0=-(1+2)P₀+2P₁+3 P₂

0=-(2+2)P₁+1P₀+3P₃

0=-(1+3)P₂+2P₀+2P₃

0=-(2+3)P₃+2P₁+1P₂

Решив данную систему получим

P₀=6/15=0.4; P₁=3/15=0.2; P₂=4/15=0.27; P₃=2/15≈0.13.

Т.е. в стационарном состоянии система в среднем

40% находится в состоянии S₀ (оба узла исправны),

20%- в состоянии S₁ (1-й эл-т ремонтируется, 2-й исправен),

27%- в состоянии S₂ (2-й эл-тремонтируется, 1исправен),

13%- в состоянии S₃ – оба эл-та в ремонте.

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

Пусть система в состоянии S₀приносит доход 8 усл.ед. в единицу времени; в состоянии S₁-доход 3 усл.ед.; в состоянии S₂- доход 5;в состоянии S₃-доход=0

Стоимость ремонта в единицу времени для эл-та 1- 1(S_1,S₃) усл.ед., эл-та 2- (S_2,S₃) 2 усл.ед. Тогда в стационарном режиме:

Доход системы в единицу времени будет:

W_дох=8P₀+3P₁+5P₂+0P₃=8·0.4+3·0.2+5·0.27+0·0.13=5.15 усл.ед.

Стоимость ремонта в ед. времени:

W_рем=0P₀+1P₁+2P₂+(1+2)P₃=0·0.4+1·0.2+2·0.27+3·0.13=1.39 усл.ед.

Прибыль в единицу времени

W= W_дох-W_рем=5.15-1.39= 3.76 усл.ед

Проведя определённые расходы можно изменить интенсивности λи μ и, соответственно, эффективность системы. Целесообразность таких расходов можно оценить, проведя пересчёт P_i. и показателей эффективности системы.

ПРОЦЕССЫ РАЗМНОЖЕНИЯ И ГИБЕЛИ.

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

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

Особенность его состоит в том, что все состояния системы можно втянуть в одну цепочку, в которой каждое из среднихсостояний системыот S₁ до S_n-1связано с соседними состояниями справа и слева прямой и обратной стрелкой(переходом),а крайние состояния и только с одним соседним (внутренним) состоянием

Термин «схема размножения и гибели» берет начало от биологических задач, где подобной схемой описывается изменение численности популяции. Процесс размножения и гибели соответствует как бы двум потокам: «размножение»-переход от состояния к с интенсивностью за счет возникновения требований в системе и «гибели»-переход от к с интенсивностью – за счет убывания («обслуживания») требований.

Для схемы размножения и гибели граф состояний системы имеет вид:

В случае, если в системе существуют только потоки требований «вперед»,т.е. за счет их возникновения, то процесс рассматривается как «процесс чистого размножения». Если измерение состояний системы происходит только «назад», за счет обслуживания требований,то говорят о «процессе чистой гибели».

Пусть все потоки событий, переводящие систему S из состояния в состояние –простейшие. Тогда уравнения Колмогорова-Чепмена для неё могут быть записаны в виде:

……………………..

……………………...

Для стационарного режима, при их можно записать в следующем виде:

…………………..…

…………………….

Подставив предыдущее уравнение в последующее (например, для второго уравнения) получим:

Подставив, аналогично, каждое предыдущее уравнение в последующее получим следующую систему:

…………………

………………

Каждое из уравнений этой системы характеризует баланс «прямых» и «обратных» потоков из состояния в состояние с учетом вероятностей состояний.Выразим из них вероятности всех последующих состояний через предыдущее:

…

…

Таким образом все финальные вероятности состояний системы можно выразить через интенсивность потоков и вероятность начального состояния. Дополнив систему нормирующим условием получим:

Отсюда получим выражение для P_0:

Или ….

Если число состояний n конечно, то ряд, стоящий в выражении для P₀ –сходится и, следовательно, вероятности P₀и P_k (1 ≤k≤n) отличны от нуля.В этом случае в системе существует стационарный режим.

Если же число возможных состояний n системы неограниченно (n = ∞), то ряд может расходиться. В этом случае режима статического равновесия в процессе (системе) не существовует. Тогда P₀и остальные P_k (k> 0) будут = 0.

Для того, чтобы режим статического равновесия существовал необходимо, чтобы ряд в P₀сходился. Для этого необходимо, чтобы, начиная с некоторого состояния i₀, выполнялось условиедля всех i>i₀. т.е. интенсивность процесса «гибели» была выше, чем интенсивность процесса размножения. В противном случае номер состояния k системы будет неуклонно возрастать.

Для стационарного режима вероятности P_k будут равны

1 < k < n

Зная значения вероятностей P_k можно вычислить основные характеристики рассматриваемой СМО.

ОПРЕДЕЛЕНИЕ ОСНОВНЫХ ХАРАКТЕРИСТИК СМО

Рассмотрим Систему Массового Обслуживания следующего вида

. . .

Входной поток

Очередь

m

n

Каналы обслуживания

Выходной поток

Здесь: n – число каналов обслуживания, m –максимальная длина очереди.

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

Под состоянием СМО будем понимать k - число заявок, находящихся в ней. Оно будет изменяться от 0, когда заявок в системе нет, до n+m, когда все каналы обслуживаются, и все места в очереди заняты. Подобную СМО можно представить в виде графа состояний, с помощью которого можно записать описывающие его поведение уравнения. Решив их для любого произвольного момента времени t (в частности для стационарного режима t=∞) можно определить значения вероятностей нахождения СМО в одном из состояний S_k

k = 0, n+m t> 0.

Зная их можно определить основные характеристики СМО, такие как:

1. Среднее число занятых каналов обслуживания

2. Средняя длина очереди

3. Вероятность, что поступившее в момент времени tтребование получит отказ

4. Вероятность, что поступившее требование будет обслужено

Аналогично могут быть найдены:

5. Вероятность, что поступившее в систему требование сразу поступит в канал на обслуживание

6. Вероятность, чтотребование попадёт в очередь

ФОРМУЛА ЛИТТЛА

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

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

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

Обозначим: X(t) – число заявок, прибывающих в СМО, до момента t, Y(t) –число заявок покидающих СМО к моменту t. Тогда Z(t) = X(t) – Y(t) - - число заявок находящихся в системе в момент времени t (см рис)

Найдём среднее число заявок, находящихся в системе для некоторого, достаточно большого интервала T: