Моделирование систем лекция. Моделирование систем. Литература по теме Тема Модели на основе метода статистических испытаний

• Название: Литература по теме Тема Модели на основе метода статистических испытаний
• Анкор: Моделирование систем лекция
• Дата: 17.08.2022
• Размер: 2.59 Mb.
• Имя файла: Моделирование систем.pdf
• Тип: Литература; #647642
• страница: 3 из 13

Тема 3. Модели стохастических систем
Цели изучения темы:
 понять понятие и особенности стохастических систем;
 познакомиться с пуассоновским потоком заявок, имеющим большое значения для моделирования широкого класса систем и процессов;
 познакомиться с основными аналитическими моделями систем массового обслуживания.
Успешно изучив тему, Вы:
получите представление о:
 как строятся математические модели систем массового обслуживания на примере системы с отказами;
 как применяются модели систем массового обслуживания;
 постановке и примерах задач проверки гипотез;
 критериях, применяемых при оценивании гипотез;
 подходах к сбору исходных данных и анализу результатов моделирования в системах потоками заявок;
будете знать:
 как характеризуется пропускная способность систем с отказами и как они рассчитываются;
 какие показатели характеризуют очередь в системе с ожиданием и как они рассчитываются;
 как применить модели к решению экономических и инженерных задач;
 как практически применить критерий проверки гипотезы к реальной задаче, возникающей при моделировании.
Задачи изучения темы:
 понять свойства потока, которые относят поток к пуассоновским;
 овладеть способом определения характеристик потока с помощью формулы Пуассона;
 научиться применять математический аппарат описания марковских процессов к построению моделей систем массового обслуживания;
 познакомиться с основными показателями, используемыми в моделях систем массового обслуживания.

35
Вопросы темы:
1. Стохастические системы. Модели стохастических систем.
2. Системы массового обслуживания.
3. Основные понятия теории вероятностей.
4. Параметры системы, способы оценивания, пример оценивания.
5. Простейший поток. Формула Пуассона.
Вопрос 1. Стохастические системы. Модели стохастических
систем.
В ряде систем, которые называются стохастическими (от греческого στοχαστική – умеющий угадывать), известных также как недетерминированные, или вероятностные, в силу действия недостаточно изученных или вовсе неизвестных случайных факторов предсказать поведение модели однозначно нельзя. Описание и исследование моделируемой системы может быть построено на использовании аппарата теории вероятностей и математической статистики, а также известных законов распределения случайных величин. К стохастическим моделям можно отнести модели систем массового обслуживания (парикмахерская, банк, билетная касса, справочное бюро и т.п.), где момент прихода очередного требования и продолжительность нахождения его в системе однозначно непредсказуемы.
Любое исследование системы методом моделирования основывается на использовании как количественных, так и качественных сведений относительно изучаемой системы. Одним из первых и наиболее важных этапов процесса моделирования является этап сбора исходных данных и приведение их к виду, наиболее полно соответствующему требованиям удобства их последующего использования в модели. Например, исследование систем массового обслуживания, о которых будет идти речь далее, начинается с изучения того, что необходимо обслуживать, иначе говоря, с изучения характеристик входящего потока заявок. В нетривиальных случаях требуется также обследование самой системы массового обслуживания с целью нахождения характеристик обслуживания (потока обслуживания).
Вопрос 2. Системы массового обслуживания.
Значительный интерес для практики представляют модели систем массового обслуживания(СМО), к которым сводятся множество задач анализа и проектирования информационных систем. Системы этого класса характеризуются наличием (рис. 7) потока запросов (заявок), поступающих на вход системы (входящим потоком), необязательной
очереди ждущих обслуживания заявок, обслуживающим прибором,
или каналом и потоком обслуженных заявок (выходящим потоком).

