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

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

004614128

Горбатенко Анна Евгеньевна

.-'.У

■' и

ИССЛЕДОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С КОРРЕЛИРОВАННЫМИ ПОТОКАМИ В СПЕЦИАЛЬНЫХ ПРЕДЕЛЬНЫХ УСЛОВИЯХ

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

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

2 5 НОЯ 2010

Томск-2010

004614128

Работа выполнена на кафедре теории вероятностей и математической статистики факультета прикладной математики и кибернетики ГОУ ВПО «Томский государственный университет»

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

профессор Назаров Анатолий Андреевич

Официальные оппоненты: доктор физико-математических наук,

доцент Рожкова Светлана Владимировна

кандидат физико-математических наук, доцент Колесникова Светлана Ивановна

Ведущая организация: Сибирский федеральный университет,

г. Красноярск

Защита состоится 2 декабря 2010 г. в 12:30 на заседании диссертационного совета Д 212.267.08 при ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 36, корп. 2, ауд. 102. гиМ *

Отзывы на автореферат (в двух экземплярах), заверенные гербовой печатью организации, просим направлять по адресу: 634050, г. Томск, пр. Ленина, 36, ученому секретарю ТГУ Буровой Н.Ю.

С диссертацией можно ознакомиться в Научной библиотеке ГОУ ВПО «Томский государственный университет» по адресу г. Томск, пр. Ленина, 34а.

Автореферат разослан 27 октября 2010 г.

Ученый секретарь

диссертационного совета Д 212.267.08, доктор технических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В 1924 г. Д. Юл опубликовал работу, в которой определил понятие процесса чистого размножения, а в 30-х годах В. Феллер ввел понятие процесса размножения и гибели. Одновременно были опубликованы фундаментальные работы по теории массового обслуживания А.Н. Колмогоровым, А.Я. Хинчи-ным и Ф. Поллачеком.

Основные работы в СССР по теории массового обслуживания с 60-х годов принадлежат школам Б.В. Гнеденко, A.A. Боровкова.

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

Одним из новых направлений исследований стало изучение процессов обслуживания в системах, входящие потоки которых отличны от классических потоков (пуассоновскш и рекуррентный потоки). В книге Б.В. Гнеденко, И.Н. Коваленко, изданной в 2007 г., потоки этого класса названы специальными потоками однородных событий. В монографии А.Н. Дудина и В.И. Клименок специальные потоки названы коррелированными.

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

Потоки Кокса являются основой класса специальных или коррелированных потоков, наиболее популярным из которых является МАР-поток (Markovian Arrival Process). Впервые понятие МАР-потока было введено М. Ньютсом в 1979 г., а затем уточнено Д. Лукантони. Описание этого потока од-

нородных событий можно найти в работах Б.В. Гнеденко, И.Н. Коваленко, А.Н. Дудина, А.А. Назарова. Данный поток широко применим при исследовании СМ О.

В терминах различных математических школ МАР-потоки также называются дважды стохастическими потоками, которые были введены в 1964 г. Д. Кингменом. В таких потоках, во-первых, интервалы времени между наступлениями событий являются случайными, во-вторых, с течением времени интенсивность потока меняется случайным образом. Частными случаями дважды стохастических потоков являются альтернирующие, синхронные и полусинхронные потоки, рассматриваемые A.M. Торцевым и его учениками с целью оценки параметров этих потоков.

Наиболее общим ординарным потоком однородных событий является полумарковский или SM-поток (Semi-Markovian process). Идея введения такого потока была выдвинута Э. Леви (1954 г.) и В. Смитом (1955 г.). Системы массового обслуживания с таким входящим потоком интенсивно изучаются в настоящее время.

Исследователи, занимающиеся потоками, также занимались изучением СМО с неограниченным числом приборов, на вход которых поступают специальные потоки, применяя главным образом методы численного анализа. В работах Д. Баума, Л. Броера, были рассмотрены СМО BMAP|GI|oo, COX|GI|oo, получено асимптотическое распределение числа занятых приборов в условии растущего времени обслуживания.

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

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

В рамках указанной цели были поставлены следующие задачи:

1. Определение специальных предельных условий и классификация этих условий.

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

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

Научная новизна результатов, выносимых на защиту, состоят в следующем:

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения работы и отдельные ее результаты докладывались и обсуждались на следующих научных конференциях:

1. IV Всероссийская научно-практическая конференция «Научное творчество молодежи», г. Анжеро-Судженск, 2007г.

2. VII Всероссийская конференция по финансово-актуарной математике и смежным вопросам, г. Красноярск, 2008г.

3. XII Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2008г.

4. Международная научная конференция «Теория вероятностей и, случайные процессы, математическая статистика и приложения», г. Минск, 2008г.

5. Международная научная конференция «Математические методы повышения эффективности функционирования телекоммуникационных сетей». Минск, 2007г.

6. VII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2008г.

7. Международная научная конференция "Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей". Минск, 2009г.

8. VIII Международная конференция по финансово-актуарной математике и смежным вопросам. Красноярск, 2009г.

9. XIII Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2009г.

10. VIII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2009г.

11. Международная конференция, посвященной 75-летию профессора, доктора физико-математических наук Г.А. Медведева. Минск, 2010г.

12. XTV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2010г.

13. The third international Conference «Problems of Cybernetics and Informatics» (PCI'2010). Baku, 2010.

14. International conference «Modern Stochastics: Theory and Applications II», Kiev, 2010.

Работа выполнена при поддержке АВЦП «Развитие научного потенциала высшей школы (2009-2010 гг.)» Федерального агентства по образованию по проекту «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи».

Публикации. По результатам выполненных исследований автором опубликовано 17 печатных работ, в том числе 5 статей, из них 3 в изданиях, рекомендованных списком ВАК.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 105 наименований. Общий объем работы составляет 156 страницу, в том числе основной текст 145 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 определяются специальные предельные условия для рассматриваемых коррелированных потоков (MAP, SM) и проводится исследования рассматриваемых потоков с помощью метода асимптотического анализа в специальных предельных условиях.

Случайный процесс n{t) для рассматриваемых коррелированных потоков не является марковским, поэтому с помощью метода дополнительной переменной в разделе 1.1 выполнена их марковизация, а в разделе 1.2 получены системы дифференциальных уравнений Колмогорова для характеристических функций, определяющих функционирование этих потоков.

Для МАР-потока была введена дополнительная переменная k(t). Для марковского процесса {&(?),«(/)} определены характеристические функции

H{k>U,t)^eJWP(k,n,t)

тй

и получена задача Коши

.Я(и,0) = Я, для векторной характеристической функции

H{u,t) = {H(\,u,t),H(2,u,t),...}.

Здесь Q - матрица инфинитезимальных характеристик, управляющей цепи Маркова Щ), а матрица В = A+D*Q, А - диагональная матрица условных ин-тенсивностей МАР-потока, D - матрица вероятностей наступления событий МАР-потока в момент изменения состояния управляющей цепи Маркова, R -вектор стационарного распределения вероятностей цепи Маркова Щ).

