KOI WIN L^AT_EX PS PDF |== > К списку публикаций To the list of publications

Стохастические транспортные сети и устойчивость динамических систем

В.И. Оселедец, Д.В. Хмелёв

11 ноября 1998

Аннотация

Мы исследуем устойчивость предельного детерминированного процесса, получаемого при N®Ґ. Далее, мы применяем наши результаты к системе массового обслуживания со сложной дисциплиной выбора прибора.

Ключевые слова: Марковские процессы, нелинейные динамические системы, глобальная асимптотическая устойчивость, производящий оператор, сходимость, метод среднего поля, теория массового обслуживания.

Содержание

1  Введение

Введем дроби f_k=n_k/N, V=W/N, где n_k - (случайное) число узлов, количество приборов в которых равно k, а W - количество приборов, находящихся в виртуальном узле. В технических целях удобно перейти к накопленным вероятностям u_k=е_i=k^m f_i.

Пространство X_N состояний марковского процесса U_N(t), который описывает систему, содержит всех такие вектора u=(u₁, ј, u_m, V)^т из (1/N)Z₊^m+1, что

1=u0 і u1 і ј і um і 0, V і 0и V+u1+ј+um = r.

(1)

Производящий оператор A_N(t) процесса U_N(t) действует на функции и задается следующим образом

ANt f(u) =Nl(t) m-1 е k=1  (uk-uk+1)[f(u-ek/N+em+1/N)-f(u)]+ +Nl(t)um[f(u-em/N+em+1/N)-f(u)]+ +N V m е k=1  (uk-1-uk)[f(u+ek/N-em+1/N)-f(u)],

(2)

где e_i - вектор, i-тая координата которого равна 1, а остальные координаты равны 0.

Метод среднего поля подсказывает, что в пределе при N®Ґ эволюция u становится детерминированной. Более точно: пусть X означает множество всех векторов R^m+1, удовлетворяющих (1). Тогда, если распределение начального состояния U_N(0) сходится к дираковской дельта-функции, сконцентрированной в точке g О X, то распределение U_N(t) сосредотачивается при больших N на траектории u(t) О X, удовлетворяющей системе дифференциальных уравнений

Ч u   =f(u(t),l(t)),

(3)

где

fi(u,l) =l(ui+1-ui)+V(ui-1-ui), i=1,ј, m-1, u0=1, fm(u,l) =-lum+V(um-1-um), fm+1(u,l) =lu1-V(1-um).

(4)

Техническим инструментом в исследовании поведения этой нелинейной системы служит теорема 3.3 о глобальной асимптотической устойчивости систем дифференциальных уравнений весьма общего вида. Эта теорема, которая, в частности, дает возможность исследовать случай зависимых от времени коэффициентов, представляет несомненный практический и теоретический интерес.

2  Основные определения и результаты

Теорема 1 Пусть l(t) - кусочно-непрерывная функция. Тогда

(а) для всех g О X в X существует единственное решение u(t, t, g), t і t задачи Коши (3) с u(t, t, g)=g;

(б) существует такое g > 0, что для любых g, gў О X

||u(t,t,g)-u(t,t,gў)|| Ј const·exp(-g(t-t));

(в) если функция l(t) периодическая с периодом T, то существует такое единственное g^* О X, что u(t, t, g^*) является T-периодическим решением (3) и для любого g О X

||u(t,t,g)-u(t,t,g*)|| Ј const·exp(-g(t-t));

(г) если l(t) постоянна, то существует и единственно такое g^* О X, что u(t, t, g^*)=g^* и для любого g О X

||u(t,t,g)-g*|| Ј const·exp(-g(t-t)).

Стационарное решение g^* пункта (г) легко находится (см. [1]). Определим семейство операторов T_N=T_N(t, t) по правилу

TN(t,t)f(g)=E(f(UN(t)) | UN(t)=g),g О XN.

(6)

Теорема 2 Если l(t) кусочно-постоянна, то для всех f О C(X), равномерно по t на произвольном отрезке из R_t⁺={t і t},

lim N®Ґ  sup t Ј s Ј t  sup g О XN  |TN(s,t)f(g)-f(u(s,t,g))|=0.

(7)

Обозначим через e_g дельта-меру Дирака, сосредоточенную в точке g О X.

Теорема 3 Пусть выполнены условия теоремы 2.2. Если U_N(t) по распределению сходится к e_g, то

