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

Теория массового обслуживания — богатая и интенсивно развивающаяся область математического знания. Начиная с работ А. К. Эрланга [1], ей была присуща очевидная практическая направленность, что приводило к появлению множества естественных и интересных вероятностных задач.

В настоящей диссертации исследуются модели теории массового обслуживания, связанные с сетями из перемещающихся приборов. Такого рода системы получили название поллинг-систем и они являются популярной областью среди исследователей (см., например, книгу А. А. Боровкова [2]). Отметим, что очень многие классические модели теории массового обслуживания по сути своей являются поллинговыми. Вспомним, например, модель Б. В. Гнеденко [3] системы из п ткацких станков, время от времени выходящих из строя (из-за обрыва нити) и требующих ремонта, оказываемого т работниками, перемещающимися между станками. Вероятностная модель, избранная Б. В. Гнеденко приводила к исследованию марковской цепи с непрерывным временем и состоянием, описываемым одной переменной, а именно, числом неисправных станков (такая система, в частности, описана в книге В. Феллера [4, I том, раздел XVII.7]). Очевидно, в этой задаче достаточно естественно возникает поллинговая модель обслуживания заявок, возникающих на станках, перемещающимися работниками. Однако, учёт того, что работники перемещаются, очень усложняет анализ функционирования описанной системы.

Как и в других математических дисциплинах, в теории массового обслуживания можно наблюдать постепенное усложнение исследуемых моделей и задач, вызванное необходимостью лучше понять изучаемые явления. Развитие происходит от простейших моделей с одним обслуживающим прибором к сетям обслуживания со случайным выбором обслуживающего прибора и далее к сетям обслуживания, на которых загрузка при сложном взаимодействии с заявками перераспределяется между приборами (именно к последнему классу относятся поллинговые системы). При этом наблюдается стремление исследовать как можно более широкий класс возможных распределений времён обслуживания и времён между появлениями заявок. Далее будут упомянуты некоторые работы, в которых отражается отмеченная тенденция.

А.К. Эрланг [1] (см. также книгу А. Я. Хинчина [5, § 20]) получил свои известные формулы с использованием теории цепей Маркова с конечным пространством состояний. Кроме того, он изучал цепи Маркова со счётным пространством состояний, которые описывались счётной системой линейных дифференциальных уравнений, где вопросы о сходимости к стационарному решению уже требуют привлечения тонких вероятностных соображений (этот вопрос решили А. Н. Колмогоров [6] и В. Феллер [4,.

I том, гл. XVII.5]). Формулы Эрланга получены в предположениях на экспоненциальное распределение времени обслуживания и пуассоновость входного потока заявок. Эти предположения казались слишком ограничительными и многие исследователи обратились к изучению общего времени обслуживания. В случае конечной системы обобщение формул Эрланга получил Б. А. Севастьянов [7].

Формулы, описывающие стационарное поведение систем с общим временем обслуживания получили Ф. Поллачек [8] и А. Я. Хинчин [9] (см. также работы Д.Г. Кен-далла [10, 11]). В работе Д. В. Линдли [12] изучалось асимптотическое поведение времени ожидания начала обслуживания при поступлении в очередь к одному обслуживающему прибору. В [12] интервалы между поступлением заявок и времена обслуживания считались последовательностями независимых одинаково распределённых величин. При аналогичных условиях Дж. Кифер и Дж. Волфовиц [13] исследовали уже случай нескольких обслуживающих приборов. Затем P.M. Лойнес [14, 15] обобщил результаты Д. В. Линдли, а также Дж. Кифера и Дж. Волфовица на случай стационарных метрически транзитивных последовательностей времён обслуживания, обнаружив, в частности, что стационарный режим для систем с несколькими обслуживающими приборами может не быть единственным. Дальнейшие результаты и обобщения в области систем с общими временами обслуживания и интервалами между поступлениями заявок получили П. Франкен [16] и А. А. Боровков [17], что нашло отражение в книге А. Брандта, П. Франкена и Б. Лизека [18]. Также упомянем работу Дж.Ф. Кингмана [19] об алгебраической природе формул для стационарного распределения времени ожидания и числа заявок в очереди к одному прибору.

Другое направление в усложнении исследуемых моделей состоит в изучении сетей систем массового обслуживания, в которых заявки перемещаются от одной системы к другой. В рамках этой задачи замечательное наблюдение сделал Дж.Р. Джексон [20, 21], обнаруживший явные формулы для стационарного распределения числа заявок, проходящих последовательность обслуживающих приборов сообразно некоторой обрывающейся цепи Маркова. Многочисленные примеры явных решений для многочисленных сетей обслуживания приведены в книге Ф. П. Келли [22]. Тем не менее, сложность изучаемых сетей обслуживания очень велика и явные формулы для стационарного состояния системы удаётся найти лишь с учётом предположений экспоненциальности времён обслуживания и пуассоновости входного потока.

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

В частности, в настоящей диссертации изучается следующая модель, возникшая из попыток разгрузки центров городов с помощью введения системы электромобилей. Предполагается, что сами электромобили находятся на некоторых стоянках, на которые приходить пользователи, забирающие автомобили на время поездки и оставляющие их, возможно, на какой-нибудь другой стоянке. Транспортные сети такого сорта введены в работе Л. Г. Афанасьевой, Г. Файоля, С. Ю. Попова [23], и их в дальнейшем изучали Л. Г. Афанасьева, Ф. Делкойн, Е. М. Гинзбург, В. И. Оселедец, Г. Файоль, Д. В. Хмелёв [24, 25, 26, 27, 28, 29]. Обзор по поллинговым моделям можно найти в книге А. А. Боровкова [2] (см. также [30]).

