Автоматика и телемеханика, № 6, 2019

(Ченстоховский университет технологий, Польша),

Д.Я. КОПАТЬ (e-mail: dk80395@mail.ru)

(Гродненский государственный университет, Беларусь)

ПРОГНОЗИРОВАНИЕ ОЖИДАЕМЫХ ДОХОДОВ

В ОТКРЫТЫХ МАРКОВСКИХ СЕТЯХ

С ЗАЯВКАМИ РАЗЛИЧНЫХ КЛАССОВ

И РАЗЛИЧНЫМИ ОСОБЕННОСТЯМИ

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

которой удовлетворяют ожидаемые доходы открытых марковских сетей

массового обслуживания с различными особенностями. Число состояний

сети в этом случае и число уравнений в данной системе бесконечно.

Потоки поступающих в сеть заявок являются простейшими и независи-

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

ным законам. Доходы от переходов между состояниями сети являются

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

систем в единицу времени, когда они не меняют своих состояний, так-

же зависят только от этих состояний. Для решения системы разностно-

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

последовательных приближений, совмещенный с методом рядов. Пред-

ставлен пример анализа марковской G-сети с сигналами и групповым

удалением положительных заявок. Найденные ожидаемые доходы пока-

зывают, что они могут быть возрастающими и убывающими функциями

времени; могут принимать положительные и отрицательные значения.

Ключевые слова: сеть массового обслуживания, ожидаемые доходы, за-

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

DOI: 10.1134/S0005231019060060

1. Введение

Cистемы массового обслуживания (СМО) с доходами в стационарном ре-

жиме были введены в рассмотрение в [1], а сети - в [2]. Обзор результатов,

полученных по системам и сетям массового обслуживания (СеМО) с дохо-

дами в стационарном режиме, содержатся в [3]. Он посвящен нахождению

средних доходов в системах сетей, зависящих только от их состояний и не

зависящих от времени, и решению методом динамического программирова-

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

в системах. Доходы от переходов между состояниями сети при этом не учиты-

вались. СеМО с доходами в нестационарном (переходном) режиме изучались

в [4, 5]. Заявка при переходе из одной СМО в другую приносит последней

некоторый доход, а доход первой СМО уменьшается на эту величину. При

этом доходы от переходов между состояниями сетей зависели от их состоя-

ний и времени или являлись случайными величинами (СВ) с заданными мо-

104

ментами первого и второго порядков. В обзорной статье [6] приведены ре-

зультаты по анализу, оптимизации и выбору оптимальных стратегий управ-

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

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

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

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

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

ственных системах и других объектах. Как известно, функционирование лю-

бой марковской СеМО можно описать при помощи цепей Маркова с непре-

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

В простейшем случае марковские цепи с небольшим числом состояний и до-

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

рассмотрены в монографии [7].

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

без учета доходов рассматривались многими авторами [8-13]. В них же пред-

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

и для почти всех марковских сетей, стационарное распределение вероятно-

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

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

введены в рассмотрение E. Gelenbe [8] как модели поведения компьютерных

вирусов в информационно-телекоммуникационных системах и сетях и назы-

ваются ныне G-сетями. Обзор результатов по анализу таких сетей и их при-

менению приведен в [14-16]. G-сети с положительными и отрицательными за-

явками многих классов в стационарном режиме в случае, когда число классов

обоих типов одинаково, рассматривались в [17-18]. Нахождение нестационар-

ных вероятностей состояний марковской G-сети с положительными и отри-

цательными заявками многих классов модифицированным методом последо-

вательных приближений, совмещенным с методом рядов, изложено в [19], а

для G-сети с сигналами и групповым удалением заявок - в [20].

В последние годы большое внимание было уделено исследованию марков-

ских сетей с доходами и различными особенностями: c ограниченным време-

нем ожидания заявок и ненадежными СМО [21, 22]. В случае, когда доходы

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

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

доходов систем сети и дисперсий доходов был предложен приближенный ме-

тод, точность которого возрастает, если СМО сети функционируют в усло-

виях высокой или, наоборот, низкой нагрузки. В [23] рассматривалась мар-

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

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

и могут зависеть от ее состояний. Для сети, допускающей мульпликативное

представление для совместного стационарного распределения вероятностей

состояний, для ожидаемых доходов систем сети выведена система разностно-

дифференциальных уравнений (РДУ), для решения которой также предло-

жено использовать метод последовательных приближений, совмещенный с

методом рядов. В данной статье эти результаты обобщены на случай любых

марковских сетей с заявками многих классов.

105

2. Анализ доходов в марковских сетях методом последовательных

приближений, совмещенным с методом рядов

На основании ранее полученных результатов [6, 21-27] было замечено, что

в общем случае систему РДУ для ожидаемых доходов открытой марковской

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

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

поломкам, заявки могут быть “нетерпеливыми” и с иными различными осо-

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

dV (d,k,l,t)

= -Λ(d,k,l)V (d,k,⃗l,t) +

∑

(1)

l) ×