"t і t sup t Ј s Ј t  ||UN(s)-u(s,t,g)||® 0 по вероятности.

Если l(t) периодична с периодом T, то процессы U_N,t(n)=U_N(t+nT), где n=0, 1, ... , образуют множество однородных цепей Маркова с дискретным временем и конечным числом состояний, каждая из которых в силу связности обладает единственной инвариантной мерой m_N,t=m_N,t+T. Пункт (в) теоремы 2.1 утверждает, что у системы (3) существует единственный инвариантный цикл u(t, 0, g^*).

Теорема 4 Пусть l(t)=l(t+T). Тогда

(а) для t О [0,T) на множестве X существует единственная вероятностная мера, инвариантная относительно динамической системы g®u(t+T,t,g), g О X. Эта мера сосредоточена в точке u(t, 0, g^*), т.е. равна e_{u(t, 0, g^*)};

(б) инвариантные меры m_N,t процессов U_N,t сходятся по вероятности к e_{u(t, 0, g^*)},

Последняя теорема охватывает также случай l(t) є const. Действительно, тогда m_N,t=m_N, где m_N - стационарная мера процесса U_N и m_N®e_g^* по вероятности.

3  Вспомогательные утверждения

3.1  Коэффициент эргодичности и его свойства.

Линейное отображение A неотрицательно (положительно), если ARⁿ₊ Н Rⁿ₊ (ARⁿ₊ М Int(Rⁿ₊)). Если A-B неотрицательно, мы пишем A і B, (если A-B положительно, A > B). Из определений следует, что матрицы просто сравниваются покомпонентно.

В дальнейшем нам потребуются следующие две леммы относительно неотрицательных матриц.

Лемма 1 Пусть A і B і 0 и C і D і 0. Тогда AC і BD і 0.

Для доказательства достаточно сложить неравенства (A-B)C і 0 и B(C-D) і 0. По индукции из этой леммы получаем, что если A₁ і B і 0, ј, A_n і B і 0, то A_nјA₁ і Bⁿ.

Лемма 2 Пусть A=aC и B=bD, где C и D - марковские отображения и a, b > 0. Если A > B і 0, то k(A) > k(B). Если A і B і 0, то k(A) і k(B)

Доказательство. Пусть ||A||=a, ||B||=b. Ввиду неравенства треугольника ||A||_L Ј ||A-B||_L+||B||_L. Если A-B > 0, то, ввиду (8), ||A-B||_L < ||A-B||. Поскольку ||(A-B)e_i||=a-b, то ||A-B||=||A||-||B||. Следовательно, ||A||_L < ||A||-||B||+||B||_L или ||B||-||B||_L < ||A||-||A||_L, что и требовалось. Случай A і B рассматривается аналогично. q.e.d.

3.2  Глобальная асимптотическая устойчивость некоторых динамических систем.

Положим по определению

a(z)=- min i  min x О X  Jii(x,z),   X М Rn.

(10)

Пусть е_i=1ⁿ x_i - первый интеграл системы (9), т.е. е_i=1ⁿ f_i(x,z) = 0. Отсюда следует, что J(x, z)L М L. Мы наложим более сильное ограничение: для всех t і 0, x О X и z О W матрица exp(tJ) задает марковское отображение, что эквивалентно условию неотрицательности недиагональных элементов и равенству нулю суммы всех строк матрицы J.

Пусть X - компактное выпуклое подмножество аффинного многообразия L+c, c О Rⁿ, и, кроме того, X инвариантно относительно динамической системы (9). Теперь предположим, что существует такая матрица B і 0, что

(а) для всех z О W, x О X J(x,z) + (z+a(z))I і B, где I является единичной матрицей, z і 0;

(б) B - пропорциональна марковской матрице и для некоторого n₀ О N коэффициент эргодичности k( (I +B)^n₀ ) > 0.

Теорема 3 Для любого t₀ О R и t > 0 отображение x(t₀+t, t₀, ·): X® X является сжимающим. Если, сверх того, при фиксированном t и фиксированной функции z(t)

sup t0 О R  exp ж и у х t0+t t0  a(z(t))dt ц ш =C(t) < Ґ,

то коэффициент сжатия отображения x(t₀+t, t₀, ·) равномерно по t₀ ограничен сверху числом q < 1.