Вплоть до недавнего времени арсенал методов теории массового обслуживания не позволял эффективно подходить к изучению подобных моделей. Обычно можно легко задать цепь Маркова, которая описывает изучаемую систему. Однако, пространство состояний марковской цепи оказывается существенно многомерным и выписать стационарное распределение за редкими исключениями не удаётся. Например, Р. Л. Добрушин придерживался той точки зрения, что явные формулы для стационарных распределений в «общем случае» получить нельзя (см. обзор Ф.И. Карпе-левича, Е. А. Печерского и Ю. М. Сухова [31] о подходе Р. Л. Добрушина к теории сетей систем массового обслуживания). Среди исключений есть, впрочем, уже упомянутый представительный класс открытых и замкнутых сетей Джексона, введённый самим Дж.Р. Джексоном в 1963 году в работе [21]. С точки зрения вычисления операционных характеристик системы интересно знать именно явную формулу для стационарного распределения, из которой хорошо видно, как параметры системы влияют на целевую функцию. Поэтому возникает вопрос о нахождении асимптотических формул для стационарного распределения в многочисленных предельных случаях: для большой или малой загрузки, нулевых времён перемещения (в частности, результат Б. В. Гнеденко [3] может рассматриваться как предельный случай ситуации, когда время перемещение работников между станками равно нулю) и пр. В настоящей диссертации асимптотические формулы изучаются в предельном случае, отвечающем большой размерности системы массового обслуживания (большая размерность чаще всего связана с большим числом приборов или очередей к этим приборам, каждую из которых надо описывать отдельной координатой). Такую задачу можно решать с помощью так называемого метода среднего поля. Этот метод состоит из следующих шагов. Сначала надо выбрать пространство состояний сети таким образом, чтобы при увеличении числа компонент сети поведение системы становилось все более и более детерминированным, а в пределе состояние системы описывалось бы детерминированной системой дифференциальных уравнений (которые могут быть и нелинейными). Далее, при соблюдении условий эргодичности системы показывается, что имеется единственная неподвижная точка, которая притягивает все остальные решения. Отсюда следует, что единственная мера, инвариантная относительно этой системы дифференциальных уравнений, сосредоточена в её неподвижной точке. Далее необходимо показать, что семейство всех инвариантных мер допредельных конечных сетей являются относительно компактным. Отсюда следует, что для всякой последовательности мер имеется сходящаяся подпоследовательность. Однако, сходящаяся подпоследовательность мер должна быть инвариантна относительно предельной динамики и отсюда извлекается, что предельная точка должна совпадать с вырожденной мерой, сосредоточенной в неподвижной точке.

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

Согласно обзору [31], этот метод в «интуитивной» форме известен математикам и инженерам довольно давно — с 60-х годов XX века, однако, вопрос о строгом обосновании всех описанных шагов сталкивается с большими трудностями. Авторы обзора [31] называют гипотезой Р. Л. Добрушина утверждение о том, что все шаги описанного метода действительно можно строго обосновать математически в большинстве систем. К этой гипотезе очень близка несколько более частная гипотеза А. А. Боровкова о предельном поведении замкнутой полностью симметричной сети Джексона с общим временем обслуживания заявок (см. [32]). Отметим, что гипотеза Боровкова доказана лишь в двух частных случаях, а именно A.JI. Столяр [33] разобрал случай постоянного распределения времени обслуживания, а Ф.И. Карпе-левич и А. Н. Рыбко [34] изучили случай экспоненциально распределённого времени обслуживания.

Одним из самых сложных вопросов является вопрос о сходимости решений нелинейной системы дифференциальных уравнений к неподвижной точке. В частности, после работы [32] Ф. И. Карпелевича и А. Н. Рыбко именно доказательство сходимости некоторой нелинейной системы уравнений к неподвижной точке осталось последним препятствием в доказательстве гипотезы А. А. Боровкова.

Такого рода задача называется задачей о глобальной асимптотической устойчивости. Заметим, что хорошо развита лишь теория локальной устойчивости, то есть, устойчивости в окрестности неподвижной точки, в то время как в случае глобальной асимптотической устойчивости исследователь может надеяться лишь на собственную интуицию, которая поможет ему построить функцию Ляпунова (которую иногда называют пробной функцией). Одним из немногих свойств нелинейной системы дифференциальных уравнений, которые позволяют исследовать её сходимость к неподвижной точке, является покоординатная монотонность решений по начальному условию. Такое свойство действительно имеется для целого класса систем возникающих в данном контексте, хотя и требует определённого искусства в выборе системы координат.

Монотонность, однако, не имеет мест для систем с законом сохранения типа суммы координат. Тогда никакие два начальных данных с одинаковой суммой координат не сравнимы между собой. Между тем, в силу свойств допредельной стохастической динамики иногда в детерминированном пределе остаётся монотонность решений по начальным состояниям. В теореме 14 (см. ниже) показана эквивалентность монотонности по начальным данным и неотрицательности недиагональных элементов матрицы Якоби исследуемой системы дифференциальных уравнений. Из того, что матрица Якоби неотрицательна вне диагонали и из того, что сумма координат является первым интегралом системы, следует (при некоторых дополнительных условиях технического характера), что фазовый поток является сжатием. Этим фактом, разумеется, можно воспользоваться для доказательства существования неподвижной точки и сходимости к ней решений с любыми другими начальными данными.

Такое наблюдение представляется достаточно общим, и, насколько известно автору диссертации, все системы, возникающие в данном контексте, для которых удалось провести полное исследование сходимости к единственной неподвижной точке, попадают в указанный класс. Описанный результат для конечномерных нелинейных систем дифференциальных уравнений доказан в первой главе диссертации. Далее он применяется в проведении изложенной выше программы исследования асимптотических характеристик. В первой главе описано несколько таких применений: для простейшей транспортной сети, для сети приборов с выбором наименьшей из двух очередей, кластерной транспортной сети, а также для транспортной сети с непоказательным распределением времени перемещения приборов.

Во второй главе диссертации доказано, что изложенное выше наблюдение проходит и в случае счётных систем дифференциальных уравнений. Трудность, связанную со счётностью системы, удаётся обойти с помощью введения семейства компактных инвариантных множеств, которое, как будет показано на примерах, довольно часто можно легко угадать. Любопытным примером применения этого наблюдения в случае счётных систем являются счётные цепи Маркова с непрерывным временем. Известно, что такие цепи Маркова описываются с помощью бесконечной системы линейных дифференциальных уравнений Колмогорова (см. книгу В. Феллера [4]).

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

