Финаев В.И. Аналитические и имитационные модели

Подождите немного. Документ загружается.

151

применяют математические модели, изложенные в работе

[19]. Если же рассматривать сложные структуры СМО

(многофазные, многоканальные, приоритетные), то

получить математическую модель в виде аналитических

зависимостей невозможно. Поэтому для исследования

сложных структур СМО разрабатывают имитационные

модели [20].

Для СМО приняты обозначения

А/В/m/L, в которых:

- первая позиция

А определяет функцию

распределения входного потока заявок (интервала времени

между поступающими заявками);

- вторая позиция

В определяет функцию распределения

закона обслуживания;

- третья позиция определяет

m число каналов

(приборов) обслуживания;

- четвертая позиция

L определяет максимально

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

Аналитические законы функций распределений имеют

следующее общепризнанное кодированное обозначение:

М – показательное распределение;

- распределение Эрланга r–го порядка;

- гиперпоказательное распределение порядка k;

D - вырожденное распределение;

G - произвольное распределение.

7.2. Модель входного потока заявок и времени

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

Входной поток заявок характеризуется начальным

моментом времени

, моментами времени t

поступления

i-х заявок, случайными величинами ε

- интервалами

времени между заявками,

-t

i-1

. Модель потока в общем

152

виде представляет собой конечномерную функцию

распределения вероятностей:

F(х

,х

,...,х

)=Р{ε

<х

, ε

<х

,..., ε

<х

Если ε

- величины детерминированные, то имеем дело с

равномерным потоком заявок. Можно задать для каждого

плотности распределения

(х). В том случае, когда

плотность совместного распределения будет определяться

как

f(х

,х

,...,х

)=f

(х)f

(х)...f

(х), получим поток Пальма с

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

Известны три характеристики для классификации

входных потоков:

- ординарный поток, если за сколь угодно малый отрезок

времени вероятность появления двух и более заявок равна

нулю;

- стационарный поток, если вероятность поступления

заявок за интервал времени

,t) не зависит от выбора

момента

;

- поток без последействия, если вероятность появления

k-заявок внутри некоторого интервала не зависит от

появления заявок до момента начала этого интервала.

Простейший поток (поток Пуассона) удовлетворяет всем

трем условиям. Для этого потока вероятность поступления