Θ_i∗j∗αmβbγθη(d,k,

i^∗,j^∗=0 α,β,γ,θ,η=0 m=0 b=0

(

)

×V

^d+I_i∗ -I_j∗,k

I_α +

I_β -

I_γ,l

I_θ

I_η,t

+ E(d,k,l),

гд

I_α - вектор размерности Ψr, состоящий из нулей, за исключением ком-

поненты с номером α, которая равна 1, Ψ - некоторое целое положительное

число, r - число типов заявок, I_α - вектор размерности n, состоящий из ну-

лей, за исключением компоненты с номером α, которая равна 1

d - вектор

размерности n с компонентами d_i, где d_i - количество исправных линий об-

служивания в i-той СМО,^k - вектор размерности Ψr с компонентами k_ic,

где k_ic - количество положительных заявок типа c в i-й СМО,l - вектор

размерности Ψr с компонентами l_ic, где l_ic - количество сигналов типа c в i-й

СМО, i = 1, n, c = 1, r. Здесь^V (d,k,l,t) = (v1(d,k,l,t),... ,vn(d,k,⃗l,t))T , где

T - знак транспонирования, v_i(d,k,⃗l,t) - ожидаемый доход, который полу-

чает i-я СМО за время t, если в начальный момент времени сеть находится

в состоянии (d,k,l), Λ(d,k,l),E(d,k,⃗l) - некоторые функции, различные для

каждой сети обслуживания,^E(d,k,l) = (E1(d,k,l), . . . , En(d,k,⃗l))T .

Будем считать, что ряд

∑

(2)

Θ_i∗j∗αmβbγθη(d,k,l

)

i^∗,j^∗=0 α,β,γ,θ,η=0 m=0 b=0

сходится. Для марковских сетей, рассмотренных ранее [25-27], это было до-

казано.

Вектор x = (d,k,⃗l) является вектором (2Ψr + n)-мерного пространства с

неотрицательными целочисленными компонентами. Поставим в соответствие

каждой точке этого пространства одновалентный тензор

Ξ_χ(d,k,

l) = Θ_i∗_j∗_αmβbγθη(d,k,

l),

где

χ = m(n + 1)²(Ψr + 1)⁵ + β(n + 1)²(Ψr + 1)⁴ + i^∗(n + 1)(Ψr + 1)⁴ +

+ j^∗(Ψr + 1)⁴ + α(Ψr + 1)³ + γ(Ψr + 1)² + θ(Ψr + 1) + η

106

и двухвалентный тензор

(

)

(

)

Δ_iν

^V(d,k,l,t)

=v_i

^d+I_i∗ -I_j∗,k

I_α +

I_β -

I_γ,l

I_θ

I_η,t

где

ν = m ∗ (n + 1)²(Ψr + 1)⁵ + β^∗(n + 1)²(Ψr + 1)⁴ +ⁱ(n + 1)(Ψr + 1)⁴ +

+^j(Ψr + 1)⁴ + α^∗(Ψr + 1)³ + γ^∗(Ψr + 1)² + θ^∗(Ψr + 1) + η^∗,

m^∗,β^∗,¯i,j, α∗, γ∗, θ∗, η∗- некоторые фиксированные, но не обязательно им

равные, значения индексов m, β, i^∗, j^∗, α, γ, θ, η соответственно. Будем счи-

тать, что Ξ₀(d,k,l) = -Λ(d,k,⃗l). Кроме того, образуем трехвалентный тен-

зор [28]

(

)

(

)

T_iνχ

^V(d,k,l,t)

=Δ_iν

^V(d,k,l,t) Ξχ(d,k,l).

Свернем данный тензор по второму и третьему индексу и обозначим полу-

ченную свертку через T^∗iνχ(d,k,⃗l,t). Тогда система РДУ (1) примет вид

(

)

dV (d,k,l,t)

(3)

=T^∗iνχ

^V(d,k,l,t)

+ E(d,k,l).

Как следует из системы (3), ее решение можно представить в виде

⎛

∫

(

)

l)t ⎝V₍d,k,

^V(d,k,l,t) = e-Λ(d,k,

l,0) + eΛ(d,k,

⃗l)xT^∗iνχ

^V(d,k,⃗l,x) dx +

(4)

⎞

[

]

^E(d,k,l)

l)t

⎠_.

1-e-Λ(d,k,

Λ(d,k,l)

Обозначим черезVq(d,k,l,t) приближениеV (d,k,⃗l,t) на q-й итерации, и пусть

Vq+1(d,k,⃗l,t) - решение системы (3), полученное методом последовательных

приближений. Тогда из (4) вытекает, что

⎛

∫

(

)

Vq+1(d,k,l,t) = e-Λ(d,k,l)t ⎝V(d,k,l,0)+ eΛ(d,k,

⃗l)xT^∗iνχ

V_q(d,k,⃗l,x) dx +

(5)

⎞

[

]

^E(d,k,l)

l)t

⎠_.

