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

Л ! На правах рукописи

Чегодасв Александр Вячеславович

Математические модели и методы оценки характеристик стохастических систем, близких к поглощающим.

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Тверь - 2009

003489522

Работа выполнена на кафедре прикладной математики Вологодского государственного педагогического университета

Научный руководитель:

доктор физико-математических наук. Профессор Зейфман Александр Израилевич

Официальные оппоненты:

доктор физико-математических наук, профессор

Хохлов Юрий Степанович

доктор физико-математических наук, профессор

Язенин Алсксндр Васильевич

Ведущая организация: Московский государственный университет им. М.В. Ломоносова. Факультет ВМК.

Защита состоится 22 января 2010 г. в 14.00 на заседании Диссертационног совета Д.212.63.04 по защите диссертаций на соискание ученой степен кандидата физико-математических наук при Тверском государственно: университете (170100 г. Тверь, ул. Желябова, д. 33 ауд. 52)

С диссертацией можно ознакомиться в научной библиотеке Тверског государственного университета по алресу: 170000, Тверь, ул. Володарского, 44а

Объявление о защите диссертации и автореферат опубликованы 11.12.200 гю на официальном сайте Тверского государственного университета по адресу: http://universitv.tversu.ru/aspirants/abstracts/.

Автореферат разослан \ 9" декабря

Ученый секретарь диссертационного Совета, д.т.н.

М.В. Михно

Общая характеристика работы

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

Впервые, задачи теории массового обслуживания возникли га требований телефонного дела, физики и рациональной организации массового обслуживания (билетные кассы, магазипы и прочес) в пачале предыдущего столетия. Первые исследования по этой тематике были приведены в работах А.К.Эрлапга. Основные его исследования в этой области относятся к 1908-1922 годам. С того времени интерес к проблемам, выдвинутым Эрлангом, значительно возрос. Оказалось, что подобные задачи возникают в самых разнообразных направлениях исследований: в естествознании, в технике, экономике, транспорте, военном деле, организации производства и многих других. Для решения проблем такого рода примерно в 50-х годах двадцатого пека была создана так называемая теория массового обслуживания (англоязычный термин - теория очередей), являющаяся с тех пор активпо развивающимся разделом прикладной теории вероятностей.

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

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

В числе математиков, заложивших основы теории и приложений этой области и сформировавших ее современный облик (в части, близкой к тематике настоящего исследования), следует отметить Р.Л.Добрушина, Б.В.Гнеденко, В.В.Калашникова, И.П.Макарова, А.И.Зейфмапа, Н.В.Картантова, В.В.Анисимова, Е.Уап Ооогп'а, \У.\¥ЫИ'а и мпогих других.

Как известно, получение явных выражений для вероятностей состояний стохастических моделей возможно лишь в исключительных случаях, поэтому одной из

важнейших задач при исследовании таких моделей давно считается исследование поведения модели при 4 —* оо и, в частности, скорости сходимости к предельному режиму и связанных с: этим функционалов.

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

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

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

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

Цель работы.

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

предельных вероятностей состояния и рассмотрение ее применения для конкретных классов моделей; в основном из теории массового обслуживания.

Методика исследования.

В работе исследуется прямая система Колмогорова, имеющая вид:

