Блинов А.И., Васильев С.А., Севастьянов Л.А.

Abstract

Решение задач математического моделирования сложных транспортных сетей на данном этапе представляет большую сложность по причине большого объема данных, которые приходится анализировать. Например, огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и использование современных вычислительных алгоритмов в планировании перевозок дает большой экономический эффект. Проведенный анализ показал, что этот подход является эффективным для решения широкого круга технических и технологических проблем проектирования, строительства и функционирования транспортных систем. В рамках этого подхода удается создать эффективный алгоритм минимизации затрат на проектирование, строительство и эксплуатацию таких систем. Транспортные задачи могут быть решены симплексным методом, однако матрица системы ограничений транспортной задачи часто настолько сложна, что для ее решения разработаны специальные методы. В данной работе исследуются крупномасштабные транспортные сети с использованием приближения среднего поля Добрушина. Показано, что анализ эволюции крупномасштабных транспортных систем можно описать с помощью системы дифференциальных уравнений бесконечного порядка. Для этой системы можно поставить задачу Коши тихоновского типа с малым параметром, который вносит сингулярное возмущение. В статье доказана теорема существования решения этой задачи Коши. Аналитические методы в теории транспортных сетей; системы дифференциальных уравнений бесконечного порядка; малый параметр; счетные цепи Маркова; крупномасштабные транспортные сети; приближение среднего поля Добрушина; транспортная задача; динамика сложных систем.

Introduction

large-scale transport network using Dobrushin’s mean-field approximation. It is shown that the analysis of the evolution of large-scale transport systems can be described using systems of differential equations of infinite order. For this system, it is formulated the Cauchy problem Tikhon type with a small parameter  , which introduces a singular perturbation. The theorem of existence of the solution of this Cauchy problem is proved.

Analytical methods in transport networks theory; systems of differential equations of infinite order; small parameter; countable Markov chains; large-scale transport networks; Dobrushin mean-field approximation; transportation problem; dynamics of complicated systems.

In this paper -lsacraglee transport networks are studied using Dobru-sfhieilnd mapeparnoach [-15,410,1719]. We assume that the transport networks deal with the problem of proving the global conv solutions of certain infinite systems of ordinary differential equat-ionndsepetnodenat tsiomluetion. In work, [ 4,5,10 ] the infinite systems eroefntidaliff equations modelling -lsacraglee transport systems are studied and the sufficient conditions of global stability and global asymptotic stability are obtained.

Cauchy problems for the systems of ordinary differential equations of infiinnvietestigaotredder was A.N. Tihonov [ 14 ], KP.ePr.sidsky [ 11 ], OZ.Aha.utykov [ 2-021 ], JuK.orobeinik [ 6 ], MK.Ara.snoselsky, P.PZ.abreyko [ 8 ], A.MS.amoilenko, Yu.VT.eplinskii [ 12 ] other researchers.

It was studied the singular perturbed systems of feroerndtiinaalry equdaiftions by A.N. Tihonov [ 15 ], A.B. Vasil'eva [ 16 ], S.A. Lomov [ 9 ] other researchers.

In papers [ 3 ], [ 7 ], [ 13 ] the authors built various -smcaoldeelsqueoufeinlagrgesystems and considered their dynamics.

In paper [ 2 ] it was investigsaitnegdulatrhe perturbed systems of ordinary differential equations of infini order of Tikho-ntoyvpe  x = F (x(t, gx ), y(t, g y ),t) , y = f (x(t, gx ), y(t, g y ),t) with the initial conditxio(tn0 s) = gx , y(t0 ) = g y , whexr,egx X ,X  l1 and y,g yY

Y, Rn t, t0 ,t1  ( t0 < t1 )t,0 ,t1 T T,  R ,gx and g y are given vectors, > 0 is a small real parameter.

In this paper we considregree-dscalea transport network systems that consists of infinite number of net service nodes with a Poisson input flow of requests. We assume that theN nqoudeuesing ansdryNstem has servers. At each noNdenod(es) the arrivals of particles formn afloPwoissoof rate. For an empty node a particle leaves the system. A server at the node takes the particle and moves to a random node exponential of me1a/n . The number of servers at each noNdeno(doefs) thiesse bounded m .by We conesrid the property of the system for the limiting determinisNtic pro.ceTsshe asevolution analysis o-sfcalearge transport systems can be described using an infinite system of differential equations. It is possible Tikhonov type Cauchy epmroblfor this system with small parameter. In this paper we ap-pfliyeldDobrushin approaches from [ 5,10 ] for analysis of the singular perturbed systems of ordinary differential equation order.

