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

• Автор: Гинзбург, Екатерина Михайловна
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 109 с.

Содержание
Введение
1. Транспортные модели с управлением. Описание и эргодические теоремы
1.1. Постановка задачи и методы исследования
1.2. Теоремы эргодичности для сетей малой размерности
1.2.1. Системы из двух узлов. Формулировка эргодической теоремы
1.2.2. Вспомогательные марковские цепи
1.2.3. Доказательство эргодической теоремы для систем из двух узлов
1.2.4. Теорема эргодичности для систем из трех узлов с мгновенно передвигающимися перевозчиками
1.3. Эргодические теоремы для полусимметричных систем
1.4. Исследование стационарного режима
1.5. Исследование неэргодического случая
1.5.1. Свойства векторов усредненных сносов
1.5.2. Построение вспомогательной марковской цепи и ее свойства
1.5.3. Построение пробной функции
1.5.4. Доказательство теоремы
2. Управляемая симметричная транспортная система с потерями
2.1. Постановка задачи и формулировка теоремы о сходимости полугрупп операторов
2.2. Доказательство корректности краевой задачи
2.3. Обоснование теоремы о сходимости полугрупп
2.3.1. Лемма о существенном подпространстве
2.3.2. Доказательство теоремы о сходимости полугрупп
2.4. Стационарная точка системы дифференциальных уравнений
3. Асимптотическая оптимизация
3.1. Свойства стационарных точек динамических систем с разным пороговым уровнем
3.2. Исследование эффективности управления и оптимизация
3.3. Поведение сети при быстром движении перевозчиков
3.4. Поведение сети при увеличении числа приборов
Заключение
Приложение
Список литературы

Введение
Теория сетей обслуживания возникла в 60-е годы и сформировалась в 70-е годы в связи с приложениями, и прежде всего в связи с интенсивным развитием вычислительных систем, систем передачи информации, сетей ЭВМ и т.д. Под сетью обслуживания обычно понимают совокупность взаимодействующих между собой систем обслуживания (узлов, станций). Взаимодействие определяется распределениями маршрутов движения вызовов между станциями, типами систем обслуживания, действующих в узлах, дисциплинами обслуживания, распределениями времен обслуживания и т.д.
Из разнообразных сетей обслуживания в отдельную группу выделяют системы поллинга. Эти системы состоят из конечного числа станций, посещаемых одним или несколькими обслуживающими приборами. Прибор после окончания обслуживания на станции г направляется на станцию j в соответствии со стохастической матрицей маршрутизации Р = (pij). В литературе рассматривались различные варианты обслуживания требований в узле. Например, прибор может обслуживать по одном)' требованию в каждой очереди, или все требования, которые поступили в данный узел к моменту его прихода, или часть требований, пока время на их обслуживание не превысит некоторой величины (обслуживание с прерыванием) и т.д. По поллинговым системам имеется обширная литература. В частности, им посвящен специальный выпуск журнала ”Queueing Systems” (v. 11, 1992).
К типу поллинговых можно отнести транспортные модели, в которых обслуживание клиентов состоит в их перевозке из одного узла сети в другой. Системы такого вида впервые были исследованы в работе [15] Афанасьевой, Файолем и др. в 1997 г. Ими была рассмотрена открытая система из N узлов и V приборов, которые передвигаются по узлам сети, развозя требования. Прибытия требований образуют некоторый случайный процесс. Каждое требование с вероятностью рг направляется в узел г, pi > 0, YliLiP< — 1- Если в момент поступления требования в узел в нем есть прибор, то он перевозит требование из узла г в узел назначения j, в течение случайного времени т,у. Узел назначения j выбирается с вероятностью рц, числа Pij образуют стохастическую матрицу Р. После прибытия в узел назначения требование сразу же покидает систему, а поведение прибора определяется тем, есть ли ожидающие требования в этом узле. Если таких требований нет, то прибор остается там. Если же ожидающие требования есть, прибор забирает одно из них и везет его в узел к, который выбирается с вероятностью p3k- Прибор развозит требования до тех пор, пока не остановится в узле без клиентов. Такую систему мы будем называть ,6-системой.
6-системы отличаются от стандартных систем поллинга тем, что приборы передвигаются по узлам сети только вместе с требованиями.
При изучении сетей обслуживания чаще всего исследуются эргодические свойства возникающих случайных процессов. В предположении экспоненциальности управляющих последовательностей (последовательности времен обслуживания, интервалов между моментами приходов вызовов) для исследования процессов обслуживания