1-e-Λ(d,k,

Λ(d,k,l)

В качестве начального приближения возьмем стационарное значение дохода

V₀(d,k,l,t)=V (d,k,l)= limV (d,k,⃗l,t), которое удовлетворяет соотношению

t→∞

(

)

(6)

Λ(d,k,l)V (d,k,⃗l) = T∗iνχ

^V(d,k,l,t)

+ E(d,k,l).

107

Для последовательных приближений справедливы следующие утверждения.

Теорема 1. Последовательные приближенияVq(d,k,⃗l,t), q = 0,1,2,... ,

сходятся при t → ∞ к стационарному решению системы уравнений (3).

Теорема 2. Последовательность

V_q(d,k,⃗l,t), q = 0,1,2,..., построен-

ная по схеме (5), при любом ограниченном по t нулевом приближении

V₀(d,k,⃗l,t) сходится при q → ∞ к единственному решению системы урав-

нений (3).

Теорема 3. Каждое последовательное приближениеVq(d,k,⃗l,t), q ≥ 1,

представимо в виде сходящегося степенного ряда

∑

(7)

V_q(d,k,⃗l,t) =

g_ql(d,k,l)tl,

l=0

коэффициенты которого удовлетворяют рекуррентным соотношениям:

gq+1l(d,k,l) =

{

}

(8)

∑

-Λ(d,k,l)

(-1)u+1u!

^V(d,k,l,0)-

T^∗iνχ(g_ql(d,k,l)) ,

Λ(d,k,l

l)u+1

) u=0Λ(d,k,

gq0(d,k,l) =V (d,k,l,0),g0l(d,k,l) =V (d,k,⃗l,0)δl0.

Доказательство теорем 1-3 приведено в Приложении 1.

Cистема уравнений (3) может быть сведена к системе счетного числа ли-

нейных неоднородных обыкновенных дифференциальных уравнений с посто-

янными коэффициентами, которая в матричной форме может быть записана

в виде

dU_i(t)

= Q_i(t) + AU_i(t),

где U^Ti (t) = (U_i(1, t), U_i(2, t), . . . , U_i(L, t), . . .) - искомый вектор ожидаемых

доходов i-той системы, L - номер переобозначенного состояния сети. Данную

систему можно решить прямым методом, используя матричную экспоненту

∫t

U_i(t) = e^AtU_i(0) +

eA(t-τ)Q_i(τ)dτ, или численными методами. Но необхо-

димо помнить, что из-за неограниченности размерности матриц D, Q_i(t) на

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

они имеют специфический вид [24].

Аналогично, как в [22], можно показать, что если вектор Q_i(t) не зависит

от времени, т.е. Q_i(t) = Q_i, то при больших t

U_i(t) = (DU_i(t) + Q_i)t = g_it + U_i(0),

т.е. доход i-й системы линейно зависит от времени. Стационарное решение

для дохода i-системы существует и равно U_i(0), если DU_i(t) + Q_i - нулевой

вектор.

108

3. Нахождение ожидаемых доходов G-сети с сигналами

и групповым удалением заявок

Будем рассматривать открытую G-сеть массового обслуживания с n одно-

линейными системами обслуживания (СМО). В i-ю СМО из внешней среды

поступает простейший поток обычных заявок (положительных) с интенсив-

ностью λ+0i и дополнительный поток сигналов, который также является про-

стейшим с интенсивностью λ(c)0i, i = 1, n. Все поступающие потоки независи-

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

некоторый доход, а доход первой СМО уменьшается соответственно на эту

величину. Длительности обслуживания положительных заявок в i-й СМО

распределены по экспоненциальному закону с параметром μ_i, i = 1, n. После

окончания обслуживания положительной заявки в i-й СМО она направляется

в j-ю СМО с вероятностью p+ij опять как положительная заявка, а с вероят-

∑

ностью p^-ij как отрицательная заявка, и с вероятностью pi0 = 1 - (p+ij + p^-ij)

j=1

уходит из сети, i, j = 1, n.

Если в некоторый момент времени в i-й СМО находится k_i ≥ B_i положи-

тельных заявок, где B_i - целочисленная случайная величина, то при поступ-

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

ло положительных заявок в ней уменьшается на B_i (уничтожается сразу B_i

положительных заявок). Если k_i ≤ B_i, то в i-й СМО не остается заявок. Слу-

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

заявок в i-й СМО и подчиняется произвольному дискретному закону распре-

деления: P {B_i = m} = π_im, m ≥ 1, π_im = 0, m ≤ 0.

В сети циркулируют не только положительные заявки, но и сигналы. Сиг-

нал, поступающий в i-ю СМО, в которой нет положительных заявок, уходит

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

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

сигнал мгновенно перемещает положительную заявку из i-й СМО в j-ю СМО

с вероятностью q_ij, в этом случае сигнал называют триггером; или с вероят-

∑

ностью qi0 = 1 - q_ij сигнал срабатывает как отрицательная заявка и уни-

j=1

чтожает в i-й СМО группу положительных заявок.

Под состоянием сети в момент времени t будем понимать вектор (k, t) =

= (k₁, . . . , k_n, t), где k_i - количество положительных заявок в i-й СМО, кото-

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

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

ходном режиме, зависящие от времени.

Пусть I_i - нулевой вектор размерности n, состоящий из нулей, за исклю-

чением компоненты c номером i , которая равна 1; u(x) - единичная функция

Хевисайда,

^{ 1, x > 0,

u(x) =

0, x ≤ 0.

109

Опишем возможные переходы цепи Маркова в состояние (k, t) за время Δt:

1) из состояния (k - I_j , t), j = i: в этом случае в j-ю СМО за время Δt

поступит положительная заявка с вероятностью λ+oj u(k_j )Δt + o(Δt), j = 1, n,

доход системы S_i в этом случае составит r_i(^k)Δt + v_i(k - I_j , t); если i = j, то

доход системы S_i составит r0i(k - I_i) + v_i(k - I_i, t), где r0i(k - I_i) - доход i-й

системы от данного перехода;

2) из состояния (^k + I_j, t), j = i: при этом положительная заявка уходит из

сети во внешнюю среду или после завершения обслуживания переходит в m-ю

СМО как сигнал, если в ней не было заявок, вероятность такого события рав-

на (μ_jpj0 + μ_jp^-jm(1 - u(k_m)))Δt + o(Δt), m, j = 1, n, доход системы S_i в этом

случае составит r_i(^k)Δt + v_i(^k + I_j , t); если i = j, то доход системы S_i соста-

вит -Ri0(^k + I_i) + v_i(^k + I_i, t), где Ri0(^k + I_i) - доход i-й системы от данного

перехода;

3) из состояния (^k + I_m - I_d, t), m = i, d = j: в данном случае после окон-

чания обслуживания положительной заявки в m-й СМО она направляется

в d-ю СМО снова как положительная заявка или поступивший в m-ю СМО

сигнал мгновенно перемещает положительную заявку из системы m-й СМО в