It is possible to formulate Tikhonov tyypeproCbaleumch for this system with small  paanrdameitneirtial conditions. We study the singular perturbed Tikhonov systems of ordinary differential equations of inf u = f (u(t, gu ),U (t, gU ),t) , U = F (u(t, gu ),U (t, gU ),t) with condituio(n0,sgu ) = gu U, (0, gU ) = gU , the initial where  > 0 is a small real parameter. orTehme othfe existence of solution for this Cauchy problem is prove

Large-scale transport network model

Let's consider a large-scale transport networks that consist of N nodes, a virtual node and rN servers. At each node (of these N nodes) the arrivals of particles form a Poisson flow of rate  . If a particle arrives at an empty node then the particle leaves the system. Otherwise, if there is a server at the node then the server takes the particle and jumps to the virtual node. At this node the server waits for an exponential time of mean t = 1 /  . After the server jumps to a random node with uniform distribution. If the number of servers at the chosen node equals m then the server waits for the following attempt at the virtual node. The non-negative number of servers at each node (except virtual) is bounded by m . Consider the fractions fk = nk / N , V = W / N , where nk is the (random) number of nodes with k servers and W is the number of servers at the virtual node. It is more convenient to regard the tail probabilities uk = im=k fi . The state space of the corresponding Markov process UN (t) = (uk (t),V (t)) is the set X N of all vectors u = (u1, ,um ,V )T in (1 / N )Zm1 such that 1 = u0  u1   um , V  0, u1   um V = r. The generator of U N (t) is the operator AN (t) acting on functions and given by AN (t) f (u) = N m1(uk  uk 1)[ f  u  ek  emN1   f (u)] 

k =1  N  N um[ f  u  ek  emN1   f (u)],

 N  NV m(uk 1  uk )[ f  u  ek  emN1   f (u)]

k =1  N where ek denotes a vector with the component of number k equal to 1 and others equal to 0 .

The mean-field approximation suggests that the whole process U N (t) is asymptotically deterministic as N   . More precisely, let X denote the set of all Rm1 vectors defined by (1). Then, if the distribution of the initial state U N (0) converges to the Dirac delta-measure concentrated at some point g  X , the distribution of U N (t) is concentrated on the orbit u(t)  X as N   where u(t) is the solution of the following system of differential equations (mean-field equations)  V (t) =  u1(t) V (t) u0 (t), u0 (t) = 1;  uk (t) =  ui1(t)  ui (t)   V (t) ui1(t)  ui (t) ,    uk (t)  V (t) = r(t), r(r) > 0,  V (0) =kV=00  0, uk (0) = gk  0, k = 0,1, 2, ,  1 = g0  g1  g2 , , t  0  

 where r(t) > 0 is a parameter and g = gk k =1 is a numerical sequence. The infinite order system (2) is non-linear and its right-hand side depends on time.

Large-scale queueing systems model with a small parameter

We can investigate infinite system of differential equations with small parameter such form  V (t) =  u1(t) V (t) u0 (t), u0 (t) = 1;  uk (t) =  uk 1(t)  uk (t)  V (t) uk 1(t)  uk (t), k = 1, 2, , n,  sk uk (t) =  uk 1(t)  uk (t)  V (t) uk 1(t)  uk (t), k = n 1, n  2, ,  uk (t)  V (t) = r(t), r(t) > 0,  k =0  V (0) = V0  0, uk (0) = gk  0, k = 0,1, 2, ,  1 = g0  g1  g2 , , t  0,   where  is a small parameter that bring a singular perturbation to the system (2) which allows us to describe the processes of rapid change of the systems and s = sk k=n1 (sk > 0) is a numerical sequence.