Доказательство. Пусть F(t₀+t, t₀, g) = ¶x(t₀+t, t₀, g)/¶g матрица Якоби отображения x(t₀ +t, t₀, ·): X® X. Тогда F задает марковское отображение. Из теории дифференциальных уравнений известно, что Fў_t=J(x(t₀+t, t₀, g), z(t))F(t₀+t, t₀, g), F(t₀, t₀, g)=I (это - т.н. уравнение в вариациях). Введем

Y(t)=Fexp ж и zt+ у х t0+t t0  a(z(t))dt ц ш

и

A(t)=J ж и x(t0+t,t0,g),z(t) ц ш +(z+a(z(t0+t)))I.

Из неравенства A(t) і B и уравнения Yў(t)=A(t)Y(t), Y(0)=I, с помощью леммы 3.1 можно получить следующие оценки:

Y(t) і exp(tB) і  tn0exp(-t) (n0)! (I+B)n0.

Принимая во внимание лемму 3.2, получаем

k(Y(t)) і  tn0exp(-t) (n0)! k((I+B)n0) > 0.

Поскольку

k(F) = k(Y)exp ж и -zt- у х t0+t t0  a(z(t))dt ц ш ,

обнаруживаем, что k(F) > 0, или ||F||-||F||_L > 0. Поскольку ||F||=1, находим, что sup_{g О X}||F||_L < 1. При условии C(t) < Ґ легко получить равномерную оценку по t₀.

Наконец, положим

g(s)=(1-s)g1+sg2, 0 Ј s Ј 1, g1, g2 О X.

Замечая, что gў(s)=g₂ - g₁ О L, получаем

||x(t0+t,t0,g2)-x(t0+t,t0,g1)|| Ј у х 1 0  ||F ж и t0+t,t0,g(s) ц ш gў(s)||ds Ј

Ј sup g О X  ||F||L у х 1 0  ||gў(s)||ds = sup g О X  ||F||L||g2 - g1||.

Последнее доказывает теорему. q.e.d.

4  Доказательства теорем 2.1-2.4

Проверим выполнение условий теоремы 3.3. Во-первых, множество X является выпуклым компактным подмножеством R^m+1 и является подмножеством аффинного многообразия L+r e_m+1, где L - линейное подпространство R^m+1 векторов с суммой координат равной 0.

Во-вторых, матрица Якоби задает марковское отображение F и

a(l)=- min i  min x О X  Jii(x,l) = max (l+r, 1+r/m).