Если первые две главы посвящены исследованию асимптотического поведения сложных моделей теории массового обслуживания, то третья глава посвящена изучению модели бесконечной транспортной сети. Заметим, что теория асимптотического поведения конечных моделей теории массового обслуживания довольно хорошо развита [31], в то время как изначально бесконечных моделей ещё не так хорошо исследованы (см. работы А. А. Боровкова, Д. Коршунова, Р. Шацбергера [35] и С. Г. Фосса, Н. И. Черновой [36]). При введении в модель существенной бесконечности появляются неожиданные эффекты. Например, в третьей главе показано, что транспортная сеть никогда не является эргодичной, что обусловлено наличием семейства различных инвариантных мер. Это связано с тем, что транспортная сеть является обобщением хорошо известного процесса с нулевой областью зависимости, который открыл Ф. Спицер [37]. Процесс с нулевой областью зависимости относится к широко известному классу систем взаимодействующих частиц, появившемуся из разнообразных физических моделей, вроде модели Изинга (см. книгу Т. М. Лиггетта [38]). Процессу с нулевой областью зависимости посвящено много работ (см. Ф. Спицер [37], Т. М. Лиггетт [39], Е. Вэймер [40], Е. Д. Анджел [41], М. Я. Кельберт, М. Л. Концевич и А. Н. Рыбко [42]). Третья глава посвящена обобщению полученных этими авторами результатов на случай бесконечной транспортной сети. Кроме того, в ней показано, как можно применить метод среднего поля для получения устойчивости бесконечной транспортной сети в пределе метода среднего поля.

Более подробное изложение результатов, полученных в диссертации, требует некоторых определений. Как обычно, обозначим n-мерное вещественное пространство через Rn. Для всякого х = (жх,., £&bdquo-)т € Е" определим норму ||-|| по правилу ||ж|| = |a-i| +. + |ж&bdquo-|, где | • | означает абсолютную величину числа. Под понимается множество покоординатно неотрицательных векторов х <Е Rn. Под I: Жп Rn подразумевается тождественное отображение: Ix = х для всех х € R71.

Введём линейное подпространство L = {х Е W1: Xi +. + хп = 0}. Линейное отображение A: Rra —" Мп назовём марковским, если транспонированная матрица этого отображения является стохастической или AR" С Ж&trade-, (1, ., 1) А = (1, ., 1). Пусть, А = аВ — отображение, пропорциональное марковскому отображению В с коэффициентом пропорциональности, а > 0. Для такого отображения, А определим коэффициент эргодичности k (A) по правилу к (А) = ЦАЦ — ||A||L. Здесь.

А\= sup ||Аж|| = max||Aej||, sup ||Лж|| =тахр (е^-е^)||/2, a-eL,||ffi||=l где ||а-|| = |re 11 +. + хп, а {е*} — стандартный базис в Rn. Отметим, что ||Б|| = 1, к (В) = 1 — j|B|ji и к{А) = ак (В). Для стохастических матриц Вт коэффициент эргодичности ввёл P. JL Добрушин и его определение совпадает с нашим (см. [43, с. 77, (1.12')] и [44, с. 372, (3.22)]).

Первая глава диссертации посвящена исследованию конечномерных моделей. В разделе 1 исследуется автономная конечномерная система дифференциальных уравнений x = f (x), xeRn, (*) обладающая следующими свойствами.

1) векторное поле f (x) дифференцируемо по аи матрица Якоби.

J (x) = df/dx = (dfi/dXj) непрерывно зависит от х. Эти условия обеспечивают при t ^ 0 существование и единственность решения x (t, g) системы (*) с начальным условием ж (0, д) = д. Кроме того, x (t, g) непрерывно дифференцируемо по д.

2) Существует множество X, инвариантное относительно динамической системы (*), и, кроме того, X — компактное выпуклое подмножество аффинного многообразия L + с при некотором cGln.

3) Система (*) обладает первым интегралом Ym=ixii т-еfi (x) — 0- Отсюда следует, что J (x)L С L или, что-то же самое, сумма строк матрицы J (x) равна нулю. Кроме того, недиагональные элементы матрицы J (x) неотрицательны при всех.

Заметим, что третье условие носит вероятностный характер и означает, что матрица J (x) является матрицей интенсивностей переходов некоторого марковского процесса (см. книгу И. И. Гихмана и А. В. Скорохода [46], а также книгу Дж.Р. Норри-са [45]).

Здесь и далее, в изложении результатов диссертации используется независимая нумерация, но в скобках указывается ссылка на исходное утверждение из основного текста диссертации. Во избежание затемняющих суть дела технических подробностей иногда утверждения приводятся не в самой общей форме. Например, результаты о сжатии фазового потока приводятся лишь для автономных систем дифференциальных уравнений, хотя в основном тексте диссертации доказаны аналогичные утверждения в неавтономном случае).

Теорема 1 (Теорема 1.6). Если выполнены условия 1)-3), то для любых начальных условий g°, д1? X при всяком t ^ 0 выполнено неравенство т. е. функция x (t,-): X —> X не увеличивает расстояние между любыми двумя точками.

Теперь предположим, что существует линейное отображение В ^ 0, удовлетворяющее при некотором? ^ О следующим условиям а) при всех х е X верно неравенство J{x) + (7 ^ J5, где I является единичной матрицейб) В — пропорционально марковскому отображению и при некотором щ € N выполнено k ((I + В) п°) > 0.

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

Теорема 2 (Теорема 1.9). В условиях 1)~3) и (а)-(б) при всяком t > 0 существует такое q = q (t) < 1, что для любых начальных условий g°, д1 G X выполнено неравенство.

М^д1) — x (t, g°)\ ^ q\gl-g т. е. отображение x (t, ¦): X -" X является сжимающим с коэффициентом сжатия q = q (t) < 1.

Дальнейшие обобщения этих теорем приведены в разделе 1 главы 1. Рассмотренные нелинейные дифференциальные уравнения очень естественно появляются при применении метода среднего поля к некоторым сложным моделям теории массового обслуживания.