36
Рис. 7. Элементы СМО
Поток заявок (другие названия: запросы, вызовы, требования и т.д.), исходящий из источника заявок, поступает на вход СМО в случайные моменты времени для обслуживания. Этот входной поток может представлять собой вызовы от абонентов, передаваемые сообщения и т.д. Обслуживание поступившей заявки продолжается некоторое случайное время, после чего канал освобождается и готов к принятию следующей заявки. Случайный характер потока заявок приводит к тому, что в какие-то промежутки времени на входе СМО скапливается излишне большое число заявок (они либо образуют очередь, либо покидают СМО не обслуженными); в другие же периоды
СМО будет работать с недогрузкой или простаивать.
Для СМО в рамках теории массового обслуживания разработаны математические модели, которые широко применяются для количественного оценивания системных показателей. Многие модели основаны на уже рассмотренном ранее аппарате марковских процессов.
Проиллюстрируем применение теории на нескольких моделях СМО.
Вопрос 3. Основные понятия теории вероятностей.
Если событие А при некотором испытании может как произойти, так и не произойти, то такое событие называется случайным.
Случайному событию приписывается некоторое число между 0 и
1, называемое его вероятностью и обозначаемое через Р(А).
Вероятность того, что событие Ане произойдет, обозначается
Р(Ã):
Р(Ã)=1 – Р(А).

37
Если результаты опыта сводятся к схеме случая и общее число случаев (опытов) равно N, то вероятность события А выражается как:
( )
A
N
P A
N

,
где
NA-число случаев благоприятных событию А (или число случаев, при которых событие А произошло). Например, если подбрасывается симметричная монета, то событие А={выпадает герб} – случайное, то ему естественно приписать вероятность.
1
( )
2
P A 
.
События А и В называются несовместными, если они не могут происходить одновременно, т.е.,Р(АB)=0.
Набор событий А
1
, А
2
,…. А
k образует полную группу, если, во- первых, любые два из них несовместны
P(Аi Аj)=0

i ≠ j,
и, во-вторых, одно из этих событий обязательно происходит, иначе говоря
Р(А1)+ Р(А2)+…+Р(Аk) =1.
Например, при бросании игрального кубика могут выпасть числа 1,
2, 3, 4, 5, 6. Введем шесть событий
А1={выпадает цифра 1}
А2={выпадает цифра 2}
…,
А6={выпадает цифра 6}.
Нетрудно видеть, что эти события образуют полную группу. В силу симметрии кубика, естественно положить все вероятности Р(А
i
) равными 1/6.

38
Можно предложить и другие полные группы событий. Например, взять три события B
1
, B
2
, B
3
, где
В
1
={выпадает1}
В
2
={выпадает2, 3 или 4}
В
3
={выпадает5 или 6}.
При этом,
1 2
3 1
3 1
2 1
(
)
, (
)
, (
)
6 6
2 6
3
P B
P B
P B

 
 
.
Условная вероятность события А при условии В есть
Р(А/B) = P(AB) / P(B),
(в предположении, что Р(В)>0).
Если событие А не зависит от события В, то
Р(А/B) = P(A).
Формула умножения вероятностей. Вероятность совместного появления двух событий равна произведению вероятности одного из них на условную вероятность другого, вычисленную в предположении, что первое событие уже наступило:
(
)
( )
(
/ )
P AB
P A P B A


Для независимых событий вероятность произведения событий равна произведению их вероятностей:
(
)
( )
( )
P AB
P A P B


, т.е., вероятность совместного появления двух независимых событий равна произведению вероятностей этих событий.
Если события А
1
,…,А
n
, P(Ai) > 0 образуют полную группу событий, то вероятность события В может быть представлена как сумма произведений безусловных вероятностей событий полной группы на условные вероятности события В (формула полной вероятности):

