Марковские случайные процессы
СОДЕРЖАНИЕ
Введение…………………………………………………………………………3
1 Основные понятия теории массового обслуживания……..............4
2 Одноканальная СМО с отказами………………………………..….6
3 Многоканальная СМО с отказами……………………………..….10
4 Одноканальная СМО с ожиданием………………………...…..15
5 Одноканальная СМО с ограниченной очередью…………...……19
6 Многоканальная СМО с неограниченной очередью…………….22
7 Многоканальная СМО с ограниченной очередью…………...…..28
8. Многоканальная с ожиданием………………………….…..
Заключение………………………………………………………….………....33
Задачи для самостоятельного решения
ВВЕДЕНИЕ
Сложный характер рыночной экономики и современный уровень предъявляемых к ней требований стимулируют использование более серьезных методов анализа ее теоретических и практических проблем. В последние десятилетия значительный вес в экономических исследованиях приобрели математические методы. Математическое моделирование все более и более становится одним из основных и наиболее плодотворных методов изучения экономических процессов и объектов. Математический анализ экономических задач органично превращается в часть экономики. Положительная оценка этого подтверждается и тем, что начиная с 1969 г. Нобелевские премии в области экономики присуждаются, как правило, за экономико-математические исследования.
|
|
|
Одним из важных разделов экономико-математического моделирования является теория массового обслуживания, представляющая собой теоретические основы комплекса вопросов эффективности конструирования и эксплуатации систем массового обслуживания. Системы массового обслуживания встречаются во многих областях экономики (производство, техника, военная область, быт и др.) и предназначены для многократного использования при выполнении однотипных задач.
Основоположником теории массового обслуживания считается известный датский ученый А.К. Эрланг. Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909 г. работу "Теория вероятностей и телефонные переговоры", в которой решил ряд задач по теории систем массового обслуживания с отказами.
Значительный вклад в создание и разработку общей теории массового обслуживания внес выдающийся советский математик А.Я. Хинчин. Его первые труды в этой области стали появляться с 1930 г., когда ему, как члену Совета депутатов, была поручена работа в отделе связи. Благодаря результатам А.Я. Хинчина значительно сократилось время проводившейся тогда автоматизации московской городской телефонной сети, существенно снизились стоимости работ и было введено много технических усовершенствований. Последующие работы А.Я. Хинчина в этой области были изданы после его смерти, в 1963 г., в виде монографии. Сам термин теория массового обслуживания предложен А.Я. Хинчиным. В зарубежной литературе чаще используется название теория очередей.
|
|
|
Предлагаемое учебное пособие посвящено изложению основ теории массового обслуживания и ее применению в моделировании систем массового обслуживания различных областей экономики. При этом рассматриваются простейшие системы, в которых протекает марковский случайный процесс "гибели и размножения".
Основные понятия теории массового обслуживания
Многие экономические задачи связаны с системами массового обслуживания (СМО), т. е. такими системами, в которых, с одной стороны, возникают массовые запросы (требования) на выполнение каких-либо услуг, с другой — происходит удовлетворение этих запросов. СМО включает в себя следующие элементы: источник требований, входящий поток требований, очередь, обслуживающие устройства (каналы обслуживания), выходящий поток требований. Исследованием таких систем занимается теория массового обслуживания.
|
|
|
Методами теории массового обслуживания могут быть решены многие задачи исследования процессов, происходящих в экономике. Так, в организации торговли эти методы позволяют определить оптимальное количество торговых точек данного профиля, численность продавцов, частоту завоза товаров и другие параметры. Другим характерным примером систем массового обслуживания могут служить склады или базы снабженческо-сбытовых организаций, и задача теории массового обслуживания в данном случае сводится к тому, чтобы установить оптимальное соотношение между числом поступающих на базу требований на обслуживание и числом обслуживающих устройств, при котором суммарные расходы на обслуживание и убытки от простоя транспорта были бы минимальными. Теория массового обслуживания может найти применение и при расчете площади складских помещений, при этом складская площадь рассматривается как обслуживающее устройство, а прибытие транспортных средств под выгрузку — как требование. Модели теории массового обслуживания применяются также при решении ряда задач организации и нормирования труда, других социально-экономических проблем.
Системой массового обслуживания (СМО)называется комплекс взаимосвязанных элементов, состоящий из некоторого числа обслуживающих единиц (каналов), в котором происходит удовлетворение массовых запросов (требований), поступающих в систему в случайные моменты времени. Обслуживание каждой заявки длится в течение некоторого случайного времени и зависит от показателей эффективности системы. После того, как заявка обслужена, она покидает канал, и система готова к приему очередной заявки. Примеры СМО - телефонная станция, автостоянка, кассир магазина, служба занятости.
|
|
|
Основные элементы СМО - источник требований, входящий поток заявок, каналы обслуживания, выходящий поток заявок.
Предметом теории СМО является построение математических моделей (т. е. образов реального экономического объекта, описанных с помощью уравнений, формул, графиков, схем и т. д.) для теоретического анализа и практического использования свойств СМО.
Показатели эффективности СМО - характеристики работы системы, описывающие ее способность справляться с потоком заявок. Эффективность функционирования СМО описывается такими показателями:
1) Эффективность использования СМО - абсолютная или относительная пропускные способности системы, среднее число занятых каналов (коэффициент использования СМО), средняя продолжительность использования СМО, интенсивность нагрузки канала;
2) Качество обслуживания заявок - среднее число заявок, обслуженных СМО в единицу времени, вероятность простоя системы, вероятность отказа в обслуживании, среднёе число заявок в очереди, среднее число заявок в системе и др.
 |