В разделе 2 главы 1 изучается сеть из N узлов и rN обслуживающих приборов (автомобилей). В каждый узел в соответствии с пуассоновским потоком интенсивности X (t) поступают заявки (пассажиры). Пуассоновские потоки заявок в разные узлы независимы. Заявка, попавшая в пустой узел, покидает систему. Если заявка попадает в узел с приборами, то случайно и равновероятно выбирается один из приборов, который забирает заявку и перемещается экспоненциально распределённое время. Движение прибора моделируется с помощью введения дополнительного виртуального узла: когда прибор начинает перемещаться, он попадает в виртуальный узел, где находится экспоненциально распределённое время со средним значением 1, а затем перемещается в узел, равновероятно выбираемый из всех N узлов. Если число приборов в выбранном узле равно т, прибор ждёт следующей попытки в виртуальном узле экспоненциально распределённое время со средним 1 и т. д. Таким образом, в каждом узле (кроме виртуального) может находиться от 0 до т приборов.

Пусть щ — число узлов, количество приборов в которых равно ку fk = щ/N — доля этих узлов, W — количество приборов, находящихся в виртуальном узле, а V = W/N. В технических целях удобно перейти от Д к накопленным долям ик = Y^Lk /"•.

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

Из наших предположений следует, что эволюция системы описывается некоторым марковским процессом ?/#(?), для которого можно выбрать пространство состояний Хм содержащее все такие вектора и = (ui, ., ит, V) T из (1/7V)Z++1, что выполнены неравенства.

1 = щ ^ iii ^ ¦ • ¦ > ит ^ О, V ^ 0 и V + щ +. + ит = г. (*).

Кроме того, из наших предположений следует, что производящий оператор Ajq{t) процесса U^it), который действует на функции над XN, задаётся следующим образом ш—1.

A?f (и) = NX (t) — uk+1)[f (u — ek/N + em+l/N) — f (u)}+ k=1 N (t)um[f (u — em/N + em+i/N) — f (u)}+ m NVY,(V>k-i — uk)[f (u + ek/N — em+i/N) — f (u)}, k=l где e* — вектор, г-тая координата которого равна 1, а остальные координаты равны 0. В силу конечности Xn оператор AN (t) определяет единственный марковский процесс UN (t).

Метод среднего поля подсказывает, что в пределе при N —> со эволюция и становится детерминированной. Более точно: пусть X означает множество всех векторов Rm+1, удовлетворяющих (*). Тогда, если распределение начального состояния U^ (0) сходится к вырожденной мере, сконцентрированной в точке д е X, то распределение Слг (£) сосредотачивается при больших N на траектории u (t) е X, удовлетворяющей системе дифференциальных уравнений w = /(u, А), (**) где fi (u, А) = A (ai+1 — щ) + 1 — щ), г — 1, .т — 1, щ = 1, /то (и, Л) = -ит + V (wm 1 — ито), /m+i (u, л) = Ami — V (1.

Система (я*) является нелинейной с квадратичной правой частью. Чтобы строго сформулировать утверждение о сходимости процесса U^it) к решению u (t, g) системы (**) с начальным условием д, определим семейство производящих операторов Тдг = Tjv (t) по правилу.

Теорема 3 (Теорема 2.2). Для всех /? С (Х), равномерно по t на произвольном отрезке из R+ = {t ^ 0},.

Доказательство этой теоремы опирается на классические результаты о сходимости марковских процессов, если сходятся их производящие операторы [47].

Обозначим через ед дискретную вероятностную меру, сосредоточенную в точке.