l-ю СМО, вероятность этого события равна (μ_mp+mdu(k_d) + λom) q_mdu(k_d))Δt+

+o(Δt), m, d = 1, n, доход системы S_i в этом случае составит r_i(^k)Δt+

+v_i(^k + I_m - I_d,t); если m = j, i = d, то доход S_i составит -r_ji(^k +I_j -I_i)+

+v_i(^k + I_j - I_i,t); если k = i, j = d, то доход S_i составит r_ij(k - I_j + I_i)+

+v_i(k - I_j + I_i,t);

4) из состояния (^k + I_j + I_s - I_c, t), s, c, j = i: в этом случае после окончания

обслуживания заявки в j-й СМО она направляется в s-ю СМО как сигнал,

который мгновенно перемещает положительную заявку из s-й СМО в СМО

с номером c; вероятность такого события равна μ_jp^-jsq_scu(k_c)Δt + o(Δt), до-

ход системы S_i в этом случае составит r_i(^k)Δt + v_i(^k + I_j + I_s - I_c, t); при

j = i доход составит -r_ics(^k) + v_i(k + I_j + I_s - I_c,t); при s = i доход составит

r_jci(^k) + v_i(^k + I_j + I_s - I_c,t); при c = i доход составит r_jis(^k)+v_i(^k+I_j +I_s -

- I_c,t);

5) из состояния (^k + mI_j, t), j = i: в данном случае сигнал извне поступает

в j-ю СМО и уничтожает в ней группу положительных заявок величиной m;

вероятность такого события равна λ(c)ojqj0π_jmΔt + o(Δt); доход системы S_i в

этом случае составит r_i(^k)Δt + v_i(^k + mI_j , t); если i = j, то доход системы S_i

составит -r_i(^k + mI_i)Δt + v_i(^k + mI_i, t), где -R_i(^k + mI_i) - доход i-й систе-

мы от данного перехода;

6) если сигнал поступает извне в j-ю СМО, j = i, в которой нет заявок,

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

этого события равна

∑

λ(c)ojqj0(1 - u(k_j))π_jm

P(k + rI_j)Δt + o(Δt), i,j = 1,n,

r=1

110

доход системы S_i в этом случае составит

^∑ r_i(k + rI_j)Δt + v_i(k + rI_j,t); ес-

r=1

∑

ли i = j, то

R_i(^k + rI_j)Δt + v_i(^k + rI_j,t);

r=1

7) из состояния (^k + I_j + mI_s, t), j, s = i: в этом случае после окончания

обслуживания заявки в j-й СМО она направляется в s-ю СМО как сигнал,

который уничтожает случайную группу положительных заявок; вероятность

такого события равна μ_j p^-jsqs0π_smΔt + o(Δt), j, s = 1, n, доход системы S_i в

этом случае составит -r_i(^k + I_j + mI_s)Δt + v_i(^k + I_j + mI_i, t), при i = j он

будет равен r_is(^k + I_i + mI_s)Δt + v_i(^k + I_j + mI_i, t), а при s = i равен R_ji(^k +

+ I_j + mI_i)Δt + v_i(k + I_j + mI_s,t);

8) если же после окончания обслуживания заявки в j-й СМО она направ-

ляется в s-ю СМО как сигнал, который не застает в этой СМО заявок, то

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

события равна

∑

μ_jp^-js(1 - u(k_j))qs0π_sm

P(k + I_j + rI_s)Δt + o(Δt), i,j,s = 1,n;

r=1

∑

доход системы S_i в этом случае при j = i составит

[r_is(^k + I_i + rI_s)Δt +

r=1

∑

+v_i(^k + I_i + mI_s,t)], при s = i он составит

[-R_ji(^k + I_i + rI_s)Δt + v_i(^k +

r=1

+ I_i + mI_s,t)];

9) из состояния (k, t) при этом в каждую СМО S_i не поступают положи-

тельные сигналы и в них за время Δt не обслужилось ни одной положи-

тельной заявки или сигнал поступает в пустую систему; вероятность этого

события равна

∑[

(

)

]

λ+oj + λ(c)

+ μ_j u(k_j) Δt + o(Δt),

j=1

доход системы S_i в этом случае составит r_i(^k)Δt + v_i(k, t),

10) из остальных состояний: с вероятностью o(Δt).

В данном случае система РДУ для ожидаемых доходов имеет вид (3), где

E_i(d,k,⃗l) = Ei(k) = ri(k) + λ+oiu(ki)r0i(k - Ii) -

(

)

μ_ipi0 + μ_ip^-im(1 - u(k_m))

Ri0(^k + I_i) -

(

)

− μ_ip+isu(k_s) + λ(c)oiq_isu(k_s) r_is(^k + I_i - I_s) -

111

∑

(c)

-μ_ip^-qscu(kc)rics(k) - λo

qj0

π_jmR_i(^k + mI_i) -

m=0

∑

-λ(c)qj0(1 - u(ki))

π_jm

R_i(^k + rI_i) -

m=0

r=1

∑

-μ_ip^-isqs0

π_smR_ji(^k + I_j + mI_i) +

m=0

∑

+μ_jp^-(1 - u(kj ))qs0

π_sm

r_is(^k + I_i + rI_s,t) -

m=0

r=1

∑

- μ_ip^-isq_scu(k_c)r_jsi(^k) - μ_jp^-qs0

π_sm

r_is(^k + mI_s),

j,s=1

m=0

r=1

⎛

(

)

T_iνχ

^V(d,k,l,t)

=δ_i∗j∗δ⃗d⃗1