Using (3) we can write Tikhonov problems for systems of ordinary differential equations of infini a small parameterand initial conditions V (t) =  u1(t) V (t) u0 (t), u0 (t) = 1;  u = f (u(t,  , , gu ),U (t, , , gU ), t),   sk U = F (U (t, , , gU ), t);  V (0) = V0  0, u(0, , , gu ) = gu ,  U (0, , , gU ) = gU ,  where u, f  X , X  Rn1 are (n+1)-dimensional functions; U , F  Y , Y  l1 are infinite-dimensional functions and t  0,T0  ( 0 < T0   ), t  T , T  R ; gu  X and gU  Y are given vectors trajectory of this system integral manifoldS totally.

If we assume in (4)= 0thtahtan problem of singular perturbations

 (gu = gk kn=0 , gU = gk k=n1 , 1 = g0  g1  g2 , ) ,  > 0 is a small real parameter; u(0, gu ) = gu and U (0, gU ) = gU are the conditions for solutions of (4). Given functions f (u(t,,, gu ),U(t,,, gU ),t) and F(U(t,,, gU ),t) are continuous functions for all variables fk (u(t, , , gu ),t) =  uk1(t)  uk (t)  V (t) uk1(t)  uk (t), k = 1, , n,

Fk (U (t, , , gU ),t)   Uk1(t) Uk (t)  V (t) Uk1(t) Uk (t), k = n 1, n  2, Let S is an integral manifold

of the systeXmY (4T) .in If any t*poin0t,T0  (u(t* ),U (t* ),t* )  S of has at least one com mSotnhis potirjneatctooryn (u(t,G),U (t, g),t)  S belongs the we have a degenerate system

of the ordinary differential equations V (t) = u1(t) V (t) u0 (t), u0 (t) = 1,  u = f (u(t, , , gu ),U (t),t),   0 = F (u(t, , gu ),U (t, , ), t);  u(0, , gu ) = gu ,   where teh dimension of this system is less than the dimension of the system (4), since F (u(t, ),U (t, ), ,t) = 0 in the system (6) are the algebraic equations (not differential equations). Thus system (9) we can use limited number of the initial cosnysdtietimons (4t)h.enMofsotr natural for this case we can use the initial conduit(i0o,ns, gu ) = gu for the system (6) and the initial Uc(o0n,di,tUioyn)s= gU disregard otherwise we get the overdefined system. We can solve the system (6) if t F (u(t, ),U (t, ), ,t) = 0 has roots. If it is possibele wtoe scoalnv find a finite set or countable set of th Uq (t, , gu ) = uq (u(t, , gu ),t) where q  N . If the implicit fFun(uct(ito,n),U (t, ), ,t) = 0 has not simple structure we must investigate the question about the choice of roots. Hence we can us Uq (t, , gu ) = uq (u(t, , gu ),t) ( q  N ) in (10) and solve the degenerate system ud = f (ud (t, , gu ),uq (ud (t, , gu ),t), ,t);   Ud (0, , gu ) = gu .

Since it is not assumed that Utqh(et, ,rgouo)ts= uq (u(t, , gu ), ,t) satisfy the initial conditions of the Cauchy (4)Uq((0)  gu , q  N ), the problem other at the initial moments of tti>m0e . Also teheris a very interesting question about behaviors ofu(tt,he,gu s)olutions of the singular perturbed problem (4) and thued(t,so,lguut)ioonfs the degenerate problem (6).t =W0hwene solutioUns(t, , gU ) (4) andUq (t, , gu ) do not close to each have u(0, , gu ) = ud (0, , gu ) . Do these

solutions close to each tothe0r,T0 w?henThe answer to this question depends on using rUooq(tts, , gu ) = uq (u(t, , gu ),t) and the initial conditions, which we apply for the systems

Analysis of infinite order system of differential equations

We can rewrite Tikhonov problems (4) for systems of ordinary differential equations of infinite small parameter and initial conditions in the form v = FR (v(t, , , , v0 ),t),   v(0, , , , v0 ) = v0 , where v = (V ,u0,u1, ,un ,Un1,Un2, ),

FR0 = u1(t) V (t) u0 (t),

FRk =  uk1(t)  uk (t)  V (t) uk1(t)  uk (t), k = 1, , n, ,