Обозначим через д* точку д* = (и*,., и*т, V*), которая является стационарным решением системы (**) т. е., /((?*, А) = 0. Тогда при k = 1, ., т, V* = V (p) = Ар, где р единственным образом определяется из условия на первый интеграл:

V (p) + щ{р) +. + ит{р) = г.

При обозначении L (p) = щ (р) +. + ит (р), с учётом V = Хр последнее условие принимает вид.

L{p) + А р = г.

Если A (t) — постоянна, то процессы U^ (t), образуют семейство однородных цепей Маркова с непрерывным временем и конечным числом состояний, каждая из которых в силу неприводимости обладает единственной инвариантной мерой.

TN (t)f (g) = Е (f (UN (t)) | UN (0) = д), де XN.

N-*oo0 <^s<^tg€XN lim sup sup |7jv (s)/(^) — f (u (s, g)) = 0. gex.

Теорема 4 (Теорема 2.3). Если 0) no вероятности сходится к eg, то sup ||{7jv (s) — u (s, t, —" 0 no вероятности при всех t ^ 0.

0<.

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

Теорема 5 (Теорема 2.4). Инвариантные меры ц,^ процессов U^ слабо сходятся к дискретной мере, сосредоточенной в д*..

Кроме того, в разделе 2 исследуется случай непостоянного Л (t)..

В разделе 3 показано, как теорему 2 можно применять для доказательства сходимости в модели Н. Д. Введенской, P.JI. Добрушина и Ф. И. Карпелевича [48] с дополнительным ограничением на длину очереди..

Раздел 4 посвящён техническому результату, который позволяет изучать поведение предельной динамической системы строго «внутри» фазового пространства. Дело в том, что на границе фазового пространства свойства динамической системы могут нарушаться: например, может пропадать равномерное сжатие фазового потока..

В разделе 5 рассматривается задача, которая не поддаётся непосредственному применению теоремы 2, но после замены координат удаётся в некоторых показать сходимость частных случаях. У матрицы Якоби, приведённой в разделе 5 первой главы, имеется ровно один элемент, который может принимать отрицательные значения. Во многих современных задачах асимптотического анализа возникают системы дифференциальных уравнений с матрицами Якоби ещё более сложной структуры. Возможно, дальнейшее изучение системы раздела 5 позволит найти более общий подход к системам, в которых отсутствует монотонность..

Раздел 6 посвящён обобщению модели раздела 2 в сторону асимметричности. А именно, узлы разбиваются на несколько районов, в каждом из которых маршрутизация равновероятна. Оказывается, что и в этом случае можно найти неподвижную точку, к которой в силу аналога теоремы 5 и сходятся инвариантные меры конечных систем..

Заметим, что все модели, рассмотренные в разделах 2−6, а также освещённые в многочисленных работах [23, 48, 49, 50, 51, 52, 53] предполагают экспоненциальность распределения времён обслуживания..

В разделе 7 рассмотрена простейшая модель транспортной сети, аналогичная модели раздела 2 с тем усложнением, что время перемещения прибора от одного узла к другому распределено не показательно, а по т.н. гиперэрланговскому закону. Ги-перэрланговским законом называют конечную смесь эрланговских распределений, а эрланговское распределение, в свою очередь, имеет плотность 0 при х < 0 и и1×1е~ух/(/ — 1)! при х > 0, где параметры удовлетворяют условиям и > 0 и I? N..

Хорошо известно (см., книгу Н. П. Бусленко, В. В. Калашникова и И. Н. Коваленко [54, с.265−269], а также книгу С. Асмусена [55, с.71−78]), что конечная смесь эрлан-говских распределений сколь угодно точно в метрике пространства L1 приближает любое заданное наперёд распределение с конечным средним..

Основной результат раздела 7 состоит в том, что при большом количестве компонент системы распределение приборов по узлам сети зависит лишь от математического ожидания гиперэрланговского распределения, а вид этого распределения такой же как для экспоненциального случая. То есть распределение числа приборов по узлам описывается теми же формулами, что и в разделе 2..

Вторая глава диссертации посвящена исследованию существенно счётномерных систем. В разделе 1 изучается устойчивость некоторого специального класса счётных систем дифференциальных уравнений. Подход к исследованию устойчивости состоит в усовершенствовании подхода, изложенного в разделе 1 первой главы диссертации. Различие между конечномерным и счётномерным случаем у систем из рассматриваемого класса аналогично различию между конечными и счётными цепями Маркова. Условие на положительность коэффициента эргодичности некоторой степени матрицы Якоби соответствует условию Дёблина эргодичности цепи Маркова (об условии Дёблина см. [56]). Хорошо известно, что условие Дёблина весьма ограничительно, и, например, обычный процесс рождения и гибели с существенно счётным пространством состояний ему уже не удовлетворяет. Можно показать, что у всех бесконечных систем дифференциальных уравнений из [48, 57, 49, 50, 34] коэффициент эргодичности матрицы Якоби равен 0 (при этом можно воспользоваться приёмом из леммы 1.2). Поэтому вводится обобщение коэффициента эргодичности, которое называется коэффициентом эргодичности по направлению..

С использованием коэффициента эргодичности по направлению можно доказывать строгое уменьшение расстояния между образами любых двух начальных условий. Отметим, что в этом случае нельзя пользоваться принципом сжимающих отображений, поскольку коэффициент сжатия зависит от точки и может быть сколь угодно близок к 1. Поэтому мы используем специальные теоремы о неравномерном сжатии..

Следуя обозначениям и терминологии книги А. Н. Колмогорова и С. В. Фомина [58] обозначим через пространство последовательностей х = (х0, хх,. .)т с нормой \х\ = |жо| + l^i| +. Мы полагаем х бесконечным столбцом, чтобы подчеркнуть аналогию с конечномерным случаем. Норма ||-|| индуцирует норму, а следовательно, и топологию на ограниченных линейных операторах A: lx \А\ = sup||Ar||/||:c|]..

Хфй.

Окрестность точки д € 1 обозначим через Ue (g) = {х? l | ||д — ж|| < е}. Все векторные и матричные неравенства следует понимать как покомпонентные. Под I понимается тождественное преобразование: Ix = х для всех х? 1..

Линейное отображение, А 1Х -> назовём марковским, если Ah ^ 0 при любом h ^ 0 и (1, .1, .)А — (1, .1, .). Заметим, что отображение, А — марковское, если его транспонированная бесконечная матрица является стохастической..

Введём линейное подпространство L = {д Е l | до +. = ()}. Рассмотрим отображение, А = аВ, где, а > 0 и В — марковское отображение, В: li —v Определим коэффициент эргодичности k (A, g) отображения А: 1 —> 1 по направлению g Е /i{0} по правилу k (A, g) = ||А||||з|| - ЦА^Ц. Здесь.

А\ = sup ||Ас|| =8ир||^||,.

X6ii,||"||=l г где efc — вектор, каждая координата которого, кроме к-й равной 1, равна 0. Очевидно, к{А, д) = ак{В, д)..

Можно также определить коэффициент эргодичности отображения, А по правилу к (А) = || Л || - ||Л||х,. Это определение аналогично определению пункта 1.1 первой главы. Очевидно, к (А) = inf ММ = щ sup Ж зеьо ||5|| 3&euro-Д0 (Ы|.

Очевидно, если к (А) > 0, то к (А, д) > 0 для всех д? L 0. Обратное утверждение верно в конечномерном случае, но, вообще говоря, неверно в бесконечномерном случае. Действительно, в конечномерном случае (или в случае компактного оператора.

А).

Mn^ir = 1к= fi^ ~ = еА о \д\ sei. llsll=i g? L, M=l e'?L' где L' — {д' д' = Ад при некотором д Е L, ||(?|| = 1}. Множество L' компактно в силу компактности оператора А. Заметим ЦАЦ — ||-|| — непрерывная функция на L' и она принимает те же значения, что и к (А, д) при д Е LО, ||д|| = 1, а потому ||Л|| —1| 0 для всякого д' Е L'. Поэтому функция ||А|| — ||-|| достигает на U минимума, и этот минимум, равный к (А)у строго больше нуля..

Рассмотрим теперь бесконечномерный случай. Назовём размахом ленточной матрицы ограниченного оператора, А такое число d, что аг] = 0, как только i — j > d. Лемма 6 (Лемма 1.2). Пусть В — марковский оператор с размахом d, а > 0 и, А = аВ. Тогда при всех t ^ 0 имеем k (exp (tA)) = 0. Однако, существуют марковские операторы с размахом 1, для которых при всех t > 0 и при всех g Е L выполнено k (exp (tA), g) > 0..

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

Будем говорить, что семейство {Fa} всюду плотно в множестве U С X, если для любого х € U и для любого е > 0 существует такое, а и х 6 Fa, что р (х, х) < е. Автору не удалось найти никаких ссылок на следующую простую теорему, которая очень полезна в контексте исследуемых далее задач..

Теорема 7 (Теорема 1.7). Пусть отображение / строго уменьшает расстояния, т. е. для любых х, у € X выполнено p (fx, fy) < р (х, у). Предположим, что существует семейство {i7^} компактных подмножеств X, удовлетворяющее условиям а) {Fa} всюду плотно в X, б) fFa С Fa для любого Fa 6.