39
Случайные величины.Пусть даны полная группа событий А
1
, А
2
, …,
Аk с вероятностями pi =P(Аi), i=1,2…,k и набор чисел х
1
, х
2
, …, х
k
Случайной величиной называют некоторое значение, которое ставится в соответствие какому-либо событию.
Непрерывная случайная величинаХ – это величина, которая может принимать любые действительные значения.
Дискретная случайная величина Х – это величина, принимающая значение хi, если происходит событие Аi (то есть, с вероятностью pi).
Например, результат наблюдений Х за постоянной физической величиной Q можно рассматривать как случайную величину, принимающую различные значения Z, в различных наблюдениях за ней.
Если поставить в соответствие одной стороне монеты значение 1, а другой 2, то результатом бросания монеты будет дискретная случайная величина, принимающая значение 1 или 2.
Несколько случайных величин называются
одинаково
распределенными, если их распределения совпадают (т.е. они принимают одинаковые значения с одинаковыми вероятностями). Как следствие, одинаково распределенные случайные величины имеют одинаковые средние и дисперсии.
Например, если подбросить кубик несколько раз и обозначить через Хn значение, выпадающее при n-ом подбрасывании, то эти случайные величины будут одинаково распределены.
Несколько (скажем, n) случайных величин х1, х2, …, хn называются независимыми, если вероятность того, что одновременно первая из них приняла значениес1, вторая – значениес2, n-ая - значение
сn, совпадает с произведением вероятностей.
1 1
2 2
(
)
(
) ...
(
)
n
n
P X
c
P X
c
P X
c



 

.
Каковы бы ни были числа с
1
, с
2
, …, с
n
Независимость можно понимать как отсутствие влияния результатов одних испытаний на другие.
Например, если мы подбросим два одинаковых кубика по разу, то всего различных исходов 36 (каждому варианту выпадения первого кубика может соответствовать 6 вариантов выпадения второго), и все они «равновозможны», т.е. вероятность того, что на первом выпадет число с
1
, а на втором – с
2
(где с
1
, с
2
– любые целые числа от 1 до 6), равна
1 36
, что совпадает с произведением
1 1 6 6

. Значит, соответствующие случайные величины независимы.
Функции распределения. Наиболее универсальный способ описания случайных величин заключается в отыскании их интегральных или дифференциальных функций распределения.

40
Под
интегральной
функцией
распределения
результатов наблюдений понимается зависимость вероятности того, что результат наблюдения Xi в i-м опыте окажется меньшим некоторого текущего значения х, от самой величины х:
( )
(
)
X
i
F x
P X
x


.
Поскольку функция распределения вероятности представляет собой вероятность, то она удовлетворяет следующим свойствам:

0
( ) 1
(
,
)
X
F x
при x


  

(
)
0,
(
) 1
X
X
F
F
 
 

( )
X
F x
– неубывающая функция от x.

1 2
2 1
(
)
( )
( )
X
X
P x
X
x
F x
F x




Вопрос 4. Параметры системы, способы оценивания, пример
оценивания.
Во многих задачах теории массового обслуживания для определения необходимого показателя эффективности достаточно знать
распределение входящего потока, дисциплину очереди (например, случайный выбор, обслуживание в порядке поступления или с приоритетом) и распределение времени обслуживания. В других задачах нужно иметь дополнительную информацию. Например, в случае отказов в обслуживании нужно определить вероятность того, что поступившее требование получит отказ сразу после прибытия или через некоторое время, т.е. покинет очередь до или после присоединения к ней.
С теоретической точки зрения очереди можно рассматривать как потоки, проходящие через систему пунктов обслуживания, соединенных последовательно или параллельно. На поток оказывают влияние различные факторы; они могут замедлять его, приводить к насыщению и т.д.
Система массового обслуживания в зависимости от числа каналов и их производительности, а также от характера потока заявок обладает некоторой пропускной способностью.
Для задания и описания эффективности функционирования конкретной СМО используются такие параметры как:
 среднее число заявок, находящихся в СМО;
 среднее число заявок, находящихся на обслуживании;
 среднее число заявок, находящихся в очереди;
 среднее время ожидания в очереди;
 среднее время нахождения в СМО.

41
В зависимости от условий задачи и целей исследования в качестве характеристик эффективности обслуживания могут применяться также и другие численные показатели и функции, например:
 вероятность того, что поступившая заявка немедленно будет принята к обслуживанию;
 закон распределения времени ожидания;
 средний доход, приносимый СМО в единицу времени, и т.д.;
 среднее время простоя системы;
 закон распределения длительности ожидания требования в очереди;
 и другие.