δ_θηδ⃗l⃗0 ⎝δb1δ_αiδ_γj λ+0ju(k_j) +

)

(

)

∑

+ μ_jp+jiu(k_i) (1 - δij) +

(1 - δ_si)(μ_ipi0 + μ_ip^-is(1 - u(k_s)))

s=1

∑

(1 - δ_ij )λ(c)0jqj0π_jm +

(1 - δ_js)μ_j p^-jsqs0π_sm +

j=1

s=1

⎞

+ u(m + 1)μ_ip^-is(1 - u(k_s))qs0π_sm + δb1δ_αiδ_βj δ_γsμ_ip^-ijq_jsu(k_s)⎠ ×

(

)

×v_i

^d+I_i∗ -I_j∗,k

I_α +

I_β -

I_γ,l

I_θ

I_η,t

где1n - вектор размерности n, состоящий из единиц, δ_ij - символ Кронекера.

Сходимость ряда (2) следует из неравенства

(

)_∗

Ξ_χ(d,k,⃗l)12Ψr+n

⎛

(

)

=δ_i∗j∗δ_⃗

δ_θηδ_⃗

⎝δb1δ_αiδ_γjδm1 λ+0ju(k_j) + μ_jp+jiu(k_i) (1 - δij ) +

d¹n

l⁰

112

)

∑

(

)

+δm1

(1 - δ_si)

μ_ipi0 + μ_ip^-is(1 - u(k_s))

s=1

∑

(1 - δ_ij )λ(c)0jqj0π_jm +

(1 - δ_js)μ_j p^-jsqs0π_sm +

j=1

s=1

⎞

+ μ_ip^-is(1 - u(k_s))qs0u(m + 1)π_sm + δb1δ_αiδ_βjδ_γsμ_ip^-ijq_jsu(k_s)⎠ ≤

⎛

(

∑

(

)

≤

⎝δαiδ_γj λ+0ju(k_j) + μ_jp+jiu(k_i)

(1 - δ_ij ) +

α,β,γ,

)

∑

(

)

(1 - δ_si)

μ_ipi0 + μ_ip^-is(1 - u(k_s))

s=1

∑

(1 - δ_ij )λ(c)0jqj0π_jm +

(1 - δ_js)μ_j p^-qs0

π_sm +

α,β,γ, m=0 b=0 j=1

s=1

m=1

⎞

∑

+ μ_ip^-is(1 - u(k_s))qs0

π_sm + δb1δ_αiδ_βjδ_γsμ_ip^-ijq_jsu(k_s)⎠ .

m=1

∑

Но π_sm = 1, так как сигнал, действующий как отрицательная заявка, все-

m=1

гда уничтожает какое-то ненулевое количество положительных заявок. По-

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

Пример 1. Рассмотрим открытую G-сеть с n = 5 однолинейными СМО.

Вероятности поступления положительных и отрицательных заявок в i-ю си-

стему p+0ic, p-0ic равны соответственно p-01 = 0,3; p-02 = 0,1; p-0i = 0,3; i = 3, 5,

∑

p+0i = 0,2, i = 1,5,

p-0i = 1,

p+0i = 1. Интенсивности входного потока по-

i=1

ложительных заявок равны λ⁺ = 120, λ^- = 100. Интенсивности обслужива-

ния заявок различных классов равны: μ₁ = 35, μ₂ = 42, μ₃ = 51, μ₄ = μ₅ = 50.

Пусть вероятности p+ij равны соответственно: p+ij = p^-ij = 0,12; i = j; pi0 = 0,04,

i = 1,5.

Доходы i-й системы равны соответственно r_i(^k) = 2, r0ic(^k) = 2, Ric0(^k) = 4,

r_icjs(^k) = 4, i,j = 1,7, s,c = 1,3. На рисунке изображено изменение доходов

первой СМО сети в зависимости от времени, полученное с помощью компью-

тера с использованием (7), (8), при этом начальным состоянием сети было

(1, 1, 1, 1, 1). Вектор доходов в начальный момент времени^V (k, 0) был нуле-

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

метром 5 для всех СМО.

113

Для нахождения последовательных приближений расчеты проводились до

k^∗)| ≤ ε, где ε = 10-6.

итерации l^∗, при которой выполняется условие |d(d)q∗l

k^∗ : d(d)ql

k^∗) = max |d(d)ql(^k)|. Согласно теоремам 1 и 2 решение системы (1)

можно получить методом последовательных приближений на итерации q^∗,

при которой |Vq∗₊₁(k, t) -Vq∗ (k, t)|, где |Vq∗₊₁(k, t) -Vq∗ (k, t)| - вектор-стол-

бец размерности n c компонентами |v_iq∗₊₁(k, t) - v_iq∗ (k, t)|, v_iq∗ (k, t) - прибли-

жение ожидаемого дохода i-й СМО, полученное на итерации q^∗.

Замечание 1. Отметим, что в [29] описывается метод решения бесконеч-

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

циентами, основанный на применений преобразования Лапласа к построению

решений. В [30] предложено для нахождения решения дифференциально-

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

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

находятся достаточно сложно. В данной статье для нахождения ожидаемых

доходов в системах открытых марковских СеМО предложена методика реше-

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

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

приближение представимо в виде сходящегося степенного ряда, коэффици-

енты которого связаны рекуррентными соотношениями, поэтому их удобно

находить с помощью компьютера. Это позволяет находить ожидаемые дохо-

ды систем сети за приемлемое процессорное время. В [31] с помощью разра-

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

и положительными заявками и доходами показано, что данный алгоритм об-

ладает достаточно высокой точностью.

4. Заключение

Проведено исследование в переходном (нестационарном) режиме откры-

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