Тогда существует единственная неподвижная точка х* 6 X, удовлетворяющая уравнению fx* = х*, и для любого х G X выполнено fnx -" х*..

Иногда неподвижная точка известна и удобно пользоваться следующим признаком сходимости..

Теорема 8 (Теорема 1.8). Предположим, что X — банахово пространство, а х* — неподвижная точка отображения /. Пусть отображение f строго уменьшает расстояния, т. е. для любых х, у € X выполнено p (fx, fy) < р (х, у). Также предположим, что при некотором е > 0 для множества U?(x*) = {ж G X | Цж — ж*|| ^ е} существует семейство {Fa} компактных подмножеств Ue (x*), удовлетворяющее условиям а) семейство {Fa} всюду плотно в Ue (x*), б) fFa С Fa при всех Fa е {i^}..

Тогда неподвижная точка х* единственна и для любого х G X при п —> со выполнено p (fnx, х*) -" 0..

В счётномерном пространстве, вообще говоря, вопрос о существовании решений системы дифференциальных уравнений надо изучать специально. Пусть x (t, g) — единственное решение системы уравнений х = f (x), xeh, f: 1 г ->• h (**) с начальным условием x (to, g) = g G l. Более того, пусть x (t, g) непрерывно дифференцируемо зависит от начального условия, а производная Ф (t, g) = dx (t, g)/dg решения по начальному условию непрерывна по g и удовлетворяет системе уравнений в вариациях: х = f (x), Ф = J{x)§, x (t0,g) =g е h, $(t0,g) = I: k -)> h, (* * *) где J (x) = (dfi/dxj)ij=1 — матрица оператора Якоби, а I — тождественный оператор..

Теорема 9 (Теорема 1.11). Пусть функция f (x) и её производная J (x) при х? Uv (g) непрерывны и удовлетворяют условиям ||/(ж)|| < Mq, ||"/(ж)|| < Тогда существует такое число 5 > О, 5 = min ('/j/M0,1/Mi), что для всякого t в интервале (t0 — 5, t0 + 5) дифференциальное уравнение (**) имеет одно и только одно решение, удовлетворяющее условиям x (t0,g) = g и x (t, g)? Uv (g). При этом x (t, g) непрерывно дифференцируемо по начальному условию и его производная удовлетворяет уравнению (***)..

Обозначим L = {д? l | до + • • • = 0}. Во всех последующих результатах предполагается, что существует такое выпуклое множество X С с + L, с? что x (t, g) € X при всех д? X при любом t ^ 0 и exp (tJ (g)) ~ марковское отображение..

Теорема 10 (Теорема 1.13). Для любых gQ, д1? X при всех t ^ 0: ||x{t, gl) — x{t, g°)\ ^ lb1.

Чтобы доказать сходимость любого решения к стационарному, необходимо проверять дополнительные условия..

Теперь предположим, что существует линейное отображение В ^ 0, удовлетворяющее при некотором (^ 0 следующим условиям а) при всех х? X верно неравенство J (x) + (I ^ В, где / является единичной матрицейб) В —- пропорционально марковскому отображению и для t > 0 коэффициент эргодичности ехр (Ш) по любому фиксированному направлению д? L {0} строго больше нуля: k (exp (tB), д) > 0..

Теорема 11 (Теорема 1.15). Если X выпукло, X С с + L, где с? 1, и выполнены условия (а) и (б)7 то для любого г > 0 и для любых g°, д1? X, д1 — д° ф 0:.

Теорема 12 (Теорема 1.16). Пусть выполнены условия теоремы 11 и существует семейство компактных множеств удовлетворяющее условиям а) семейство множеств {Fa} всюду плотно в X, б) для любого Fa? {Fa} выполнено x (t, Fa) С Fa при любом t ^ 0..

Тогда существует единственная неподвижная точка д* и для любого g? X выполнено x (t, g) —> g* при t оо..

В следующих разделах 2, 3 главы 2 приводятся примеры явного построения семейства Fa. Иногда можно выбрать Fa = Fg = {x{t, g) 11 ^ 0} и доказать, что для всякого g траектория {x (t, g) | t ^ 0} предкомпактна..

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

Теорема 13 (Теорема 1.18). Если i) существует такая однородная эргодичная положительно возвратная цепь Маркова со счётным числом состояний N U {0} и непрерывным временем, с матрицей интенсивностей переходов Q = (qij), что ^ Jij{x (t, g)) ^ 'Yho.mi nPU любых l^k l^k j ^ т, к € {0,., з] U {т + 1,.}, t > 0, д е Xii) существует неподвижная точка g* = x (t, g*) G X, то для любого g € X траектория решения {x (t, g) | t ^ 0} предкомпактна..

Связь требования на неотрицательность недиагональных элементов матрицы J (g) с поведением x (t, g) раскрывается в следующей теореме..

Теорема 14 (Теорема 1.22). Пусть x (t, g) € h при любом t ^ 0 и g G 1. Следующие утверждения равносильны: i) для всех g недиагональные элементы J (g) неотрицательны-.

И) для всех g для любого h? h ^ 0 x (t, g + h) ^ x (t, g)..

Эту теорему можно сформулировать для решений x (t, •), остающихся в некотором «толстом» множестве X С hОднако технические условия, которые в этом случае надо наложить на X, затемнили бы существо дела, в то время как максимальной общности нам так и не удалось бы достичь. Доказательства всех описанных теорем проведены в разделе 1 второй главы настоящей диссертации..

В разделе 2 второй главы получено новое доказательство сходимости системы, которую изучали Н. Д. Введенская, P.JI. Добрушин и Ф. И. Карпелевич в [48]. Они показали покоординатную сходимость, в то время как применение теорем 10−14 позволяет доказать сходимость по норме в пространстве 1..

В разделе 3 изучается система дифференциальных уравнений для замкнутой системы с законом сохранения типа суммы компонент..