Для SM-потока были введены дополнительные переменные s{t), z{t). Для этого марковского процесса {j(f),n(r),z(f)} определены характеристические функции

#(w>/) = fynP(w,r),

л=0

и получена задача Коши

8H(u,z,t) = dH(u,z,t) ЙЕГ («ДО у }

at & dz I w >' (2)

tf(u,z,0) = J?(z), для векторной характеристической функции

Л (a,z,0 = {Я(.'.11,г,0,Я(2,н,г,0,...} •

Здесь / - единичная матрица, a i?(z) - вектор стационарного распределения двумерного марковского процесса {j(/),z(/)} , A(z) - полумарковская матрица.

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

1. В условии предельно редких изменений состояний потока. Условие предельно редких изменений состояний МАР-потока:

tfMfe. 5-»0,

определяющие достаточно малые значения инфинитезимальных характеристик. Здесь Qtv> матрица инфинитезимальных характеристик управляющей МАР-потоком цепи Маркова k(t)

Условие предельно редких изменений состояний полумарковского потока формализуется следующим равенством для матрицы Р(8) вероятностей переходов его вложенной цепи Маркова

P(8) = I + b-Q.

2. В условии растущих условных интенсивностей потока. Условием растущих условных интенсивностей МАР-потока:

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

3. В условии квазиразложимости.

Цепь Маркова k(t) с непрерывным временем t будем называть квазиразложимой, если выполняется следующее условие:

0м = 6 +eg04,5-»0, где 5 - некоторый малый положительный параметр (8 0).

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

P{d) = P+5-Q,

где 5 - некоторый малый положительный параметр (5—>0). Здесь Р - блочно-диагональная матрица, блоки которой являются стохастическими матрицами, а свойства матрицы Q совпадают со свойствами матрицы инфинитезимальных характеристик.

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

Теорема 1.1 .Длярешения Р(к,и,[,Ь) задачи (1) существует предел

= (3)

6—>0

в котором функция имеет вид

^(А:,м,/) = Л(А:)ехр[(еу'' -1)^}- (4)

Следствие. Асимптотическое распределение вероятностей Р^п,^ числа п(1) событий потока в условии предельно редких изменений состояний МАР-потока, наступивших за время I, является взвешенной суммой пуассоновских распределений с параметрами Хк1 и с весами И(к), то есть имеет вид

(5)

Аппроксимацию первого порядка можно существенно уточнить, рассматривая асимптотики более высокого порядка, полагая

+ (6)

т=I

где

= (7)

-я

Теорема 1.2. Функции ^ (&, и, Г) определяются рекуррентной последовательностью

0 »

В разделе 1.5 рассматривается МАР-потока в условии растущих условных интенсивностей. Исследование МАР-потока в данных условиях сводится к исследованию МАР-потока в условии предельно редких изменений состояний, которое было выполнено в разделе 1.4.

В разделе 1.6 и 1.8 были исследованы МАР-поток и БМ-потоке методом асимптотического анализа в условии квазиразложимости, позволивший существенно понизить размерность решаемых задач, исследование которых выполнено методом асимптотического анализа в условии растущего времени наблюдения. Найдено асимптотическое распределение вероятностей ^(М) числа н(г) событий, наступивших в квазиразложимом потоке.

Асимптотическое распределение вероятностей числа событий, наступивших в квазиразложимом МАР-потоке за время < является взвешенной суммой дискретных аналогов гауссовских распределений и имеет вид

где

ат ~г{т]В{т)Ет, а1=ат + 2/МВ™Ет, В™ =Л(и) + Вектор-строка /2(я) является решением системы

/2(а)в„т+г(т)(в(т)-ат1(т)) = 0, которое удовлетворяет условию

Л(а%=о-

Константы ст определяются системой

' м

ш=1 М

1т=1

Асимптотическое распределение вероятностей числа событий, наступивших в квазиразложимом БМ-потоке за время г является взвешенной суммой дискретных аналогов гауссовских распределений и имеет вид

г с. л-1/ с . 2->\

где

а„ =

* >а1=ап+231ЖЕт

г{т)АЕ т м & т

(П)

Здесь вектор функция /¿т)(г) является таким решением уравнения которое удовлетворяет условию

Ля)ЫЕ„=о.

Константы ст определяются системой

м

т=\ И

,м=1

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

Теорема 1.3 Асимптотическое при 5—»0 распределение вероятностей Р1 (и,г) числа п событий, наступивших в БМ-потоке за время г в условии предельно редких изменений состояний потока, имеет следующий вид

и

где

а*=й->

о

г — это вектор стационарного распределения вероятностей вложенной цепи Маркова.

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

Случайный процесс /(/) для рассматриваемых СМО с коррелированными входящими потоками не является марковским. Поэтому с помощью метода дополнительной переменной в разделе 2.1 была выполнена их марковизация, аналогично марковизации для потоков, и получены системы дифференциальных уравнений Колмогорова для характеристических функций, определяющих функционирование этих систем.

Для векторной характеристической функции Н{и) системы с входящим МАР-потоком, при задании дополнительного условия, получена следующая задача

н(о)=к.

Для векторной характеристической функции Н(и,г) системы с входящим БМ -потоком, при задании дополнительного условия, получена следующая задача

Я(0,г) = Л(4

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

В разделах 2.2 и 2.3 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивностей найдено первое приближение асимптотического стационарного распределения вероятностей числа /(О занятых приборов в системе

МАР|М|°о, которое является взвешенной суммой пуассоновских распределений с весами Я(к). Поэтому рассматриваемое распределение может быть многомодальным.

(14)

К

р*=7'

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

В разделах 2.4 и 2.5 и 2.6 проведено исследование систем МАР(М[со с квазиразложимым МАР-потоком и систем 8М|М|со в условии предельно редких изменений состояний и условии квазиразложимости. В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условиях растущего времени обслуживания.

Асимптотическое стационарное распределение вероятностей /¡(г) для системы МАР|М|оо с квазиразложимым МАР-потоком имеет вид

В условии предельно редких изменений состояний входящего БМ-потока распределение вероятностей числа занятых приборов в системе 8М|М|оо имеет вид

' Г (»-«.Г 1 (гщх-а^:

(15)

ехр1

2а

(16)

где

а^а,8^

&

Здесь функция является таким решением уравнения

иг. от аг

которое удовлетворяет условию

/2(5,оо) = 0.

Для системы 8М|М|со с квазиразложимым БМ-потоком распределение вероятностей числа занятых приборов в системе имеет вид

и

т=1

ехр-(^)

Е««р

2о1

(17)

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

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

Случайный процесс /(*) для рассматриваемых СМО с коррелированными входящими потоками не является марковским. Применение метода дополнительной переменной не дает марковизацию процесса ¡'(¿), поэтому в данной главе был применен метод просеянного потока, основная идея которого заключается в том, что с вероятностью Бф поступившая заявка формирует событие просеянного потока, а с вероятностью 1 - не рассматривается.

В некоторый конечный момент времени число «(/) событий, наступивших в просеянном потоке равно числу занятых приборов в рассматриваемой системе массового обслуживания, то есть и(/|) = г'(^).

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

Для векторной характеристической функции #(и,г) просеянного потока системы МАР|С1|оо, при задании начального условия, получена следующая задача Коши

dt wv 1 >' (18) H{u,t0) = R, t0<t<tv

Для векторной характеристической функции H(u,z,t) просеянного потока системы SM GI|°o, при задании начального условия, получена следующая задача Коши

dt dz dz l w * ' w ul (19)

Jf(u,z,t0) = R(z).

В разделах 3.3 и 3.4 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивностей найдено первое приближение асимптотического распределения вероятностей числа /(/) занятых приборов в системе MAP|GI|co, которое является взвешенной суммой пуассоновских распределений с весами R{k).

(20)

к

где

О оо

р*=VÖ> b= ¡S(x)dx= j(l-B(x))dx.

-СО О

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

В разделе 3.5 3.7 и 3.8 проведено исследование системы МАР|01|оо в условии квазиразложимости, системы 8М|01|оо в условиях предельно редких изменений состояний потока и в условии квазиразложимости . В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условиях растущего времени обслуживания.

Для системы МАР|С1|со в условии квазиразложимости распределение вероятностей числа занятых приборов в системе имеет вид

лП ./„ Г /

т=\

(21)

Рт=«Л стт =Рт +2КтР, р= \8\х)сЬ, К и=/2(т)В(и)£т.

В условии предельно редких изменений состояний полумарковского потока найдено распределение вероятностей числа занятых приборов в системе 8М|(П|со.

4(0-11

1ехРи^1

(22)

В предельном условии квазиразложимости для систем 8М(С1|оо удается существенно понизить размерность решаемых задач. Найдено распределение вероятностей числа занятых приборов в системе

т=\

ехр<-

с-р.)

2ст„

(23)

В разделе 3.6 исследована система массового обслуживания МАРЩда. Продолжительность обслуживания заявок является детерминированной величиной, равной Ь. Доказана следующая теорема.

Теорема 3.1 Распределение вероятностей Р{т) числа занятых приборов в системе МАР\0\оо имеет следующий вид

г

2п

(д~(е*-1)В-сот(и)1)

т-Л И/(и)"(Йт(и)

Ес1и,

(24)

здесь сот(и) собственные числа матрицы (б-(е-'"

В разделе 3.9 исследована система массового обслуживания 8М|Б|оо. Доказана следующая теорема.

Теорема 3.2 Распределение вероятностей Р{С) числа занятых приборов в системе БЩИ|оо имеет следующий вид

(25)

р(0=5 ЙО-^Х1 - * (у))2 л-

где

о

величина а определяется равенством

1

а =-,

гАЕ

матрица А имеет вид

A=\(P-A{x))dx, о

а вектор г — это вектор стационарного распределения вероятностей вложенной цепи Маркова.

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

Для определения точности аппроксимации находится расстояние Колмогорова At.

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

Для оценки точности результатов, полученных с помощью имитационного моделирования, рассматривается система M|G|°o. Для данной системы распределение числа занятых приборов является пуассоновским с параметром р = X ■ b, где b - среднее время обслуживания заявки. Погрешность имитационной модели составляет менее 1%.

Ниже приведены примеры графиков распределений вероятностей числа событий, наступивших в MAP и SM-потоках, полученных методами асимптотического анализа, имитационного моделирования и реализаций численного алгоритма решения систем уравнений Колмогорова.

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

Рис.4.1 - Распределение вероятностей числа событий, наступивших в МАР-

потоке за время X = 5

Рис.4.2 - Распределение вероятностей числа событий, наступивших в БМ-

потоке за время 1 = 5

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

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

Таблица 4.1

Таблица 4.2

1 5 = ОД 5 = 0,05 6 = 0,01

Д0 I 0,0523 0,0360 0,0070

A, | 0,0422 0,0167 0,0086

Д2 | 0,0418 0,0164 0,0087

При уменьшении параметра 8 уменьшается отклонение результатов асимптотического анализа в специальных предельных условиях от результатов допредельного исследования коррелированных потоков и от результатов имитационного моделирования для СМО с неограниченным числом приборов и коррелированными входящими потоками. При 6 < 0,01 величины Ак составили менее 0,01. Это позволяет сделать вывод о том, что применение метода асимптотического анализа для коррелированных потоков дает достаточно точную аппроксимацию допредельного распределения.

В заключении диссертации приведены основные результаты.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В журналах перечня ВАК (редакция от 19 февраля 2010 года)

¡.Горбатенко А.Е. Асимптотический анализ системы ММР|М|1|ИПВ в условии предельно редких изменений состояний входящего потока / А.Е. Гор-батенко, A.A. Назаров // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2009. - Т. 315. - №5. -С. 187-190.

2. Горбатенко А.Е. Асимптотики произвольного порядка для системы MAP|GI|oo в условии растущей интенсивности входящего потока / А.Е. Горбатенко // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010 -№ 2 (11). - С. 35-43.

3. Горбатенко А.Е. Исследование полумарковского потока в условии предельно редких изменений его состояний / А.Е. Горбатенко, A.A. Назаров // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - 2010. - № 2 (28). - С. 8-11.

В других изданиях:

4. Горбатенко А.Е. Метод асимптотического анализа МАР-потока в условии предельно редких изменений состояний потока / А.Е. Горбатенко, A.A. Назаров II Современные информационные компьютерные технологии: сб. науч. ст. в 2 ч. (mcIT - 2008). - Гродно: ГрГУ, 2008. - Ч. 2. - С. 30-32.

5. Горбатенко А.Е. Исследование МАР-потока в условии растущей интенсивности / А.Е. Горбатенко, A.A. Назаров // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2008.-№3(4).-С. 66-70.

6. Горбатенко А.Е. Исследование системы ММР |м| оо в условиях предельно редких изменений состояния входящего потока / А.Е. Горбатенко // Материалы XI Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 20-21 апреля 2007 г. - Томск: Изд-во Том. ун-та, 2007. - Ч. 1. - С. 14-17.

7. Горбатенко А.Е., Назаров А.А. Исследование системы MAP|GI|<x> в условиях предельно редких изменений состояния входящего потока / А.Е. Горбатенко // Труды VII Всероссийской конференции по финансово-актуарной математике и смежным вопросам. Красноярск, 29 февраля - 4 марта 2008 г. -Красноярск: Сибирский федеральный ун-т, 2008. - Ч. 2. - С. 58-62.

8. Горбатенко А.Е. Метод асимптотического анализа ММР-потока в условии растущей интенсивности / А.Е. Горбатенко // Материалы ХП Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г. Анжеро-Судженске, 18-19 апреля 2008 г. - Томск: Изд-во Том. ун-та, 2008. - Ч. 1. - С. 14-17.

9. Горбатенко А.Е. Исследование системы MAP|GI|oo в условии растущей интенсивности входящего потока / А.Е. Горбатенко, А.А. Назаров // Теория вероятностей и, случайные процессы, математическая статистика и приложения. Сборник научных статей международной научной конференции. Минск, 15-19 сентября 2008 г. - Минск: Издательский центр БГУ, 2008. - С. 52-56.

10. Горбатенко А.Е. Нахождение асимптотик произвольного порядка для системы MAP|GI|oo в условии растущей интенсивности входящего потока / А.Е. Горбатенко // Информационные технологии и математическое моделирование (ЙТММ-2008): Материалы VII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 14-15 ноября 2008 г. - Томск: Изд-во Том. ун-та, 2008. - Ч. 2. - С. 10-15.

11. Горбатенко А.Е. Метод асимптотического анализа ММР-потока, управляемого квазиразложимой цепью Маркова, в условии растущего времени / А.Е. Горбатенко // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции "Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей". Минск, 26-29 января 2009 г. - Минск: РИВШ, 2009. - С. 85-89.

12. Горбатенко А.Е. Асимптотический анализ МАР-потока, управляемого квазиразложимой цепью Маркова // Труды VIII Международной конференции по финансово-актуарной математике и смежным вопросам. Красноярск, 24-26 апреля 2009 г. - Красноярск: Сибирский федеральный ун-т, 2009. - Ч. 2. -С. 26-28.

13. Горбатенко А.Е. Исследование системы ММР | М | оо в условии квазиразложимости цепи Маркова / А.Е. Горбатенко // Материалы XIII Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 14-15 мая 2009г. - Томск: Изд-во Том. унта, 2009.-Ч. 1.-С. 26-28.

14. Горбатенко А.Е. Асимптотический анализ системы MAP | M | оо в условии квазиразложимости цепи Маркова / А.Е. Горбатенко // Информационные технологии и математическое моделирование (ИТММ-2009): Материалы VIII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г.Анжеро-Судженске, 12-13 ноября 2009г. - Томск: Изд-во Том. ун-та, 2009. -4.1. - С. 16- 20.

15. Горбатенко А.Е. Исследование квазиразложимого полумарковского потока / А.Е. Горбатенко // Теория вероятностей математическая статистика и их приложения: сборник научных статей (материалы Международной конференции, посвященной 75-летию профессора, доктора физико-математических наук Г.А. Медведева). Минск, 22 - 25 февраля 2010г. - Минск: РИВШ, 2010. -С.53-59.

16. Горбатенко А.Е. Исследование системы SM|M|ao в условии предельно редких изменений состояний потока и условии растущего времени обслуживания / А.Е. Горбатенко, C.B. Лопухова // Материалы XTV Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г. Анжеро-Судженске, 15-16 апреля 2010г. - Томск: Изд-во Том. ун-та, 2010.-4.1.-C.I6-19.

17. Gorbatenko A. SM|M|oo in special limit conditions / A. Gorbatenko, S. Lopuchova // The third international conference «Problems of cybernetics and infor-matics»(PCI'2010), Baku, Azerbaijan. 6-8 September, 2010. - Baku: Elm, 2010. -V.2.-P.213-217.

Подписано к печати 20.10.2010. Формат 60x84/16. Бумага "Снегурочка". Печать XEROX. Усл.печ. л. 1.16Уч.-изд. л. 1.05

_Заказ 1720-10. Тираж 100 экз. _

Национальный исследовательский Томский политехнический университет Система менеджмента качества Томского политехнического университета сертифицирована NATIONAL QUALITY ASSURANCE по стандарту ISO 9001:2008

МЯЕЛСЛО^ТПГ 634050, г. Томск, пр. Ленина, 30

Тел./факс: 8(3822)5^35-35, www.tpu.ru

Введение.

Глава 1 Исследование коррелированных потоков в специальных предельных условиях.

1.1 Математические модели коррелированных потоков.

1.2 Уравнения Колмогорова для коррелированных потоков.

1.3 Специальные предельные условия для коррелированных потоков.

1.4 Исследование МАР-потока в условии предельно редких изменений состояний.

1.5 МАР-потоки в условии растущих условных интенсивностей.

1.6 Исследование квазиразложимого МАР-потока.

1.7 Исследование БМ-потока в условии предельно редких изменений состояний.

1.8 Исследование квазиразложимого 8М-потока.

Резюме.

Глава 2 Исследование марковских СМО с неограниченным числом приборов и коррелированными входящими потоками в специальных предельных условиях.

2.1 Уравнения Колмогорова для марковских СМО с неограниченным числом приборов и коррелированными входящими потоками.

2.2 Исследование систем МАР|М|оо в условии предельно редких изменений состояний входящего потока.

2.3 Системы МАР|М|оо в условии растущих условных интенсивностей входящего потока и конечной загрузки системы.

2.4 Исследование систем МАР|М|со с квазиразложимым входящим потоком.

2.5 Исследование систем 8М|М|оо в условии предельно редких изменений состояний входящего потока.

2.6 Исследование систем 8М|М|оо с квазиразложимым входящим потоком. 78 Резюме.

Глава 3 Исследование немарковских СМО с неограниченным числом приборов и коррелированными входящими потоками в специальных предельных условиях.

3.1 Метод просеянного потока.

3.2 Уравнения Колмогорова для немарковских СМО с неограниченным числом приборов и коррелированными входящими потоками.

3.3 Исследование систем МАР|С1|оо в условии предельно редких изменений состояний.

3.4 Системы МАР|С1|оо в условии растущих условных интенсивностей входящего потока и конечной загрузки системы.

3.5 Исследование систем МАР|ОЦсо с квазиразложимым входящим потоком.

3.6 Метод матричной экспоненты для исследования систем МАРр|оо.

3.7 Исследование систем 8М|СТ|оо в условии предельно редких изменений состояний входящего потока.

3.8 Исследование систем 8М|С1|оо с квазиразложимым входящим потоком.

3.9 Метод интегральных преобразований для исследования систем 8М|Б|оо 108 Резюме. НО

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

4.1 Имитационные модели СМО с неограниченным числом приборов и коррелированными входящими потоками.

4.2 Применение алгоритмов численного анализа к исследованию коррелированных потоков и СМО с детерминированным обслуживанием

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

Резюме.

Математические модели систем массового обслуживания широко применяются при исследовании процессов в. системах управления и организаций промышленными и сельскохозяйственными предприятиями, в сфере обслуживания (от предприятий общественного питания и бытового обслуживания до регулирования уровня воды в водохранилищах [69-70]); очистки воды [69]; в системах проектирования и анализа функционирования автоматизированных систем управления (АСУ) [69], в распределенных болыпемасштабных вычислительных системах, кластерных и Grid-системах, в системах противовоздушной обороны и средствах радиолокации, в различных экономических системах, системах телекоммуникации и т.п.

Первые работы по теории массового обслуживания связаны с именем датского ученого А.К. Эрланга (1878 - 1929) — сотрудника телефонной компании (до 1922). Его труды, опубликованные в 1908-1922 годах, в области проектирования и анализа функционирования телефонных станций вызвали большой интерес к математическим задачам по организации работы телефонных сетей.

Краткий исторический очерк развития теории массового обслуживания содержится, например, в работе [102].

В 1924 г Д. Юл (G. Jule). опубликовал работу, в которой определил понятие процесса чистого размножения, а в 30-х годах В. Феллер (W. Feller) ввел понятие процесса размножения и гибели. Одновременно были опубликованы фундаментальные работы по теории массового обслуживания А.Н. Колмогоровым, А .Я. Хинчиным [80] и Ф. Поллачеком (F. Pollaczek).

Основные работы в СССР по теории массового обслуживания с 60-х годов принадлежат школам Б.В. Гнеденко [26-28], A.A. Боровкова [7, 8].

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

Одним из новых направлений исследований стало изучение процессов обслуживания в системах, входящие потоки которых отличны от классических потоков (пуассоновский и рекуррентный потоки [25-28, 52, 53]). В книге [28] Б.В.Гнеденко, И.Н. Коваленко, изданной в 2007, потоки этого класса названы специальными потоками однородных событий. В монографии А.Н. Дудина и В.И. Клименок [46] специальные потоки названы коррелированными.

В 1955 году Д. Кокс [89] предложил рассматривать потоки, интенсивность которых зависит от состояний некоторого процесса, управляющего такими потоками. Эти потоки были названы процессами Кокса. Позже были даны общие определения таких потоков [28].

Потоки Кокса являются основой класса специальных или коррелированных потоков, наиболее популярным из которых является МАР-поток (Mark-ovian Arrival Process). Впервые понятие МАР-потока было введено Ньютсом в 1979 году [99], а затем во время нового всплеска исследований уточнено Jly-кантони [97, 98]. Описание этого потока однородных событий можно найти в работах Б.В. Гнеденко, И.Н. Коваленко [28], А.Н. Дудина [46], A.A. Назарова [64]. Данный поток широко применим при исследовании СМО. Так, например, в работах [9, 10, 12, 24, 25, 73, 81, 97-99] рассматриваются системы, в которых на входе - МАР-поток. Непосредственно исследованию самого МАР-потока посвящена работа [99].

В терминах различных математических школ МАР-потоки также называются дважды стохастическими потоками, которые были введены в 1964 году Кингменом [95]. В таких потоках, во-первых, интервалы времени между наступлениями событий являются случайными, во-вторых, с течением времени интенсивность потока меняется случайным образом. Частными случаями дважды стохастических потоков [29, 30, 46] являются альтернирующие [54], синхронные [18, 19] и полусинхронные потоки [32], рассматриваемые A.M. Торцевым и его учениками с целью оценки параметров этих потоков.

Наиболее общим ординарным потоком однородных событий является полумарковский или SM-поток (Semi-Markovian process) [58]. Идея введения такого потока была выдвинута Леви (1954) и Смитом (1955). В книге Д. Кокса, В. Смита [54] наряду с исследованием простого процесса восстановления (рекуррентного потока) представлен альтернирующий процесс восстановления, модель которого может быть обобщена на случай полумарковского потока или его частного случая — потока марковского восстановления (Markovian renewal process). Системы массового обслуживания с таким входящим потоком интенсивно изучаются в настоящее время [72,73, 93, 95, 97, 98, 101].

Исследователи, занимающиеся потоками, также занимались изучением СМО с неограниченным числом приборов, на вход которых поступают специальные потоки, применяя главным образом методы численного анализа. В работах Д. Баума [8], JL Броера [9], были рассмотрены СМО BMAP|GI|oo, COX|GI|oo^ получено асимптотическое распределение числа занятых приборов в условии растущего времени обслуживания.

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

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

В частности для МАР-потока, заданного матрицами

1 0 0 -0.8 0.2 0.6 " 0 0.7 0.5

Л = 0 4 0 0.2 -0.5 0.3 0.6 0 0.8

0 0 8 0.2 0.3 -0.5 0.2 0.3 0 при заданных значениях 8 = 0.01 и ¿ = 5 распределение вероятностей

Р(м)=Р{и(*) = л}, где ;;(/) - число событий, наступивших в МАР-потоке за время имеет вид, как на следующем рисунке.

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

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

В рамках указанной цели были поставлены следующие задачи: 1. Определение специальных предельных условий и классификация этих условий.

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

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

Научная новизна и результаты, выносимые на защиту, состоят в следующем:

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

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

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

4. Применив интегральный подход к исследованию систем массового обслуживания с неограниченным числом приборов с входящим МАР-потоком и детерминированным обслуживанием с использованием методов просеянного потока, матричной экспоненты и формулы Сильвестра [25, 59] найдено допредельное распределение вероятностей числа занятых приборов в системе.

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

Результаты, представленные в работе, имеют как теоретическое, так и практическое значение.

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

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

Публикации. По материалам диссертации опубликовано 16 работ, из них 3 статьи в журналах списка ВАК:

1. Горбатенко А.Е. Асимптотический анализ системы ММР|М1|ИПВ в условии предельно редких изменений состояний входящего потока / А.Е. Горбатенко, A.A. Назаров // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2009. - Т315. - №5. - С. 187-190.

2. Горбатенко А.Е. Асимптотики произвольного порядка для системы MAP|GI|oo в условии растущей интенсивности входящего потока // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. — № 2 (11). — С. 35-43.

3. Горбатенко А.Е. Исследование полумарковского потока в условии предельно редких изменений его состояний / А.Е. Горбатенко, A.A. Назаров // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - 2010. - № 2 (28). — С. 8-11.

4. Горбатенко А.Е. Исследование системы ММР | М | оо в условиях предельно редких изменений состояния входящего потока // Материалы XI Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 20-21 апреля 2007г. - Томск: Изд-во Том. ун-та, 2007. - Ч. 1. - С. 14-17. I

5. Горбатенко А.Е. Исследование системы MAP|GI|qo в условиях предельно редких изменений состояния входящего потока / А.Е. Горбатенко, А.А.Назаров // Труды VII Всероссийской конференции по финансово-актуарной математике и смежным вопросам. Красноярск, 29 февраля - 4 марта 2008 г. - Красноярск: Сибирский федеральный ун-т, 2008. -4.2. — С. 58-62.

6. Горбатенко А.Е. Исследование МАР-потока в условии растущей интенсивности / А.Е. Горбатенко, A.A. Назаров // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2008. - № 3 (4). - С. 66-70.

7. Горбатенко А.Е. Метод асимптотического анализа ММР-потока в условии растущей интенсивности // Материалы XII Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 18-19 апреля 2008 г. - Томск: Изд-во Том. ун-та, 2008. -Ч. 1.-С. 14-17.

8. Горбатенко А.Е. Исследование системы MAP|GI|oo в условии растущей интенсивности входящего потока / А.Е. Горбатенко, A.A. Назаров // Теория вероятностей и, случайные процессы, математическая статистика и приложения. Сборник научных статей международной научной конференции. Минск, 15-19 сентября 2008 г. - Минск: Издательский центр БГУ, 2008. - С. 52-56.

9. Горбатенко А.Е. Метод асимптотического анализа МАР-потока в условии предельно редких изменений состояний потока / А.Е. Горбатенко, A.A. Назаров // Современные информационные компьютерные технологии: сб. науч. ст. в 2 ч. (mcIT - 2008). - Гродно: ГрГУ, 2008. - Ч. 2. - С. 30-32.

10. Горбатенко А.Е. Нахождение асимптотик произвольного порядка для системы MAP|GI|oo в условии растущей интенсивности входящего потока // Информационные технологии и математическое моделирование (ИТММ-2008): Материалы VII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 14-15 ноября 2008 г. - Томск: Изд-во Том. ун-та, 2008. - Ч. 2. - С. 10-15.

11. Горбатенко А.Е. Метод асимптотического анализа ММР-потока, управляемого квазиразложимой цепью Маркова, в условии растущего времени // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции "Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей". Минск, 26-29 января 2009 г. - Минск: РИВШ, 2009. - С. 85-89.

12. Горбатенко А.Е. Асимптотический анализ МАР-потока, управляемого квазиразложимой цепью Маркова // Труды VIII Международной конференции по финансово-актуарной математике и смежным вопросам. Красноярск,

24-26 апреля 2009 г. - Красноярск: Сибирский федеральный ун-т, 2009. - Ч. 2.

- С. 26-28.

13.Горбатенко А.Е. Исследование системы ММР|м|оо в условии квазиразложимости цепи Маркова // Материалы XIII Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 14—15 мая 2009г. - Томск: Изд-во Том. ун-та, 2009. -Ч. 1.

- С. 26-28.

14. Горбатенко А.Е. Асимптотический анализ системы MAP | M | оо в условии квазиразложимости цепи Маркова // Информационные технологии и математическое моделирование (ИТММ-2009): Материалы VIII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г.Анжеро-Судженске, 12-13 ноября 2009г. - Томск: Изд-во Том. ун-та, 2009.-Ч. 1.-С. 16-20.

15. Горбатенко А.Е. Исследование квазиразложимого полумарковского потока // Теория вероятностей математическая статистика и их приложения: сборник научных статей (материалы Международной конференции, посвященной 75-летию профессора, доктора физико-математических наук Геннадия Алексеевича Медведева). Минск, 22-25 февраля 2010г. - Минск: РИВШ, 2010.

- С. 53-59.

16. Горбатенко А.Е. Исследование системы SM|M|oo в условии предельно редких изменений состояний потока и условии растущего времени обслуживания / А.Е. Горбатенко, C.B. Лопухова // Материалы XIV Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г. Анжеро-Судженске, 15-16 апреля 2010 г. - Томск: Изд-во Том. унта, 2010.-Ч. 1.- С. 16-19.

17. Gorbatenko A. SM|Mqo in special limit conditions / A. Gorbatenko, S. Lopuchova // The third international conference «Problems of cybernetics and in-formatics»(PCP2010), Baku, Azerbaijan. 6-8 September, 2010. - Baku: Elm, 2010. -V. 2. — P.213-217.

Апробация работы. Основные положения работы и отдельные ее результаты докладывались и обсуждались:

1. XI Всероссийская научно-практическая конференция «Научное творчество молодежи», г. Анжеро-Судженск, 2007 г.

2. VII Всероссийская конференция по финансово-актуарной математике и смежным вопросам, г. Красноярск, 2008 г.

3. XII Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2008 г.

4. Международная научная конференция «Теория вероятностей и, случайные процессы, математическая статистика и приложения», г. Минск, 2008 г.

5. Международная научная конференция «Математические методы повышения эффективности функционирования телекоммуникационных сетей». Минск, 2007 г.

6. VII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2008 г.

7. Международная научная конференция "Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей". Минск, 2009 г.

8. VIII Международная конференция по финансово-актуарной математике и смежным вопросам. Красноярск, 2009 г.

9. ХШ Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2009 г.

10.VIII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2009 г.

11 .Международная конференция, посвященной 75-летию профессора, доктора физико-математических наук Геннадия Алексеевича Медведева. Минск, 2010 г.

12.XIV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2010 г.

13.The third international Conference «Problems of Cybernetics and Informatics» (РСГ2010). Baku, 2010.

14. International conference «Modern Stochastics: Theory and Applications II», Kiev, 2010.

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

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

Основной целью исследования потоков является нахождение распределения вероятностей числа n(t) событий, наступивших в потоке за время L

Случайный процесс n(t) для рассматриваемых коррелированных потоков не является марковским, поэтому с помощью метода дополнительной переменной в разделе 1.1 выполнена их марковизация, а в разделе 1.2 получены системы дифференциальных уравнений Колмогорова для характеристических функций, определяющих функционирование этих потоков.

Для МАР-потока была введена дополнительная переменная k(t) и рассмотрен случайный процесс который является двумерной цепью

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

00

H(k,u,t) = Y,eJimP(k,n,t) п=0 и,0) = Д9 для векторной характеристической функции

Здесь <2 - матрица инфинитезимальных характеристик, управляющей цепи Маркова к{(), а матрица В = А+0*(), А - диагональная матрица условных ин-тенсивностей МАР-потока, £> - матрица вероятностей наступления событий МАР-потока в момент изменения состояния управляющей цепи Маркова, Я — вектор стационарного распределения вероятностей цепи Маркова Щ).

Для 8М-потока были введены дополнительные переменные .?(/), и рассмотрен случайный процесс который является трехмерным марковским процессом. Для этого марковского процесса определены характеристические функции со л=0 и для них составлена система дифференциальных уравнений Колмогорова, из которой при задании начальных условий получена задача Коши дН{и,г,{) дН(и,0,() дt дг дг

Н(и,г,0) = для векторной характеристической функции

Н(и,г,/) = {#(1, (2,г/,г,.

Здесь / - единичная матрица, а Я{г) - вектор стационарного распределения двумерного марковского процесса {.?(/),А(г) - полумарковская матрица.

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

1. В условии предельно редких изменений состояний потока Условие предельно редких изменений состояний МАР-потока:

8^, 5—>0, определяющее достаточно малые значения инфинитезимальных характеристик. Здесь матрица инфинитезимальных характеристик управляющей

МАР-потоком цепи Маркова к(/).

Условие предельно редких изменений состояний полумарковского потока формализуется следующим равенством для матрицы Р(Ь) вероятностей переходов его вложенной цепи Маркова

Р(5) = / + 8-С>.

2. В условии растущих условных интенсивностей потока Условие растущих условных интенсивностей МАР-потока: определяющее достаточно большие значения условных интенсивностей потока и существенные различия их значений.

3. В условии квазиразложимости.

Цепь Маркова к(1) с непрерывным временем I будем называть квазиразложимой, если выполняется следующее условие:

2(1) = <2+§2(0), 8->О, где 5 — некоторый малый положительный параметр (8 —> 0).

Цепь Маркова к{1) является квазиразложимой, если множество ее состояний можно разбить на Мквазизамкнутых классов к,(/), Ы\,М (переход из одного класса в другой осуществляется редко).

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

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

Р(8) = Р + 8-2, где 8 — некоторый малый положительный параметр (8 —0). Здесь Р — блочно-диагональная матрица, блоки которой являются стохастическими (марковскими) матрицами, а свойства матрицы совпадают со свойствами матрицы инфинитезимальных характеристик.

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

С помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивно-стей в разделах 1.4 и 1.5 найдено первое приближение асимптотического распределения вероятностей числа событий, наступивших в МАР-потока за время / в виде которое является, взвешенной суммой пуассоновских распределений с весами Я(к), поэтому рассматриваемое распределение может быть многомодальным. Также найдены асимптотики более высокого порядка, существенно повышающие точность аппроксимации допредельного распределения.

В разделе 1.6 был исследован МАР-поток методом асимптотического анализа в условии квазиразложимости, позволивший существенно понизить размерность решаемых задач, исследование которых выполнено методом асимптотического анализа в условии растущего времени наблюдения [60]. Найдено асимптотическое распределение вероятностей Рх{п,1) числа «(/) событий, наступивших в квазиразложимом МАР-потоке за время / в виде

1 2а„,< т 1 где параметры ат и а~ определяются равенствами а=г{т)В{т)Е, т т' здесь дО») + £)(">) * 0 тт ■ а вектор-строка /2(т) является решением матричного уравнения (системы линейных алгебраических уравнений) которое удовлетворяет условию

Лт)Ет = 0.

Константы ст определяются системой т=1

Л/

Найденное асимптотическое распределение вероятностей является взвешенной суммой дискретного аналога гауссовских распределений.

В разделе 1.7 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и преобразований Лапласа найдено асимптотическое распределение вероятностей числа и (г) событий, наступивших в 8М-потока за время которое имеет вид (М=1 - "Ш1 - «"*)£ V. (1 - о; {у)уу,

Z7t -О0 У 3 СО л Т 00

К -а, У « 4=1 где 1 »-> о а вектор г — это вектор стационарного распределения вероятностей вложенной цепи Маркова.

В разделе 1.8 был исследован БМ -поток методом асимптотического анализа в условии квазиразложимости, позволивший существенно понизить размерность решаемых задач, исследование которых выполнено методом асимптотического анализа в условии растущего времени наблюдения [60]. Найдено асимптотическое распределение вероятностей Рх{п^) числа и(7) событий, наступивших в квазиразложимом 8М-потоке за время t в виде м т=1 ехр

2а2/ т

Еехр у=0

2а2? т где 1 я« г{т)АЕ. су! = а + 2

5/^(0) т т дг

Е, т » здесь вектор функция /2("'} (г) является таким решением уравнения дй"!)(;), дЯ™ (0) дг + дг - / )" ^ « = о, которое удовлетворяет условию Константы ст определяются системой т=1 М

2>.= т=1

Найденное асимптотическое распределение вероятностей Р^и,/) является взвешенной суммой гауссовских распределений.

Во второй главе выполнено исследование марковских систем массового обслуживания с неограниченным числом обслуживающих приборов и с корре

- 19лированными входящими потоками (MAP, SM) в специальных предельных условиях (условие предельно редких изменений состояний потока, условие растущей интенсивности потока, условие квазираложимости управляющего потоком процесса).

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

Случайный процесс i{t) для рассматриваемых СМО с коррелированными входящими потоками не является марковским. Поэтому с помощью метода дополнительной переменной в разделе 2.1 была выполнена их марковизация и получены системы дифференциальных уравнений Колмогорова для характеристических функций, определяющих функционирование этих систем.

Для систем с входящим МАР-потоком была введена дополнительная переменная k(t) и рассмотрен случайный процесс [k(t)J(t)}, который является двумерной цепью Маркова. Для этого марковского процесса определена векторная характеристическая функция Н (г/) и для нее составлено дифференциально-матричное уравнение Колмогорова, из которого при задании дополнительного условия получена следующая задача я(о)=я.

Для систем с входящим SM-потоком были введены дополнительные переменные s(t), z(t) и рассмотрен трехмерный процесс , который является марковским процессом. Для этого марковского процесса определена векторная характеристическая функция H(u,z) и для нее составлено дифференциально-матричное уравнение Колмогорова, из которого при задании дополнительного условия получена следующая задача z v 'du dz L } z

H(0,z) = R(z).

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

В разделах 2.2 и 2.3 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивностей найдено первое приближение асимптотического стационарного распределения вероятностей числа i(t) занятых приборов в системе МАР|М|оо, которое является взвешенной суммой пуассоновских распределений с весами R(k). Поэтому рассматриваемое распределение может быть многомодальным. где Ч

Рк= — •

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

В разделе 2.4 проведено исследование системы МАР|М|оо с квазиразложимым МАР-потоком. В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условиях растущего времени обслуживания [66].

Асимптотическое стационарное распределение вероятностей /}(;) является взвешенной суммой дискретных аналоговых гауссовских распределений, то есть имеет вид м т=1 ехр

2сг

2>р v=0

2al где здесь вектор-строка /2(т) является решением матричного уравнения (системы линейных алгебраических уравнений)

В разделе 2.5 исследованы системы 8М|М|со в асимптотическом условии предельно редких изменений состояний полумарковского потока. С помощью метода асимптотического анализа в условиях растущего времени обслуживания, которое было предложено в работе [66], найдено распределение вероятностей числа занятых приборов в системе

КО=1л

Хехр т=О

2 а?

2П где а. = ■ а2 — а 5 о ' здесь функция является таким решением уравнения дг & дг которое удовлетворяет условию

В разделе 2.6 проведено исследование системы 8М|М|оо с квазиразложимым 8М-потоком. В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условии растущего времени обслуживания[66]. Найдено распределение вероятностей числа занятых приборов в системе м m=1 ехр

2а!

2>р v=0

2а?

21Л 2 а + 2 у > Е , и m т' а вектор функция /2(т) (z) является таким решением уравнения которое удовлетворяет условию

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

Основной целью исследования систем массового обслуживания является нахождение распределения вероятностей числа /(/) занятых приборов в системе. Случайный процесс i(t) для рассматриваемых СМО с коррелированными входящими потоками не является марковским. Применение метода дополнительной переменной не дает марковизацию процесса i(t), поэтому в данной главе был рассмотрен метод просеянного потока [66], основная идея которого заключается в том, что с вероятностью S(f) поступившая заявка формирует событие просеянного потока, а с вероятностью 1 - S(t) не рассматривается. Зависимость S от / определяется распределением времени обслуживания.

В некоторый конечный момент времени i\ число n(t) событий, наступивших в просеянном потоке равно числу занятых приборов в рассматриваемой системе массового обслуживания, то есть п(Н) = /(/1). Исследование таких систем массового обслуживания сводится к исследованию просеянного потока.

Для просеянного потока системы МАР|С1|оо введена дополнительная переменная к{{) и рассмотрен двумерный процесс который является нестационарной цепью Маркова. Для этого марковского процесса определена векторная характеристическая функция Н (и,/) и для нее составлено матричнодифференциальное уравнение Колмогорова, из которого при задании начального условия получена задача Коши

Для просеянного потока системы SM|GI|oo были введены дополнительные переменные s(t), z(t) и рассмотрен трехмерный процесс {s{t\n{t),z{i)^, который является марковским процессом. Для этого марковского процесса определена векторная характеристическая функция H(u,z,t) и для нее составлено матрично-дифференциальное уравнение Колмогорова, из которого при задании начального условия получена задача Коши

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

В разделах 3.3 и 3.4 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивностей найдено первое приближение асимптотического распределения вероятностей числа г(/) занятых приборов в системе МАР|01|оо, которое является взвешенной суммой пуассоновских распределений с весами Я(к). Поэтому рассматриваемое распределение может быть многомодальным:

H(u,t0) = R, t0<t<tx. dt с

H(u,z,t0) = R(z). где

Рк=К -ь,

О «3

6= |(1-Я (*))*&.

-00 О

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

В разделе 3.5 проведено исследование системы МАР|01|оо с квазиразложимым МАР-потоком. В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условиях растущего времени обслуживания [66]. Найдено распределение вероятностей числа занятых приборов в системе и т=\ ехр<

Р~р т)2

2а у=0 сг

Р т = атЪ, ст2и=рт+2ктР, ¡32(х)с1х, к т =

00

В разделе 3.6 исследована система массового обслуживания МАРр|оо с неограниченным числом приборов, на вход которой поступает МАР-поток заявок, а продолжительность обслуживания заявок является детерминированной величиной, равной Ь.

Исследование системы МАР|Б|оо выполнено методом матричной экспоненты. Найдено распределение вероятностей числа занятых приборов в системе МАРр|оо 2п} ыь Ц ю,(г/) —ш (г/)

Ес1и.

В разделах 3.7 и 3.8 исследованы системы 8М|С1|оо с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и в условии квазиразложимости с помощью метода асимптотического анализа в условиях растущего времени обслуживания [66].

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

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

В разделе 3.9 исследована система массового обслуживания 8М|Б|оо с неограниченным числом приборов, на вход которой поступает полумарковский поток заявок, а продолжительность обслуживания заявок является детерминированной величиной, равной Ъ.

Исследование системы 8М|Э|со проводилось с помощью преобразования Фурье-Стильтьеса. Найдено распределение вероятностей числа занятых приборов в системе $М|Б|оо. о

00

00 о величина а определяется равенством а - -, гАЕ матрица А имеет вид

00 о а вектор г - это вектор стационарного распределения вероятностей вложенной цепи Маркова.

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

Для определения точности аппроксимации находится расстояние Колмогорова Ак.

Для коррелированных потоков Ак определяется следующим образом

Ак = тах|^(л,/)-^(т7,/) , где - допредельная функция распределения числа событий наступивших в потоке за время /, полученная с помощью метода матричной экспоненты для МАР-потока и с помощью интегрального преобразования для 8М-потока, (/?,/) - аппроксимация допредельной функции распределения числа событий наступивших в потоке за время полученная с помощью метода асимптотического анализа в специальных предельных условиях .

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

Для оценки точности результатов, полученных с помощью имитационного моделирования рассматривается система МАР|С1|оо, на вход которой поступает МАР-поток с параметрами Хк = X и - 0. Также рассматривается систе-I ма 8М|01|оо, на вход которой поступает полумарковский поток, для которого условные функции распределения имеют вид О^ (х) = 1 - . Время обслуживания заявок является рекуррентным с функцией распределения В(х). В этих системах входящие потоки являются простейшими и распределение числа занятых приборов является пуассоновским (формула Эрланга) с параметром Где Ъ - среднее значение времени обслуживания заявки. Погрешность имитационной модели составляет менее 1%.

Для СМО с неограниченным числом приборов и коррелированными входящими потоками величина Ак определяется следующим образом где ^Р(г) - функция распределения числа занятых приборов в системе, полученная с помощью имитационного моделирования, ^ (/') — аппроксимация допредельной функции распределения числа занятых приборов в системе, полученная с помощью метода асимптотического анализа в специальных предельных условиях.

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

При 5 < 0,01 величины Ак составили менее 0,01. Это позволяет сделать вывод о том, что применение метода асимптотического анализа для коррелированных потоков дает достаточно точную аппроксимацию допредельного распределения.