Далее, J(x,l(t))+([`(l)]+a(l(t)))I і B, где

B = ж з з з з з з з з з з з з з з з и 0 - l   0 ... 0 0 0 0 0 - l   ... 0 0 0 0 0 0 ... 0 0 0 : : : ··· :  : : 0 0 0 ... 0 - l   0 0 0 0 ... 0 0 0 - l   0 0 ... 0 0 - l   ц ч ч ч ч ч ч ч ч ч ч ч ч ч ч ч ш ,

[`(l)] определена в (5).

Матрица (I+B)^m имеет следующий вид:

(I+B)m = ж з з з з з з з з з з з и * * * ... * * 0 0 * * ... * * 0 0 0 * ... * * 0 : : : ··· :  : : 0 0 0 ... * * 0 0 0 0 ... 0 * 0 * * * ... * * * ц ч ч ч ч ч ч ч ч ч ч ч ш ,

где * обозначены положительные элементы матрицы.

Отсюда вытекает, что k((I+B)^m) > 0. Остается проверить инвариантность X относительно (3).

Достаточно проверить инвариантность IntX. Если последнее утверждение выполнено, ввиду непрерывной зависимости траекторий (9) от начального условия, всякое решение (9) с начальной точкой на относительной границе X, никогда не покинет X.

Пусть компоненты вектора u(t, t, g)=(u₁(t), ј, u_m(t), V(t)) О IntX. Выполнены следующие строгие неравенства

1=u0 > u1 > u2 > ј > um > 0, V > 0.

(11)

Пусть для любого t О [t,t₀) u(t, t, g) О IntX, но u(t₀, t, g) П IntX. В момент t₀ некоторые неравенства в (11) превращаются в равенства.

Если V(t₀)=0 то [ dV/dt]|_t=t0-0=l(t₀-0) u₁(t₀) і [`(l)] r/m > 0 и мы приходим к противоречию с тем, что V(t₀)-V(t) < 0 для t < t₀.

Следовательно, заведомо V(t₀) > 0. Для уменьшения числа частных случаев введем виртуальную переменную u_m+1 є 0. С ее помощью мы можем переписать выражение для f_m в (4):

fm(u,l) = l(um+1-um)+V(um-1-um).

Поскольку 1=u₀ > u_m+1=0 возможны только следующие два случая. 1) Существует такое i, что u_i-1(t₀)=u_i(t₀) > u_i+1(t₀), 2) существует такое j, что u_j-1(t₀) > u_j(t₀)=u_j+1(t₀).

В случае 1) [(du_i-1)/dt]|_t=t0-0 = V(t₀)(u_i-2(t₀)-u_i-1(t₀)) і 0, [(du_i)/dt]|_t=t0-0 = l(t₀-0)(u_i+1(t₀)-u_i(t₀)) < 0. Получаем [(d(u_i-1-u_i))/dt]|_t=t0-0 > 0 и приходим к противоречию с тем, что [u_i-1(t₀)-u_i(t₀)]-[u_i-1(t)-u_i(t)] < 0 при t < t₀. Случай 2) рассматривается аналогично. Аналогичная идея использовалась в [4,Лемма 2].

Применение теоремы 3.3 дает все заключения теоремы 2.1 и завершает доказательство. q.e.d.

Доказательство. [Доказательство теоремы 2.2.] Без потери общности предположим l(t) є l для любого t, следовательно, T_N(t,t)=T_N(t-t). Теперь воспользуемся методом, изложенным в [2].

Пусть C(X) - банахово пространство непрерывных функций на X c равномерной метрикой ||f||=max_{x О X} |f(x)|. Определим полугруппу T(t) на C(X) по правилу

T(t)f(g)=f(u(t, 0, g)).

(12)

В разделе 2 мы определили полугруппу T_N(t)=T_N(t,0) на C(X_N). Полугруппы T(t), T_N(t) сильно непрерывны. Пусть A (A_N) обозначает производящий оператор полугруппы T(t) (T_N(t)). Обозначим через D(A) область определения оператора A. Из (12) следует, что f О D(A) для любой функции f О C(X) с

¶f/¶u1, ј,¶f/¶um,¶f/¶V,   ¶2 f/¶2 u1, ј, ¶2 f/¶2 um,¶2 f/¶2 V О C(X).

Обозначим через D множество всех таких функций. Можно показать, что D является существенным (core, см. [4,c.31] и [5]) подпространством оператора A. Ввиду теорем о сходимости марковских процессов (см., например, [5,Chapter 1, Theorem 6.1]) достаточно проверить, что для всех f О D

lim N®Ґ  sup x О XN  |AN f(x)-A f(x)|=0,

что можно проделать аналогично [4]. q.e.d.

Доказательство. [Доказательство теоремы 2.3] Теорема является следствием теоремы 2.2 и, например, [5,Chapter 4, Theorem 2.11]. q.e.d.

Доказательство. [Доказательство теоремы 2.4.] Пункт (а) вытекает из пункта (в) теоремы 2.1.

Перейдем к доказательству пункта (б). Пусть m_N,t - инвариантная мера процесса U_N,t(n). Множество X компактно, следовательно, множество вероятностных мер на X также компактно относительно слабой сходимости. Из теоремы 2.2 следует, что всякая мера m_t, являющаяся предельной точкой для последовательности мер m_N,t, инвариантна относительно полугруппы T(t+nT), n=0, 1, ... . Ввиду пункта (а), m_t совпадает с мерой, сосредоточенной в точке u(t, 0, g^*) и доказательство завершено. q.e.d.

5  Замечание о модели из [4]

В [4] рассмотрена модель системы обслуживания S_N, с N одинаковыми обслуживающими приборами с неограниченной очередью к каждому из них, наполняемая пуассоновским входным потоком с интенсивностью Nl. Времена обслуживания н.о.р. экспоненциально со средним 1. При прибытии каждая заявка выбирает случайно 2, возможно, совпадающих, прибора (с вероятностью 1/N²) и затем направляется к прибору с меньшей очередью (включая заявку, находящуюся в обслуживании). Если очереди к обоим приборам одинаковы, заявка наугад равновероятно выбирает одну из них. Мы рассмотрим систему S_N^m с ограничением m на максимальную длину очереди. В системе S_N^m заявка, выбравшая обе очереди с m заявками, покидает систему.

Уравнения среднего поля для S_N^m при N®Ґ имеют следующий вид

Ч u   k  = (uk+1-uk) +l(uk-12 - uk2),   k=1, ј,m -1 , Ч u   m  = -um +l(um-12 - um2),

(13)

где 1 = u₀ і u₁ і ј і u_m і 0 , u_k - доля приборов, в очереди к которым стоит не меньше k заявок (включая обслуживаемую в данный момент). Введем переменную V:

Ч V   = u1 +lum2 - l,V і 0, V(0) = m - m е i=1  ui(0).

(14)

Пусть x О R^m+1 обозначает вектор

(x1, ј,xm+1)=(u1,ј,um,V).

Запишем систему (13), (14) следующим образом

Ч x   =f(x,l)

(15)

Множество X (см. раздел 3.2) определяется так:

X = {x О Rm+1| 1 і x1 і ј і xm і 0,  xm+1+ m е i=1  xi = m, xm+1 і 0 }.

Ввиду [4,Лемма 1], множество X инвариантно относительно (15). Найдем матрицу Якоби

J(x,l) = ж з з з з з з з з з з з и -b1 1 0 ... 0 0 0 2lu1 -b2 1 ... 0 0 0 0 2lu2 -b3 ... 0 0 0 : : : ··· :  : : 0 0 0 ... -bm-1 1 0 0 0 0 ... 2lum-1 -bm 0 1 0 0 ... 0 2lum 0 ц ч ч ч ч ч ч ч ч ч ч ч ш ,

где b_i = 1+2lu_i. Ввиду (10) a(l)=1+2l. Ясно, что J(x, l)+a(l) I і B где

B = ж з з з з з з з з з з з и 0 1 0 ... 0 0 0 0 0 1 ... 0 0 0 0 0 0 ... 0 0 0 : : : ··· :  : : 0 0 0 ... 0 1 0 0 0 0 ... 0 0 0 1 0 0 ... 0 0 1 ц ч ч ч ч ч ч ч ч ч ч ч ш ,

Матрица (I + B)^m имеет следующий вид

(I+B)m = ж з з з з з з з з з з з и * * * ... * * 0 0 * * ... * * 0 0 0 * ... * * 0 : : : ··· :  : : 0 0 0 ... * * 0 0 0 0 ... 0 * 0 * * * ... * * * ц ч ч ч ч ч ч ч ч ч ч ч ш ,

где * обозначает положительные элементы матрицы.

Отсюда вытекает, что k((I + B)^m) > 0 и, следовательно, справедлива

Теорема 1 Для любого l > 0, динамическая система (5.1), (5.2) имеет единственное экспоненциально глобально устойчивое стационарное решение.

Рассмотрим систему

Ч x   =f(x,l(t)),

(16)

где f(x, l) определена в (15), а T-периодичная функция l(t) кусочно-непрерывна с infl(t) > 0.

Следующая теорема непосредственно вытекает из теоремы 3.3.

Теорема 2 Динамическая система (16) имеет единственную экспоненциально притягивающую T-периодичную траекторию.

Благодарности

Работа первого автора поддержана грантами РФФИ N960100377 и N99-01-01104. Работа второго автора частично поддержана грантом s98-2042 фонда ISSEP.

Список литературы

[1]

Afanassieva L.G., Fayolle G., Popov S.Yu. Models for transportation networks. - Journal of Mathematical Science, 1997 v.84, N3, p. 1092-1103.

[2]

Добрушин Р.Л. Центральная предельная теорема для неоднородных цепей Маркова. I//Теория вероятностей и её приложения, Т.1, N⁰1, с.72-89.

[3]

Добрушин Р.Л. Центральная предельная теорема для неоднородных цепей Маркова. II//Теория вероятностей и её приложения, Т.1, N⁰4, с.365-425.

[4]

Введенская Н.Д., Добрушин Р.Л., Карпелевич Ф.И. Система обслуживания с выбором наименьшей из двух очередей - асимптотический подход. - Проблемы передачи информации, 1996, т. 32, N1, с. 20-34.

[5]

Either S.N., Kurtz T.G. Markov Processes characterization and convergence. N.Y.: John Willey and Sons, 1986, 529 p.

[6]

Vvedenskaya N.D. and Suhov Yu.M. Dobrushin's Mean-Field Approximation for a Queue with Dynamic Routing. - Markov Processes and related fields, 1997, N3, p. 493-526.

Перевод заглавия на английский язык:
Stochastic transportation networks and stability of dynamical systems

Содержание