Выбор показателя зависит от вида системы.
Рассмотрим следующую простую ситуацию для системы с одним обслуживающим устройством:
Текущее время
0 2
6 11 12 19 22 26 36 38 45 47 49 52 61
Время ожидания
0 3
6 2
10 5
6 6
0 0
0 3
5 3
0
Время обслуживания
5 7
1 9
2 4
4 3
1 2
5 4
1 2
1
Время ухода
5 12 13 22 24 28 32 35 37 40 50 54 55 57 62
В первой строке дано время прибытия клиента, во второй – время ожидания клиентом обслуживания, в третьей – время обслуживания клиента, в четвертой – время ухода клиента из системы, равное сумме момента времени прихода клиента в систему, времени ожидания обслуживания и времени обслуживания. Для определения времени ожидания в очереди нужно найти разность между моментом ухода из системы предыдущего клиента и моментом времени прибытия клиента, чье время ожидания вычисляется. Время ожидания будет равно этой разности, если она положительна, и нулю в противном случае.
Для получения статистически значимых данных о реальном процессе потребовалась бы значительно большая выборка, однако некоторые важные характеристики системы массового обслуживания можно оценить и на этом примере. В данном случае десять клиентов из пятнадцати ожидают. Среднее время ожидания для этих клиентов равно
49/10; среднее время ожидания для всех клиентов равно 49/15.
Можно вычислить также общее время простоя канала. Канал простаивает в ожидании клиента, если очередной клиент прибывает после ухода предыдущего клиента. Таким образом, общее время простоя равно сумме положительных разностей между моментом прибытия клиента и моментом ухода предыдущего клиента. Доля времени, в течение которого канал простаивает, равна отношению последней величины к общему времени работы.

42
Если бы выборка была достаточно велика, то, подсчитав число случаев, когда ожидает один клиент, группа из двух клиентов и т.д., можно было бы получить вероятность того, что ожидает один клиент, два клиента и т.д., т.е. получить вероятность появления таких групп.
Читателю предлагается ответить на вопрос: какую пользу можно извлечь из этих вероятностей?
Другой важной величиной является вероятность того, что в произвольный момент времени ожидает данное число клиентов.
Например, четвертый клиент ожидает вместе с третьим в течение единицы времени, а затем остается и ожидает в течение единицы времени вместе с пятым клиентом. Здесь образовались две ожидающие группы по два клиента в каждой.
Можно построить диаграмму, состоящую из горизонтальных параллельных отрезков. Каждый отрезок связан с определенным клиентом, а его длина соответствует длительности ожидания данным клиентом. Сверху проводится базисная линия, на которой откладывается текущее время. Каждый отрезок должен начинаться в момент прибытия клиента и оканчиваться в момент начала обслуживания. Таким образом, можно определить число ожидающих клиентов и длительность ожидания для этого числа клиентов.
Например, отрезок, соответствующий второму клиенту, протянется от второй до пятой единицы времени, а отрезок, соответствующий третьему клиенту, – от шестой до двенадцатой единицы. Эти два отрезка не перекрываются. Однако отрезок, соответствующий четвертому клиенту, протянется от одиннадцатой до тринадцатой единицы времени и перекроется на единицу времени с отрезком, соответствующим предыдущему клиенту. Он перекроется также и с отрезком, соответствующим следующему клиенту. Чтобы найти вероятность того, что в какой-либо момент времени ожидает группа из двух клиентов, берется отношение общей длительности ожидания группами из двух клиентов ко всему времени.
При повторении эксперимента для новых данных возникнет новая ситуация. При достаточном числе повторений для практического случая можно оценить вероятность того, что в данный момент времени ожидает данное число клиентов. Эта вероятность отличается от предыдущей, которая вычисляется для любого момента времени. Она находится подсчетом частоты случаев, когда в данный момент времени ожидает один клиент, группа из двух клиентов и т.д.