от переходов между состояниями сети зависят от ее состояний. Рассмотрена

обобщенная система РДУ для ожидаемых доходов в системах сети, состоя-

щая из счетного числа таких уравнений. Для решения системы предложено

применить метод последовательных приближений, совмещенный с методом

рядов.

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

ся к стационарному ожидаемому доходу, вид которого указан в статье, а сама

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

мы РДУ. Любое последовательное приближение представимо в виде сходя-

щегося степенного ряда с бесконечным радиусом сходимости, коэффициенты

которого удовлетворяют рекуррентным соотношениям, что является удобным

при расчетах на компьютерах. Полученные результаты проиллюстрированы

примером.

Дальнейшие исследования могут быть связаны с нахождением ожидае-

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

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

рядков.

114

ПРИЛОЖЕНИЕ

Доказательство теоремы 1. Доказательство проведем методом ма-

тематической индукции. Для первого приближения имеем:

⎛

⎞

∫

(

)

l)t ⎝V₍d,k,

V₁(d,k,l,t) = e-Λ(d,k,

l,0) + eΛ(d,k,

⃗l)xT∗0iνχ

^V(d,k,⃗l,x) dx⎠ +

[

]

^E(d,k,l)

l)t

1-e-Λ(d,k,

Λ(d,k,l)

⎛

⎞

(

)∫ t

=e-Λ(d,k,l)t ⎝V(d,k,

⃗l,0) + T∗0iνχ

^V(d,k,l)

eΛ(d,k,l)xdx⎠ +

[

]

^E(d,k,l)

l)t

1-e-Λ(d,k,

Λ(d,k,l)

(

⁾1-e-Λ(d,k,⃗)t

l)t

=e-Λ(d,k,

^V(d,k,⃗l,0) + T∗0iνχ

^V(d,k,

l,x)

Λ(d,k,l)

)

[

]

^E(d,k,l)

l)t

1-e-Λ(d,k,

-→

Λ(d,k,l)

t→∞

(

)

-→

T∗0iνχ

^V(d,k,l,x)

+ E(d,k,l)

= V(d,k,l).

^t→∞ Λ(d,k,l)

Отcюда следует, что при q = 1 теорема выполняется. Предположим, что

утверждение теоремы справедливо до q-й итерации. Используя (4) и правило

Лопиталя, будем иметь:

lim

Vq+1(d,k,⃗l,t) =

t→∞

⎛

⎞

∫

(

)

^E(d,k,l)

= lim

⎝V₍d,k,l,0)+

eΛ(d,k,

⃗l)xT^∗qiνχ

^V(d,k,⃗l,x) dx⎠+

l)t

^t→∞ eΛ(d,k,

Λ(d,k,l)

d,k,

e^Λ(

l)xT^∗

(^V (d,k,l,t))

^E(d,k,l)

qiνχ

= lim

^t→∞ Λ(d,k,l)eΛ(d,k,

Λ(d,k,l)

T^∗qiνχ(V (d,k,l,t))

^E(d,k,l)

= lim

= V(d,k,l).

^t→∞ Λ(d,k,l)

Λ(d,k,l)

Поэтому теорема справедлива и для q + 1. Тогда, используя метод математи-

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

Доказательство теоремы 2. ПосколькуV0(d,k,⃗l,t) - ограниченная

по t функция, то в силу (4)V1(d,k,⃗l,t) также ограничена, поэтому



(Π.1)

^V

1(d,k,l,t) -V0(d,k,l,t)≤C

(d,k,l),

115

где |V1(d,k,l,t) -V0(d,k,⃗l,t)| - вектор-столбец размерности n c компонента-

ми |vi1(d,k,l,t) - vi0(d,k,l,t)|, vi1(d,k,l,t), vi0(d,k,l,t) - приближение ожи-

даемого дохода i-й СМО на первой и нулевой итерациях соответственно,

i = 1,n,

^C(^k) - некоторый не зависящий от t вектор-столбец размерности,

как и^V (d,k,⃗l,t), равный n.

Покажем, что выполняется неравенство



tq-1

(Π.2)

^V

q(d,k,l,t) -Vq-1(d,k,l,t)≤C

^∗ηq-1

(q - 1)!

где

(

)_∗

maxη(d,k,l) = η, maxC(d,k,l) =C∗, η(d,k,l) = Ξχ(d,k,⃗l)12Ψr+n

d,k,l

Здесь и нужна сходимость ряда (2).

Из (Π.1) следует, что при q = 1 это неравенство выполняется. Предполо-

жим, что оно выполняется при q = N, и покажем, используя (4), его спра-

ведливость при q = N + 1. Имеем:



(Π.3)

^V

N+1(d,k,

l,t) -VN(d,k,l,t)≤

⎛

⎞

∫

(

(

(

)

(

))∗

)



≤e-Λ(d,k,

l)t ⎝ eΛ(d,k,

l)x Ξχ

d,k,l)

ΔNiν

d,k,l, t)

- ΔN-1iν

d,k,l, t)



⎠≤

(

)

∫

xN-1

l)t

l)x

≤ C^∗η^N e-Λ(d,k,

eΛ(d,k,

(N - 1)!

Из неравенства e-Λ(d,k,

l)te-Λ(d,k,

l)x ≤ 1, x ∈ [0, t], следует, что

∫t

∫

xN-1

t^N

l)t

l)x

