Содержание к диссертации
Введение
1 Основные понятия 11
1.1 Дифференциальные уравнения в банаховом пространстве И
1.2 Одномерный ПРГ 12
1.3 Общий процесс типа рождения и гибели 15
1.4 Логарифмическая норма оператора 18
1.5 Свойства подпространств в /і 18
2 Процессы рождения и гибели с периодическими интенсивностями 20
2.1 Бесконечный ПРГ с 1-периодическими интенсивностями 20
2.2 Конечный ПРГ с 1-периодическими интенсивностями . 36
2.3 Бесконечный ПРГ с интенсивностями, близкими к периодическим 47
3 Процессы типа рождения и гибели 59
3.1 ОПТРГ с 1-периодическими интенсивностями 59
3.2 Асимптотически эквивалентные ПРГ 63
3.3 Процессы, близкие к вырождающимся 65
4 Описание моделей 67
4.1 Использование ПРГ в теории массового обслуживания . 67
4.1.1 Применения к телефонии 68
4.1.2 Применение к обслуживанию машин 69
4.1.3 Общая схема 70
5 Вычисление предельных средних 72
5.1 Система с неограниченным числом мест ожидания . 72
5.2 Система с ограниченным числом мест ожидания . 80
5.3 Система с неограниченным числом мест ожидания и ин-тенсивностями, близкими к периодическим 86
5.4 Простейшие модели эпидемий 89
Приложение 92
Описание программы 92
Список литературы
- Общий процесс типа рождения и гибели
- Логарифмическая норма оператора
- Конечный ПРГ с 1-периодическими интенсивностями
- Асимптотически эквивалентные ПРГ
Введение к работе
Актуальность темы исследования. Марковские цепи с непрерывным временем играют важную роль в математическом моделировании многих процессов, возникающих в самых разнообразных областях исследований: технике, биологии, экономике, военном деле и т.д. Особенно успешными являются применения марковских цепей в теории массового обслуживания и теории надежности.
Первоначально такого рода задачи возникли из требований телефонного дела, физики и рациональной организации массового обслуживания (билетные кассы, магазины и прочее) в начале предыдущего столетия. Первые исследования по этой тематике были приведены в работах А. К. Эрланга. Основные его исследования в этой области относятся к 1908-1922 годам. С того времени интерес к проблемам, выдвинутым Эрлангом, значительно возрос. Оказалось, что подобные задачи возникают в самых разнообразных направлениях исследований: естествознании, технике, экономике, транспорте, военном деле, организации производства и многих других. Для решения проблем такого рода примерно в 50-х годах двадцатого века была создана так называемая теория массового обслуживания (англоязычный термин - теория очередей), являющаяся с тех пор активно развивающимся разделом прикладной теории вероятностей.
В числе математиков, заложивших основы теории и приложений этой области и сформировавших ее современный облик (в части, близкой к тематике настоящего исследования), следует отметить Р. Л. Добрушина, Б. В. Гнеденко, В. В. Калашникова, И. П. Макарова, А. И. Зейфмана, Н. В. Карташова, В. В. Анисимова, Е. Van Doorn'a, W.Whitt'a и многих других.
Наиболее распространенной из моделей, описывающих реальные
системы массового обслуживания, является так называемый процесс рождения и гибели - это частный случай марковского процесса с непрерывным временем и не более чем счетным числом состояний. В основном в работе изучаются именно ПРГ, но затрагиваются и более общие процессы типа рождения и гибели (ОПТРГ), которые широко используются при моделировании эпидемических ситуаций.
В работе рассматриваются вопросы, связанные с периодическими режимами, которые имеют важное значение в прикладной математике при изучении математических моделей в разнообразных областях исследований. Периодические решения и устойчивость дифференциальных уравнений изучали многие авторы, например, В. А. Якубович, М. Г. Крейн, Е. В. Воскресенский, А. И. Перов, М.Т.Терехин
Цель работы:
Изучение математических моделей процессов рождения и гибели (ПРГ), общих процессов типа рождения и гибели (ОПТРГ), сводящихся к системам линейных дифференциальных уравнений. Исследование вопросов существования двойного среднего и предельного среднего, и вопросов вычисления этих характеристик, а также скорости сходимости к ним.
Методика исследования:
Для решения поставленных задач используется эволюционный оператор (оператор Коши) и генеральный показатель дифференциального уравнения в банаховом пространстве, и методы их оценки. Проблемы вычисления искомых параметров сводятся к изучению дифференциальных уравнений на множестве стохастических векторов. В этом случае возникают проблемы, связанные с получением явных оценок генерального показателя. Для получения этих оценок используется логарифмическая норма оператора, понятие которой введено
у Лозинского, а для операторов в банаховом пространстве изучено Далецким и Крейном. В случае ПРГ доказывается существование предельного среднего и получена его оценка. Получена оценка для предельного среднего и двойного среднего через систему с меньшим числом состояний. В случае ОПТРГ предполагается слабая эргодичность X(t). Доказывается существование и получаются оценки. Рассматриваются другие способы вычисления указанных параметров.
Научная новизна:
В диссертации найдены новые условия существования предельных средних и способы их вычисления, а также получены оценки скорости сходимости к этим характеристикам.
Практическая значимость результатов: Полученные в работе результаты могут быть использованы в исследовании конкретных систем линейных дифференциальных уравнений и стохастических моделей в технике, химии, биологии, физике и других отраслях научных знаний.
Основные положения, выносимые на защиту:
Достаточные условия существования среднего и двойного среднего для бесконечного процесса рождения и гибели с периодическими интенсивностями. Определение скорости сходимости данных характеристик.
Аппроксимация бесконечного процесса рождения и гибели конечным процессом рождения и гибели. Алгоритм нахождения предельных средних характеристик.
Вопросы, связанные с существованием и построением предельных средних характеристик для систем массового обслуживания, описываемых нестационарными процессами рождения и гибели с интенсивностями, близкими к периодическим.
Апробация диссертации: Результаты работы докладывались на: семинарах кафедры прикладной математики ВГПУ (2005 год), на заседании научно-исследовательского семинара по качественной теории дифференциальных уравнений в Рязанском государственном университете, семинаре в Римском университете (Италия, 2003 год), зимней школе "Современные проблемы теории функций и их приложения" (Саратов, 2004) международной школе-семинаре по геометрии и анализу (Ростов-на-Дону, 2004), 24 международном семинаре по проблемам устойчивости стохастических моделей в Юрмале (Латвия, 2004 год), 25 международном семинаре по проблемам устойчивости стохастических моделей в Майори (Италия, 2005 год), на объединенных научных семинарах кафедры прикладной математики и Средневолжского математического общества под руководством профессора Е.В. Воскресенского (Саранск, 2006)
Публикации: Основные результаты опубликованы в [1]-[12].
Структура и объем диссертации: Диссертационная работа состоит из введения, пяти глав, разбитых на параграфы, приложения, библиографического списка литературы, включающего 71 работу отечественных и зарубежных авторов. Работа изложена на 129 листах машинописного текста.
Общий процесс типа рождения и гибели
Общий процесс типа рождения и гибели (ОПТРГ) - это частный случай марковского процесса с непрерывным временем и конечным или счетным числом состояний, в котором имеются несколько типов "частиц", и ненулевыми предполагаются "интенсивности" изменения количества "частиц" одного типа не более чем на единицу, либо переход "частицы" из одного типа в другой. ОПТРГ являются реалистическими моделями в химии, иммунологии, физике. Стационарные процессы такого вида исследовались, например, в [4],[39],[32],[53],[8], [23],[34]. Матрица интенсивностей ОПТРГ имеет существенно более сложную структуру, поэтому построение предельных характеристик даже в стационарной ситуации представляет собой не слишком простую задачу.
Рассмотрим систему S, элементы которой могут находится в состояниях с номерами 1,2,3,..., iV. Обозначим количество элементов, находящихся в момент t в состоянии г, через щ{і) и введем вектор-строку п = (щ, П2,..., пд ). Будем предполагать, что если в момент t в состояниях 1,2,3,..., N. находятся соответственно пі, П2, пз,..., пдг элементов, то в интервале (, t + At) возможны следующие варианты: а) увеличение на 1 числа элементов, находящихся в состоянии і, без изменения остальных - с вероятностью А;.п() At + o(At) б) уменьшение на 1 числа элементов, находящихся в состоянии і. без изменения остальных - с вероятностью ЦІІП{І) At + o(At) в) переход одного элемента из состояния і в состояние j без изме нения остальных - вероятностью fijin{t) At + o(At) г) система остается без изменений - с вероятностью 1-(Е(Ы0+ #.«( ))+ D ЩПЩ М + o{bt) д) все остальные переходы - с вероятностью o(At), причем все o(At) равномерны по п. При N=1 получаем обычный процесс рождения и гибели (ПРГ).
Далее будем предполагать, что: 1) все интенсивности А;іП (t). fii!n (t), P(jM (t) являются линейными комбинациями конечного числа локально суммируемых на полуоси [0, оо) функций,
Понятие логарифмической нормы для конечных матриц введено и изучено Лозинским [21]; на случай оператор - функций оно обобщено в [9]. Ниже приводятся само это понятие и важные оценки связанные с ним. Определение 5 Число 7(л( )) = ,ію 1№ + )11-№«) называется логарифмической нормой оператора А. Теорема 5 При всех t 0 существует {A(t)), причем справедлива формула: 1ІЩ) = Abm " - (1.4.9) Следствие: l{A{t))=snp[ajJ + Z\aji{t)\ І \ іфі ) Теорема 6 Для любых t, s(t s 0) выполняется неравенство: e-l!l(-A(r))dr j/ s) ej!nWT))dr 1.5 Свойства подпространств в l\
Пусть А -пространство с заданной нормой д. Пусть А состоит из z = (ZQ,Z\,...) таких, что если z є А, то z Є h, и найдется такое число к, что при любом z Є А выполняется: H/i = EM HMU j=0 При выполнении этих условий будем записывать А С 1\. Рассмотрим частный случай подпространства в 1\. I di di di ...\ Пусть D = , d = infj i di О О d2 d2 ... О 0 d3 ... Пусть А = 1\D -пространство всех векторов таких z — (zi, z2, что \\z\\llD = \Dz\k -Покажем, что 1щ С h: 4IID = di ЕР« + d2 »=2 + dz EP f=3 + ... d EP i=l + i=2 + EP г =3 + ... oc Л Pi » =1 + ОС E# i=2 + ЕР i=2 + ос ЕРг і=3 + ... ЕИ = іІ Отсюда /ш С і Теорема 7 Пусть В : 1\ - 1\- линейный оператор. Пусть В действует на векторы из Іц), тогда
Логарифмическая норма оператора
Окончательно используя (2.1.41), (2.1.47) и (2.1.49), получаем (2.1.37). D Из теорем (8), (9) получаем следующее утверждение. Теорема 10 Пусть существует последовательность {di} такал, что а 0. Тогда для любого t О №( ) - S{4(i)l (0) = 0} - -e + (2.1.50) Замечание 1 Неравенство (2.1.50) позволяет находить предельное среднее. Для начала находим t, при котором первое слагаемое достаточно мало. Затем, зафиксировав полученное t, находим N так, чтобы второе слагаемое было достаточно мало (ЛЛ/дг - оо при N - оо ). Теорема (10) позволяет вычислять предельное среднее с заданной точностью.
Теорема 11 Пусть существует последовательность {di} такая, что о 0 и infj. i -у1 0. Тогда ПРГ имеет двойное среднее Е. Более того, верны оценки
Замечание 2 Таким образом, для нахождения среднего и двойного среднего можно взять t и N, при которых верны оценки и вычислить эти средние, взяв в качестве начального вектора ео- Однако, если N невелико, можно находить эти параметры иначе. Можно найти начальный вектор, который определяет периодическое решение. Несложно показать, что его нахождение сводится к решению системы из уравнений (2.1.57) (tf(0,l)-l)x(O)=0 5i ,-(0) = l
Далее, используя этот начальный вектор, можно найти среднее, решая как задачу Коши. Или, решая систему линейных уравнений, найти все векторы, также, как было показано для х(0). А затем, используя их, найти двойное среднее.
Замечание 3 Оценки (2.1.50)и(2.1.52) состоят из двух слагаемых. Для первого и второго слагаемых можно взять различные последовательности di с целью их уменьшения. 2.2 Конечный ПРГ с 1-периодическими интенсивностями
В данном параграфе получены достаточные условия существования среднего и двойного среднего для конечного ПРГ с периодическими интенсивностями. Рассмотрено аппроксимирование конечного ПРГ конечным ПРГ с меньшим числом состояний. Показаны способы вычисления средних.
Пусть Хм (t), t 0 - нестационарный ПРГ с пространством состояний S = {0,1,...} и интенсивностями рождения An (t), t 0, и гибели \in (t), t 0, п Є S.
Используя содержимое 4 первой главы, можем записать систему Колмогорова = Л( )р, р = р(0, 0, (2-2.58) где р() = {рі,Р2, - ),РІ- вероятность того, что система находится в г-том состоянии. Далее предполагается выполнение следующих условий \n{t)=vna(t), Hn{t) = rinb{t), 0, neS, (2.2.59) где = 0, 0 i/n L, п = 0,..., 0 т/п М, п = 1,.... (2.2.60) Пусть а (), 6 (t) неотрицательны, 1-периодичны и интегрируемы на [0,1]. Более того, предполагается что для всех t Є [0,1]
Возьмем последовательность положительных чисел 1 = d-\ = do d\ ... . Положим ( k {t) = \к {t) + рк+i (t) - h+i (t) - %±Pk (t), ,k 0, (2.2.62) « ah и /1 a (t) = inf ak (t). a = a(t) dt, M0= sup l\{u)du, M = eMo+Q , W = inf . (2.2.63) \t-s\ \Js к к Введем обозначение: Х \ - ПРГ, полученный из X (t), с состояниями {0,1,... ,Ni}. Теорема 12 . Пусть существует последовательность {dj} такая, что а 0. Тогда существует предельное среднее ф{ї) такое, что \{Хм(Ь)\Хн(0) = к}-ф(ї)\ -» 0 при t - сю для любого к. Более того, выполняется оценка при к = 0: \E{XN(t)\XN(0) = к} - ф(і)\ е Л\ (2.2.64) Доказательство. Пусть 1\Е - пространство следующих последовательностей
Конечный ПРГ с 1-периодическими интенсивностями
Пусть X (t), t 0, - "вспомогательный" неоднородный ПРГ с пространством состояний S = {0,1,...}, интенсивности рождения К {i), t 0, и гибели цп (t), t 0, п Є S, которого являются периодическими функциями от времени t с периодом, равным единице. Будем предполагать, что для вспомогательного процесса выполняются следующие условия (стандартные для ситуации с переменными интенсивностями): Хп {t) = vna (і), цп (t) = г]пЬ (і), і 0, п Є 5, (2.3.99) где щ = 0, 0 ип L оо, 0 77„+1 М ос, п 5. (2.3.100)
Пусть а (і) и 6 (і) неотрицательны, 1-периодичны и интегрируемы на [0,1]. Более того, для получения более простых оценок предполагается, что для всех t [0,1] a{t) аи6( ) Ь. (2.3.101)
Рассмотрим теперь основной ("возмущенный") ПРГ Л (t), t О, с тем же пространством состояний S и интенсивностями рождения К (0 і 0, и гибели ц п (t), t 0, и Є , для которого выполнены аналогичные стандартные условия, а вместо 1-периодичности предполагается, что \ n(t) - \n{t) = A„(t), /4W - lh,(t) = Ш, I2-3-102) где "возмущения" интенсивностей малы: \K(t)\ є, \fin{t)\ г при всех і 0 и п S.
Как и в предыдущих параграфах, предполагается, что векторы вероятностей состояний рассматриваемых процессов описываются соответствующими прямыми системами Колмогорова.
Возьмем некоторую последовательность положительных чисел 1 = d-i = d,Q d\ ... Положим ock (t) = \k (t) + //HI W - AH1 (і) - цк ( ), 0, (2.3.103) a a и введем некоторые вспомогательные величины: Г = sup (2+ + ), a(t) = Mak(t), а = J a(t)dt, M0= sup а(и) 1щ M = e w+a , W = inf = . (2.3.104) -s r Теорема 15 Пусть существует последовательность {di} такая, что а 0, inik i -у1 0, а Г ос и а - Те 0. Тогда вспомогательный ПРГ X(t) имеет l-периодическое предельное среднее ф(і), причем для любого начального условия Х (0) = к и всех t О справедлива оценка \Е{Х (і)\ХЩ = к}-ф(і)\ Доказательство
Рассмотрим прямую систему уравнений Колмогорова для каждого из рассматриваемых процессов: = A(t)p, P = p(t) = (Po(t),Pi(t),-.-)1, 0, (2.3.106) и -?r = A (t)p% р =р (0, 0. (2.3.107) Заменим р0 = 1 - Е РІ в (2.3.106) и р 0 = I - Е- К в (2.3.107). Тогда соответственно получаем:
Все дальнейшие результаты получены по аналогии с первым параграфом данной главы. Снова использована так называемая логарифмическая норма оператора, введенная в конечномерном случае в [21] и обобщенная на случай банахова пространства в [9].
Логарифмическая норма операторной функции, задаваемой матрицей B(t) = {bjj(t)} в пространстве (і, вычисляется по формуле 7(S) = supL- + IMV (2.3.И8)
При этом для оператора Коши V(t, т) соответствующего дифференциального уравнения (2.3.108) справедливо неравенство V( ,r) exp(j\{B{s)) ds),t T 0. (2.3.119)
Отметим, что если все внедиагональные элементы матрицы B(t) неотрицательны при всех t 0, то вместо (2.3.118) получается более простая формула 7 (S(t))= sup ! ;( ) (2.3.120)
Рассмотрим теперь величины (2.3.103), тогда l(B(t))lD = 1(DB(t)D i)l = -miak(t). (2.3.121) С учетом неравенства треугольника для логарифмической нормы и того, что логарифмическая норма оператора не превосходит обычной (т. е. для любого оператора К при любом выборе нормы справедливо неравенство 7 [К) /v), получаем в любой из рассматриваемых норм
Выберем теперь z(0) так, чтобы соответствующее z() было 1-периодическим. Тогда соответствии с (2.3.129), при всех tПоложим теперь dn-\ — п и обозначим соответствующую матрицу 5, тогда соответствующая норма вычисляется по формуле хі = npn и с учетом неравенства W\IE (W1MID (2-3-135) получаем утверждение теоремы. Теорема 16 Пусть выполнены условия теоремы (15). Тогда ПРГ X (t) имеет предельное среднее ф (і), причем выполняется неравенство ІЕ СО т - п )\ W(aMlre) (і+TJp) (2.3.136)соответствующее ему среднее Т,к kpk{t) = 4 (t) также будет 1-периодическими, кроме того, в
Доказательство
Существование ф (і) вытекает из оценок (2.3.125) и (2.3.135). Для получения оценки (2.3.136) достаточно в неравенстве (2.3.105) при любом фиксированном к устремить t к бесконечности,
Асимптотически эквивалентные ПРГ
Основным предметом изучения является среднее число требований в системе (в единицу времени - предельное среднее, вообще - двойное среднее).
Система с потерями.
Пусть имеется т обслуживающих приборов, каждый из которых доступен (когда он свободен) для каждого из поступающих в систему требований и одновременно способен обслуживать только одно требование. Каждое требование, поступившее в систему, начинает обслуживается немедленно, если в ней имеется хотя бы один свободный прибор. Если же все приборы заняты, то требование теряется, получает отказ.
Если под Ек понимать состояние системы, когда в ней находится к требований, то система может находится лишь в состояниях EQ, Е\, , Ет. Мы находимся в условиях схемы ПРГ, для которой Xn(t) = X(t) при п т и Xn(t) = 0 при п ш, тп = 0 при п = 0 и п т, jin(t) = nfi(t) при 1 п т.
Система с ограниченным числом мест ожидания.
Данная модель отличается от предыдущей наличием очереди длины г. Когда поступает требование и все приборы заняты, то оно сохраняется в очереди, если есть место. Однако, если при поступлении требования все приборы заняты и нет свободных мест в очереди, то требование теряется. Мы находимся в условиях схемы ПРГ, для которой Xn(t) = Л (і) при 0 п m + r vi \n(t) = 0 при п т + г, //о( ) = 0, цп{і) — п\і{ї) при 1 п m, nn(t) = ш(л при m п т + г, fik(t) = 0 при к т-\-г. Система с неограниченным числом мест ожидания. Xn(t) = А(), fio(t) = 0, /in(t) = nn[t) при п т, fin(t) = m i(t) при п т.
Рассмотрим следующую задачу массового обслуживания. Группа из т машин, которые время от времени выходят из строя, обслуживаются г мастерами. Каждый раз, когда машина выходит из строя, мастер должен проделать определенную работу, чтобы вернуть ее в рабочее состояние. В случае, когда имеется всего один мастер, и во время ремонта выйдет из строя другая машина, она будет ожидать начала обслуживания до момента завершения ремонта первой машины. В случае, когда имеется несколько мастеров, если в некоторый момент число неработающих машин превысит число мастеров, то избыточное число машин должно ожидать освобождение мастера.
В книге [4] приводится задача Пальма о простое машин. Основным предметом поиска является среднее число машин находящихся в ремонте (в единицу времени - предельное среднее, вообще - двойное среднее). Задача сводится к ПРГ.
Пусть X(t) обозначает число машин, не работающих в момент t. Имеются состояния EQ,. Если в момент времени t не работает і машин, то говорим, что система находится в состоянии ЕІ.
Предполагаем: 1) если в момент t машина работает, то вероятность того, что в интервале (, t + At) она выйдет из строя и потребует обслуживания, равна XAt+o(At); 2). если в момент t машина ремонтируется, то вероятность того, что в интервале (t,t + At) ремонт окончится и машина вернется в рабочее состояние, равна /iAt+o(At);
В книге [4] приводится, что Ао() = mX(t), Xn(t) = (га - n)X(t) при 1 n га, mo = 0, fin(t) — гщ{і) при 1 n r, fin(t) = rfi(t) при r n m.
Схема нахождения двойного среднего и предельного среднего для данных случаев почти одинакова, и может использоваться содержимое первой главы.