FRk =  sk  uk1(t)  uk (t)  sk V (t) uk1(t)  uk (t), k = n 1, n  2, , where v00 = V , vk0 = gk ,k = 1, 2, • are strongly continuous in v0 , v1, vi ( , , , t), i = 0,1, 2, ; • satisfy the inequalities v = FR (v0 , v1, , vn , , , , , t),  v(0, , , , v0 ) = v0 ,

Definition. A functionFR v0 , v1, , vn , , , , , t  is called strongly continuous if  0fo>r 0 ,anythere exNis0t and  0 > 0 such that the inequ|avli'ityvi' |<  0 , i = 0,1, 2, , N0 , implies the estimate for 0a,ny 0, > 0 | FR v0' , v1' ,  , ,   FR v0' , v1' , , , ,  |<  0.

Theorem. Assume that the right-hand sides of the system of equations (10) • are defined for any vi ( , , ,t)  R1,i = 0,1, 2, ,   0,  0, > 0 and all t T0 = 0, t R1 ;

for fixed t T0 ,   0 ,   0 ,  > 0 and measurable in t T0 for fixed | FRi t, v0 , v1, , , ,  |< Mi (t) for all i = 0,1, 2, , where Mi (t) are functions summable on the segment T0 and for any   0,  0, > 0 .

v00 , v10 , 

Then, for any vector with real coordinates, there exists at least one solution v0 ( , , , t), v1( , , , t),  of the system of equations (14) such that vi (0) = vi0 ,i = 0,1, 2, .

Proof. We replace the system of equations (8) by the following system

t vi (t) = vi0  FRi t, v0 (t), v1(t), , , ,  dt,i = 0,1, 2, , 0 of integral equations: and consider a pminagp A( )

t zi (t) = vi0  FRi t, v0 (t), v1(t), , , ,  dt, i = 0,1, 2, ,

0 another system

n variables vi (t)i=0 measurable with respectt fotor fixedvi ,i = 0, n , then the function

(t) = FR (t,0 (t), ,n (t), , , ) which establishes a correspondence between an arbitrary countable system

 of thiszis(ot)rti=0 . Note thatFR (itf, v0 , , vn , , , ) is a continuous function of finiytely  of contivni(uto)ui=s0 afnudnctions man is measurable ii(ft),i = 0, n , are measurable.

Thus, the function

n (t) = FR (t,0 (t), ,n (t), 0, 0, , , , ) is measurable and, therefore, the function

FR (t,0 (t),1(t), , , , ) = (t, , , ) is also measurable because

(t) = nlimn (t, , , ), which readily follows from the condition of strong continuity. The requirement of summability fo  condition 3 of Theorem. We consider a systemvio(ft)if=u0nacstionas poiPntof an abstract spRa.ce If there exists a poiPntinvariant unedr mapping A )( (14), then it specifies a solution of the system of equatio and, hence, of system (10).

Consider a sMet0 formed by three poPintfsor whichvi (t)i=0 satisfy the conditions

t t | vk (t)  vk0 | M k (t)dt , | vk (t)  vk (t) | M k (t)dt, k = 0,1, 2, .

0 t

It is easy to see that Am)app(i1n4g) (maps theM0 sineto tsielf. We now introduce mapBp)ingby( putting every pointP in correspondence with a set of numbers

0 n a0 , , a0 , , N0 N0

, a1n , , ann , , nNn nNn

, t where Ni = vi0  Mi (t)dt and the numberasnr n,r=0 ( an0 , , ann , ) are the coefficients of the Fourier expansion 0 a funcotin vn (t) in a certain complete orthogonal system of functions onT0 . theBy seogrmdernitng the set of numbers (16), we obtain a numerical bs0 e,bq1u,en,cben , . Moreover, we have  t t 2 ank 2 =  vn (t)2 dt  t  vn0  M k (t)dt  dt  k=0 0 0  0 

   ank 2  a  12 = a 2 .

i=0bi2 = 0=1k=0  nNn  n=0 n 6

Thus, mapping B ( ) maps theM0 sientto a subsMet0* of the Hilbert s pl2ace. Therefore, mappiAng ) ( induces a mappinAg* ) ( of the Ms0*etinto itself. Further, if mapAp*i)ng ha(s a fixed Pp*oinMt 0* , then the corresponding pointP*  M0 determines the solution of equation (17) and, hence, (10). To use the theorem, it suffices to show thaMt0* tihse csoemt pact and conIfvePx.* = (b0' , ,bn' , ) and P* = (b0' , ,bn' , ) are points froMm0* , then the point

 P*   P* = ( b0'   b0' , b1'   b1' , ),   = 1, > 0, > 0, belongs toM0* because it corresponds to the system of functions

 v0' (t)   v0' (t), v1' (t)   v1' (t), . specifying a point from tMhe0 . Insdeteed, t t  vk' (t)   vk' (t)  vk0 =  (vk' (t)  vk0 )   (vk' (t)  vk0 )  (   )Mk (t)dt = Mk (t)dt, 0 0 i.e., condition 1 isfiedsa.tisSimilarly, the inequality t  vk' (t' )   vk' (t' )  vk' (t' )   vk' (t' )  (   )M k (t)dt 0 implies condition 2. Hence, tMhe0* issetconvex. In this set, we choose an arbitrary seqPuien.ceThiosf points * sequence corresponds to the sequence oPfi v(i)