Рисунок 1- Схема СМО
Поток заявок, поступающих в систему, характеризуется интенсивностью λ, то есть частотой появления заявок в системе, или средним числом заявок, поступающих в систему в единицу времени.
Интенсивность μ потока обслуживаний,- это величина, обратная среднему времени обслуживания, или число заявок, обслуженных системой в единицу времени.
(1)
Интенсивность нагрузки канала обслуживания ρ, - это величина, показывающая среднее число заявок, поступающее в систему за среднее время обслуживания одной заявки:
(2)
При этом его экономический смысл заключается в том, что показатель ρ, - это среднее число каналов, которое необходимо иметь, чтобы обслуживать в единицу времени все поступающие в систему требования. Условие
, (3)
где п - число каналов обслуживания, означает, что необходимое число каналов обслуживания должно быть больше ρ.
Классификация СМО:
По дисциплине обслуживания:
- СМО с отказами, когда заявка, поступившая в систему в момент, когда все каналы заняты, остается необслуженной;
- СМО с ожиданием (очередью), в которых заявка в случае занятости всех каналов становится в очередь и ожидает обслуживания;
- Системы с ограничением длины очереди;
- Системы с ограниченным временем ожидания;
По месту нахождения источника требований:
- Замкнутые СМО, когда источник требований находится в самой системе;
- Открытые СМО, когда источник требований находится вне системы;
По числу обслуживающих каналов:
- Одноканальные;
- Многоканальные.
Возможны и другие признаки классификации.
Задача 1.1. Известно, что заявки на ремонт аппаратуры в телевизионном ателье поступают с интенсивностью 9 заявок в час, а средняя продолжительность ремонта – 45 минут. Определить показатели эффективности работы СМО (телеателье): интенсивность потока обслуживания, показатель нагрузки канала обслуживания. Определить необходимое количество мастеров телеателье.
Решение. Согласно принятым обозначениям, 
.
При этом для определения интенсивности потока обслуживаний необходимо единицу времени разделить на среднее время обслуживания (в данном случае единица времени – час). Найдем показатель нагрузки работы одного мастера: 
. Значит, для успешной работы системы необходима работа семи мастеров телеателье.
Задача 1.2. В порту имеется один причал для разгрузки судов. В среднем суда в порт поступают каждые 1,5 суток. Среднее время разгрузки судна составляет 40 часов. Справляется ли причал с разгрузкой?
Решение. Определим показатели интенсивности потока обслуживания, потока требований, нагрузки причала. Аналогично рассуждениям, приведенным в предыдущем примере, 
.
Это означает, что причал перегружен.
Вопросы для закрепления:
1. Что называется математической моделью экономического процесса?
2. Что называется системой массового обслуживания?
3. Приведите примеры СМО.
4. Опишите основные элементы СМО.
5. Перечислите основные признаки классификации СМО.
6. Классифицируйте следующие СМО: парикмахерская, автозаправочная станция, небольшой магазин с одним кассиром, супермаркет, склад оптовой продажи, рабочий-наладчик оборудования, зубной врач, сберкасса, телефон-автомат, интернет-магазин, санаторий, автомобиль такси;
7. Перечислите основные показатели эффективности обслуживания требований.
8. Какие экономические параметры работы СМО называются показателями эффективности использования системы?
Марковские случайные процессы
Пусть рассматривается система 
, имеющая 
возможных состояний: 
. Будем считать, что в любой момент времени система может находиться только в одном состоянии, а переход системы из состояния в состояние происходит мгновенно, скачком.
Случайным процессом называется процесс изменения во времени состояния какой-либо системы в соответствии с вероятностными закономерностями. Каждая смена состояния называется шагом процесса.
Процесс называется процессом с дискретными состояниями, если его возможных состояний конечное число, или их можно пронумеровать: ,… Процесс называется процессом с непрерывным временем, если смена состояний системы происходит в случайные, не фиксированные заранее моменты времени.
Если при наблюдении за процессом при каждом 
-м шаге фиксировать номер состояния 
, то последовательность номеров состояний системы 
, 
описывает эволюцию этой системы. Такая последовательность называется цепью Маркова, если процесс является случайным процессом без последействия, или марковским. Это значит, что вероятность попасть в момент времени 
в состояние 
зависит только от предыдущего состояния, в котором находилась система в момент 
.
Вероятности 
того, что из предыдущего состояния 
система перейдет в состояние , называются вероятностями перехода за один шаг. Удобно записывать вероятности перехода в виде матрицы, которая называется матрицей вероятностей перехода цепи Маркова за один шаг.
Она обладает следующими свойствами:
1. 
;
2. для всех 
.
Вектор-строка 
, где 
- вероятность того, что начальным состоянием системы является состояние 
, называется вектором начальных вероятностей. Зная вектор начальных вероятностей и матрицу вероятностей перехода, можно определить вероятность возникновения любого состояния системы при каждом шаге процесса.
Матрица 
называется матрицей вероятностей перехода цепи Маркова за п шагов. При этом выполняется соотношение 
.
Если из состояния 
система может перейти в состояние 
с положительной вероятностью за конечное число шагов, то состояние 
называется достижимым из состояния .
Состояние 
называется существенным, если для каждого состояния 
, достижимого из , также достижимо из 
. Если же найдется хотя бы одно состояние 
, достижимое из 
, из которого не достижимо , то состояние 
называется несущественным.
Состояние 
называется поглощающим, если при переходе системы в это состояние она остается только в этом состоянии и не может перейти ни в какое другое состояние.
При анализе процессов с дискретными состояниями удобно вместо матрицы 
пользоваться схемой, графом состояний, вершинами которого являются состояния цепи, а стрелками показаны возможные переходы из состояния в состояние.
Задача 2.1. Построить граф состояний, соответствующий матрице вероятностей перехода за один шаг:
.
 |
