Analysis of the RQ-systems by the asymptotic semi invariants methods..pdf За последние годы выявилась необходимость разработки методов исследова-ния RQ-систем. В частности, стремление максимально использовать возможности современных вычислительных машин, систем связи, технологического оборудо-вания приводит к своеобразным и интересным новым задачам в теории RQ-систем.В теории массового обслуживания аналитическое решение обладает рядом по-ложительных качеств: оно не привязано к определенным числовым значениям па-раметров потока и системы обслуживания, позволяет находить оптимальные ре-шения и делать общие заключения. Однако во многих случаях аналитическое ре-шение получить затруднительно, поскольку задача настолько сложна, что реше-ние составленных уравнений, к которым сводится задача, представляет собой практически неразрешимую задачу [1, с. 249]. Альтернативным подходом являет-ся применение метода асимптотических семиинвариантов для исследования таких задач [2, т. 13, с. 88].1. Постановка задачиРассмотрим RQ-систему, то есть однолинейную систему массового обслужи-вания с источником повторных вызовов (ИПВ), на вход которой поступает про-стейший поток заявок с интенсивностью λ. Считается, что требование, заставшее прибор свободным, занимает его для обслуживания в течение случайного време-ни, распределенного по экспоненциальному закону с параметром μ. Если прибор занят, то поступившая заявка переходит в источник повторных вызовов, где осу-ществляет случайную задержку, продолжительность которой имеет экспоненци-альное распределение с параметром σ. Из ИПВ после случайной задержки заявка вновь обращается к прибору с повторной попыткой его захвата. Если прибор сво-боден, то заявка из ИПВ занимает его на случайное время обслуживания, если же он занят, то заявка мгновенно возвращается в источник повторных вызовов для реализации следующей задержки случайной продолжительности [3, с. 272]. Необ-ходимо найти распределение вероятностей числа заявок в источнике повторных вызовов.86А.А. Назаров, И.А. СеменоваПусть i(t) - число заявок в ИПВ, а l(t) - определяет состояние прибора следующим образом: ) 0, если прибор свободен, ( { 1, если прибор занят.ОбозначимP{l(t) = l,i(t) = i} = P(l,i,t)вероятность того, что прибор в момент времени t находится в состоянии l и в источнике повторных вызовов находится i заявок. Процесс {l(t),i(t)} изменения во времени состояний описанной системы является марковским.Для распределения вероятностей P(l,i,t) состояний {l,i} рассматриваемой RQ-системы дифференциальные уравнения Колмогорова [4, с. 22], имеют видdP(0,i,t =-(! + ic:)P(0,i,t) + yP(1,i,t),1 i(1)(X + ]i)P(1,i,t) + XP(0,i,t) + a(i + 1)P(0,i + 1,t) + XP(1,i-1,t).dt2. Метод асимптотических семиинвариантовПрименяя систему (1) для стационарного распределения P(l,i,t) = P(l,i), составим систему уравнений, определяющих характеристические функции [5, с. 105]соH(l,u) = i,ejuiP(l,i) =P{l(t) = l}M{ ejui(t) \l(t) = l} ,=0где j =-1 - мнимая единица. Получим систему уравнений(2)-егj5H(0,u) =-H(0,u) + цH(1,u), дuaje -ju дH(0,u =хH(0,u) + (х( e ju -1 ) -|а) H(1,u),решение {H(0,u), H (1,u)} которой удовлетворяет условию нормировкиH(0,0) + H(1,0) = 1.Систему (2) будем решать методом асимптотического анализа в условии большой задержки в ИПВ, то есть при условии σ→0.Для компактной записи вычислений дальнейшие исследования будем проводить в матричном виде [6, с. 83]. Обозначив вектор-строку H ( u)={H (0,u),H (1 ,u)}, систему (2) перепишем в видеvj^PA(ju) = H(u)B(ju); дuH(0)E = 1,где E - единичный вектор-столбец, а равенство (4) - условие нормировки.Исследование RQ-систем методом асимптотических семиинвариантов87Здесь матрицы A (ju) и B(ju) можно записать в виде0 0v!ц, Я.(e - ju-1)-ц,v=0 v!11 , A=(0 (-1)^-^Л (0 0A(0)= 0 0>A = 0 0), B (0) = W -ц>B [0 Ч-1)2.1. Асимптотика первого порядкаДля нахождения асимптотики первого порядка обозначим σ=ε, и в уравнении (3) выполним замены [7, с. 130]u = aw, H(u) = F1(w,e) . Тогда уравнение (3) примет видjdF^e) A(jew) = F1(w,s)B(jew),Owа равенство (4) запишется следующим образом:F1(0,e)E = 1.Теорема 1. Предельное, при ε→0 значение F1(w) решения F1(w,e) уравнения (5), удовлетворяющего условию (6), имеет видF1(w) = R-ejwC1 ,где вектор R является решением системыR(B0+k1A0) = 0,удовлетворяющим условию нормировкиRE = 1, а величина κ 1 является решением нелинейного уравненияR(B1+K1A1)E = 0,где вектор R=R(κ1) зависит от κ 1 и является решением системы (7), (8).Доказательство. В задаче (5), (6) выполним предельный переход при ε→0, получим системуF 1 ( w ) A0=F1(w)B0, owрешение F1(w) которой запишем в виде произведенияF1(w)= R1 (w) = R- exp {jwk1 }(9)вектора R, определяемого системойRE = 1,и скалярной функции Φ 1(w), вид которой определен равенством (9). Значения величины κ 1 определим следующим образом.88А.А. Назаров, И.А. СеменоваСложим все уравнения системы (5), умножив это равенство справа на единичный вектор-столбец E, получим равенствоj 1 , ) A(jεw)E = F1 (w,ε)B(jεw)E,∂wв котором разложим матрицыA (jεw) = A0+ jεwA1 +Ο(ε2), B (jεw) = B0+ jεwB1 + Ο (ε2 ), получимj 1 w , ) jεwA1 E = F1 (w,ε)jεwB 1 E + Ο (ε2 ) .∂wВыполнив здесь предельный переход при ε→0 и подставляя сюда произведение (9), получим нелинейное скалярное уравнение относительно величины κ 1R(B1+κ1A1)E = 0,где вектор R=R(κ 1) определяется системой (10).Теорема доказана.Найденные функции F1(w), служат основой построения асимптотики первого порядка.Определение. Функцию{ κσ 1}h1(u) = exp { jбудем называть асимптотикой первого порядка характеристической функции H ( u)=H (0,u)+H (1 ,u) числа заявок i(t) в источнике повторных вызов, а величину κ 1/σ - асимптотическим семиинвариантом первого порядка.2.2. Асимптотика второго порядкаДля нахождении асимптотики второго порядка в уравнении (3) выполним заменуH(u) = exp j - κ 1 } H2(u), тогда для вектор-функции H2(u) получим уравнениеσ j ∂ H 2(u) = H 2 (u){B(ju)+κ 1 A(ju)} ,(∂ uрешение H2(u) которого удовлетворяет условиюH2(0)E = 1. Теперь, в системе (12), (13) обозначим σ = ε 2 и выполним заменыu = εw, H2(u) = F2(w,ε). Получим задачуjε ∂F2{J^A(jεw) = F2 (w,ε){B(jεw) + κ 1A(jεw)} ;(14)∂wF2(0,ε)E = 1.Исследование RQ-систем методом асимптотических семиинвариантов89Теорема 2. Предельное, при ε→0 значение F2(w) решения F2(w,ε) уравнения (14), удовлетворяющего условию (15), имеет видF2(w) = R-exp\2K2\где вектор R определен в предыдущей теореме, а величина κ2 определяется равенством -{g 1(B1+^A)E+12R(B2+vi1A2)E}g(B1+K1A1)E + RA1Eв котором векторы g и g1 являются произвольными частными решениями следующих систем уравнений:g(B0+K1A0) + RA0=0,g1(B0+K1A0) + R(B1+K1A1) = 0.Доказательство теоремы выполним в три этапа [9, с. 130]. Этап 1. В задаче (14), (15) выполним предельный переход при ε→0, получим систему{F2(w)(B0+K1A0) = 0,F2(0E = 1,решение F2(w) которой запишем в виде произведенияF2(w) = R02(w) = R-exp\( jw )K2\,где вектор R определен системой (10), а значение величины κ2 определим ниже. Этап 2. Решение F2(w,ε) системы (14) запишем в виде разложенияF2 (w, e) = {R + jewf1 (w)} Ф2 (w) + О(e2) =которое подставим в систему (14), получим равенствоjej2wK2RA (jew) = {R + jewf1 (w)} {B(jew) + yl1A (jew)} + О (е2 ) . Подставляя сюда разложение матриц A(jεw) и B(jεw): A (jew) = A0 + jewA1 + О (е2 ) ,B (jew) = B0+ jewB1 +o(e2), и принимая во внимание систему R (B0+ κ 1 A0)=0, запишем равенство-jewK2RA0 ={R + jewf1 (w)} {B0 + к1 A 0 + jew [B1 + к1 A 1 ]} + О (е2 ) == jewR (B 1 + K1 A 1 ) + jewf1 (w) (B0 + к1 A0) + О (е2 ) , из которого получим систему уравненийf1(w)(B0+K1A0) + R(B1+K1A1) + K2RA0=090А.А. Назаров, И.А. Семеноваотносительно вектора f 1( w). Решение f1(w) этой системы найдем в видеf1(w) = G1(w)R + f1,где G1(w) - произвольная скалярная функция, а вектор f 1 является решением системы уравненийf1(B0+K1A0) + R(B1+K1A1) + K2RA0=0.Решение f1 этой системы запишем в виде суммыf1=g1+K2g,где векторы g и g1 являются решениями системg(B0+K1A0) + RA0=0,g1(B0+K1A0) + R(B1+K1A1) = 0.Решение каждой из этих систем содержит слагаемое вида C·R, которое можно включить в первое слагаемое G1(w)R разложения (19), поэтому решениями g и g1 систем (22) могут быть любые частные решения этих неоднородных систем.Этап 3. Для нахождения значения величины κ2 сложим все уравнения системы (14), домножив это равенство справа на единичный вектор E, получимjeF 2 ( w ,I) a (jew) E = F2 (w,e) {B (jew) + к1 A (jew)} E .dwПодставляя сюда разложение матриц A(jεw) и B( j εw), разложение (18), а также применяя равенство (11), получим равенствоf1(w)(B1+K1A1)E + 12R(B2+K1A2)E + K2RA1E = 0.(23)Тогда, в силу равенства (19) и опять же равенства (11), равенство (23) можно переписать в виде(G1(w)R + f1)(B1+K1A1)E + 12R(B2+K1A2)E + K2RA1E == f1(B1+K1A1)E + 12R(B2+K1A2)E + K2RA1E = 0.(24Подставляя сюда разложение (21), получим(g1+K2g)(B1+K1A1)E + 12R(B2+K1A2)E + K2RA1E = 0,откуда найдем значение величины κ2 в виде-{g1(B1+K1A1)E + 12R(B2+K1A2)E}2g(B1+K1A1)E + RA1Eсовпадающим с (16).Таким образом, для нахождения величины κ2 в разложении (18) достаточно ограничиться постоянными векторами f 1, то есть разложение (18) находить в видеопределяя этот вектор решением системы (20).Теорема доказана.Найденные функции F2(w), служат основой построения асимптотики второго порядка.Исследование RQ-систем методом асимптотических семиинвариантов91Определение. Функциюh I \ju K1ju ) K2a2 aбудем называть асимптотикой второго порядка характеристической функции H ( u) числа заявок i(t) в источнике повторных вызовов, а величину κ2/σ - асимптотическим семиинвариантом второго порядка.2.3. Асимптотика произвольного порядкаДля нахождении асимптотики произвольного порядка будем применять метод математической индукции. Пусть вектор функция Hn(u) (n ≥3 ) удовлетворяет уравнению^j^Hn u A(ju) = Hn(u)\B(ju) + K1A(ju) + fijuKv+1A(ju)\, (25)дu[v=1 v!Jв котором известны все κν при ν = 1, 2,…, n - 1.Пусть с применением уравнения (25) найдено значение величины κ n, тогда выполним заменуHn(u) = exp{n^ЦHn+1(u)и получим уравнение для вектор-функции Hn+1(u):^5Hn u (u A(ju) = Hn+1(u)|B(ju) + к1 A(ju) + n 1 juку+И0u)1 (26)решение Hn +1(u) этого уравнения удовлетворяет условиюHn+1(0)E = 1.Далее, применяя (26), (27), найдем значение величины κ n +1. Для этого в задаче (26), (27) обозначим σ = ε n+1 и выполним заменыu = ew, Hn+1(u) = Fn+1(w,&), получимjsn Fn«{w,*) A{jew) =dw= Fn+1(w,s)\b(jsw) + k1A(jSw) + n 1 (j wkv+1A(JSw) ;(28)Fn+1(0,s)E = 1.Теорема 3. Предельное, при ε→0 значение Fn +1(w) решения Fn +1(w,ε) уравнения (28), удовлетворяющего условию (29), имеет видFn+1(w) = R-exp\jw n кn+1(n+1)! где вектор R определен выше, а величина κ n +1 определяется равенством92А.А. Назаров, И.А. СеменоваKn+1 =-\g n (B 1 + 1 A)E + n 1+ 1YC n+1 fv\ B т+1-v +YC n+1-vKk1 A n1k E +k=0+n 1+ 1R[Bn+1 + k =0Сkn+1кk+1An+1-k\E\ {g(B 1 + vl1A1)E + RA1E} ,(30)в котором векторы g и gn определяются неоднородными системами линейных алгебраических уравненийg(B0+K1A0) + RA0=0,g n (B 0 +KA) + l1 C n fv (b n-v +^C nk -vKk+1 A n -v-k)+R(B n +fiC knKk+1 A n -k1 = 0v=Кk=0JУk=0и произвольными дополнительными условиями, выделяющими частные решения этих систем из множества всех их решений, а векторы f ν определяются разложениямиfv =gv +Kv+1g , v = 1,n-1.Доказательство. Доказательство этой теоремы, как и для асимптотики второго порядка, выполним в три этапа.Этап 1. В задаче (28) - (29) выполним предельный переход при ε→0, получим системуFn+1(w)(B0+K1A0) = 0,{ Fn+1(0E = 1,решение Fn +1(w) которой запишем в виде произведенияFn+1 (w) = Rфn+1 (w) = R-exp\( j) кn+1 >(31)вектора R, найденного выше и определяемого системой (10), и скалярной функци-ей Φn+1(w), вид которой определен равенством (31). Значение величины κn+1 будет определено ниже.Этап 2. Решение Fn+1(w,ε) системы (28) запишем в виде разложенияnvFn +1 (w,6) = |R + =1 ( j w ) f |фn +1 ( w ) + o(5n +1)которое подставим в систему (28). Получим равенствоn![ v=1 v!v=1Исследование RQ-систем методом асимптотических семиинвариантов93Подставляя сюда разложение матриц A( j εw) и B(jεw)nv0 v!v ;~ v!v ;A(j£w)=Jv=получим равенствоR n^w m Bm*1Cm k 1 Am k + n°8wrfmЛm-vЛ"|| 2-1 mfv Bm-v + Z0 Cmk-v^+1Am-v-k Г = 0(8 ) .Приравнивая здесь коэффициенты при одинаковых степенях ε, получим последовательность систем линейных алгебраических уравнений относительно векторов R и fν :R(B0+к1A 0) = 0, f 1(B0 + k1A0) + R(B1 +К1 A 1 + к2A 0) = 0,…n Cn fv [ Bnv + n Cn kк^1 An-v-k I+R f Bn + n Cn k +1 An -k 1 = 0. (34)v=1Ik=0JIk=0JПоследнюю систему из (34) для вектора fn запишем в видеfn (B0 +к1 A 0)+ n 1 Cn f (Bnv +£Cn-v^+1 An-v J+R Bn + n 1 Cnкk+1 An_k1+кn+1RA0 =0v=1Ik=0J Ik=0Jи ее решение fn найдем в виде суммыfn=gn+Kn+1g, где вектор g определен системой (22), а вектор gn является решением системыn-1Лn-vЛfn-\Лg n (B 0 +MA) + EC n fv B -v+ZC n-vKk+ A -v-k \+R B n +YC nkk+lA -k =0.v=1Ik=0JIk=0Этап 3. Для нахождения значения величины κ n+1 сложим все уравнения системы (28), домножив это равенство справа на единичный вектор столбец E. Принимая во внимание разложение (32), и разложение матриц A( j εw) и B( j εw), получим равенствоn+1 / jew)m ( mfm-vЛZj! jLCmfv Bm-v + Zj Cm_vK.k+1Am_v_k +m=1 mlv=1lk=0J+R [Bm + k CmkЧ+1Am_k )\e + 0 (en+2 ) = 0 .В силу равенств (34) все слагаемые в (36), содержащие величину ε в степени меньше чем n+1 равны нулю, поэтому из (36) получимn+1(n+1-vЛ(n+1 kliC fvB -v+ Zj Ci+1-vKk+1 A n+1-v-k \E + R\B n+1 +2^Cи+1к4.+1 A n+1_k E = 0.v=1Ik=0JIk=094А.А. Назаров, И.А. СеменоваПриравнивая здесь во внимание равенства A 0 E = 0, B0E = 0, можно записатьnfn+1-vЛfп2_г n+1 fv Bi+1-v + Zj C n+1-vk+iA +1-v-k ]E + R\ B n+1 + £^C n+1kk+1 A n+1_k E = 0.v=1Vk=0JУk=0Принимая во внимание равенство (35) и выделяя здесь слагаемые, содержащие величину κ n +1, получимГn-1fn-vIv=1Vk=0Jсовпадающее с (30).Теорема доказана.Найденные функции Fn +1(w) служат основой построения асимптотики произвольного порядка.Определение. Функциюhn+1(u) = exp< n 1^^>(37)U=1 v! CTJ будем называть асимптотикой (n+1)-го порядка характеристической функции H ( u) числа заявок i(t) в источнике повторных вызовов, а величину κ n+1/σ - асимптотическим семиинвариантом (n+1)-го порядка.3. Численный анализ RQ-системДля того чтобы получить распределение вероятностей числа заявок в источнике повторных вызовов в допредельной ситуации, необходимо рассмотреть систему уравнений Колмогорова (1) для стационарного распределения P(l,i) [8, с. 76]l-(X+ia)P(0,i) + u.P(1 ,i) = 0,|-(Х + ц)P(1 ,0 + ХP(0,0 + аО+1)P(0,i + 1) + ХP(1,i-1) = 0(38)Решение системы (38) запишем в виде алгоритма численной реализации.1.i = 0. Сначала найдем решения V(k,i) системы (38), удовлетворяющие условию V(0,0) = 1. Для этого из первого равенства системы (38) выразим V (1,0) иподставим во второе равенство, получим V(0,1) XV(0,0) (X + lx)V(1,0)-XV(0,0)V(1,0) =, V(0,1) =.2.i = 1.V(1, 1) =, V(0,2) =г) (1 , )( 0,1)1,) .|х2а3.i = 2.V(1,2)=', V(0,3) = ^( 0,(1, .|х3а4.Для реализации основного алгоритма, когда i = N, запишем уравненияV(0, N) -, V (1, N) -.Na|xИсследование RQ-систем методом асимптотических семиинвариантов95Далее, получаем величинуP(k,i)IIV(v,n)V(K,i),которая численно определяет двумерное распределение вероятностей P(k,i). Одномерное маргинальное распределение P(i), определяемое равенствомP(i) = P(0,i) + P(1,i),численно решает поставленную задачу нахождения распределения вероятностей числа заявок в источнике повторных вызовов, которое естественно совпадает с P(i).4. Область применимости асимптотических результатов к допредельной ситуацииС помощью полученной асимптотики произвольного порядка (37) и обратного преобразования Фурье, запишем асимптотическое распределение вероятностей числа заявок в источнике повторных вызовов [9, с. 107]Pn(i) = y\e- juihn(u)du.-к2лРаспределение (39) будем называть асимптотической аппроксимацией n-го по-рядка допредельного распределения.Теперь выясним, насколько результаты, полученные с помощью асимптотиче-ского анализа, близки к результатам, полученным численно в допредельной си-туации. Для этого найдем расстояние Колмогорова между этими распределениямиD max0

Скачать электронную версию публикации