Пример открытой СеМО

Сеть грузовых перевозок состоит из трёх узлов:

узел 1 - морской порт (система М|М|m₁);

узел 2 - железнодорожный вокзал (система М|М|m₂);

узел 3 - аэропорт (система М|М|m₃).

В данную сеть поступает простейший поток грузов с интенсивностью - g = (g₁, g₂, g₃). Интенсивность обслуживания в узлах СеМО m = (m₁, m₂, m₃). Матрица маршрутизации имеет вид

0 a 0

P = 1-b 0 b

d 1-d 0

В стационарном режиме работы СеМО при числе обслуживания приборов в узлах m=(1,3,2), интенсивности поток а извне g = (1,3,2), интенсивности обслуживания в узлах m=(15,10,9) и вероятностях переходов a=1/2, b=2/3, d=1/2 определить:

1. Вероятность того, что вокзал свободен от грузов.

2. Вероятность того, что в аэропорту скопилась очередь.

3. Среднюю длину очереди в аэропорту.

4. Среднее время ожидания и пребывания в морском порту.

Решение. Для определения интенсивностей входящих потоков в узлах СеМО пишем уравнения баланса

l₁-l₂(1-b)-l₃d = g₁;

l₁a + l₂ - l₃(1-d) = g₂;

-l₂b + l₃ = g₃;

Решая эту систему, находим формулы для определения l₁,l₂,l₃:

l₁=(g₁+g₂+g₃)/(1-a);

l₂=(ag₁+g₂+g₃(1-d+ad))/((1-a)(1-b(1-d)));

l₃=(abg₁+bg₂(1-a(1-b)g₃))/((1-a)(1-b(1-d))).

По этим формулам в условиях данного примера получаем l = (12,15,12). Стационарный режим данной СМО существует, т.к.

l₁/ (m₁m₁) = 12/15 = 4/5<1, l₂/ (m₂m₂)=15/(10*3)=1/2<1,

l₃/ (m₃m₃)= 12/(9*2)=2/3<1.

1. Вероятность того, что вокзал свободен от грузов, т.е. вероятность р₂₀, находится по формуле для CMO М|М|3 во втором узле:

P₂₀ = [ (3/2)^k/k! + (3/2)³ / (3! (1-1/2))]^-1 = 4/19.

2. Вероятность того, что в аэропорту скопилась очередь, то есть вероятность1-p₃₀-p₃₁-p₃₂, находим по формуле для СМО М|М|2 в третьем узле:

р₃₀= [1 +4/3+ (4/3)² / (2 (1 -2/3))] ^-1=1 /5 ;

р₃₁= р₃₀4/3=4/15;

р₃₂= р₃₀(4/3)² = 4/45;

Следовательно, искомая вероятность равна 4/9.

3. Среднюю длину очереди в аэропорту определяем по формуле для системы М|М|2:

q = p₃₂r₃/m₃(1-r₃/m₃)^-2=8/15.

4. Среднее время ожидания и пребывания в морском порту находим по формулам для системы М|М|1:

W = (r₁/m₁)/(1-r₁)=4/15;

T = (1/m₁)/(1-r₁)=1/3.

Лекция №7 Замкнутые экспоненциальные сети

Рассмотрим СеМО, состоящую из N узлов обслуживания, в которой постоянно находятся К заявок, переходящих для обслуживания из узла в узел СеМО в соответствии с вероятностями, задаваемыми матрицей маршрутизации. Это соответствует сети Джексона, у которой

g_i=0 , p_ij =1.

Время обслуживания каждым из m приборов узла J имеет показательное распределение с параметром m_j.

Обобщением результатов Джексона на случай замкнутых СеМО занимались В.Гордон и Г.Ньюелл, которые в 1967 году показали, что и в случав замкнутой экспоненциальной сети стационарное распределение вероятностей состояний СеМО имеет вид произведения.

Система уравнений баланса (8.3) в таких сетях принимает вид

l = lP , (8.6)

где l=(l₁,l₂,...,l_N) - вектор-строка интенсивностей потоков, входящих в узды СеМО, P- матрица маршрутизации. Уравнение (2.6) позволяет определить l_i с точностью до постоянного множителя (т.е. найти относительные значения l_i).

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

Тогда решение систем уравнений (8.6) определяется единственным образом и l_i , можно трактовать как вероятность того, что в стационарном режиме произвольно выбранный переход из одного узла в другой окажется переходом в i-й узел. Для однозначного определения l_i можно также положить одну из координат вектора равной любому числу (например l₁=1), тогда остальные координаты определяются единственным образом из системы (2.6) (если ее ранг равен N-1).

Пусть р(k)= р(k₁, k₂,..., k_N) обозначает стационарное распределение процесса Q(t)=(Q₁ (t), . . . ,Q_N(t)), т.е.

р(k)= р(k₁, k₂,..., k_N) = lim P{Q(t)=k}. (8.7)

t®¥

В случае замкнутой СеМО между компонентами вектора состояний k= (k₁, k₂,..., k_N) есть зависимость:

(8.8)

Тем не менее, и здесь стационарное распределение вероятностей имеет вид произведения.

Стационарные вероятности р(k) состояний процесса Q(t) являются решением следующей системы уравнений глобального равновесия:

р(k₁,k₂,...,k_N) + min (k_i , m_i) m_i (1-p_ii) =