p0o(itn)t,sv1(i) (t),  in teh seMt0 . According to conditions 1 and 2, the sequenvc0(ei) (t),i = 0,1, 2, , is uniformly bounded and equicontinuous and, consequently, it cont subsequence v0(0 ) (t), v0(1) (t), , v0(s ) (t), that converges uniformly t inT0 . However, the sequence v1(h ) (t), h   , is also uniformly bounded and equicontinuous, aitnd, alshoencceontains a convergent subsequence

v1(0) (t), v1(1) (t), , v1(s ) (t), .

This process can be continued infinitely.

We compose the table and rewrite the sseetqueonfces row v0(0 ) (t)v0(1) (t)v0(2 ) (t) v1(0 ) (t)v1(1) (t)v1(2 ) (t) v2( 0) (t)v2(1) (t)v2( 2) (t) by row v0(0 ) (t)v0(1) (t)v0( 2 ) (t)

P0 , P1, P2 , , Pn ,   P* , P*  = i=0  (bi'  bi' )2 =  1 t  n=0 n2 N 2  (vn'  vn' )2 dt ,

n 0 n0 1 t   P0* , Pk*   n=0 n2 N 2  (vn0  vnk )2 dt  t  n 0 n=n0 n

2 of a convergent sequence supplemented whence it follows that to aP0 poMin0t (uniformly int  T0 )F. or the sake of convenience, we is arbitrarily small for sufficientlyn0 alanrdgek . This means that tMhe0* issetcompact. Note that one can easily prove that mapping (B) is a homeomorphism, Mi.e0., antdheM 0*saertes topologicayll equivalent. Theorem is proved.

Conclusions

We consider the property of the system for the limiting determNinistic . pTrohceessevoalsution analysis of larg-escale transport systems can be described using an infinite system of difftereinstiapl osesqibulaetiotnos. I formulate Tikhonov type Cauchy problem for this system with smanlld painriatmiaeltecronditions. Tikhonov type

Cauchy problem for

this solutions for this hCyaucproblem is system proved

Acknowledments

with

small ipsaraimnveetsetrigated. with taking into account ,p a,ra.meters

The theorems of existence of by

The publication was prepared with the support of the “RUDN RFBF grants №-07-0185795, № -0176-00556.

Uni-v1e0r0si”ty anPdrogpramrtiall5y funded физик-оматематических наук, профессор кафедры прикладной вероятностей, Российский университет дружбы народов,

References

1. Afanassieva L.G. , Fayolle G. , Popov S. Yu . Models for Transportation Networks // J. Math. Science. - 1997 . - Vol. 84 , Issue 3. - P. 1092 - 1103 .

2. Bolotova G.O. , Vasilyev S.A. , Udin D.N. Systems of Differential Equations of Infinite Order with Small Parameter and Countable Markov Chains // Distributed Computer and Communication Networks - 19th International Conference, DCCN 2016 Communications in Computer and Information Science. (Moscow, November 21-25 , 2016 ). - Vol. 678 . Publisher: Springer Verlag, 2016 . - P. 565 - 576 .