e-Λ(d,k,

dx ≤

dx =

(N - 1)!

поэтому из (Π.3) получаем, что неравенство (Π.2) имеет место. Поскольку

(

)

∑

(

)

lim

V_q(d,k,⃗l,t) = lim

V₀(d,k,l,t)+

Vq+1(d,k,l,t)-Vq(d,k,l,t)

q→∞

n=0

∑(

)

= V₀(d,k,⃗l,t) +

Vq+1(d,k,l,t) -Vq(d,k,l,t)

≤

q=0

∑

≤ V₀(d,k,⃗l,t) +

C^∗η^q t^q

= C^∗e^ηt,

q=0

то предел последовательностиVq(d,k,⃗l,t), q = 0,1,2,... , существует. Обозна-

чим его черезV∞(d,k,

l,t). ПодставляяV∞(d,k,l,t) в (2) вместоV (d,k,l,t),

116

видим, чтоV∞(d,k,

⃗l,t) является решением системы уравнений (1), удовле-

творяющим начальным условиямV∞(d,k,l,0) =V (d,k,⃗l,0) согласно преды-

дущей теореме.

Предположим, что существует другое решение системы уравнений (1)

^W(d,k,⃗l,t). Тогда для него справедливо соотношение (4), если заменить в нем

^V(d,k,l,t), T∗iνχ(V (d,k,⃗l,t)) соответственно на

^W(d,k,l,t), T∗iνχ(W(d,k,⃗l,t)).

Аналогично, как при доказательстве неравенства (Π.2), можно показать, что



q-1



выполняется неравенство

^V

q(d,k,l,t)-W(d,k,l,t)≤Mηq-1

, где M -

(q - 1)!

некоторая константа. Правая часть этого неравенства стремиться к нулю, как

∑

t^q

общий член сходящегося ряда

Mη^q

= Me^ηt, поэтому lim

V_q(d,k,⃗l,t) =

q→∞

q=0

= W(d,k,⃗l,t). Но ранее уже получили, что limVq(d,k,l,t) =V (d,k,⃗l,t), по-

q→∞

этому^W (d,k,l,t) =V (d,k,⃗l,t), что и доказывает единственность решения си-

стемы уравнений (3).

Доказательство теоремы 3. Покажем, что коэффициенты степен-

ного ряда (7) удовлетворяют рекуррентным соотношениям (8). Подставим

последовательные приближения (7) в соотношение (4). Тогда с учетом того,

что

[

]l+1

∫t

∑

[-Λ(d,k,l)]l

l)t

e-Λ(d,k,

eΛ(d,k,l)xxldx =

l = 0,1,2,... ,

Λ(d,k,l)

j=l+1

получаем

∑

g_ql(d,k,

l)t^l =e-Λ(d,k,l)t V(d,k,

l,0) +

l=0

[

]

(

)

^E(d,k,l)

l)t

1-e-Λ(d,k,

+T^∗

g_ql(d,k,l)

iνχ

Λ(d,k,l)

Используя (8), этот ряд можно записать в виде

∑

(

)

T_iνχ

g_ql(d,k,l)

g_ql(d,k,⃗l)tl =

l=0

[

]

^E(d,k,l)

l)t V₍d,k,

l)t

=e-Λ(d,k,

l,0) -