| = а(0р, р = рМ, *>о. (од)

где рВД - вектор-столбец вероятностей состояний описываемого процесса, а Л(<) -матрица специального вида.

В осповпом рассматривается случай счетпого пространства состояний, которому соответствует счетная система (0.1), отождествляемая с дифференциальным уравнением в пространстве последовательностей При этом исследуются решения системы (0.1), лежащие в множестве стохастических векторов П, то есть в множестве векторов с неотрицательными координатами и единичной /1-нормой.

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

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

Основные положения, выносимые на защиту.

- Нестационарные марковские модели с непрерывным временем, близкие к поглощающим.

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

- Аппроксимация бесконечного процесса рождения и гибели конечным процессом рождения и гибели. Алгоритм нахождения предельных харр:теристик.

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

Научная новизна.

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

Практическая значимость результатов.

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

Аппробация диссертации. Результаты работы докладывались на: семинарах кафедры прикладной математики ВТОУ (Вологда, 2008), ежегодных смортах-сессиях аспирантов и молодых ученых (Вологда, 2007, 2008), международной конференции им. И.Г.Петровского (Москва, 2007), Уфимской международной математической конференции (Уфа, 2007), международном семинаре по проблемам устойчивости стохастических моделей (Нахария, Израиль, 2007), международном семинаре "Моделирование систем в коммерции, промышленности и транспорте"(Рига, Латвия, 2008), международной конференции "Геометрия в Одессе"(Одесса, Украина, 2008), XVI международной конференции "Математика. Экономика. Образование" (Ростов - на - Дону, 2008), Международной конференции "Дифференциальные уравнения и топология "(Москва, 2008), XIII международной летней концеренции по вероятности и статистике (Созополь, Болгария, 2008), международной конференции "Геометрия в Астрахани "(Астрахань, 2008).

Публикации. Основные результаты опубликованы в [1]-[15]

Структура и объем диссертации. Диссертационная работа состоит введения, пяти глав, разбитых на параграфы, приложения, библиографического списка

литературы, включающего 89 работ отечественных и зарубежных авторов. Работа изложена на 126 листах машинописного текста.

Краткое содержание работы.

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

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

Определение 1 Число (оно всегда существует)

7(Л(0)=Цщ H' + ft-f)»-1 (0.2)

lv w/ /¿-.-m h

называется логарифмической нормой операторной функции Ait).

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

Пусть X(t), t > 0 - нестационарная марковская цепь со счетным пространством состояний Е = {0,1,...} . Обозначим через p¡j(s,t) = P{X(t) = j\X(s) = t), i, j e В, 0 < 5 < t вероятность перехода из состояния i в состояние j, a Pi(f) = P(X(t) = i), i € E, t > 0 - вероятность нахождения процесса в состояпии i. Пусть р(£) = (poW'PiWi — )Т ~ вектор вероятностей состояний, Q(t) = (<fo(t)),t > 0 -соответствующая матрица интенсивностей. Положим A(t) = (a¿j(í)) = QT(t) = ?¿j(t))r. Для рассматриваемого случая марковских цепей с поглощением в нуле выполняется условие 9ooW = ûoo(t) = 0. Динамика такого процесса при некоторых дополнительных предположениях описывается прямой системой Колмогорова (0.1).

При этом оператор Коти U(t,s), 0< s < t уравнения (0.1) определяется матрицей UT(t,s) = P(s,t) = pij(s,t). Далее в тексте, если не указано противное, будет использоваться íi—норма для векторов и матриц || • ||, а именно ||х|| = |x¿| и |[С|| = sup¡ |Cjj|, где С = (су). Обозначим Г! множество всех стохастических векторов: ü = {х = (x0,Xi, ...)т : х > 0, ||х|| = 1}.

Рассмотрим p(t) £ П, исключим из системы уравнение для нулевой координаты, полагая

тогда из (0.1) получается система

где

B(t) =

I оц(4) au{t) «■21 (i) 022 (i)

V ......

Z = (pi,P2-)T

(0.3)

(0.4)

(0.5)

Пусть ¿ю -пространство последовательностей, таких, что ЦхЦю = "-У1"! ^ оо. Сначала получим условия, обеспечивающие отсутствие эргодичности цепи.

Теорема 1 Пусть существует последовательность {¿¡} положительных чисел такая, что Бир^ = (I < со,

а1 .->1 аз

Ет»»(0> о,

¡>1 а3

для произвольного ] > 1 и произвольного Ь > 0. Тогда цепь Х(Ь) неэргодична. Более того, справедлива следующая оценка

Po{t) <!-;;£ ¿»Рп(0) < 1

ап>1

для произвольного Х(0) ф 0 и произвольного t > 0.

(0.6)

Обозначим через E(t; к) математическое ожидание X(t) при начальном условии Х(0) = к.

Теорема 2 Пусть выполнены условия теоремы 1 . Пусть, кроме того, выполнено неравенство

inf >c'(i), (0.7)

t>i

где c'(t) - некоторая функция, такая что

J™c*(t)dt = -(-00. (0.8)

Тогда E(t; к) стремится к бесконечности при t —♦ оо для любого к ф 0. Более того, справедлива следующая оценка:

E(i; c'(T)dr, (0.9)

для произвольного кф Ou произвольного i > 0.

Рассмотрим эргодичыый случай.

Теорема 3 Пусть существует последовательность {¿¡} положительных чисел такая, что infi>i d, = d > 0, а

sup Е^Ч(г) = -/Цг), (0.10)

Î>1<>1 "i

причем

j~ß,(t) = + оо. (0.11)

Тогда процесс X(t) зргодичен (с предельным режимом я — ео), и для любого допустимого Х(0) и z = (pi,i>2, —справедливы оценки:

|Н(()||ш<е-/о',-(*||г(0)||1Д (0.12)

и

l!»Wlli = EftW < V£AWir £4»(о), (0-i3) i>l а ¡>1

для любого t > 0.

Замечание 1 В стационарном случае при выполнении условия ß,>Q справедливы оценки

i|z(i)||1B<e-A,||z(0)||1D, (0.14)

(0.15)

Ро(г)>1-(0.16)

d ы

для любого { > 0.

При этом попутно получается и оценка для так называемого параметра сходимости, вводимого следующим образом: /3 = $иру(А/рц(4) - П] = 0(е~и)) при 4 —> оо, а именно, 0 > р,. Более того, мы получили не только оценку для этого параметра, а существенно более содержательные явные неравенства (0.14) - (0.16).

Теорема 4 Пусть выполнены условия теоремы 3, и кроме того,

Ш = Ш ~ > 0. (0.17)

Тогда имеет предельное среднее ф = = 0, и справедлива еледующая

оценка:

(0.18)

Замечание 2 Аналогично получаются нижние оценки для скорости сходимости.

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

В §1 главы 3 изучаются, вообще говоря, нестационарные счетные марковские цепи с непрерывным временем, нулевое состояние которых является «почти поглощающим». Рассматриваются эргодичный и нуль-эргодичный случай.

Рассмотрим вспомогательную последовательность положительных чисел {¿¡} и будем сначала предполагать, что

0<т = тЫ{; М = эир < оо. (0.19)

Положим а*(<) = 5*а,ч(0 и = -а£(0-Пусть

Ы01 < £/3.(0, г > 0, (0.20)

• >1 а ¡>1

и

причем

Г°/3,(«)Л = + оо (0.21)

./о

Теорема 5 Пусть {(¿¡} - последовательность положительных чисел такая, что (0.19), (0.20) и (0.21) выполнены. Пусть е достаточно мало. Тогда Х(€) слабо эргодичпа, причем при всех р(0) справедливы следующие оценки:

|р,(0 - < е-Ц^-т^г)^^^ |р.(0) _ „,(0)| < Ше-^1-"*м<1г

(0.22)

и

Ме

НтШроИ > 1--;-гтт- (0-23)

т (1 - Ме)' ^ '

где 7г({) = (7Го(£), 7Г1(4), • • О*" ~ предельное (квази^стационарное) распределение вероятностей цепи.

Теорема 6 Пусть {4} - неубывающая последовательность положительных чисел такая, что (¡1 = 1, выполнены (0.20), (0.21), а кроме того, при некотором N выполняется условие ?щ(4) = а;о(0 = 0 при всех г > ЛГ, 4 > 0. Пусть е достаточно мало. Тогда Х(Ь) слабо эргодична, причем при всех р(0) справедливы следующие оценки:

(0-24)

¿>1 ¡>1

ПттСрМ)>1--^-, (0.25)

1 - ац£

а кроме того,

1ш1зир£(<,р)< , (0.26)

где и = эир^ а Е(Ь, р) - среднее (математическое ожидание) для X(¿) при начальном распределении вероятностей состояний р(0) = р.

В §2 главы 3 рассматриваются близкие к поглощающим счетные ПРГ. В §3 и 4 главы 3 рассматриваются близкие к поглощающим конечные марковские цепи и ПРГ соответственно.

В §5 главы 3 рассматриваются близкие к поглощающим ПРГ с катастрофами. Пусть X — X(t), t > 0 - ПРГ с катастрофами, и пусть A„(t), n„(t) и £(t) -интенсивности рождения, гибели и катастрофы соответственно.

Динамика такого процесса описывается прямой системой Колмогорова:

dp

dt

= A(i)p + g(t), t>0,,

(0.27)

тдеф) = (№, 0,0,...)г.

Ограничимся рассмотрением ПРГ, где интенсивности имеют следующий вид:

Л„ (i) = i/„A (t), tin(t) = r]nii{t), t> 0, neE,

(0.28)

также будем предполагать, что интенсивности ограничены, 0 < т]п < М, 0 < ип < М, Л(4) + д(4) + £(«) < £ < оо. Рассмотрим матрицу

D =

(dl di ¿i . \

0 d2 d2

0 0 d%

■ /

и пространства последовательностей

t\D = (z = (Р1.Р2,. • -)т : ||z||iD = \\Щ\х < ,

(0.29)

(0.30)

Положим

B =

|z = (pi,p2,.. -)T : ||z||B = ^dibil < oo ^ ,

ak = K{t) + /<*+1(t) - (t) - ^M*). k S 0,

(0.31)

(0.32)

/J(t) = iafat(t), f>t)A = fc^o jo

: +00

(0.33)

A0(i) < ¡f, t > 0.

(0.34)

Теорема 7 Пусть - неубывающая последовательность положительных чисел такая, что = 1 и числа возрастают достаточно быстро, так что Ш ^ = ш > 0. Пусть все интенсивности 1-п<:рио0ичс<:к.ие. Тогда существует 1-периодический предельный режим ж(Ь) = (тг0(4), 7Г1(4),.. ,)г и соответствующее предельное среднее ф(Ь). Более того, справедливы следующие оценки:

-¡РМЛт

1|р(0-»(011в<2е ° ||р(0) -я(0)||и>, (0.35)

Пусть

Ш) - Е(Ь:к)\ < -Л^МО) - екЦш. (0.36)

вир //}(т) <1т = К < оо, /Г = /' 0{ь) йи (0.37)

|1-а1<1-' Л

Следствие 1 Пусть при допущениях предыдущей теоремы Х(0) = к. Тогда справедливы следующие оценки:

-/№■)*• /А еке\ ||р(0-^(г)||в<2е . + (0.38)

и

№)-Е{*,к)\<-е • + (0.39)

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

Глава 5 посвящена вычислению предельных характеристик рассмотренных моделей.

Система массового обслуживания, близкая к поглощающей, с катастрофами. Рассмотрим систему массового обслуживания, которая описыается ПРГ с катастрофами X = Х((), 4 > 0. Пусть А„((), /¿„(£) и £(£) - интенсивности рождения, гибели и катастрофы соответственно. Рассмотрим семейство усеченных процессов Хп(Ь) с пространством состояний Е„ = {0,1,... ,п}; и матрицами интенсивностей

Теорема 8 Пусть выполнены условия теоремы 7. Пусть .Х(О) = Х„(0) = 0. Тогда 1М<) - р»(<)И. < 2е » у + (0.40)

, / Ч г. / Ч, 2 -!f>{T)dTeKe 6LMwieKet %

\<№ - Е0,М < -е - ^ , (0.41)

для любых t > 0, n, zde = supfc>„ = sup¿>n ¿ u £0,n = В {Xn(t) |X„(0) = O }.

Мы можем получить важные оценки для предельних характеристик (предельных 1-периодических вероятностей состояния и предельного среднего) рассматриваемого процесса. Именно, пусть даны интенсивности A(í), ¿t(í) и f(t). Тогда при условиях предыдущей теоремы существует 1-периодический предельный режим 7r(í) = (tto(í) , TTi(í)j-- )T и имеется метод, позволяющий вычислить предельные 1-периодические вероятности состояний Ji¡(t) (вероятность того, что длина цепи в момент времени t не превосходит к) следующим способом.

Пусть S - произвольное положительное число.

1. Выберем число m так, чтобы первое слагаемое в правой части (5.1.14) было меньше чем <5/3 для любого t > m.

2. Выберем п так, чтобы второе слагаемое в правой части (5.1.14) было меньше, чем <5/3 для любого í < m + 1.

3. Тогда решение задачи Коши для урезанной системы Колмогорова с начальным условием е0 на интервале [m; m+1] (с погрешностью 5/3) дает нам предельный 1-периодический режим 7r(í) = (tto{í). 7Ti(í), .. ,)т с погрешностью 5.

4. Наконец, предельное поведение Jt(í) = Pr{X(í) < к} может быть вычислено как с той же погрешностью <5.

Подобным образом может быть найдено и предельное среднее.

Вычислим предельное среднее ф(Ь) и вероятности состояний Jk{t) для некоторых к. В частности, J¡¡(t) - вероятность того, что очередь свободна в момент t.

Рассмотрим систему обслуживания M(t)/M(t)/100 с катастрофами и интепсив-ностями \(t) - 0.1 + 0.1 sin 27rí, fi(i) = 4 + 2 cos 2тrí, f (í) = 2 + sin 4ttí.

Используя метод, описанный в главе 3, положим d = 2 и <4 = dk. Тогда имеем £ = 0.2 L = 9.2, М = 100, w¡, = 2"n, = кроме того, /?(í) = /i(í) - j¡/t(t) -(d-l)A(í) = 1.9 + cos2jrt-0.1sm2irí, К < 3, и ¡3' = 1.9.

Пусть <5 = 10~6. Тогда достаточно выбрать m = 12 и п = 44. Тогда получаем предельное среднее 0(í) и все вероятности состояний Jt(t) с погрешностью 5 = Ю-6 как соответствующие характеристики решения задачи Коши с начальным условием ео для соответствующей урезанной системы Колмогорова на интервале [тп,тп + 1].

Графики 1 и 2 показывают, приближения для предельных характеристик

и

12,1 12.2 12.3 17А 12.0 12.6 12.? 12.8 12,9

Рис. 1: ф{1) при Ь 6 [12:13]

-т

1? 1.7.1 1?.7 1?.4 1?,1 17.fi 1?.7 1?Я

Рис. 2: при { £ [12; 13]

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

Полученные в работе результаты позволяют исследовать новые классы СМО. описывающиеся нестационарными марковскими цепями, близкими к поглощающим.

Публикации в изданиях, рекомендованных ВАК

[1] Зейфман А.И., Чегодаев A.B., Шоргин B.C. Некоторые оценки для близких к поглощающим марковских моделей. Информатика и ее применения, 2008, 2, №2, 35-40.

[2] Зейфман А.И., Сатин Я.А., Чегодаев A.B. О нестационарных системах обслуживания с катастрофами. Информатика и ее применения, 2009, 3, №1, 47-54.

Остальные публикации

[3] Зейфман А.И, Чегодаев A.B., Шилова Г.Н. Оценки скорости сходимости к предельному режиму для некоторых нестационарных линейных систем. Международная конференция им. И.Г.Петровского. М., МГУ, Тезисы докладов, 2007, 347-348.

[4] Шилова Г.Н.,Зейфман А.И., Чегодаев A.B. О точных оцепках скорости сходимости для конечных марковских цепей с поглощением в нуле. Уфимская международная математическая конференция. Тезисы докладов, т. 3. Уфа, 2007.3536.

[5] Чегодаев A.B. Оценки скорости сходимости для однородных марковских цепей с поглощением в нуле. Материалы ежегодных смотров-сессий аспирантов и молодых ученых но отраслям наук. Естественные и физико-математичемкие науки. Вологда, 2007, 148-151.

|G| Зейфман А.И., Чегодаев A.B. Оценки скорости сходимости для счетных марковских цепей с поглощениям в нуле. Стат. метода оценивания и проверки гипотез. Пермь, ПГУ, 2008, 196-207.

[7] Зейфман А.И., Чегодаев A.B. Оценки скорости сходимости для некоторых счетных линейных систем. Международная конференция "Дифференциальные уравнения п топология". М., МГУ, Тезисы докладов, 2008, 128-129.

[8] Зейфман А.И., Чегодаев А.В., Шилова Г.Н. Некоторые оценки для почти поглощающих процессов рождения и гибели. XVI международная конференция "Математика. Экономика. Образование". Тезисы докладов. Ростов-на-Дону, 2008, 130.

[9] Zeifman A., Chegodaev A. The bounds on the rate of convergence for absorbing continuous-time Markov chains. Finite state space. Trans, of Int. Seminar of Stability Problems for Stochastic Models, Nahariya, Israel, 2007, 201-207.

[10] Zeifman A., Chegodaev A., Shilova G. Almost absorbing continuous-time Markov chains on finite state space. TYans. of Int. Conference "Modelling of business, industrial and transport systems", Riga, 2008, 213-217.

[11] Zeifman A., Chegodaev A. On the bounds of solutions for some linear systems. International Conference "Geometry in Odessa 2008", Abstracts, Odessa, 2008,204205.

[12] Zeifman A., Chegodaev A. Some bounds for almost, absorbing Markov chains. XIII International Summer Conference on Probability and Statistics, Abstracts, Soiopol, Bulgaria, 2008, 38.

[13] Zeifman A., Satin Ya., Chegodaev A., Shilova G. Some bounds for the system of differential equations for M(t)/M(t)/N queue with catastrophes. International Conference "Geometry in Astrakhan 2008 ", Abstracts, Astrakhan, 2008, 84-86.

[14] A. Zeifman, Ya. Satin, A. Chegodaev, V. Bening, V. Shorgin. Some Bounds for M(t)/M(t)/S Queue with Catastrophes. The 3rd International Workshop on Tools for solving Structured Markov Chains, Athens, Greece, 2008.

[15] Zeifman A., Satin Ya., Chegodaev A. Some bounds for almost absorbing birth and death processes with catastrophes. Pliska Studia Mathcmatica Bulgarica, 19(2009), 293-306.

Формат 60x84 1/16. Бумага ксероксная. Печать - ризограф. Усл.печл. 1,2. Тираж 100 экз.

Отпечатано в ООО «ИПЦ «Легия» 160031, г. Вологда, ул. Октябрьская, д.19, кД 16.

Введение

1 Основные понятия

1.1 Пространство 1\

1.2 Некоторые свойства дифференциальных уравнений

1.3 Логарифмическая норма оператора

1.4 Конечные системы

1.5 Счетные системы

1.6 Марковские цепи

2 Марковские цеми с поглощением в нуле

2.1 Счетные марковские цепи с поглощением в нуле

2.2 Конечные марковские цепи с поглощением в нуле

3 Близкие к поглощаюшим марковские цепи

3.1 Близкие к поглощаюшим счетные марковские цепи

3.2 Близкие к поглощающим счетные ПРГ

3.3 Близкие к поглощаюшим конечные марковские цепи

3.4 Близкие к поглощающим конечные ПРГ

3.5 Близкие к поглощающим ПРГ с катастрофами

4 Марковские модели

4.1 Простая логистическая модель

4.2 Простое случайное блуждание с поглощением в нуле

4.3 Простое случайное блуждание с поглощением в нуле с разными скачками

4.4 Простое случайное блуждание, близкое к поглощающему

4.5 Простое случайное блуждание, близкое к поглощающему с разными скачками

5 Вычисление предельных характеристик

5.1 Система массового обслуживания, близкая к поглощающей, с катастрофами

5.2 Простое случайное блуждание, близкое к поглощающему

5.3 Простое случайное блуждание, близкое к поглощающему, с разными скачками

Актуальность темы.

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

Впервые задачи такого рода возникли из требований телефонного дела, физики тт рациональной организации массового обслуживания (билетные кассы, магазины и прочее) в начале предыдущего столетия. Первые исследования но этой тематике были приведены в работах А.К.Эрланга. Основные его исследования в этой области относятся к 1908-1922 годам. С того времени интерес к проблемам, выдвинутым Эрлапгом, значительно возрос. Оказалось, что подобные задачи возникают в самых разнообразных направлениях исследований: в естествознании, в технике, экономике, транспорте, военном деле, организации производства и многих других. Для решения проблем такого рода примерно в 50-х годах двадцатого века была создана так называемая теория массового обслуживания (англоязычный термин - теория очередей), являющаяся с тех пор активно развивающимся разделом прикладной теории вероятностей (см., например,

5, 9])

Большой прогресс для однородных марковских цепей был достигнут в последние два десятилетия с использованием специальных методик, в том числе каплинга, логарифмических неравенств Соболева, неравенства Пуанкаре и различных их модификаций (см., например, [33, 66]). Активизация исследований в последнее время обусловлена новыми областями приложений, в частности в изучении алгоритмов статистического моделирования марковских цепей, компьютерных сетей, статистической физики.

Постоянно увеличивается интерес к исследованию нестационарных (неоднородных по времени) марковских цепей (см, например, [34, 43, 45, 46, 47, 48]). Такие цепи возникают, в частности, при описашш процессов массового обслуживания. Основная часть исследований посвящспа различным вопросам, связанным с аппроксимацией для таких цепей (см.[35, 57, 56] и цитированную там литературу).

Задачи устойчивочти стохастических моделей изучались в различных постановках многими авторами, среди которых хотелось бы выделить [17, 18].

В числе математиков, заложивших, основы теории и приложений этой области и сформировавших ее современный облик (в части, близкой к тематике настоящего исследования), следует отметить Р.Л.Добрупгана, Б.В.Гнедепко, В.В.Калашникова, И.П.Макарова, А.И.Зейфмаиа, Н.В.Карташова, В.В.Анисимова, Е.Уап Боогп'а, Ш.ШЫ^'а и многих других.

Как известно, получение явных выражений для вероятностей состоянии стохастических моделей возможно лишь в исключительных случаях, поэтому одной из важнейших задач при исследовании таких моделей давно считается исследование поведения модели при £ —оо и, в частности, скорости сходимости к предельному режиму и связанных с этим функционалов.

Динамика таких процессов при некоторых дополнительных условиях описыватся прямой системой Колмогорова. В первоначальных исследованиях предполагалось, что модели описываются стационарными марковскими цепями (это означает, что соответствующая система Колмогорова имеет постоянную матрицу коэффициентов, которые называются интенсивпостями переходов). С содержательной точки зрения такая ситуация соответствует тому, что, например, "интенсивности" поступления и обслуживания требований в систему не зависят от времени. Понятно, что такое предположение достаточно далеко от реальности. В связи с этим, начиная с 70-х годов прошлого века (см. [8]), начались исследования нестационарных моделей, которым соответствуют системы линейных диффернциалных уравнений с переменной матрицей интенсивностей.

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

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

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

Цель работы.

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

Методика исследования.

В работе исследуется прямая система Колмогорова, имеющая вид:

Лс = (0.0.1) где х(£) - вектор-столбец вероятностей состояний описываемого процесса, а А(£) - матрица специального вида.

В основном рассматривается случай счетного пространства состояний, которому соответствует счетная система (0.0.1), отождествляемая с дифференциальным уравнением в пространстве последовательностей ¿1. Для исследования решений этой системы приходится опираться в основном на методы и понятия, разработанные в книге [10]. При этом исследуются решения системы (0.0.1), лежащие в множестве стохастических векторов О, то есть в множестве векторов с неотрицательными координатами и единичной ¿х-нормой.

При этом основные проблемы возникают при получении явных оценок нормы оператора Коши. Основным инструментом исследования является подход, упомянутый в [8], развитый в работах [12]-[16], [52]-[54], [С8]-[74] и базирующийся на двух основных моментах: логарифмической норме линейной операторной функции и специальных преобразованиях редуцированной матрицы интенсивностей марковской цепи.

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

Содержание работы.

Во введении содержится обоснование актуальности темы, краткий обзор результатов, цель работы, методика исследования, краткое содержание работы.

Диссертация состоит из пяти глав, разбитых на параграфы.

Выход

Основные модули программы находятся в Unit3.pas, nextdif.pas, sum.pas. Только их содержимое приводится.

Unit3.pas unit Unit3;

Коши, координаты, график, средняя, решение дифура, fresultdifurlntegralSimpson, count srednee s interface

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls. Forms, Dialogs, StdCtrls. ExtCtrls, Grids.nextdiÇsumm. ExtDlgs, ComCtrls; const bordx=50; bordy=50; strL=10; strW-5; colorconst=0; by=10: type

TForm3 = class(TForm) Button 1: TButton; Button2: TButton; GroupBoxl: TGroupBox; Image 1 : TImage; Panell: TPanel; sg: TStringGrid; Edit2: TEdit; Edit3 : TEdit: Label2: TLabel; LabeB: TLabel; Button3: TButton; Panel2: TPanel; Labcl4: TLabel; Label5: TLabel; Edit4: TEdit; Edit5 : TEdit; Edit6: TEdit; Labelö: TLabel; Edit7: TEdit; Label7: TLabel; Button5: TButton; Buttonö: TButton; Button7: TButton; Koshi: TStringGrid;

Button8: TButton; spd: TSavePictureDialog; Button9: TButton; opend: TOpenDialog; Label8: TLabel; Edit8: TEdit; Label9: TLabel; Edit9: TEdit; ButtonlO: TButton; Labeil: TLabel; Editl: TEdit; Button 11: TButton: od: TOpenDialog; ButtonD: TButton; Editl2: TEdit; Label 10: TLabel; CheckBoxl: TCheckBox; procedure ButtonlClick(Sender: TObject); procedure Button2Click(Sender: TObject); procedure Button3Click(Sender: TObject); procedure Button7Click(Sender: TObject); procedure Button8Click(Sender: TObject); procedure Button6Click(Sender: TObject): procedure Button5Click(Sender: TObject); procedure Button9Click(Sender: TObject); procedure Button 10Click(Sender: TObject); procedure Buttonl lClick(Sender: TObject); procedure Buttonl3Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure CheckBoxl Click(Sender: TObjec private { Private declarations } fhinteger; procedure SetR(dat:integer); public firstvector.nilvector:typarr; property CountR: integer read fr write SetR; procedure iresultdifurIntegralSimpson(var temp,srednee:typarr); procedure graphicSho\v(bt:extended;arr:typarr); procedure init;

Procedure show;

Procedure show2; procedure SetCoord(max,min,period,maxy,miny:extended); function countsrednee (var srednee:typarr;n,r:integer):extended; { Public declarations } end; var

Form3: TForm3; implementation uses NewDifur, Unit2, Unit5; {$R *.dfm} procedure TForm3.ButtonlClick(Sender: TObject); begin close; end; procedure TForm3.Button2Click(Sender: TObject); begin forml .close; end; procedure Tform3.SetR(dat:integer); var k: integer; begin fr:=dat; sg.RowCount:=dat+l; for k:= 1 to dat do sg. Cells [0 ,k] :=inttostr(k); Koshi.RowCount:=dat+l; Koshi.ColCount:=dat+l; end;

Procedure TForm3.show; var temp,srednee:typarr; k,kk:integer; tmp:extended; max, min,mx, my ,mx, my: extended; procedure genEi(i:integer;var tmp:typarr); begin tmp:=nilvector; tmp[i]:=l; srednee:=niljvector; end; begin for kk:=l to n size do nilvector[kk] :=0; for k:=l to strtoint(forml .editl .text) do begin genEi(k,temp); {в arr заносится ek, зануляется srednee} fresultdifurlntegral Simpson(temp. srednee); forkk:=l to strtoint(forml.editl.text) do

Koshi.Cells[k,kk]:=floattostr(temp[kk]); {сохраняется u(kk,k)} используя srednee можно получить \int(bt)A(et) u(kk,k) (s)ds} end; max:=0; for kk:=l to strtoint(forml.editl .text) do begin min:=l; fork:=l to strtoint(forml.edit 1.text) do begin tmp :=strtofloat(Ko shi. Cells [k,kkj); if tmp<min then begin min:=tmp; mx:=k;my:=kk; end; end; if min>max then begin max:=min; mx:=mx; my:=my; end; end; edit8.text:=floattostr(mx)+'' + floattostr(my)+'' + floattostr(max); end;

Procedure TForm3.show2; var temp,srednee:typarr; kk:integer; et,bt,tmp: extended; begin temp:=firstvector; fresultdifur Integral Simpson(temp, sred nc e); bt:=strtofloat(edit4.text); et:= strtofloat(edit5.text); form5.Memol .Lines.Clear: for kk:=l to strtoint(edit9.Text) do begin tmp:=countsrednee(srednee,strtoint(edit9.Text),kk); form5 .Memo 1 .Lines. Add(floattostr(tmp/(et-bt))); end; end; procedure Tform3.fresultdifurIntegralSimpson (var temp,srednee:typarr); \ar b t.et,h:extended; n:integer; begin bt:=strtofloat(edit4.text); et:= strtofloat(cdit5.text); h:= strtofloat(edit6.text); n:=strtoint(forml .editl .text); initKl; resultdifurNOTsrednee(0,bt,h,n,temp); resultdifurIntegralSimpson(bt,et,h,n,temp,srednee); end; procedure Tform3.init: var x,y:integer; begin for x:=l to form2.sg.RowCount-l do for y:=l to form2.sg.RowCount-l do begin arrKo e f[x,y]:=dat .Crcate(form2. sg. Cells [x,y]); end; end; procedure TForm3.SetCoord(max,min,period,maxy.minyrextended); var k,t,TMP,tmp2,tmpp:integer; step: extended; st: string; begin image 1 .Canvas.font.namei-arial'; tmp:=imagel.Canvas.Pen.Color; imagel.Canvas.Pen.Color:=colorconst; t:=10; for k:=0 to t do begin image 1.Canvas.Te\t0ut(0, round(imagel .Height-bordy-k/10*(imagel .Height-2*bordy)), floattostr(miny+k/t*(maxy-minY))); imagel .Canvas.MoveTo(bordx, round(image 1 .Height-bordy-k/10"- (image 1 .Height-2+bordy))); imagel .Canvas.LineTo(imagel .width-bordx, round(imagel.Height-bordy-k/10*(imagel.Height-2*bordy))); end; step:=min; if max>0 then while step<=max do begin imagel. Canvas. Mo veTo(bordx+round(step* (imagel. Width-2*bordx)/(max-min))-round(min*(imagel.Width-2*bordx)/(max-min)),bordy); imagel.Canvas.Lineïo(bordx+round(step*(imagel.Width-2*bordx)/(max-min))-roimd(min*(imagel.Width-2*bordx)/(max-min)), round(imagel .Height-bordy)); imagel. Canvas.TextOut(bordx+round(step*(image 1. Width-2*bordx)/(max-min))-round(min* (image 1. Width-2*bordx)/(max-min))imagel.Canvas.TextWidth(floattostr(step)) div 2, round(image 1 .Height-bordy)+by,floattostr(step)); step:=step+period; end; imagel.Canvas.TextOut((imagel .Width-imagel.Canvas.TextWidth(editl2.text)) div 2, imagel.Height-bordy div 2,editl2.text); imagel .Canvas.MoveTo(bordx.imagel .Ileight-bordy); imagel.Canvas.LineTo(bordx,bordy div 2); for k:= -strW div 2 to strW div 2 do begin imagel.Canvas.MoveTo(bordx,bordy div 2); imagel.Canvas.LineTo(bordx+k,bordy div 2 + strL): end; st:=image 1 .Canvas.lb nt.name; imagel.Canvas.font.name:='Symbor; tmpp:=imagel.Canvas.TextWidth('j')*5 div 4; imagel .Canvas.TextOut(0,bordy div 2,'j'); imagel.Canvas.font.name:=st; if strtoint(edit9.Text)>l then begin tmp2:=imagel .Canvas.font.Size; imagel .Canvas.font.Size:=imagel .Canvas.font.Size-3; imagel.Canvas.TextOut(tinp,bordy div 2 + 3*imagel.Canvas.font.Size div 2 +2,edit 1.Text); tmpp:=tmpp+imagel .Canvas.Text Width(editl .Text); imagel .Canvas.font.Size:=tmp2; end; imagel.Canvas.TextOut(tmpp,bordy div 2,'(t)'); imagel .Canvas.MoveTo(bordx,imagel .Height-bordy); imagel.Canvas.LineTo(imagel.Width- bordx div 2,imagel.Height-bordy); for k:= -strW div 2 to strW div 2 do begin imagel.Canvas.MoveTo(imagel.Width- bordx div 2,imagel.Height-bordy); imagel.Canvas.LineTo(imagel.Width- bordx div 2 - StrL,imagel.Height-bordy - k); end; imagel.Canvas.TextOut(imagel.Width- bordx div 2,imagel.Height-bordy,ft'); imagel. Canvas.Pen.Color:=tmp; end; procedure TForm3.Button3Click(Sender: TObject); var arr:typarr; begin if strtoint(edit9.Text)=l then arrC:=arrCl else arrc:=arrC2; if strtoint(edit9.Te\t)=l then funct:=functl else funct:=funct2; arr:=firstvector; graphicShow(0,arr); end; procedure TForm3 .graphicShow(bt:extended;arr:typarr); var h,endt,res,maxY,minY,begint:extended; n:integer; tttt,pp,pp2: integer; FirstBegt: extended; procedure Setline 1 (x.y,max:extended); begin image 1. Canvas. LineTo(round(bordx+x/max* (image 1 .width-2*bordx)), round(imagel .Height+minY* (image 1 .Height-2*bordy)/(MaxY-minY)-(bordy+y* (image 1 .Height-2*bordy)/(MaxY-minY)))); inc(tttl); end; begin tttt:-0; begint:=strtofloat(edit4.text); endt:=strtofloat(edit5.text); h:=strtofloat(edit6.text); n:=strtoint(forml .editl .text): pp:=strtoint(editl .Text); pp2 :=str toint (edi t9 .Text) ; maxY:=strtofloat(edit2.text); minY:=strtofloat(edit3 .text);

SetCoord(endt.begint,strtofloat(edit7.text),maxY,minY); FirstBegt:=begint; resultdifurNotSrednee(bt,begint,h,n,arr); res :=countsrednee(arr,pp2 ,pp) ; image 1 .Canvas.MoveTo(round(bordx), round(image 1 .Height+minY* (image 1 .Height-2*bordy)/(MaxY-minY)-(bordy+res* (image 1 .Height-2 *bordy)/(MaxY -minY)))) ; while begint<endt do begin resultdiiurNotSrednee(begint,begint+h.h,n,arr); res:=countsrednee(arr,pp2,pp); {OpncaHHc Setline(x,y,max)} Setlinel(begint-FirstBegt,res,endt-FirstBegt); // image 1.Re fresh; begint:=begint+h; end; end; procedure TForm3.Button7Click(Sender: TObject); begin

Koshi.Visible:=not Koshi.Visible; image 1 .Visible:=not image 1. Visible; end; procedure TForm3.Button8Click(Sender: TObject); begin if strtoint(edit9.Text)=l then arrC:=arrCl else arrc:=arrC2; if strtoint(edit9.Text)=l then funct:=functl else funct:=funct2; show end; procedure TForm3.Button6Click(Sender: TObject); begin if spd.Execute then image 1. Picture. SaveToFile(spd.FileName); end; procedure TForm3.Button5Click(Sender: TObject); begin imagel.Canvas.brush.Color:=imagel.Picture.bitmap.TransparentColor; imagel. Canvas. FillRect(imagel.ClientRect); end; procedure TForm3.Button9Click(Sender: TObject); var k,kk: integer: i:textfile; begin if opend.Execute then begin

AssignFile(i, opend.FileName); rewrite (i); for k:= 1 to Koshi.colcount do begin for kk:= 1 to Koshi.colcount do write(i,Koshi.Cclls[k,kk]:25); writeln(i); end; closefile(i); end end; procedure TForm3.Button 10Click(Sender: TObject); begin form5.ShowModal; end; function TForm3.countsrednee (var srednee:typarr;n,r:integcr):extended; var tmp,tmp2:extended;mt,k,kl ,k2,k3,count,kk:integer; begin count:=strtoint(forml .Editl .Text); tmp:=0; case n of 1: for k:=l to count do tmp: =tmp+srednee [k] * (k-1);

2: case r of 1: for k:=0 to round(sqrt(count))-l do begin tmp2:=0; forkk:=0 to round(sqrt(count))-l do tmp2 :=tmp2isrednee[kk+k*round(sqrt(count))+l]; tmp :=tmp+tmp2 * k; end; for k:=0 to round(sqrt(count))-l do begin tmp2:=0; for kk:=0 to round(sqrt(count))-1 do tmp2:=tmp2+srednee[k+kk*round(sqrt(count))+l]: tmp:=tmp+tmp2 * к; end; end; 3: begin

• mt:=count; for kl:=l to count do if (kl *kl *kl=count) then mt:=kl; case r of 1: 1,10,19.20 -дно for kl:=0 to mt-1 do begin tmp2:=0; for k2:=0 to mt-1 do for k3:=0 to mt-1 do tmp2 :=tmp2+srednee[k2+k 1 * mt+k3 * mt*mt+1J; tmp:=tmp+tmp2*k 1; end;

2: 1,2,3,4 -дно for kl:=0 to mt-1 do begin tmp2:=0; for k2:=0 to mt-1 do for k3:=0 to mt-1 do tmp2 :=tmp2+srednee [k2+k3 *mt+kl *mt*mt+l ]; tmp:=tmp+tmp2*kl; end;

3: 1,4,7,10,13 -дно for kl:=0 to mt-1 do begin tmp2:=0; for k2:=:0 to mt-1 do for k3:=0 to mt-1 do tmp2 :=tmp2+srednee[kl +k2* mt+k3 *mt*mt+1 ]; tmp:=tmp+tmp2*kl; end; end; end; end; countsrednee :=tmp; end; procedure TForm3.Button 11 Click(Sender: TObject); begin if strtoint(edit9.Text)=l then arrC:=arrCl else arrc:=arrC2; if strtoint(edit9. Text)= 1 then funct:=functl else funct:=funct2; show2; end; procedure TForm3.Buttonl3Click(Sender: TObject); var temp,srednee:typarr; k,kk,n: integer; et,bt,h:extended: . procedure genEi(i:integer;var tmp:typarr); begin tmp :=nilvector; tmp[ij:=l; end; begin for kk:=l to n size do nilvector[kk] :=0; temp:=firstvector; initKl; if strtoint(edit9.Text)=l then arrC:=arrCl else arrc:=arrC2; if strtoint(edit9.Text)=l then funct:=functl else iunct:=fiinct2; bt:= strtoflo at(edi t4 .text); et:= strtofloat(edit5 .text); n:=strtoint(forml .editl .text); h :=strtofloat(edit6 .text); resultdifurNOTsrednee(0,bt,h,n,temp); resultdifurIntegralSimpson(bt,et,h,n,temp.srednee); for k:=l to strtoint(forml.editl.text) do begin if et>bt then sg.Cells[l,k]:=floattostr(srednee[k]/(et-bt)) else sg.Cells[l ,1c]—'error'; sg.Cells[2,k]:=iloattostr(temp[k]); end; end; procedure TFonn3.FormCreate(Sender: TObject); begin sg.Cells[2,0]:=,PeineHHe flH^ypa'; if checkboxl .Checked then funct:=functl else funct:=funct2; if checkboxl.Checked then arrC:=arrCl else arrC:=aiTC2; end; procedure TForm3.CheckBoxlClick(Sender: TObject); begin if (Sender as tcheckbox).Checked then funct:=functl else funct:=funct2; if (Sender as tcheckbox).Checked then arrC:=arrCl else arrC:=arrC2; end; end. nextdif.pas

Рассматривается система dp/dt=A(t)p(t). Вектор р содержится в массивах типа typarr.

Масивы передаютя в процедуру как параметры - переменные для ускорения вычислений. Тип dat описывается в модуле summ. Позволяет ускорить вычисления. Используются формулы "Классического" метода Рунге Кутты.

Перед использованием продедур данного модуля, необходимо быть уверенным, что funct присвоено funct 1 или funct2. } unit nextdif; interface uses summ,Math; const nsize=l 500; type typarr=array [l.nsize] of extended; var kl.tmpkl:array[l.nsize,-1.4] of extended; // содержит коэффициенты. arrKoef:array[l .nsize,l ,.nsize] of dat; // содержит A(t); тип dat описывается в модуле summ; arrKoef^cont:array[l.nsize,l.nsize] of extended; funct: function (k,n,koef:integer;t:extended;var arr:array of extended;c:integer):extended; arrCprocedure (t:extended; n:integer); procedure resultdifurNOTsrednee(begt,maxt,h:extended;n:word; var arr:array of extended); procedure resultdifurIntegralSimpson(begt,maxt,h:extended;n:word; var arr:array of extended;var srednee:array of extended); function functl(k,n,koef:integer;t:extended;var arr:array of extended;c:integer):cxtended; function funct2(k,n,koef:integer;t:extended;var arr:array of extended;c:integer):extended; procedure arrCl(t:extended; n:integer); procedure arrC2 (t:extended; n:integer); procedure initKl; implementation procedure initKl; var y:integer; begin for y:=l to nsize do kl[y,-0]:=0; end; function functl(k,n,koef:integer;t:extended;var arr:array of extended;c:integer):extended; var temp2,temp:extended; kk:integer; { учитываются только элементы стоящие на главной диагонали и на двух рядом с гоящих диагоналях } begin temp2:=0; for kk:= max(l,k-l) to min(k+l,n) do temp2:=temp2+airKoefcont[k,kk]; // <сумма элементов в столбце> temp:=-temp2 * (arr [k-1 ]+k 1 [k,koef] /с); for kk:= max(l,k-l) to min(k+l,n) do temp :=temp+arrKoefcont[kk,k] *(arr[kk-1 ]+k 1 [kk,koef]/c); functl:=temp; end; function funct2(k,n,koef:integer;t:extended;var arr:array of extended;c:integer):extended; var temp2,temp:extended; kkrinteger; begin temp2:=0; for kk:= 1 to 11 do temp2:=temp2+arrKoefcont[k.kk]; // <сумма элементов в столбце> temp:=-temp2*(arr[k-1 ]+kl [k,koef]/c); for kk:= 1 to n do temp:=temp+arrKoefcont[kk,k]*(arr[kk-l]+kl[kk,koef]/c); funct2:=temp; end; procedure arrC 1 (t:extended;n: integer); var x: integer; begin for x:=l to n-1 do begin arrKoefcont[x,x+1 ] := arrKoef[x,x+1 ] .result(t); arrKoefcont[x+1 ,x] := arrKoef[x+1 ,x].result(t); end end; procedure arrC2(t: extended;n:integer); var x,y: integer; begin for x:=l to n do for y:=l to n do arrKoefcont[x,y] := arrKoef[x,y] .result(t); end; procedure next(n:word;t,h:extended;var arnarray of extended; var arr2:array of extended);

Нахождение p(t+h) (результат заносится в arr2) используя p(t) (из arr) методом Рунге-Кутта 4 порядка h - шаг. n- число уравнений в системе

Перед использованием необходимо обнулить kl[r,0J (если отличны от 0), где г изменяется от 1 до п. Можно для этого использовагь initKl. Использование указагелей на типизированные массивы может привести к однократному вызову аггС (вместо трех, что есть сейчас), что ускорит вычисления (используя особенности работы с шагом) var k:word; begin arrC(t,n); for k:=l to n do kl [k, 1 ] :=h* funct(k.n,0,t,arr, 1); arrC(t+h*0.5,n); for k:=l to n do kl[k,2]:=h*iunct(k,n,l,t+h*0.5,arr,2); arrC(t+h*0.5,n); for k:=l to n do k 1 [k, 3 ] :=h* funct(k,n,2 ,t+h* 0.5 ,arr,2); arrC(t+h,n): for k:=l to n do k 1 [k,4] :=h*funct(k,n,3 .t+h,arr, 1); for k:=l to n do arr2[k-l]:=arr[k-l]+(kl[k,l]+2*(kl[k,2J+kl[k,3])+kl[k,4])/6; end; procedure resultdifurNOTsrednee(begt,maxt,h:extended;n:word; var arr:array of extended);

Начальные значения находятся в arr (p(begt)).

Приводит к изменению содержимого агг (содержит p(maxt)). h - шаг. п- число уравнений в сис теме } var t:extended; begin t:=begj; if begt<maxt then while h>0 do begin next(n,t,h,arr.arr); t:=t+h; if t>=maxt then h:= maxt - t; end; end; procedure resultdifurIntegralSimpson(begt,maxt,h:extended;n:word; var arr:array of extended;var srednee:array of extended);

Нахождение интеграла.

Начальные данные находятся в arr (p(begt)). Для установки в агг нужных данных можно воспользоватся процедурой result difurNOTsrednec.

Поиск данных осуществляется методом Симпсона. Значение интеграла (от begt до maxt) помещаются в srednee.

Приводит к изменению содержимого агг (содержит p(maxt)). h - шаг. п- число уравнений в системе

Замечание: maxt-begt должно делится на 2 (т.е. между maxt и begt должно быть четное число шагов, причем последний шаг должен заканчиватся на maxt) } var k:word;tt: extended; chet:boolean; begin chet:=false; for k:=0 to n-1 do srednee|k]:=arr[k]; tt:=begt; while (tt< maxt-h)or chet do begin next(n,tt,h,arr,arr); tt:=tt+h; if chet then for k:=0 to n-1 do srednee[k]:=srednee[k]+2*arr[k] else for k:=0 to n-1 do srednee[k]:=srednee[k]+4*arr[k]; chet:=not chet; end; for k:=0 to n-1 do srednee[k]:=(srednee[k]-arr[k])*h/3; end; begin end. sum.pas

Быстрое вычисление часто используемых выражений. unit summ; interface type dat=class private l,r:dat; /nakxhar; chislo:extended; public constructor create(st:string); destructor destroy; function result(t : extend ed) : extended ; end; implementation destructor dat.destroy; begin l.Free; r.Free; inherited; end; function dat.result(t:extended):extendcd; begin case znak of result:=l.result(t)+r.result(t); '-':result:=l.result(t)-r.result(t); '*':result:=l.result(t)*r.result(t); 7':result:=l.result(t)/r.result(t); s':result:=sin(i.result(t)); 'c':result:=cos(l.result(t)); 'e':result:=exp(l.result(t)); 'q':result:=sqrt(l.result(t)); ' ':result:=chislo; 't': result :=t; end; end; constructor dat.create(st: string); function coun(st: string) :boolean; var count,k: integer; begin count:=0; if st[l]o'(' then begin coun:=false; exit; end else begin fork:=l to length(st)-l do begin if st[k]='(' then inc(count); if st[k]-)'then dec(count); if count=0 then begin coun:=false; exit; end; end; end; coun:=true; end; var k:word; code:integer; counter:word; begin while pos(',',st)>0 do st[pos(',',st)J:='.'; counter:=0; while coun(st) do st:=copy(st,2,length(st)-2); for k:=length(st) downto 1 do begin if st[k]-)' then ine(counter); if st[k]-(' then dec(eounter); if ((st[k]='+') or (st[k]='-')) and (counter=0) then begin l:=dat.create(copy(st, 1 ,k-1)): r:=dat.create(eopy(st,k+l,length(st))); znak:=st[k]; exit; end; end; for k:=length(st) downto 1 do begin if st[k]=')' then inc(counter); if st[k]='(' then dec(counter); if ((stCk]^*') or (st[k]='/')) and (counter=0) then begin l:=dat.create(copy(st, 1 ,k-1)); r:=dal.ereate(copy(st,k+l,length(st))); znak:=st[k]; exit; end; end; if st-t' then znak:='t' else if eopy(st,l,3)='sin' then begin znak:-s';

1 :=dat. create(copy(st,4,length(st))); end else if copy(st,l,3)='cos' then begin znak:-c';

1 :=dat.create(copy(st,4,length(st))); end else if copy(st,l,3)-exp' then begin znak:-e';

1:=dat. create(copy (st,4,length(st))); end else if copy(st,l,2)-pi' then begin znak:chislo:=3.1415926535897932384626433832795; end else if copy(st, 1,4)- sqrt' then begin znak:='q';

1 :=dat. create(copy(st,5 ,length(st))); end else begin znak:- '; val(st,chislo,code); end; end; begin end.

1. Анисимов В.В. Оценки отклонения переходных характеристик неоднородных марковских процессов. Укр.мат.ж.1988.40. 699706

2. Беллман Р. Введение в теорию матриц. М.:Наука, 1976.

3. Березин И.С., Жидков FI.Tl. Методы вычислений. Том II. Москва. 1960.

4. Бибиков Ю.Н. Курс обыкновенных дифференциальных уравнений.М. Наука, 1991.

5. Баруча-Рид А.Т. Элементы теории массовых процессов и их приложения. М.: Наука, 19G9.

6. Воскресенский Е.В. Асимптотическое равновесие, периодические решения и прямой меод Ляпунова // Дифференциальные уравнения, 1999. - N6. - С.729-732.

7. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1966. 576с.

8. Гнеденко Б.В., Макаров И.П. (1971). Свойства решений задачи с потерями в случае периодических интенсивностей. Дифференциальные уравнения. 7, 9, 1696-1698.

9. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М : Наука, 1966

10. Далецкий Ю.Л, Крейн М.Г. Устойчивость решений дифференциальных уравнений в банаховом пространстве. Москва.: Наука., 1970.

11. Демидович Б.П. Лекции по математической теории устойчивости. М.: Издательство Московского Университета. 1998 480с.

12. Зейфман А.И. (1989). Некоторые свойства системы с потерями в случае переменных интенсивностей. Автоматика и телемеханика, 1, 107-113.

13. Зейфман А.И Стохастические модели. Процессы рождения и гибели В тогда.: Издательство "Русь", 1994.

14. Зейфман А И., Сатин Я.А. О некоторых средних характеристиках крнечных марковских цепей с непрерывным временем // Стат мет. оцен. и проверки гипотез Пермь, ПГУ, 2005, 168-175.

15. Зейфман А.И., Сатин Я. А Средние характеристики марковских систем обслуживания /1 Автоматика и телемеханика, 2007.№9. С 122-133.

16. Зейфман А.И., Бенинг В. Е., Соколов И. А. Марков- скис цепи и модели с непрерывным временем. —М.: ЭЛЕКС-КМ, 2008 168 с.

17. Калашников В.В. Качественный анализ сложных систем методом пробных функций. -М.:Наука, 1978.

18. Карташов Н.В Сильно устойчивые цепи Маркова. В сб. Проблемы устойчивости стохаст. моделей. М.: ВНИИСИ 1981, 54-59.

19. Курош А.Г. Курс высшей алгебры. М.: ГИФЛМ. 1963.

20. Ланкастер П Теория матриц. М.: Мир, 1978.

21. Лозинский С.М Оценка погрешности численности интегрирования обыкновенного дифференциального уравнения. Изв. ВУЗов. Матем., 1958, N 5, 52-90

22. Понтрягин Л.С. Обыкновенные дифференциальные уравнения М.: Наука, 1974. 331с

23. Тараскин В.Ф. Периодический режим процессов рождения, гибели и иммиграции и их приложении в здравоохранении. В кн.: Теория массового обслуживания. Тр. III Всесоюз. школы совещания. М.: МГУ, 1976, т.2 , с. 105-112.

24. Терехин М.Т., Ретюнских Н.В. Периодические решения нелинейных неавтономных систем обыкновенных дифференциальных уравнений // Дифференц. уравнения. 2001 . Т. 37, N 4. С. 566-569

25. Хайрер Э., Нёрсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи. Москва.: Мир. 1990.

26. Anderson, W.J. (1991). Continuous-time Markov Chains. Springer, New York.

27. J.R. Aitalejo and M. J Lopez-Herrero, Analysis of the busy period for the M/M/c queue: an algorithmic approach, J. Appl. Probab. 38 (2001) 209-222.

28. Brockwell, P.J. (1986). The extinction time of a general birth and death process with catastrophes J. Appl. Probab. 23, 851-858.

29. Cairns, B. and Pollett, P. (2003). Persistence times for a general birth, death and catastrophe process. Preprint.

30. P. Coolcn-Schrijncr and E.van Doom, On the convergence to sta-tionarity of birth-death processes, J.Appl. Probab. 38 (2001) 696706.

31. Doom Ё., van. Stochastic monotonicity and queueing applications of birth-death processes. Lect. Not. Statist., v.4. p.1-118

32. Bartlelt M. Stochastic population models in ecology and epidemol-ogy. L.: Metheun and Co. Ltd., 1960.

33. Chen M.F. Eigenvalues, inequalities, and ergodic theory. N.Y.: Springer, 2005.

34. Ching Wai-Ki, Ng M. K. Markov chains: Models, algorithms and applications.— New York: Springer, 2006.

35. Di Crescenzo A., Nobile A.G. Diffusion approximation to a queueing system with time dependent arrival and service rates // Queueing Syst.,1995 No.19, p.41-72 .

36. Di Crescenzo A., Giorno V., Nobile A.G., Ricciardi L.M. (2003) On the M/M/l queue with catastrophes and its continuous approximation. Queueing Syst. 43, No.4, p.329-347 .

37. Di Crescenzo A., Giorno V., Nobilc A.G., Ricciardi L.M. (2008) A note on birth-death processes with catastrophes. Statistics and Probability Letters.

38. Dietz K. Epidemics and rumours: A survey. -J. Roy. Statist. Soc., ser. A, 1967.

39. Dietz K., Downtoun F. Carrier-borne epidemics with immigration. I. Immigration of both susceptibles and cairies. J. Appl. Prob., 1968, v. 5, N 1, p. 31-42.

40. V. Giorno and A.Nobile, On some time-nonhomogeneous diffusion approximations to queueing systems, Adv. Appl. Probab. 19 (1987) 974-994.

41. Jacka, S.D. and Roberts, G.O. (1995). Weak convergence of conditioned processes on a countable state space. J. Appl. Probab. 32, 902-916.

42. Kendall D. Determenistic and stochastic epidemics in closed populations. Proc. of 3th Berkely symp. on Math. Statist, and Prob., 1956, v. 4, p. 149-165.

43. Di Crescenzo A. and Nobile A.G. Diffusion approximation to a queueing system with time dependent arrival and service rates // QUESTA. 1995. V. 19. P. 41-62.

44. Goel N., Richter-Dvn N. Stochastic models in biology. N. Y.: Acad. Press, 1974

45. B.Gnedenko and A.Soloviev, On the conditions of the existence of final probabilities for a Markov process. Math. Operationsforsh. Stat., (1973)379-390.

46. B.L.Granovsky B.L. and A.I.Zeifman, Nonstationary Maxkovian queues, J. Math. Sci. 99 (2000) 1415-1438.

47. Granovskv, B and Zeifman, A. (2004). Nonstationary Queues: Estimation of the Rate of Convergence. Queueing Systems 46, pp. 363-388.

48. Griffeath D. Uniform coupling of nonhomogeneous Markov chains. J.Appl.Piob., 1975, 12, 753-763

49. Johnson J., Isaacson D. Conditions for strong ergodicity using intensity matrices. J.Appl.Prob., 1988, 25, 34-42

50. Karlin, S. and McGregor, J.L. (1957). The classification of birth and death processes. Trans. Amer. Math. Soc. 86, 366-400.

51. Krishna Kumar В., Anvudamambi D. (2000) Transient solution of an M/M/l queue with catastrophes. Comput. Math. Appl. 40, No. 10-11, 1233-1240.

52. S.Lcoiato. E.Orsingher, Ya.Satin, G.Shilova, A. Zeifman (2004). On some limits for nonhomogeneous birth and death processes. Trans. 24 Seminar of Stability Problems for Stochastic Models, Jurmala, Latvia, 52-53

53. S.Leorato, E.Orsingher, Ya.Satin, G.Shilova, A. Zeifman On some characteristics for nonhomogeneous birth and death processes // Труды участников международной школы-семинара по геометрии и анализу. Ростов-на-Дону, 2004, 283 284.

54. S.Leorato, E.Orsingher, Ya.Satin, G.Shilova, A. Zeifman. Some universal limits for nonhomogeneous birth and death processes. // Queueiug System, 2006, 139-151.

55. Margolius, B. (1999). Some path analysis of the Mt/Mt/c queue, Queueing Systems. 31, 59-93.

56. Mandelbaum A. and Massey W. Strong approximations for time-dependent queues // Math. Oper. Res. 1995. V. 20. P. 33-64.

57. Massey W.A. and Whitt W. On analysis of the modified offered-load approximation for the nonstationary Erlang loss model // Ann. Appl. Probab. 1994. V.4. P. 1145-1160.

58. I. Nasell On the quasi-stationary distribution of the stochastic logistic epidemic. Math. Biosci., 156, 21-40, 1999.

59. Pakes, A.G. (1987). Limit theorems for the population size of a birth and death process allowing catastrophes. J. Math. Biol. 25, 307-325.

60. L.Saloff-Coste, 1996, Lectures on finite Markov chains, Lecture Notes in Math.,1665, 301-413.

61. Sirl D., Zhangy H., Polletl P., "Computable Bounds for the Decay Parameter of a Birth-Death Process," J. Appl. Probab., 44, 476-491 (2007). Zeifman

62. Ya.Satin, G.Shilova. A.Zeifman On some characteristics for finite nonhomogeneous birth and death processes//Trans. 25 Seminar of Stability Problems for Stoch. Models, Salerno. Italy, 2005, 250-257

63. Scott, M., Isaacson D. Proportional intensities and strong ergodicity for Markov processes. J.Appl.Prob., 1983, 20, 185-190

64. Toyoizumi H., Kobayashi Y., Kaiwa K., Sliitozawa J. Stochastic Features of Computer Viruses: Towards Theoretical Analysis and Simulation (695)

65. Van Doom, E.A., Zeifman, A. (2005) Extinction probability in a birth-death process with killing. J. Appl. Probab. 42, 185-198.

66. Van Doom, E.A. Conditions for exponential ergodicity and bounds for the decay parameter of a birth-death process // Adv. Appl. Prob. 1985. 17. 514-530.

67. Yang G., Chiang G. On interrival times in simple stochastic epidemic models. J. Appl. Prob., v. 19, N 4, p. 835-841.

68. Zeifman A.I. Stability for contionuous-time nonhomogeneous Markov chains // Lect. Notes Math. 1985. V. 1155. P. 401-414.

69. Zeifman A.I. Truncation Error in a Birth and Death System, U.S.S.R. Comput. Math. Math. Phys., 1988, 28, 6, 210-211.

70. Zeifman A.I. On the estimation of probabilities for birth and death processes // J. Appl. Probab. 1995. V. 32. P. 623-634.

71. Zeifman A.I. Upper and lower bounds on the rate of convergence for nonhomogeneous birth and death processes // Stoch. Proc. Appl. 1995. V. 59. P. 157-173.

72. Zeifman A.I. (1998). Stability of birth and death processes. J. Math. Sci., 1998, v.91, N3, 3023 3031.

73. Zeifman A.I On the weak ergodicity of nonhomogeneous continuous time markov chains.

74. Zeifman A., Satin Ya., Shilova G. Bounds of the mean for some nonhomogeneous birth and death processes // Trans, of 26 Seminar of Stability Pioblems for Stochastic Models, Sovata-Bai, Romania, 2006, 91-92.

75. Зейфман А.И, Чегодаев А.В., Шилова Г.Н. Оценки скорости сходимости к предельному режиму для некоторых нестационарных линейных систем. Международная конференция им. И.Г.Петровского. М., МГУ, Тезисы докладов, 2007, 347-348.

76. Шилова Г.Н.,Зейфман А.И., Чегодаев А.В. О точных оценках скорости сходимости для конечных марковских цепей с поглощением в нуле. Уфимская международная математическая конференция. Тезисы докладов, т. 3. Уфа, 2007.35-36.

77. Зейфман А.И., Чегодаев А.В. Оценки скорости сходимости для счетных марковских цепей с поглощениям в нуле. Стат. методы оценивания и проверки гипотез. Пермь, ПГУ, 2008, 196-207.

78. Зейфман А.И., Чегодаев А.В. Оценки скорости сходимости для некоторых счетных линейных систем. Международная конференция "Дифференциальные уравнения и топология". М., МГУ, Тезисы докладов, 2008, 128-129.

79. Зейфман А.И., Чегодаев А.В., Шоргин B.C. Некоторые оценки для близких к поглощающим марковских моделей. Информатика и ее применения, 2008, 2, №2, 35-40.

80. Зейфман А.И., Чегодаев А.В., Шилова Г.Н. Некоторые оценки для почти поглощающих процессов рождения и гибели. XVIмеждународная конференция "Математика. Экономика. Образование". Тезисы докладов. Ростов-на-Дону, 2008, 130.

81. Чегодаев А.В. Оценки скорости сходимости для однородны х марковских цепей с поглощением в нуле. Материалы ежегодных смотров-сессий аспирантов и молодых ученых по отраслям наук. Естественные и физико-математичемкие науки,Вологда. 2007, 148-151.

82. Зейфман А.И., Сатин Я.А., Чегодаев А.В. О нестационарных системах обслуживания с катастрофами. Информатика и ее применения, 2009, 3, №1, 47-54.

83. Zeifman A., Chegodaev A. The bounds on the rate of convergence for absorbing continuous-time Markov chains. Finite state space. Trans, of Int. Seminar of Stability Problems for Stochastic Models, Nahariya, Israel, 2007, 201-207.

84. Zeifman A., Chegodaev A., Shilova G. Almost absorbing continuous-time Markov chains on finite state space. Trans, of Int. Conference "Modelling of business, industrial and transport systems", Riga, 2008, 213-217.

85. Zeifman A., Chegodaev A. On the bounds of solutions for some linear systems. International Conference "Geometry in Odessa 2008", Abstracts, Odessa, 2008, 204-205.

86. Zeifman A., Chegodaev A. Some bounds for almost absorbing Markov chains. XIII International Summer Conference on Probability and Statistics, Abstracts, Sozopol, Bulgaria, 2008, 38.

87. Zeifman A., Satin Ya., Chegodaev A., Shilova G. Some bounds for the system of differential equations for M(t)/M(t)/N queue with catastrophes. International Conference "Geometry in Astrakhan 2008 Abstracts, Astrakhan, 2008, 84-86.

88. A. Zeifman, Ya. Satin, A. Chegodaev, V. Bening, V. Shorgin. Some Bounds for M(t)/M(t)/S Queue with Catastrophes. The 3rd International Workshop on Tools for solving Structured Markov Chains, Athens, Greece, 2008.

89. Zeifman A., Satin Ya., Chegodaev A. Some bounds for almost absorbing birth and death piocesses with catastrophes Pliska Studia Mathematica Bulgarica, 19(2009), 293-306.