3. Gaidamaka Y. , Sopin E. , Talanova M. Approach to the analysis of probability measures of cloud computing systems with dynamic scaling / / Communications in Computer and Information Science. - 2016 . - Vol. 601 . - P. 121 - 131 .

4. Khmelev D. V. , Oseledets V.I. Mean-field approximation for stochastic transportation network and stability of dynamical system . - Preprint № 434 of University of Bremen, 1999 .

5. Khmelev D. V. Limit theorems for nonsymmetric transportation networks // Fundamentalnaya i Priklladnaya Matematika . - 2001 . - Vol. 7 , №- 4P . 1259 - 1266 .

6. Korobeinik Ju. Differential equations of infinite order and infinite systems of differential equations // Izv . Akad. Nauk SSSR Ser. Mat. - 1970 . - Vol. 34 . - P. 881 - 922 .

7. Korolkova A.V. , Eferina E.G. , Laneev E.B. , Gudkova I.A. , Sevastianov L.A. , Kulyabov D.S. Stochastization of one-step processes in the occupations number representation // Proceedings - 30th European Conference on Modelling and Simulation , ECMS 2016 (Regensburg, Germany, May 31- June 3, 2016 ). - European Council for Modeling and Simulation, 2016 . - P. 565 - 576 .

8. Krasnoselsky M.A. , Zabreyko P.P. Geometrical methods of nonlinear analysis . - Berlin , Springer-Verlag, 1984 .

9. Lomov S. A. The construction of asymptotic solutions of certain problems with parameters // Izv . Akad. Nauk SSSR Ser. Mat. - 1968 . - Vol. 32 . - P. 884 - 913 .

10. Oseledets V. I. , Khmelev D . V. Global stability of infinite systems of nonlinear differential equations, and nonhomogeneous c ountable Markov chains // Problemy Peredachi Informatsii (Russian) . - 2000 . - Vol. 36 , Issue 1. - P. 60 - 76 .

11. Persidsky K.P. Izv . AN KazSSR, Ser . Mat. Mach . - 1946 . - Issue 2 . - P. 3 - 34 .

12. Samoilenko A. M. , Teplinskii Yu . V. Countable Systems of Dierential Equations. - Utrecht , Springer, 2003 .

13. Samouylov K. , Naumov V. , Sopin E. , Gudkova I. , Shorgin S. Sojourn time analysis for processor sharing loss system with unreliable server // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) . - 2016 . - Vol. 9845 . - P. 284 - 297 .

14. Tihonov A. N. Uber unendliche Systeme von Differentialgleichungen // Rec. Math. - 1934 . - Vol. 41 , Issue 4. - P. 551 - 555 .

15. Tihonov A. N. Systems of differential equations containing small parameters in the derivatives // Mat . Sbornik N. S. - 1952 . - Vol. 31 , Issue 73. - P. 575 - 586 .

16. Vasil 'eva A. B. Asymptotic behaviour of solutions of certain problems for ordinary non-linear differential equations with a small parameter multiplying the highest derivatives // Uspehi Mat . Nauk . - 1963 . - Vol. 18 , Issie 111 , № . - 3 .P. 15 - 86 .

17. Vvedenskaya N.D. , Dobrushin R.L. , Kharpelevich F.I. Queueing system with a choice of the lesser of two queues — the asymptotic approach // Probl. inform. - 1996 . - Vol. 32 , Issue 1. - P. 15 - 27 .

18. Vvedenskaya N.D. , Suhov Yu .M. Dobrushin's Mean-Field Approximation for a Queue with Dynamic Routing // Markov Processes and Related Fields . - 1997 . - Issue 3 . - P. 493 - 526 .

19. Vvedenskaya N.D. A large queueing system with message transmission along several routes // Problemy Peredachi Informatsii . - 1998 . - Vol. 34 , №- P2 . 98 - 108 .

20. Zhautykov O. A. On a countable system of differential equations with variable parameters // Mat. Sb. (N.S. ). - 1959 . - Vol. 49 , Issue 91. - P. 317 - 330 .

21. Zhautykov O. A. Extension of the Hamilton-Jacobi theorems to an infinite canonical system of equations // Mat. Sb. (N.S. ). - 1961 . - Vol. 53 , Issue 95. - P. 313 - 328 .