Решение. Система имеет три возможных состояния:
. Изобразим вершины графа:
Рис.2
При этом состояния 
- несущественные, состояние 
- поглощающее.
· Рассмотрим марковскую цепь с двумя состояниями 
и матрицей вероятностей перехода 
. Требуется:
1. Зная вектор начальных вероятностей (1\2;1\2), найти вероятность того, что после первого шага этот процесс перейдет в состояние 
;
2. Решить ту же задачу для начального вектора (1\3;2\3).
Решение. Искомое событие состоит из двух несовместных сложных событий:
А – начальное состояние системы - 
, после первого шага система останется в этом состоянии;
В - начальное состояние системы - 
, после первого шага система перейдет в состояние 
.
Тогда по формуле вероятности суммы событий 
:
1. 
;
2. 
.
Ì Матрица вероятностей перехода имеет вид:
.
Распределение по состояниям в момент времени 
определяется вектором 
=(0,7;0,2;0,1). Найти:
1. Распределение по состояниям в момент 
;
2. Вероятность того, что цепь Маркова за четыре шага будет иметь вид (1,3,3,2).
Решение.
1. Для ответа достаточно найти произведение матриц: 
= 
=
= 
2. По формуле вероятности произведения независимых событий искомая вероятность равна: 0,7×0,4×0,3×0,4=0,0336.
¹ Построить граф состояний следующего случайного процесса: телефон-автомат может быть либо занятым, либо свободным, либо неисправным.
 |
