В предыдущих лекциях мы научились имитировать наступление случайных событий. То есть мы можем разыграть какое из возможных событий наступит и в каком количестве. Чтобы это определить, надо знать статистические характеристики появления событий, например, такой величиной может быть вероятность появления события, или распределение вероятностей разных событий, если типов этих событий бесконечно много.
Но часто еще важно знать, когда конкретно наступит то или иное событие во времени.
Когда событий много и они следуют друг за другом, то они образуют поток . Заметим, что события при этом должны быть однородными, то есть похожими чем-то друг на друга. Например, появление водителей на АЗС, желающих заправить свой автомобиль. То есть, однородные события образуют некий ряд. При этом считается, что статистическая характеристика этого явления (интенсивность потока событий) задана. Интенсивность потока событий указывает, сколько в среднем происходит таких событий за единицу времени. Но когда именно произойдет каждое конкретное событие надо определить методами моделирования. Важно, что, когда мы сгенерируем, например, за 200 часов 1000 событий, их количество будет равно примерно величине средней интенсивности появления событий 1000/200 = 5 событий в час, что является статистической величиной, характеризующей этот поток в целом.
Интенсивность потока в некотором смысле является математическим ожиданием количества событий в единицу времени. Но реально может так оказаться, что в один час появится 4 события, в другой 6, хотя в среднем получается 5 событий в час, поэтому одной величины для характеристики потока недостаточно. Второй величиной, характеризующей насколько велик разброс событий относительно математического ожидания, является, как и ранее, дисперсия. Собственно именно эта величина определяет случайность появления события, слабую предсказуемость момента его появления. Про эту величину мы расскажем в следующей лекции.
Поток событий это последовательность однородных событий, наступающих одно за другим в случайные промежутки времени. На оси времени эти события выглядят как показано на рис. 28.1 .
Примером потока событий могут служить последовательность моментов касания взлетной полосы самолетами, прилетающими в аэропорт.
Интенсивность потока λ это среднее число событий в единицу времени. Интенсивность потока можно рассчитать экспериментально по формуле: λ = N /T н , где N число событий, произошедших за время наблюдения T н .
Если интервал между событиями τ j равен константе или определен какой-либо формулой в виде: t j = f (t j 1) , то поток называется детерминированным . Иначе поток называется случайным .
Случайные потоки бывают:
- ординарные : вероятность одновременного появления двух и более событий равна нулю;
- стационарные : частота появления событий λ (t ) = const(t ) ;
- без последействия : вероятность появления случайного события не зависит от момента совершения предыдущих событий.
Пуассоновский поток
За эталон потока в моделировании принято брать пуассоновский поток .
Пуассоновский поток это ординарный поток без последействия.
Как ранее было указано, вероятность того, что за интервал времени (t 0 , t 0 + τ ) произойдет m событий, определяется из закона Пуассона:
где a параметр Пуассона.
Если λ (t ) = const(t ) , то это стационарный поток Пуассона (простейший). В этом случае a = λ · t . Если λ = var(t ) , то это нестационарный поток Пуассона .
Для простейшего потока вероятность появления m событий за время τ равна:
Вероятность непоявления (то есть ни одного, m = 0 ) события за время τ равна:
Рис. 28.2 иллюстрирует зависимость P 0 от времени. Очевидно, что чем больше время наблюдения, тем вероятность непоявления ни одного события меньше. Кроме того, чем более значение λ , тем круче идет график, то есть быстрее убывает вероятность. Это соответствует тому, что если интенсивность появления событий велика, то вероятность непоявления события быстро уменьшается со временем наблюдения.
Вероятность появления хотя бы одного события (P ХБ1С ) вычисляется так:
так как P ХБ1С + P 0 = 1 (либо появится хотя бы одно событие, либо не появится ни одного, другого не дано).
Из графика на рис. 28.3 видно, что вероятность появления хотя бы одного события стремится со временем к единице, то есть при соответствующем длительном наблюдении события таковое обязательно рано или поздно произойдет. Чем дольше мы наблюдаем за событием (чем более t ), тем больше вероятность того, что событие произойдет график функции монотонно возрастает.
Чем больше интенсивность появления события (чем больше λ ), тем быстрее наступает это событие, и тем быстрее функция стремится к единице. На графике параметр λ представлен крутизной линии (наклон касательной).
Если увеличивать λ , то при наблюдении за событием в течение одного и того же времени τ , вероятность наступления события возрастает (см. рис. 28.4 ). Очевидно, что график исходит из 0, так как если время наблюдения бесконечно мало, то вероятность того, что событие произойдет за это время, ничтожна. И наоборот, если время наблюдения бесконечно велико, то событие обязательно произойдет хотя бы один раз, значит, график стремится к значению вероятности равной 1.
Изучая закон, можно определить, что: m x = 1/λ , σ = 1/λ , то есть для простейшего потока m x = σ . Равенство математического ожидания среднеквадратичному отклонению означает, что данный поток поток без последействия. Дисперсия (точнее, среднеквадратичное отклонение) такого потока велика. Физически это означает, что время появления события (расстояние между событиями) плохо предсказуемо, случайно, находится в интервале m x σ < τ j < m x + σ . Хотя ясно, что в среднем оно примерно равно: τ j = m x = T н /N . Событие может появиться в любой момент времени, но в пределах разброса этого момента τ j относительно m x на [σ ; +σ ] (величину последействия). На рис. 28.5 показаны возможные положения события 2 относительно оси времени при заданном σ . В данном случае говорят, что первое событие не влияет на второе, второе на третье и так далее, то есть последействие отсутствует.
По смыслу P равно r (см. лекцию 23. Моделирование случайного события. Моделирование полной группы несовместных событий), поэтому, выражая τ из формулы (*) , окончательно для определения интервалов между двумя случайными событиями имеем:
τ = 1/λ · Ln(r ) ,
где r равномерно распределенное от 0 до 1 случайное число, которое берут из ГСЧ, τ интервал между случайными событиями (случайная величина τ j ).
Пример 1 . Рассмотрим поток изделий, приходящих на технологическую операцию. Изделия приходят случайным образом в среднем восемь штук за сутки (интенсивность потока λ = 8/24 [ед/час] ). Необходимо промоделировать этот процесс в течение T н = 100 часов . m = 1/λ = 24/8 = 3 , то есть в среднем одна деталь за три часа. Заметим, что σ = 3 . На рис. 28.6 представлен алгоритм, генерирующий поток случайных событий.
На рис. 28.7 показан результат работы алгоритма моменты времени, когда детали приходили на операцию. Как видно, всего за период T н = 100 производственный узел обработал N = 33 изделия. Если запустить алгоритм снова, то N может оказаться равным, например, 34, 35 или 32. Но в среднем, за K прогонов алгоритма N будет равно 33.33 Если посчитать расстояния между событиями t сi и моментами времени, определяемыми как 3 · i , то в среднем величина будет равна σ = 3 .
Моделирование неординарных потоков событий
Если известно, что поток не является ординарным, то необходимо моделировать кроме момента возникновения события еще и число событий, которое могло появиться в этот момент. Например, вагоны на железнодорожную станцию прибывают в составе поезда в случайные моменты времени (ординарный поток поездов). Но при этом в составе поезда может быть разное (случайное) количество вагонов. В этом случае о потоке вагонов говорят как о потоке неординарных событий.
Допустим, что M k = 10 , σ = 4 (то есть, в среднем в 68 случаях из 100 приходит от 6 до 14 вагонов в составе поезда) и их число распределено по нормальному закону. В место, отмеченное (*) в предыдущем алгоритме (см. рис. 28.6 ), нужно вставить фрагмент, показанный на рис. 28.8 .
Пример 2 . Очень полезным в производстве является решение следующей задачи. Каково среднее время суточного простоя оборудования технологического узла, если узел обрабатывает каждое изделие случайное время, заданное интенсивностью потока случайных событий λ 2 ? При этом экспериментально установлено, что привозят изделия на обработку тоже в случайные моменты времени, заданные потоком λ 1 партиями по 8 штук, причем размер партии колеблется случайно по нормальному закону с m = 8 , σ = 2 (см. лекцию 25). До начала моделирования T = 0 на складе изделий не было. Необходимо промоделировать этот процесс в течение T н = 100 часов.
На рис. 28.9 представлен алгоритм, генерирующий случайным образом поток прихода партий изделий на обработку и поток случайных событий выхода партий изделий с обработки.
На рис. 28.10 показан результат работы алгоритма моменты времени, когда детали приходили на операцию, и моменты времени, когда детали покидали операцию. На третьей линии видно, сколько деталей стояло в очереди на обработку (лежало на складе узла) в разные моменты времени.
Отмечая для обрабатывающего узла времена, когда он простаивал в ожидании очередной детали (см. на рис. 28.10 участки времени, выделенные красной штриховкой), мы можем посчитать суммарное время простоев узла за все время наблюдения, а затем рассчитать среднее время простоя в течение суток. Для данной реализации это время вычисляется так:
T пр. ср. = 24 · (t 1 пр. + t 2 пр. + t 3 пр. + t 4 пр. + + t N пр.)/T н .
Задание 1 . Меняя величину σ , установите зависимость T пр. ср. (σ ) . Задавая стоимость за простой узла 100 евро/час, установите годовые потери предприятия от нерегулярности в работе поставщиков. Предложите формулировку пункта договора предприятия с поставщиками «Величина штрафа за задержку поставки изделий».
Задание 2 . Меняя величину начального заполнения склада, установите, как изменятся годовые потери предприятия от нерегулярности в работе поставщиков в зависимости от принятой на предприятии величины запасов.
Моделирование нестационарных потоков событий
В ряде случаев интенсивность потока может меняться со временем λ (t ) . Такой поток называется нестационарным . Например, среднее количество за час машин скорой помощи, покидающих станцию по вызовам населения большого города, в течение суток может быть различным. Известно, например, что наибольшее количество вызовов падает на интервалы с 23 до 01 часа ночи и с 05 до 07 утра, тогда как в остальные часы оно вдвое меньше (см. рис. 28.11 ).
В этом случае распределение λ (t ) может быть задано либо графиком, либо формулой, либо таблицей. А в алгоритме, показанном на рис. 28.6 , в место, помеченное (**), нужно будет вставить фрагмент, показанный на рис. 28.12 .
Если число n
испытаний достаточно велико, а вероятность p
наступления события А
в независимых испытаниях мала, то для нахождения вероятности используется теорема Пуассона
: Если в n
независимых испытаниях вероятность p
наступления события А
в каждом из них постоянна и мала, а число испытаний достаточно велико, то вероятность того, что событие А наступит k
раз, вычисляется по формуле 
, где 
.
Эта формула называется формулой Пуассона .
Пример 15 . Вероятность попадания в самолёт при каждом выстреле из пулемёта равна 0.001. Производится 3000 выстрелов. Найти вероятность попадания в самолёт: а) один или два раза; б) хотя бы один раз.
Решение
. По условию примера n
=300, p
=0.001, 
.
а) Обозначим событие A={попадание в самолёт один или два раза}. Тогда .
б) Обозначим событие B={попадание в самолёт хотя бы один раз}. Тогда .
Потоком событий называется последовательность событий, которые наступают одно за другим в случайные моменты времени.
Например, поток вызовов в сфере обслуживания (ремонт телевизоров, вызовы скорой помощи и др.), поток вызовов на телефонной станции, отказ в работе отдельных частей некоторой системы и т.д.
Поток называется простейшим , если выполняются следующие условия:
Вероятность появления события зависит от длины промежутка времени t ;
Вероятность появления числа событий на любом промежутке времени не зависит от того, какое число событий наступило до начала этого промежутка;
Вероятность наступления двух или большего числа событий за достаточно малый промежуток времени мала и чем меньше , тем меньше становится вероятность.
При выполнении этих условий справедливо следующее утверждение:
Вероятность того, что случайное событие за время t наступит k раз, определяется по формуле
,
где - среднее число событий, наступающих в единицу времени.
Пример 16 . На ткацких станках, обслуживаемых ткачихой, в течение часа происходит 90 обрывов нити. Какова вероятность того, что за 4 минуты произойдёт: 1) один обрыв; 2) хотя бы один обрыв.
Решение
. По условию t
=4. Среднее число обрывов за одну минуту равно 
. Тогда 
.
1) 
. 2) .
Вопросы для самоконтроля знаний
1. Что называется суммой совместных событий?
2. Что называется суммой несовместных событий?
3. Как формулируется теорема сложения вероятностей несовместных событий?
4. Чему равна сумма вероятностей противоположных событий?
5. Что называется произведением двух событий?
6. Какие события называются независимыми?
7. Как формулируется теорема умножения вероятностей независимых событий?
8. Какие события называются зависимыми?
9. Что называется условной вероятностью?
10. Как формулируется теорема умножения вероятностей зависимых событий?
11. Что называется полной вероятностью события и как записывается формула полной вероятности?
12. Как записывается формула Байеса?
13. Какие испытания называются независимыми и как записывается формула Бернулли?
14. Как формулируется локальная теорема Лапласа?
15. Как формулируется интегральная теорема Лапласа?
16. Как формулируется теорема Пуассона?
Информатика, кибернетика и программирование
Определение Пуассоновского потока. Пуассоновский поток это ординарный поток без последействия. Классической моделью трафика в информационных сетях является Пуассоновский простейший поток. Он характеризуется набором вероятностей Pk поступления k сообщений за временной интервал t: где k=01 число сообщений; λ интенсивность потока.
1. Определение Пуассоновского потока. Свойства.
Пуассоновский поток - это ординарный поток без последействия.
Классической моделью трафика в информационных сетях является Пуассоновский (простейший) поток. Он характеризуется набором вероятностей P(k) поступления k сообщений за временной интервал t:
где k=0,1,… - число сообщений; λ - интенсивность потока.
Заметим, что интервал времени измерения количества сообщений t и интенсивность потока λ являются постоянными величинами.
Семейство Пуассоновских распределений P(k) в зависимости от λ изображено на рис.1. Большее значение λ соответствует более широкому и симметричному графику плотности вероятности.
Рис. 1. Пуассоновские распределения. Плотности вероятностей.
Математическое ожидание (среднее) и дисперсия Пуассоновского потока равны λ t .
Зная вероятность поступления данных за период, можно получить распределение интервала τ между соседними событиями:
Отсюда вывод: пуассоновский поток характеризуется экспоненциальным распределением интервалов между событиями.
Основным свойством пуассоновского потока , обусловливающим его широкое применение при моделировании, является аддитивность: результирующий поток суммы пуассоновских потоков тоже является пуассоновским с суммарной интенсивностью:
При моделировании Пуассоновский поток можно получить мультиплексированием совокупности ON/OFF источников, которые называются Марковскими процессами (рис.2.).
Рис. 2. Получение Пуассоновского распределения
2. СМО с отказами (классическая система Эрланга)
Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания; эта задача возникла из практических нужд телефонии и была решена в 1909 г. датским инженером-математиком А.К. Эрлангом. Задача ставится так: имеется n каналов (линий связи), на которые поступает поток заявок с интенсивностью λ. Поток обслуживаний каждого канала имеет интенсивность μ. Найти предельные вероятности состояний системы и показатели ее эффективности.
Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S 0 , S 1 ,…, S n , где S k состояние системы, когда в ней находится k заявок, т.е. занято k каналов.
Граф состояний СМО соответствует процессу гибели и размножения (рис. 3).
Рис. 3. Граф состояний СМО
Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью λ. Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S 2 (два канала заняты), то она может перейти в состояние S 1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживаний будет 2μ . Аналогично суммарный поток обслуживаний, переводящий СМО из состояния S 3 (три канала заняты) в S 2 , будет иметь интенсивность 3μ , т.е. может освободиться любой из трех каналов, и т.д.
В формуле (1) для схемы гибели и размножения получим для предельной вероятности состояния:
(1)
где члены разложения
- коэффициенты при p
0
в выражениях для предельных вероятностей p
1
, p
2
,..., p
n
.
Заметим, что в формулу (1) интенсивности λ и μ входят не по отдельности, а только в виде отношения μ/λ. Обозначим: μ/λ = p , и будем называть величину ρ приведенной интенсивностью потока заявок или интенсивностью нагрузки канала. Она выражает среднее число заявок, приходящих за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулу (1) в виде:
(2)
При этом:
(3)
Формулы (2) и (3) для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.
Вероятность отказа СМО есть предельная вероятность того, что все n каналов системы будут заняты, т.е.
Отсюда находим относительную пропускную способность вероятность того, что заявка будет обслужена:
Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ на Q:
(4)
Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0,1,..., n и вероятностями этих значений p 0 , p 1 , …, p n :
Подставляя сюда выражения (3) для p k и выполняя соответствующие преобразования, мы, в конце концов, получили бы формулу для k. Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность A системы есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем μ заявок (в единицу времени), то среднее число занятых каналов:
или, учитывая (4):
А также другие работы, которые могут Вас заинтересовать |
|||
| 43346. | Створення інформаційної бази даних служби продажу залізничних білетів | 1.19 MB | |
| Курсова робота з дисципліни Організація баз даних та знань на тему: Створення інформаційної бази даних служби продажу залізничних білетів Курсова робота студента 3 курсу групи КН48 Нестеренка М. Проектування інформаційної бази даних Створення реляційної моделі бази даних Створення бази даних | |||
| 43347. | Технологии аппаратной виртуализации | 64.5 KB | |
| Аппаратная виртуализация - виртуализация с поддержкой специальной процессорной архитектуры. В отличие от программной виртуализации, с помощью данной техники возможно использование изолированных гостевых систем, управляемых гипервизором напрямую. Гостевая система не зависит от архитектуры хостовой платформы и реализации платформы виртуализации. | |||
| 43349. | Публіцистика Уласа Самчука | 108.5 KB | |
| Деяка молодь не знає своєї історії і не може відповісти на питання Хто були їх предки. А коли все одно то це значить що все одно для нас хто є ми самі Це значить що ми не нарід не якась спільна історична збірна сила а невиразна юрба сіра маса вічно принижена без всяких ідеалів чернь4. Замкнутість людини лише у сільському просторі неминуче призведе до відчуження її від міста. | |||
| 43351. | РЕСУРСИ КОМЕРЦІЙНОГО БАНКУ, ЇХ ФОРМУВАННЯ ТА МЕНЕДЖМЕНТ | 195 KB | |
| Ресурси комерційного банку їх склад та структура. Власний капітал комерційного банку та його формування. Залучений капітал комерційного банку та його характеристика. | |||
| 43352. | Флористичні дані про медоносні рослини луків, які найбільш поширені на території України | 210.5 KB | |
| Загальна характеристика Шишацького району та Полтавської області Розділ 2.6 Інші рослини Висновки Література ВСТУП Об"єктом нашого дослідження є медоносні рослини які поширені в Шишацько му районіПолтавської областіїх значення у житті людини та характеристика. В Шищацькому районіПолтавської області нараховується велика кількість медоносних рослин. Загальна характеристика Шишацького... | |||
| 43354. | РЕАЛІЗАЦІЯ ЗМІШАНОЇ КРИПТОСИСТЕМИ ПОПЕРЕДНЬОГО ШИФРУВАННЯ | 544 KB | |
| Цей пункт забезпечує разгортання системи конфіденційного звязку управління роботою системи конфіденційного звязку первісну генерацію та розповсюдження ключів управління персоналом. Для автентифікації відкритих ключів дозволяеться використовувати послуги регіонального центру сертифікації. Генерація сеансових ключів для ГОСТ 2814789 перешифрування в режими простої заміни алгоритма ГОСТ 2814789 послідовності що отримана відповідно до пункту 1.2 Розповсюдження ключів за допомогою асиметричних криптосистем } | |||