43
Представляют интерес три вида характеристик числа ожидающих клиентов:
1. вероятность появления данной группы клиентов, ожидающих совместно;
2. вероятность появления данной группы ожидающих клиентов в любой момент времени;
3. вероятность появления данной группы ожидающих клиентов в данный момент времени.
С помощью полученных выше данных можно найти интенсивность входящего потока и интенсивность обслуживания. Если бы данные были более обширными, то можно было бы получить как распределение длительности промежутков времени между моментами прибытия клиентов, так и распределение длительности обслуживания.
Вопрос 5. Простейший поток. Формула Пуассона.
Поток требований называют однородным, если:
 все требования потока обслуживаются в системе массового обслуживания одинаково;
 рассмотрение требований (событий) потока, которые по своей природе могут быть различными, ограничивается рассмотрением моментов времени их поступления.
Потокназывается регулярным, если события в потоке следуют один за другим через интервалы времени одинаковой длительности.
Функция f(х) плотности распределения вероятности случайной величины Т, обозначающей интервал времени между событиями, для регулярного потока имеет вид:
( )
(
)
f x
x t



,
где
δ – дельта функция;
t– математическое ожидание случайной величины T.
Дисперсия интервала между событиями регулярного потока
(моментами поступления требований) D[T] равна 0, а интенсивность наступления событий в потоке (среднее число требований в единицу времени) λ равна
1
t
Потокназывается случайным, если события в потоке следуют один за другим через интервалы времени случайной длительности.

44
Случайный поток может быть описан как случайный вектор, который, в свою очередь, может быть задан одним из двух способов:
1. Функцией распределения моментов наступления событий
T
1
,T
2
,…T
n
1 2
1 1
2 2
( , ,..., )
(
,
,...,
)
n
n
n
F t t
t
P T
t T
t
T
t




,
где
t
i
– значение моментов наступления Ti(i=1,n).
2. Функцией распределения интервалов между наступлением последовательных событий τ1, τ2,…, τn:
1 2
1 1
2 2
( ,
,...,
)
(
,
,...,
)
n
n
n
F
P
 

  







,
где

i
- значения интервалов между событиями τi(i=1,n).
В последнем случае моменты наступления событий могут при необходимости быть найдены из рекуррентных соотношений:
t1=t0+
1

t2=t1+
2

………,
tn=tn-1+
n

……………
где
t
0
– момент наступления первого события потока.
Поток называется стационарным, если вероятность попадания того или иного числа событий на элементарный участок времени длиной
τ зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.
Поток событий называется потоком без последействия, если для любых непересекающихся участков времени число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой.

45
Поток событий называется ординарным, если вероятность попадания на элементарный участок двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события.
Поток событий, обладающий всеми тремя указанными свойствами, называется простейшим, или стационарным пуассоновским потоком.
Пуассоновский поток событий тесно связан с известным из теории вероятностей распределением Пуассона: число событий потока, попадающих на временной интервал некоторой величины, распределено по закону Пуассона.
Если на временной оси t, где наблюдается поток событий, выделить некоторый участок времени длины τ, начинающийся в момент
t
0
и заканчивающийся в момент t
0
+ τ, то нетрудно доказать, что вероятность попадания на этот участок ровно m событий выражается формулой:
( )
!
m
a
a e
P m
m


,
(4)
где
а – среднее число событий, приходящееся на участок τ;
е – основание натуральных логарифмов (2,71828…);
1 2 3 ... (
1)
,
1
!
1,
0
m
m если m
m
если m
   
 


 


Для стационарного (простейшего) пуассоновского потока величина а равна интенсивности потока λ, умноженной на длину интервала:
a
 
  ,
где
интенсивность, или плотность потока λ есть среднее число событий, приходящихся на единичный временной интервал. В зависимости от физической природы изучаемой системы интенсивность может иметь различную размерность, например, чел/мин, руб/день, кг/час, запросов/сек, документов/сутки, отправлений/сутки и т.д.

46
Функция распределения
( )
(
)
T
F t
P T
t


,
представляющая собой по определению вероятность того, что случайная величина Т (интервал времени между событиями) не превысит значения t, имеет для пуассоновского потока следующий вид:
( ) 1
t
T
F t
e


 
.
(5)
Такой закон распределения называется показательным (или
экспоненциальным) с плотностью λ. Величина λ называется также
параметром показательного закона.
Математическое ожидание случайной величины
T
равно:
1
t