k-событий за время t определится

)t(

λ−

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

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

распределением -

A(t)=1-ε

-λt

. Hаиболее часто применяется

при моделировании экспоненциальное распределение и

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

вероятности интервалов между заявками для эрланговского

потока r-го порядка определится

153

)t(

λ−

Если

r=0, то получаем экспоненциальное распределение.

Эрланговские распределения описывают модели потоков с

последействием. Моделями времени обслуживания могут

служить функция и плотность распределения вероятности

длительности обслуживания. При исследовании прибора

обслуживания необходимо определить эмпирическую

плотность распределения длительности обслуживания, а

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

распределениями. Hаиболее применяемые распределения:

нормальное, постоянное, экспоненциальное распределения

и распределение

Эрланга.

7.3. Модель Эрланга

При моделировании СМО исследуется изменение в

системе за сколь угодно малый отрезок времени.

Составляются уравнения в частных приращениях, от

которых затем осуществляется переход к

дифференциальным уравнениям. Рассмотрим вывод

дифференциальных уравнений, известных как модель

Эрланга. Будем рассматривать одноканальную СМО с

бесконечной очередью, с ожиданием, пуассоновсим

потоком заявок и экспоненциальным временем

обслуживания. Поток

ординарный, простейший, функция

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

экспоненциальной. Модель смены состояний можно

представить в виде графа, приведенного на рис. 7.1.

154

… …

n-1

n+1

Рис. 7.1

Составим уравнения Эрланга в частных приращениях,

которые будут отображать те изменения, которые

произошли в системе за сколь угодно малое время

Δt.

Из графа состояний (см. рис. 7.1) следует, что в числе

состояний СМО существует «особое» состояние –

состояние, при котором в СМО нет заявок. Определим это

состояние, начальное состояние, когда число заявок в СМО

n=0. Остальные состояния идентичны по своим связям с

другими состояниями и определены числом заявок в СМО

n≥1. Вероятность Р

(t+Δt) того, что СМО к моменту t+Δt

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

полной группы событий:

- в момент времени

t система была в нулевом состоянии

и за время

Δt заявки не поступали;

- в момент времени

t система была в единичном

состоянии (в СМО была одна заявка) и за время

Δt

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

Вероятность

(t+Δt) определится

(t+Δt)=Р

(t)(1-λΔt)+Р

(t)μΔt, (7.1)

где

1-λΔt - вероятность непоступления заявки в СМО за

время

Δt, μΔt - вероятность окончания обслуживания

заявки за время

Δt.

Вероятность

(t+Δt) того, что к моменту времени t+Δt

система будет в

n-м состоянии, определится из

рассмотрения следующей полной группы событий:

155

- в момент времени

t в системе было n-1 заявок и за

время

Δt поступила заявка;

- в момент времени

t система была в n-м состоянии и за

время

Δt заявки в СМО не поступили и обслуживание не

окончено;

- в момент времени

t в системе была n+1 заявка и за

время

Δt обслуживание заявки было окончено.

Вероятность

(t+Δt) определится

(t+Δt)=Р

n-1

(t)λΔt+Р

(t)[1–(λ+μ)Δt1+Р

n+1

(t)λμΔt, (7.2)

где

Δt - вероятность поступления заявки за время Δt; 1–

(λ+μ)Δt -

вероятность непоступления заявки в СМО и

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

Δt.

Уравнения (7.1) и (7.2) представляют собой модель

рассматриваемой СМО в виде уравнений Эрланга в

частных приращениях. От уравнений в частных

приращениях перейдем к дифференциальным уравнениям.

Для этого

(t) из правой части перенесем в левую,

разделим каждую часть на

Δt и определим предел при

Δt→0. Получим уравнения:

,0n),t(P)t(P

)t(dP

=μ+λ−=

1n ),t(P)t(P)t(P)(

)t(dP

1n1nn

≥μ+λ+μ+λ−=

+−

(7.3)

Уравнения (7.3) представляют собой

модель

исследуемой СМО в виде дифференциальных

уравнений Эрланга для нестационарного случая

Так как поток заявок, поступающих в систему, отвечает

условиям стационарности, то значение производных можем

приравнять к нулю.

Получим

модель СМО в виде уравнений Эрланга для

стационарного режима

=ρР

, n=0, (1+ρ)Р

=Р

n+1

+ρР

n-1

, n≥1, (7.4)

где λ/μ=ρ - коэффициент использования системы.

156

Решение системы уравнений (7.4) будет иметь

следующий вид:

=ρ

, Р

=(1-ρ), Р

= ρ

(1-ρ),

где Р

- вероятность того, что в СМО будет n заявок.

Затем могут быть определены такие характеристики

СМО, как математическое ожидание числа заявок в СМО,

математическое ожидание числа заявок в очереди и другие.

7.4. Исследование модели пуассоновского

процесса с помощью производящих функций

Будем считать, что на вход СМО поступает

пуассоновский поток заявок с интенсивностью

λ и

вероятностью

(t) того, что за время t в СМО поступит n

заявок. Делаем предположение, что при сколь угодно

малом отрезке

Δt вероятность поступления заявки

определится через

λΔt. Вероятность непоступления заявки

определится как

1-λΔt. Поток является ординарным.

Можно записать уравнение в частных приращениях.

Вероятность того, что к моменту времени

t+Δt в системе не

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

системе в момент времени

t не было заявок, и за отрезок

времени

Δt заявки в систему не поступили:

(t+Δt)=Р

(t)(1-λΔt). (7.5)

Вероятность того, что к моменту времени

1+Δt в СМО

будет

n заявок, определится как вероятность того, что в

момент

t в СМО было n заявок, и за время Δt заявка не

поступила, или к моменту времени

t в СМО были n-1

заявок, и за время

Δt поступила еще одна заявка:

(t+Δt)=Р

(t)(1-λΔt)+ Р

n-1

(t) λΔt. (7.6)

После проведения преобразований уравнений (7.5) и

(5.6), аналогичных преобразованиям уравнений (7.1), (7.2),

получим дифференциальные уравнения:

157

,0n ),t(P

)t(dP

=λ−=

1n ),t(P)t(P

)t(dP

1nn

≥λ+λ−=

−

. (7.7)

Рассмотрим решение уравнений (7.7) с применением

производящих функций.

Производящая функция

Р(z,t) для функции Р

(t)

определится

...z)t(Pz)t(P)t(P

z)t(P)t,z(P

210

+++

∑

∞

Вероятность

(t) получим из производящей функции

после того, как продифференцируем ее

n раз и положим

z=0. При решении уравнения в частных приращениях

начало отсчета времени выбирается произвольно даже

после того, как в систему поступило

i заявок. Будем

считать, что при

t=0 в СМО есть i заявок. В этом случае

(0)=0, если n≠i и Р

(0)=1, если n=i. Таким образом,

.)t(P1t)P(1, ,z)0(Pz)0(P)o,z(P

∑

===

∑

∞

.zPzP

)t,z(P

n)l(

∑

∂

∞

Если умножим дифференциально-разностное уравнение

(7.5) на

, а дифференциально-разностное уравнение (7.6)

на

и просуммируем по всем значениям n, так что

∞

∑

nnn

nn-1

n=0

dP (t)

z=-λP(t)z +

dP (t)

+z=-λP(t)z +λP(t)z,

то получим, что сумма в левой части равна

)t,z(P

∂

158

а сумма первых членов правой части равна

λР(z,t).

Просуммировав вторые члены правой части по

n, получим

).t,z(zP...

z)t(

Pz)t(

z)t(

P =+λ+λ

∑

∞

−

Если в правой части выделить множитель

λz, то всю

сумму можно записать в виде

λzР(z,t). Таким образом,

система приводится к линейному дифференциальному

уравнению для производящей функции, которое имеет вид

0)0,z(P)1z(

)t,z(P

=−λ−

∂

Решение этого уравнения при постоянном значении z

(поскольку оно не зависит от t) имеет вид

Р(z,t)=Сe

λ(z-1)t

Допустим, что к моменту t=0 не поступило ни одного

требования, тогда

Р(z,0)=1, так как i=0. Таким образом,

С=1 и

Р(z,t)=e

λ(z-1)t

Как говорилось выше,

(t) определится

)t,z(P

)t(

∂

Таким образом,

)t(

P ,

te)t(

P ,

e)t(

−

λ−

λ=

λ−

что является искомой математической моделью

пуассоновского потока.

7.5. Модель для определения времени задержки

в виде интегро-дифференциальных уравнений

Линди-Такача-Севастьянова

Модель описывает функцию распределения времени

задержки в СМО [10]. Пусть

Р(ω,t)- вероятность того, что

159

заявка ожидает в очереди в течение времени

ω(t)≤ω при

условии, что она поступила во время

t, так что

Р(ω,t)=Р{ω(t)≤ω/t}. Будем рассматривать NÆ∞

идентичных, одновременно действующих одноканальных

СМО, на вход каждой из которых поступает пуассоновский

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

функцией распределения

В(t)=Р{b<t}, где b время

обслуживания заявки.

В момент времени

t все число N СМО разобъем на две

группы:

- СМО, у которых время задержки

ω(t)≤ω;

- СМО, у которых время задержки

ω(t)>ω.

Число систем первой группы равно

NР(ω,t), а число

систем второй группы равно

N-NР(ω,t).

Рассмотрим изменения, которые могут произойти в

момент времени

t+Δt. Задача будет состоять в том, чтобы

определить вероятность

Р(ω,t+Δt) через вероятности Р(ω,t)

Р(ω+ Δt,t). Для момента времени t+Δt число систем

первой группы становится равным

NР(ω+Δt,t) минус число

тех систем

, у которых в момент времени t было время

ожидания

ω(t)≤ω, но вследствие поступления заявки за

время

Δt, ω(t) превысит уровень w. Можно записать:

NР(ω,t+Δt)=NР(ω+Δt,t) - N

. (7.8)

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

Вначале определим число систем, у которых в момент

времени

t ω(t) находится внутри интервала (х,х+dх). Так

как

Р(х,t) - функция распределения вероятностей, то после

дифференцирования при

х>0 получим ее плотность

распределения. Тогда число систем определится

,dx]

)t,x(P

∂

если х>0, или NР(0,t), если х = 0.

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

(t,t+Δt) время

ожидания превзойдет величину

ω, если за время Δt

160

поступит одна заявка и если время обслуживания y этой

заявки, сложенной с величиной

х, превзойдет величину ω,

т.е.

(х+y>ωÆy>ω-х). Поэтому нужно умножить число

систем, у которых время ожидания равно

х, на вероятность

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

Δt, т.е. на λΔt, и

на вероятность того, что время обслуживания этой заявки

превзойдет величину

ω-х. Если b(y) - плотность

распределения времени обслуживания, то вероятность

последнего события равна

∫

∞

−ω

=−ω≥

)y(d)y(b}xb{P

Для фиксированного значения времени ожидания

ω>0

число систем, которые перейдут из первой группы во

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

)x(dxB

)t,x(P

tN)y(d)y(bdx

)t,x(P

∂

Δλ=

∂

Δλ

∫

∞

−ω

которое должно быть просуммировано по всем

х, х<0≤ω .

Причем

∫

) = 1 - b(u)d(u) = 1- B(

)

. Если х=0, то

число систем, переходящих во вторую группу, определится

)x(B)t,0(tPN)y(d)y(b)t,0(tPN

Δλ=Δλ

∫

∞

Следовательно, уравнение (7.8) будет иметь вид

−

ω=

)t,t(NP)tt,(NP

∫

−−ωΔλ−

dx)x(B

)t,x(dP

)(tBN

ωΔλ

−

. (7.9)

Применим разложение функции

Р(ω+Δt,t) в ряд Тейлора

)t(0t

)t,(P

)t,(P)t,t(P Δ+Δ

ω∂

+ω=Δ+ω