d_ki min (k_j+1, m_j) m_j p_ji р(k₁, k₂,..., k_j+1, … , k_i-1, … , k_N) ,

где d_k = min (k ,1).

k_N

k₂

k₁-1

k₁+1

i=1 … p₁₂

j=2

k_N

k₂

k₁-1

k₁+1

i=1 … p₁₃

j=3 i=1

. . . . i¹1

. . . .

k₁+1

k_N-1

k₃

k₂

i=1 … p_1N

k₃

j=N

k_N

k₃

k₂+1

k₁-1

i=2 … p₂₁

k₃

j=1

k₃

k_N

k₃-1

k₂+1

k₁

i=2 … p₂₃

j=3 i=1 N N p_k

. . . . i¹2 .

. . . . i=1 j=1 .

. . . . i¹j .

k₃

k₁

k_N-1

k₃

k₂+1

i=2 … p_2N

j=N

. . . .

k₁-1

k_N+1

k₃

k₂

i=N … p₁₂

j=1

k₁

k_N+1

k₃

k₂-1

i=N … p₁₃

j=2 i=1

. . . . i¹N

. . . .

k_N+1

k₃

k₂

k₁

i=N … p_1N

N-1

k₁

k_N

k₃

k₂

i=1 … p₁₁

j=1

k_N

k₃

k₂

k₁

i=2 … p₂₂

j=2 i=1

. . . .

k₁

k_N

k₃

k₂

i=N … p_NN

j=N

Рис. 7.1.

Величина d_k, входящая в уравнение равновесия (8.9), учитывает тот факт, что

р(k₁, k₂,..., k_j +1, … , k_i-1, … , k_N) = 0, если k_i = 0. Величина min (k_i ,m_i) равна числу требований в i-м узле, находящихся на обслуживании, при условии, что всего в узле имеется к± требований. Левая часть равенства (8.9) описывает вероятностный поток, исходящий из состояния k= (k₁, k₂,..., k_N), правая часть - вероятностный поток, входящий в это состояние из соседних состояний (см. рис. 7.1).

На рис.7.1:

p_ij = m_i min (k_i +1, m_i) d_kj р(k₁, k₂,..., k_i+1,…, k_j -1, … , k_N) p_ij , i¹j

p_ii = m_i min (k_i, m_i) р(k₁, k₂,…, k_N) p_ii ;

p_k = р(k₁, k₂,…, k_N) m_i min (k_i, m_i) .

Выпишем уравнения локального равновесия:

р(k₁,k₂,...,k_N) + min (k_i, m_i) m_i (1-p_ii) =

(8.10)

min (k_j+1, m_j) m_j p_ji р(k₁, k₂,..., k_j +1, … , k_i-1, … , k_N) ,

означающее равенство вероятностных потоков: выходящего из состояния k= (k₁, k₂,..., k_N) (слева) за счет выхода требований из узла i и входящего в это состояние из соседних состояний (справа) за счет перехода требований в узел i (см. рис. 2.8).

На рис 7.2:

p_ji = m_j min (k_j +1, m_j) d_ki р(k₁, k₂,..., k_j+1,…, k_j -1, … , k_N) p_ij ;

j¹i

p_ii = m_i min (k_i, m_i) р(k₁, k₂,…, k_N) p_ii ;

p_ki = р(k₁, k₂,…, k_N) m_i min (k_i, m_i).

Рассмотрим множество чисел {x_i}, представляющих собой решения следующей системы линейных уравнений:

m_ix_i= m_jx_jp_ij, i=1, 2, …, N. (8.11)

Заметим, что эта система имеет вид уравнения баланса l=lP, если за вектор l принять векторы (m_ix_i , … , m_Nx_N).

Теорема. Если все узлы замтутой СеMО сообщающиеся, т.е. (i « j) для любых i,j = 1,2, ... N (матрица маршрутизации Р -неприводимая стохастическая матрица ), то система (8.11) имеет решение, все компоненты которого положительны (это решение конечно, определяется с точностью до постоянного множителя).

k_N

k₁+1

k₂

………………………. p_1i

j=1

k_N

k₂+1

k₁

j=2 ………………………. p_2i

Узел i

j=1

. . .

k₁+1

k_i-1+1

k_N-1

k_i+1

k₂

j= … … p_i-1ip_ki

i-1

k_i+1

k₂

k_i-1

k_i

k_N

k₁+1

j=i … … p_ii

k_i+1+1

k_N

k_i-1

k₂+1

k₁

j= … … p_i+1i

i+1

. . .

k₁

k_N

k₂+1

j=N ………………………… p_Ni

Рис. 7.2 Равновесие потоков для узла i

Решение уравнений равновесия (8.9) в этом случае имеет вид

р(k)= р(k₁, k₂,..., k_N) = 1/G(K,N) /b_i(k_i), (2.12)

k_i! , k_i£ m_i

где b_i(k_i) = ,

m_i! , k_i < m_i

G(K,N) – нормирующая постоянная, обеспечивающая равенство суммы вероятностей единице,

G(K,N) = /b_i(k_i),

где k= (k₁, k₂,..., k_N) и суммирование ведётся по всем векторам k, принадлежащим множеству А возможных состояний сети,

A = {k : k_i³0, k_i = K}.

Отметим, что в рассматриваемых замкнутых СеМО число элементов множества А конечно, оно равно числу способов размещения К требований по N узлам, т.е. равно биномиальному коэффициенту C^N^-1_N₊_K_-1.

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

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