Пусть г > 0, А > 0. Рассмотрим уравнения среднего поля для симметричной транспортной сети, которая получается при т —"¦ оо из системы, рассмотренной в [27] и разделе 2 первой главы:.

У = ХщV, ul = А («2 — Wi) + v (l — ui), u2 = Л (щ — u2) + V (ui — u2), щ = (u4 — u3) + V (u2 — u3), uk = {uk+i — uk) — V{uk"i — uk)..

Обозначим через u (t, g) единственное решение последней системы с начальным условием и (0, g) — д € 1. Уравнение сокращённо будем обозначать й = f{u)..

Для обоснования существования и единственности локального решения u (t, д) воспользуемся теоремой 9. Действительно, в ограниченном шаре ||u|| ^ С, \f (u)\ ^ 3(Л + С)(1 + ||u||) ^ 3(Л + С)(1 + С). Матрица Якоби имеет следующий вид:.

J (u) =.

-1 X 0 0 0.

1 ¦ - щР, А 0 0 щ — и2 V -/3 А 0 и2 -щ 0 V А.

Щ — щ 0 0 V -0 щ — иъ 0 0 0 V где ft = Л + V. Из вида J (и) следует, что || J (u)|| ^ max (2(A + ||it||), 2(l + IMQ) при ||и|| < С. Условия теоремы 9 выполнены, и для д € h в некоторой окрестности to — О существует решение u (t, g)..

Лемма 15 (Лемма 3.1). Множество оо к=1 является инвариантным множеством системы й = / (и) при г > 0..

При, А > 0 легко найти стационарное решение u (t, д*) = д* при t ^ 0 и доказать его единственность в U. Действительно, приравнивая правые части й = / (и) к нулю, получаем f (g*) = 0, откуда и = V/X = р, = pfc. Принимая во внимание, что К + iii +. = г, получаем уравнение на р: Р.

1-р г-р, которое имеет единственное решение р* при р > 0. Таким образом, <?д = Ар*, =.

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

Теорема 16 (Теорема 3.2). При, А > 0 для любого g G U: \u (t, g) — g*\ —> 0 при t —> оо..

Раздел 4 посвящён краткому перечислению других счётномерных систем дифференциальных уравнений, к которым применим описанный метод..

В разделе 5 изучается неприводимая апериодическая цепь Маркова со счётным пространством состояний, непрерывным временем и ограниченными в совокупности интенсивностями переходов. В этом разделе устанавливается достаточный признак эргодичности цепи Маркова в терминах существования инвариантных подмножеств у описывающей её системы дифференциальных уравнений. Отметим, что задача об эргодичности таких цепей Маркова в терминах существования инвариантного распределения решена полностью, т. е. неприводимая апериодическая марковская цепь с ограниченными интенсивностями переходов эргодична тогда и только тогда, когда имеется единственное инвариантное распределение [4, Том I, раздел XV.7] (см. также [45, с. 122, теорема 3.6.2])..

Очень часто найти само стационарное распределение в явном виде не представляется возможным и интересен сам вопрос об эргодичности цепи Маркова. Существует множество подходов для доказательства эргодичности цепей Маркова, среди которых следует выделить метод обновлений (см. книгу С. Асмусена [55]), метод склеивания (coupling'a), описанный в книге Т. Линдвала [59], и метод пробных функций (метод Фостера-Ляпунова), изложенный с современной точки зрения в книге В. А. Малышева, М. В. Меньшикова и Г. Файоля [56]. Эти подходы не апеллируют (по меньшей мере, явно) к дифференциальным уравнениям, которыми описываются цепи Маркова. В разделе 5 устанавливается некоторая новая теорема о сходимости в терминах системы дифференциальных уравнений, описывающей цепь Маркова..

Без ограничения общности будем считать, что пространство состояний эргодичной апериодической цепи Маркова состоит из целых неотрицательных чисел {0,1,2,.}. Вероятности нахождения в момент t в состоянии pi удовлетворяют прямой системе дифференциальных уравнений Колмогорова (см. [4, т. II]) х = QTx, х е h х = {po, pi,. .)т, где Pi ^ 0, Yi>oPi = 1] а матрица Q задаёт интенсивности переходов..

Далее предполагается, что матрица QT задаёт ограниченный оператор в 1 г, что эквивалентно условию q = sup⁰(—qa) < оо. Обозначим через x (t, p) решение системы дифференциальных уравнений х = Qrx. Через X обозначим множество.

X = {Р € к | Рг ^ О, ]ГРг = 1}. i^O.

Лемма 17 (Лемма 5.1). Пусть существует такое семейство компактных инвариантных подмножеств {Fa}, что для всякого, а выполнено x (t, Fa) С Fa при всех t ^ 0. Кроме того, предположим, что при некотором Q ^ q для всякого g € L выполнено k (exр (Q + С0>#) > Тогда существует единственная неподвижная точка р* G X, причём для всякого р € X имеется сходимость x (t, p) —У р* при t оо..

Таким образом, если есть хотя бы одно компактное инвариантное множество, то существует единственное инвариантное распределение р*. Некоторое обратное утверждение изложено в следующей лемме..

Лемма 18 (Лемма 5.3). Предположим, что существует инвариантное распределение р*. Тогда всякая траектория предкомпактна..

В разделе 6 показано, каким образом можно применять лемму 17 к изучению эргодичности некоторой специальной транспортной сети, состоящей всего из двух узлов, но имеющей бесконечную очередь пассажиров..

Третья глава посвящена изучению транспортной сети с изначально счётным числом узлов. Оказывается, такая сеть является обобщением хорошо известного процесса с нулевой областью зависимости, введённого Ф. Спицером [37]..

Здесь используется терминология, принятая для процессов с нулевой областью зависимости: под частицами подразумеваются приборы, а под ячейками — узлы. Так что, имеется конечное или счётное число частиц, которые находятся в счётном множестве узлов J. Переходы частиц, находящихся в узле г 6 J, происходят после истечения случайного показательно распределённого времени ц с параметром тг-. Если по прошествии этого времени узел i непуст, то одна и только одна из частиц, находящихся в ячейке, мгновенно перемещается в некоторый узел j, который выбирается с вероятностью pij. Все имеющиеся интервалы времени и переходы считаются независимыми в совокупности. Вероятности перехода из г в j составляют матрицу.

Р — {Pij)ijeJ> ^ е J Pij — 1- Этот процесс можно описать с помощью бесконечjeJ ного вектора rj (t) — {цi (t)}ieJ, t > 0, где r) i (t) — это число частиц в узле i в момент t..

Заметим, что пространство состояний этого процесса континуально, и, вообще говоря, необходимо специально доказывать теорему о существовании и единственности самого процесса. Эта теорема обоснована в [60]..

Существование феллеровского процесса r/(t) выводится из существования описывающей его марковской полугруппы S (t) ((S (t)f)(rj) = E (/(?y (i)) | r)(0) = rj)) с помощью известных теорем теории марковских [46]. Построение же марковской полугруппы S (t) можно провести с помощью техники, описанной в книге Т. М. Лиггетта [38]..

Пусть = N U {0}, Z+ = Z+U{oo}. Тогда в пространстве состояний системы W =Z+ можно ввести специальную метрику, в которой само пространство будет компактным. Пусть В — <�т-алгебра, порождаемая цилиндрическими множествами, a C (W) — банахово пространство всех действительно-значных функций на И7 с равномерной нормой..

Для всякой /? C (W) V i € J определим «меру зависимости от координаты г» по правилу.

Д/(г) = sup {| f{rj) — /© |: Ъ С е W, rfe = Q V j ф г} ..

Введём плотное в C{W) множество D (W) — |/ G C (W): ||| / Yl^fii) < ооj. Определим следующий оператор на D{W):.