1-e-Λ(d,k,

Λ(d,k,l)

[

]l+1

∑

[-Λ(d,k,l)]u

t^u.

Λ(d,k,l)

l=0

u=l+1

117

Поменяв местами индексы суммирования и разлагая e-Λ(d,k,l)t в ряд по сте-

пеням t, будем иметь

∑

^E(d,k,l)

(Π.4)

g_ql(d,k,⃗l)tl =

Λ(d,k,l)

l=0

[

]_l

{

∑

-Λ(d,k,l)

^E(d,k,l)

^V(d,k,⃗l,0) -

Λ(d,k,l)

l=0

⎫

∑

(

)

⎬

(-1)u+1u!

[

]_u T^∗

g_ql(d,k,⃗l) tl

iνχ

⎭

u=0

-Λ(d,k,l)

Если в выражении (Π.4) приравнять коэффициенты при t^l, то получим

соотношения (8) для коэффициентов ряда (7).

Доказательство того, что радиус сходимости степенного ряда (7) ра-

вен +∞, можно провести, используя формулу Коши-Адамара, аналогично

как в [32].

СПИСОК ЛИТЕРАТУРЫ

1. Crabil T. Optimal Control of a Service Facility with Varible Exponential Service

Times and Constant Arrival Rate // Manage. Sci. 1972. No. 18. P. 560-566.

2. Foschini G. On Heavy Traffic Diffusion Analysis and Dynamic Routing in Packet

Switched Networks // Comput. Perfomance. 1977. No. 10. P. 499-514.

3. Stidham S., Weber R. A Survey of Markov Decision Models for Control of Networks

of Queue // Queueing Syst. 1993. No. 3. P. 291-314.

4. Matalytski M., Pankov A. Analysis of the Stochastic Model of the Changing of

Incomes in the Open Banking Network // Comput. Sci. 2003. V. 3. No. 5. P. 19-29.

5. Matalytski M., Pankov A. Incomes Probabilistic Models of the Banking Network //

Scientific Res. Institute Math. Comput. Sci. Czestochowa Univers. Technol. 2003.

V. 1. No. 2. P. 99-104.

6. Маталыцкий М.А. О некоторых результатах анализа и оптимизации сетей Мар-

кова с доходами и их применении // АиТ. 2009. № 10. C. 97-113.

Matalytski M. On Some Results in Analysis and Optimization of Markov Networks

with Incomes and Their Application // Autom. Remote Control. 2009. V. 70. No. 10.

P. 1683-1697.

7. Ховард Р. Динамическое программирование и марковские процессы. М.: Сов.

радио, 1964.

8. Gelenbe E. Product form Queueing Networks with Negative and Positive

Customers // J. App. Probab. 1991. V. 28. P. 656-663.

9. Jackson J.R. Networks of Waiting Lines // Oper. Res. 1957. V. 5. No. 4. P. 518-521.

10. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных

сетях. М.: Наука, 1989.

11. Ивницкий В.А. Теория сетей массового обслуживания. М.: Физматлит, 2004.

118

12.

Малинковский Ю.В. Критерий представимости стационарного распределения

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

заявок в форме произведения // АиТ. 1991. № 4. С. 75-83.

Malinkovsky Yu.V. A Criterion for the Representability of the Stationary

Distribution of the States an Open Markov Queueing Network with Different

Customer Classes in the Form of a Product // Autom. Remote Control. 1991. V. 52.

No. 4. P. 503-509.

13.

Serfozo R. Introduction to stochastic networks. N.Y.: Springer-Verlag, 1999.

14.

Gelenbe E., Schassberger R. Stability of G-networks // Prob. Engin. Inform. Sci.

1992. V. 6. Is. 1. P. 271-276.

15.

Gelenbe E. G-networks: A Unifying Model for Neural and Queueing Networks //

Ann. Oper. Res. 1994. V. 48. P. 433-461.

16.

Бочаров П.П., Вишневский В.М. G-сети: развитие теории мультипликативных

сетей // АиТ. 2003. № 5. С. 46-74.

Bocharov P.P., Vishnevski В.М. G-networks: Development of the Theory of

Multiplicative Networks // Autom. Remote Control. 2003. V. 84. No. 5. P. 714-

739.

17.

Fourneau J.N., Gelenbe E., Suros R. G-networks with Multiple Classes of Negative

and Positive Customers // Theor. Comp. Sci. 1996. V. 155. P. 141-156.

18.

Gelenbe E., Labed A. G-networks with Multiple Classes of Signals and Positive

Customers // Eur. J. of Oper. Res. 1998. V. 108. No. 2. P. 293-305.

19.

Matalytski M. Analysis of G-network with Multiple Classes of Customers at Transient

Behavior // Prob. Engin. Inform. Sci. 2018. P. 1-14. doi:10.1017/S0269964818000086

20.

Matalytski M. Finding Non-Stationary State Probability of G-networks with Signal

and Customers Batch Removal // Prob. Engin. Inform. Sci. 2017. V. 31. No. 4.

P. 346-412.

21.

Маталыцкий М.А. Анализ и прогнозирование ожидаемых доходов в марковских

сетях с ограниченным временем ожидания заявок // АиТ. 2015. № 6. C. 75-90.

Matalytski M. Analysis and Forecasting of Expected Incomes in Markov Networks

with Bounded Waiting Time for Claims // Autom. Remote Control. 2015. No. 6.

P. 1005-1017.

22.

Маталыцкий М.А. Анализ и прогнозирование ожидаемых доходов в марковских

сетях с ненадежными системами обслуживания // АиТ. 2015. № 12. C. 108-120.

Matalytski M. Analysis and Forecasting of Expected Incomes in Markov Networks

with Unreable Servicing Systems // Autom. Remote Control. 2015. No.

12.

P. 2179-2189.

23.

Маталыцкий М.А. Прогнозирование ожидаемых доходов в марковских сетях с

положительными и отрицательными заявками // АиТ. 2017. № 5. С. 56-70.

Matalytski M. Forecasting Anticipated Incomes in the Markov Networks with Positive

and Negative Customers // Autom. Remote Control. 2017. V. 78. No. 5. P. 815-825.

24.

Копать Д.Я., Маталыцкий М.А. Нахождение ожидаемых доходов в сети с по-

ложительными и отрицательными заявками различных типов // Вестн. ГрГУ.

Сер. 2. 2018. № 1. С. 132-144.

25.

Копать Д.Я., Науменко В.В., Маталыцкий М.А. Нахождение ожидаемых до-

ходов в сети массового обслуживания со случайным временем ожидания поло-

жительных и отрицательных заявок // Веcтн. ГрГУ. Сер. 2. 2017 . Т. 7. № 1.

С. 147-153.

119

26. Маталыцкий М.А., Копать Д.Я. Нахождение ожидаемых доходов в сети с

разнотипными положительными и отрицательными заявками // Веcтн. ГрГУ.

Сер. 2. 2018. Т. 8. № 2. С. 129-140.

27. Matalytski M., Kopats D. Analysis of the Network with Multiple Classes of Positive

Customers and Signals at a Non-Stationary Regime // Prob. Engin. Inform. Sci.

2018. P. 1-13. doi:10.1017/S0269964818000219

28. Рашевский П. Риманова геометрия и тензорный анализ. М.: Наука, 1967.

29. Валеев К.Г., Жаутыков О.А. Бесконечные системы дифференциальных урав-

нений. Алма-Ата: Наука, 1974.

30. Коробейник Ю.Ф. Дифференциальные уравнения бесконечного порядка и бес-

конечные системы дифференциальных уравнений // Изв. АН СССР. Сер. мат.

1970. Т. 34. № 4. P. 881-922.

31. Matalytski M., Naumenko V. Simulation Modeling of HM-networks with

Consideration of Positive and Negative Messages // J. Appl. Math. Comput. Mechan.

2015. V. 14. No. 2. P. 49-60.

32. Маталыцкий М.А., Науменко В.В. Стохастические сети с нестандартным пере-

мещением заявок. Гродно: Изд-во ГрГУ, 2016.

Статья представлена к публикации членом редколлегии Б.М. Миллером.

Поступила в редакцию 28.12.2017

После доработки 24.01.2019

Принята к публикации 07.02.2019

120