Решение. Система имеет три состояния, причем сразу после ремонта аппарат переходит в состояние «свободен». Изобразим три вершины графа, соответствующие состояниям:
Рис. 3
- аппарат занят;
- аппарат свободен;
- аппарат неисправен.
Стрелками показаны возможные смены состояний. Состояния 
и 
- несущественные.
s
1. Что называется случайным процессом?
2. Что называется шагом процесса?
3. Какой процесс называется марковским?
4. Что такое «цепь Маркова»?
5. Как составить матрицу вероятностей перехода цепи Маркова за один шаг? За n шагов?
6. Как, зная вектор начальных вероятностей и матрицу вероятностей перехода, определить вероятность возникновения любого состояния системы при каждом шаге процесса?
7. Какими свойствами обладает матрица вероятностей перехода цепи Маркова?
8. Как составить граф состояний системы?
9. Какое состояние системы называется достижимым из некоторого состояния?
10. Какое состояние системы называется несущественным? Поглощающим?
Одноканальная СМО с отказами
Рассмотрим упорядоченное множество состояний некоторой системы S : S 0 , S 1 , S 2 ,…, Sk ,…; предположим, что все потоки, переводящие систему из состояния в состояние, - простейшие.
Пусть для любого состояния Sk переходы возможны только в соседние состояния: либо в Sk -1,либо в Sk +1.Граф состояний такой системы изображен на рисунке 2:
Рисунок 2-Граф состояний одноканальной СМО с отказами.
Случайные процессы, происходящие в таких системах, имеют специальное название, традиционно происходящее из биологии: схема гибели и размножения (состояние Sk соответствует некоторой популяции численностью k , смена состояния происходит при рождении либо гибели одного члена популяции).
Рассмотрим систему с одним каналом обслуживания, в которую поступает простейший поток заявок с интенсивностью λ. Если в момент поступления очередной заявки канал занят, то заявка покидает систему необслуженной. Такие системы называются системами без ожидания, или с отказами в обслуживании.
Пусть поток обслуживаний имеет интенсивность μ. Граф состояний такой системы показан на рисунке номер 3:
Рисунок 3- Система без ожидания.
Система имеет два состояния:
S 0 – канал свободен и готов к приему очередной заявки;
S 1 – канал занят.
Эти величины можно интерпретировать как вероятности того, что заявка будет обслужена либо получит отказ:
(3)
Относительная пропускная способность системы, то есть доля всех обслуженных заявок из числа всех поступивших в систему, равна вероятности обслуживания:
(4)
Абсолютная пропускная способность системы, то есть число обслуженных заявок в единицу времени, - это произведение интенсивности потока заявок на долю всех обслуженных заявок:
(5)
Интенсивность μ потока обслуживаний П0б есть производительность канала. Имеет место равенство
, (6)
где Тоб - среднее время обслуживания одной заявки, относящееся только к обслуженным заявкам, т.е. математическое ожидание М [Т0б] случайной величины Т0б.
Стационарность потока означает, что его вероятностные характеристики не зависят от времени.
Дата добавления: 2018-10-26; просмотров: 438; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!