Af (fl) = > 0hiPij (/(• • -т -1 • • .V, +1 • ¦ •) — 1Ш) ¦ ieJ jeJ.

Теорема 19 (Теорема 1.1, [60]). Если sup 7- < 00, supУ^тjPjj <00, (х) iej ieJ jeJ то.

1) Замыкание, А оператора, А является инфинитезималъным оператором марковской полугруппы S (t) и подпространство D (W) является существенным подпространством для А..

2) Существует единственный феллеровский процесс rj (t): (Г2, S, Р) (W, B) с заданным инфинитезималъным оператором A- (Q, Р) — некоторое вероятностное пространство..

Следствие 20 (Следствие 1.2). Если выполнено одно из утверждений:.

• sup 7 г < оо, sup Pji < 00 ieJ ieJ jej.

• E 7 г < ooieJ утверждения (l)-(2) теоремы 19 верны..

Далее всюду предполагается, что условие (х) выполнено..

Предположим, что однородная марковская цепь с пространством состояний J и переходной матрицей Р является апериодичной и неприводимой. Введём.

Предположение А: Существует положительная инвариантная мера п = для Р (необязательно конечная, см. [4, раздел XV. 11])..

Предположение Б: Существует единственная инвариантная вероятностная мера 7 Г = (-7Гij. j для Р (которая называется стационарной)..

Предположение В: Счётная цепь Маркова с переходной матрицей Р является транзиентной. Обозначим def 1U, , а = sup — <00. (х х J iEJ Ъ.

Пусть pmax = 1/а. Для любого р € [0- pmax] и р = 00 введём меру-произведение Ьр{-) на (W, B) с координатными множителями /*(•), i 6 J, определяемыми по-разному в следующих двух случаях: т= щ = если р е [0- ртах] и < 1, то.

0, к = оо если же р = ртах, р (щ/ъ) = 1 либо просто р = оо, то.

0, к е Z+,.

1, А- = оо..

Введём L = {Lp (-): р € [0- pmax]: р = оо}. Обозначим через L выпуклую оболочку.

1= п.

К-замкнутое выпуклое множество, КЭЪ.

Пусть М. — класс всех инвариантных мер марковского процесса {r/(t)}f>0..

Следующие три утверждения доказываются с помощью слегка изменённых доводов доказательств утверждений 2.14, 3.1, 2.15, 2.16 из [40]- отличие состоит в том, что надо там брать меру s — f вместо a = (a (x): х G J) (используя обозначения.

I. ^ J ieJ.

40])..

Теорема 21 (Теорема 1.4). Предположим, что выполнены предположение, А и условие (хх). Тогда замкнутая выпуклая оболочка L множества мер.

Lp (-): ре [0-Ртах], р = оо} включена в класс М. всех инвариантных мер марковского процесса Пусть.

Е’Ч /.

-<оо. (X X X).

Утверждение 22 (Утверждение 1.5). Предположим, что выполнены предположение, А и условие (х х х). Тогда V р 6 [0- ртах] i? J гц < оо =1..

Теорема 23 (Теорема 1.6). Пусть выполнены предположение, А и условие (х х х). Предположим, что для узла jo € J выполнено условие ^j0/lj0 = max 7^/7*. Тогда.

V k е Z+ Vr/°: т/г° = оо ieJ imP{Vjo (t)>kr](0) = r1(i} = l. t-t00 k J.

Теорема 24 (Теорема 1.9). Предположим, что выполнено одно из следующих условий:.

1) 7 < оо и предположение В-.

2) 7 < oo U /j е J J2Pij < iieJ.

3) Vj E J Y2Pij ^ ^ u существует такая неубывающая последовательность iej конечных множеств {Jn}n-1> Ji С J2 С ., J Jn = J, что sup 7j —> 0 при n jeJJn n —> 00, а матрицы P^ = (Pij)i, jeJn неприводимы-.

4) Пусть Vj? J YhPij ^ 1- Введем обрывающуюся цепь Маркова Y = {Ym}™=1 ieJ с пространством состояний J и переходной матрицей РТ = (j>ji)i, jejОбозначим через Pj (J) вероятность того, что Y оборвется при выходе из начального состояния Yq = j. Предположим, что Pj (J) — 1 для всех j? J и sup 7, < 00. jeJ.

Тогда для любого 77(0)? процесс r](t) —> 0 слабо при t —>¦ 00. Наконец, в разделе 2 предложен подход к изучению поведения процесса с нулевой областью зависимости с использованием методов, разработанных во второй главе..