традиционно используется аппарат многомерных марковских цепей.
Обозначим через X = {п} однородную цепь Маркова со значениями в фазовом пространстве X, и будем использовать ее представление в виде
Хп+1 = Хп + #(А„,п),
где распределение 0(х,п) = 0{х), х Е X, зависит только от х.
Первые сравнительно общие условия эргодичности для многомерных марковских цепей были получены, по-видимому, в [6]-[9], где рассматривается решетчатое блуждание в положительном октанте с ограниченными скачками в{х) < с, распределение которых в точке х не зависит от х при хг > с (свойство частичной однородности в пространстве). Примерно через 10 лет после работ [6]-[9] появились работы [2], [10]. [22], [29], [30], [31], посвященные изучению решетчатых цепей Маркова в положительном квадранте X = {(*1,3:2) : *1 > 0, Ху > 0), для которых Е{ 9{х) } не зависит от Х{ при ж; > с, а также выполнены некоторые другие условия. Примерно в то же время были анонсированы результаты [16], [17], касающиеся эргодичности так называемых асимптотически однородных в пространстве (зависимость распределения 9{х) от XI исчезает при |ж;| —» оо) цепей Маркова в Б (й = 2,3) и включающие в себя оценки скорости сходимости и оценки вероятности больших уклонений.
Переход к анализу марковских цепей большей размерности выявил появление принципиально новых возможностей (по сравнению с цепями в Б, Б2), которые приводят к эргодичности. Само их описание представляет трудности (см. [27]).
В монографии А. А. Боровкова [1] приведены результаты, посвященные эргодичности и устойчивости широкого класса случайных процессов, в том числе многомерных марковских процессов как с дискретным, так и с непрерывным временем. Однако теоремы, касающиеся необходимых и достаточных условий эргодичности для многомерных марковских процессов, содержат громоздкие, трудно проверяемые условия. Видимо, для приложений наиболее плодотворным является путь непосредственного использования методов, примененных при доказательстве таких теорем, поскольку часто технически проще доказать эргодические теоремы для конкретного процесса, нежели проверять условия общих теорем. В разделе, посвященном приложениям, именно так доказаны необходимые и достаточные условия эргодичности систем поллинга. ’’Прямой подход” к отысканию таких условий был предложен еще в [18].
Другое направление при изучении сетей обслуживания состоит в исследовании количественных характеристик процесса, описывающего поведение сети, при увеличение размеров сети. Из разнообразной литературы, посвященной поллинговым системам (см., например, [32]), известно, что получить точные результаты такого рода при конечном числе узлов в сети N практически невозможно даже при простейших предположениях. Однако во многих приложениях (телекоммуникационные, транспортные системы) основной проблемой является изучение именно больших сетей, IV —э оо.
Один из возможных подходов к решению таких задач основан на так называемой гипотезе хаоса. Эта идея заимствована из статистической физики, и состоит в том,

Теорема 3. Если для всех i,i = 1
0 < р- < Жу+Т’ (56)
то цепь Маркова (к эргодична. При выполнении (56) стационарное распределение имеет вид
п{п1а) = Са Д р{ [{И — У + 1)р;)л', (57)
где С — нормирующий множитель.
Замечание. Если р3 = 0 для некоторого у, то у £ появляются несущественные состояния; на множестве существенных состояний £ эргодична при выполнении тех же условий Pi < дг —у ДЛЯ всех i.
Доказательство. Если все р; > 0, то £ является неприводимой цепью Маркова. Мы докажем, что указанные т(п,а) являются решением системы уравнений п = 7гР, где Р — матрица переходных вероятностей для £. При выполнении условия Р* < дг _ у д. 1 полученный набор чисел образует сходящийся ряд, а это значит, что £ эргодична (см., например, [12], глава 15, §7).
Пусть Р(т, /3, п, а) — вероятность того, что за один шаг £ перейдет из состояния (т,0) в состояние (п,а). Тогда система уравнений тг = 7гР примет вид
7Г (п,а) = еа)Р<1{гч>Ц + 12п(п +а)Р(п +),а,п,а) +
г(£а j>0
+ Х2 +3,)р{п + 3,13,п,а), у £ Iм. (58)
Рфа:>о
Чтобы записать Р(п+у, /3, п, а) в более удобном виде, для (тг+у, о) 6 Н определим функцию /га(г,тг+у, з, гг), равную вероятности того, что прибор, начавший движение из узла I, когда система находилась в состоянии (п +у, а), закончит движение в узле 5, и в системе будут находиться п требований. Как показывают соотношения
Аа(г,п,в,?г) = —(59) 1 Л
ь.а(у,п + ),з,п) = +у у ф о, (60)
функции /га(г,гг + у, з,п) зависят только от у, что позволяет ввести функцию /г (у) для у е Наеа по формуле /г(у) = /га(г,п + у, в, гг) при у € 2а. Если а ф /3, то Р(га + у,/?, тг,а)фО только тогда, когда найдется такое i, что п| = 0, (3 — аи{г}{з) для некоторого 5 £ а, причем такой переход возможен, только если поступившее требование попадет в узел i, вызвав движение прибора, который в конце своего движения остановится в узле з. Учитывая эти обстоятельства, уравнения (58) можно записать так:
гг (гг,а) = Ж! 7т(п - е;, а)рг1{„,- >1} + Аа 52 п(п + ),а)кО) +

+ 521{П;=0}Л-12 12 тг(п + у,аи{г}{з} )Л(у). (61)