,
(6)
а дисперсия составляет
2 1
[ ]
D T


.
(7)
Среднеквадратическое отклонение случайной величины T находится как квадратный корень из дисперсии:
1
[ ]
T
D T




.
(8)
Как нетрудно видеть, математическое ожидание величины Т равно ее среднеквадратическому отклонению, что является характерной особенностью экспоненциального распределения.
Таким образом, вероятность появления m событий в заданном промежутке времени описывается пуассоновским распределением, а вероятность того, что временные интервалы между событиями потока не превзойдут некоторого наперед заданного значения, описывается
экспоненциальным распределением. Это различные описания одного и того же стохастического процесса.

47
В качестве примера рассмотрим банковскую систему, работающую в реальном масштабе времени и обслуживающую большое число клиентов. В часы пик запросы от кассиров банка, работающих с клиентами, образуют пуассоновский поток и поступают в среднем по два в 1 с (λ = 2). Поток состоит из заявок, поступающих с интенсивностью 2 заявки в секунду.
Рассчитаем вероятность Р (m) появления m сообщений в 1 с. Так как λ = 2, то из формулы (4) имеем
2 2
( )
!
m
e
P m
m


.
Подставляя m=0, 1, 2, 3… получим следующие величины (с точностью до четырех десятичных знаков):
m
0 1
2 3
4 5
6 7
8 9
Р(m)
0,1353 0,2707 0,2707 0,2707 0,0902 0,0361 0,0120 0,0034 0,0009 0,0002
Возможно поступление и более 9 сообщений в 1 с, но вероятность этого очень мала (около 0,000046).
Полученное распределение может быть представлено в виде гистограммы:
Выводы:
1. Существуют несколько критериев, которые могут применяться для проверки гипотез. Выбор конкретного критерия зависит от условий, в которых производится оценивание гипотезы, в первую очередь, от объема выборки используемых для оценивания данных.
2. Для моделирования широкого класса систем и процессов необходимо строить математическое описание циркулирующих потоков объектов различного класса (информационных, материальных). Потоки могут характеризоваться различными свойствами, которые обусловливают тот или иной вид их математического описания.

48 3. Важным частным случаем потоков в моделируемых системах и процессах является пуассоновский поток. Поэтому в практических задачах целесообразно подвергать проверке гипотезу о принадлежности наблюдаемого потока к пуассоновскому, применяя тот или иной критерий.
Вопросы для самопроверки:
1. Какие системы называют стохастическими?
2. Что такое пуассоновский поток?
3. Как записывается и что позволяет найти формула Пуассона?
4. Как называется и что означает параметр пуассоновского закона?
5. Какому закону распределения подчиняются интервалы между поступлением отдельных заявок потока?
6. Как найти вероятность того, что в течение определенного интервала поступит не более определенного числа требований?
7. Чему равно математическое ожидание интервала времени между событиями в пуассоновском потоке?
8. Чему равно среднеквадратическое отклонение интервала времени между событиями в пуассоновском потоке?
9. Для чего нужно аппроксимировать экспериментальные данные относительно потока заявок и времени обслуживания в системе массового обслуживания теоретическими зависимостями?
10. Какие шаги нужно выполнить, чтобы построить теоретическую зависимость?
11. Зачем нужно проводить оценку статистической значимости результата?
Литература по теме:
1. Градов В.М. Компьютерное моделирование: учебник / В.М.
Градов, Г.В. Овечкин, П.В. Овечкин, И.В. Рудаков. – М.: ИНФРА-М,
2017. – 264с.
2. Емельянов А.А. Модели процессов массового обслуживания //
Прикладная информатика, 2008, № 5 (17), С. 92-130.
3. Математическое моделирование системных объектов: учебное пособие / Фоменков С.А., Камаев В.А., Орлова Ю.А.; ВолгГТУ,
Волгоград, 2014. – 340с.
4. Тутубалин В.Н. Теория вероятностей и случайных процессов, –
М., Изд-во МГУ,1992 – 400с.

49