Пиши Дома Нужные Работы

Обратная связь

Принцип последовательной проводки заявок

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

 

32. Языки и инструментальные системы имитационного моделирования.

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



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

Рассмотрим основные понятия, связанные с алгоритмическими языками и их реализацией на ЭВМ вообще и языками моделирования в частности.

Язык программирования представляет собой набор символов, распознаваемых ЭВМ и обозначающих операции, которые можно реализовать на ЭВМ. На низшем уровне находится основной язык машины, программа на котором пишется в кодах, непосредственно соответствующих элементарным машинным действиям (сложение, запоминание, пересылка по заданному адресу и т. д.). Следующий уровень занимает автокод (язык АССЕМБЛЕРА) вычислительной машины. Программа на автокоде составляется из мнемонических символов, преобразуемых в машинные коды специальной программой - ассемблером.

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

Интерпретатором называется программа, которая, принимая инструкции входного языка, сразу выполняет соответствующие опeрации в отличие от компилятора, преобразующего эти инструкции в запоминающиеся цепочки команд. Трансляция происходит в течение всего времени работы программы, написанной на языке интерпретатора. В отличие от этого компиляция и ассемблирование представляют собой однократные акты перевода текста с входного языка на объектный язык машины, после чего полученные программы выполняются без повторных обращений к транслятору.

Программа, составленная в машинных кодах или на языке АССЕМБЛЕРА, всегда отражает специфику конкретной ЭВМ. Инструкции такой программы соответствуют определенным машинным операциям и, следовательно, имеют смысл только в той ЭВМ, для которой они предназначены, поэтому такие языки называются машинно-ориентированными языками.

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

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

 

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

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

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

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

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

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

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

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

Действие игры происходит на плоскости, разделенной на клетки. Каждая клетка окружена 8 такими же клетками (так называемая окрестность Мура) и может находиться в двух состояниях - живом или мертвом (быть пустой). Гибель и рождение всех организмов происходит одновременно. На состояние любой клетки оказывают влияние только состояния соседних с ней клеток. Во времени эти состояния дискретно изменяются в соответствии со следующими правилами (генетическими законами Конвея).

1. Выживание или гибель. Если живая клетка имеет менее 2 или более 3 соседей в окрестности из 8 клеток, то в следующем поколении она умирает (моделирование реальных условий - недостатка питания или перенаселенности), в противном случае она выживает.

2. Рождение. В пустой клетке появляется новая живая клетка, если у нее ровно 3 соседа.

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

 

34. Общие сведения о моделировании стохастических процессов.

Для произвольных потоков событий, переводящих систему из состояния в состояние, аналитические решения получены только для отдельных частных случаев, а в общем случае удовлетворительных методов математического описания соответствующих процессов не существует.
В тех случаях, когда построение аналитической модели явления по той или иной причине трудно осуществимо, применяется другой метод моделирования, известный под названием метода статистических испытаний или, иначе, метода Монте-Карло.
Существо метода. Вместо того, чтобы описывать случайное явление с помощью аналитических зависимостей, производится «розыгрыш» - моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Так же как в жизни, когда конкретное осуществление процесса складывается каждый раз по иному, так и в результате «розыгрыша» мы получаем один экземпляр – одну реализацию случайного явления. Произведя такой «розыгрыш» очень большое число раз, мы получим статистический материал – множество реализаций случайного явления – который можно обработать обычными методами математической статистики.
Нередко такой прием оказывается проще, чем попытки построить аналитическую модель явления и исследовать зависимость между его параметрами на этой модели. Для сложных операций, в которых участвует большое число элементов (машин, систем, людей, коллективов) и в которых случайные факторы сложным образом взаимодействуют между собой, метод статистических испытаний, как правило, оказывается проще аналитического.
В сущности, методом «розыгрыша» может быть решена любая вероятностная задача: однако оправданным он становится только в случае, когда процедура «розыгрыша» проще, а не сложнее применения аналитических методов.
Пример 1. Решается задача: по некоторой цели производится 4 независимых выстрела, каждый из которых попадает в нее с р=0,5. Для поражения цели требуется не менее двух попаданий. Определить вероятность поражения цели.
Аналитический способ. Вероятность поражения цели вычисляется через вероятность противоположного события. Вероятность непоражения цели = сумме вероятностей ни одного попадания и ровно одного попадания; вероятность ни одного попадания 0,54; вероятность одного попадания равна:
, следовательно
.
Розыгрыш. Будем моделировать процедуру стрельбы с помощью другой, тоже случайной процедуры. Будем бросать 4 монеты: условимся - герб попадание, решка – промах. Цель поражена - не менее двух гербов. Розыгрыш в нашем случае – бросание четырех монет, результат этого опыта - «поражение или не поражение цели». Повторим такой опыт (бросание 4 монет) очень много раз подряд. Тогда согласно теореме Бернулли, частота поражения цели почти наверняка будет мало отличаться от вероятности этого события W; значит, если мы бросим четыре монеты большое число раз N, мы почти наверняка получим число близкое к W, т.е. к 0,688. В данном случае определение вероятности W розыгрышем было несравненно трудней, чем аналитическим расчетом.
Пример 2. Анализ поведения дискретного объекта (дискретные входные и выходные переменные) - «задача о пьяном прохожем или задача о случайном блуждании». Прохожий решил прогуляться, стоя на углу улиц. Пусть вероятность того, что, достигнув очередного перекрестка, он пойдет на север, юг, восток и запад, одинакова. Какова вероятность того, что пройдя 10 кварталов, прохожий окажется не далее 2 кварталов от места, где он начал прогулку.
Обозначим его местонахождение на каждом перекрестке двумерным вектором (x1, x2) («выход»), где x1 – направление с востока на запад и x2– направление с севера на юг. Каждое перемещение на один квартал к востоку (x1 + 1), а каждое перемещение на один квартал к западу (x1 – 1) (x1 - дискретная переменная). К северу x2 + 1, к югу x2 – 1. Начальное положение (0,0).
Если в конце прогулки абсолютные значения х1 и х2 будут больше 2, то будем считать, что он ушел дальше двух кварталов в конце прогулки протяженностью в 10 кварталов. Т.к. вероятность движения нашего прохожего в любом из 4 направлений по условию одинакова и равна 0,25, то можно оценить его передвижение с помощью таблицы случайных чисел. Условимся, что если случайное число (СЧ) лежит в пределах от 0 до 24, пьяный пойдет на восток и мы увеличим х1 на 1; если от 25 до 49, то он пойдет на запад и х1-1; если от 50 до 74, он пойдет на север и x2 + 1; если от 75 до 99, то на юг и x2 – 1.
Блок-схема поведения прохожего.

Нужно провести достаточно большое число «машинных опытов», чтобы получить достоверный результат. Другими методами такую задачу решить практически невозможно.
В литературе этот метод получил название метода имитационного моделирования, а также машинного, статистического, вероятностного, Монте-Карло или метода машинной имитации. В принципе имитационное моделирование можно осуществлять на широком спектре устройств, начиная с аналоговых ЭВМ и кончая листом бумаги с карандашом, однако, как правило, ориентируются на использование ЭВМ.
Метод имитационного моделирования может рассматриваться как своеобразный экспериментальный метод. Отличие от обычного эксперимента заключается в том, что в качестве объекта экспериментирования выступает имитационная модель, реализованная в виде программы на ЭВМ. При таком экспериментировании с моделью (в отличие от «решения» модели при аналитическом, например, моделировании) могут быть применены статистические методы.
Заметим, что методом статистических испытаний можно находить не только вероятности событий, но и средние значения (математические ожидания) случайных величин. При этом применяется закон больших чисел (теорема Чебышева). Согласно этой теореме, при большом числе опытов среднее арифметическое наблюденных значений случайной величины почти наверняка мало отличается от её математического ожидания. Аналогичным образом могут быть найдены не только математические ожидания, но и дисперсии интересующих нас случайных величин.
Метод Монте-Карло есть метод математического моделирования случайных явлений, в которых сама случайность непосредственно включается в процесс моделирования и представляет собой его существенный элемент. Каждый раз, когда в ход операции вмешивается тот или другой случайный фактор, его влияние имитируется с помощью специально организованного «розыгрыша» или жребия. Таким образом, строится одна реализация случайного явления, представляющая собой как бы результат одного «опыта». При большом числе реализаций интересующие нас характеристики случайного явления (вероятности, математические ожидания) находится так же, как они находятся из опыта.
Моделирование случайных явлений методом Монте-Карло имеет общие черты с процессом набора опыта отдельными людьми и человеческими коллективами. И тут, и там каждая отдельная реализация случайна; устойчивые закономерности обнаруживаются лишь при многократном наблюдении явления, при обширном опыте. Большое число реализаций, требующееся при применении метода Монте-Карло, делает его вообще громоздким и трудоемким.

35. Теоретические основы метода стохастического моделирования.

См 34.

36. Моделирование случайных чисел с равномерным распределением вероятности на интервале [0; 1].

Необходимость получения случайных чисел подчиняющихся распределению определенного вида при моделировании связана со случайным характером изучаемых процессов. Для получения таких чисел служит равномерно распределенная последовательность случайных чисел на интервале [0, 1), которая используется для получения случайных чисел любого типа распределения. В программное обеспечение ЭВМ включены специальные программы - датчики случайных чисел, обращение к которым приводит к выдаче случайного значения в интервале [0, 1). Число значащих цифр зависит от реализации датчика случайных чисел и возможностей ЭВМ. Для описания системы с очередью и одним прибором необходим именно такой генератор. Обычно генератор задан в виде функции и выдает шестизначное случайное число равномерно распределенное на интервале от 0,000000 до 0,999999 включительно. Для удобства дальнейшего изложения будем считать, что эта функция имеет имя RAND.

Алгоритмов генерирования случайных чисел достаточно много чаще всего используется следующий. Представим для простоты, что необходимо генерировать случайные четырехзначные равномерно распределенные число на интервале от 0,0000 до 0,9999 включительно. Для этого в алгоритме используют два положительных, нечетных целых числа, каждое из которых может содержать до четырех цифр. Первое из этих двух чисел, никогда не меняющее свое значение называется "ядром", второе, изменяющееся - "множителем". Каждый раз, когда надо получить новое случайное число, значение множителя изменяют в соответствии с некоторой последовательностью. Первым шагом алгоритма является умножение ядра на множитель. Результат (в общем случае) - восьмиразрядное целое число. Его используют для получения нового значения множителя, применяемого на следующем шаге алгоритма. При этом правые четыре цифры произведения используются в качестве нового множителя, средние, умноженные на 10-4 - в качестве случайного числа. Например, пусть число 5167 выбрано в качестве ядра, начальное значение 3729. Для выработки первых случайных чисел используют следующие шаги алгоритма:

1. Получить произведение ядра и множителя: 5167*3729=19267743.

2. Взять число 7743 (правые четыре цифры произведения) в качестве нового значения множителя.

3. Число 0,2677 (средние четыре цифры произведения) использовать в качестве случайного числа.

При генерации второго случайного числа его значение будет равно 0,0080 (ядро 5167, умноженное на множитель 7743, дает 40008081 и определяет новый множитель 8081 и случайное число 0,0080) и т.д. Получаемая таким образом последовательность случайных чисел обладает двумя недостатками:

1. Множитель и ядро могут быть нулями.

2. Последовательность случайных чисел, выработанных ранее повторяется. Количество случайных чисел, выработанных прежде, чем они могут повторяться, называется периодом (или длиной) генератора случайных чисел.

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

1. Ядро и множитель заключены в интервале нечетных целых чисел от 1 до 2147483647 включительно.

2. Любой датчик имеет восемь отличных друг от друга встроенных ядер: 37584381, 1909996635, 442596621, 340029185, 1964463183, 1235671459, 1480745561 и 2030226625. При генерации очередного числа значение соответствующего ядра выбирается случайно среди восьми возможных значений.

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

· первая половина произведения становится следующим значением множителя для данного датчика;

· внутреннюю часть произведения используют в качестве случайного числа (после записи его в виде десятичной дроби);

· другую внутреннюю часть произведения используют для определения какое из восьми ядер данного датчика следует использовать для получения случайного числа.

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

Для рассматриваемой задачи с очередью и одним прибором, необходимо иметь целые значения равномерно распределенных случайных чисел для задания интервалов прибытия заявок и интервалов обслуживания. Специфика описания выборок случайных чисел приводит к необходимости определения наименьшего и наибольшего значения целых чисел в выборке. Например, необходимо установить, что время обслуживания распределено равномерно и заключено в интервале [12, 20]. Средним арифметическим выборки является 16, а размах (в статистическом смысле) 8. В имитационном моделировании размахом называют половину этой величины, что позволяет компактно записывать свойства выборки 16±4. Такую запись, общий вид которой A±B, часто используют для описания равномерного распределения, включающего целые значения от A-B до A+B где A и B также целые. Недостатком этой записи является невозможность задания четного числа значений. Запись 16±4 описывает выборку из десяти значений, 17±5 - из одиннадцати и т.д.

Случайное число из интервала A±B определяют добавлением к наименьшему возможному значению A-B "случайной доли" размаха (в статистическом смысле) 2*B. Значение датчика случайных чисел рассматривается как "случайная доля", т.е. значение целого равномерно распределенного случайного числа определяется как целая часть результата вычисления :

(A - B) + RAND*2*B

Однако, при этом возникает проблема получения наибольшего значения A+B, т.к. максимальное значение датчика случайных чисел 0,999999. В этой связи вычисляют значение целого равномерно распределенного случайного числа по формуле:

(A - B) + RAND*(2*B+1)

Таким образом, если установлено 8±3, то имеем следующие равновероятные значения: 5, 6, 7, 8, 9, 10, 11. Вероятность получения каждого равна 1/7.

Кроме рассмотренного существуют другие методы генерирования случайных чисел.
В основе этих методов получения случайных чисел, распределенных по любым законам, так же лежит использование генератора случайных чисел в интервале 0…1. Наибольшее распространение получили следующие методы генерирования:

· квадратов;

· произведений;

· мультипликативный конгруэнтный;

· смешанный конгруэнтный.

Метод квадратов. В квадрат возведено текущее случайное число и из результатов средних разрядов выделяется следующее число.
Метод произведений. Два следующих друг за другом случайных числа умножают а из произведения средних разрядов выделяют следующее случайное число.
Мультипликативный конгруэнтный метод. В качестве текущего значения случайного числа выделяют остаток от деления произведения предыдущего случайного числа и постоянного множителя a на постоянное число m:

yi=a*yi-1*(mod m),

где a, m -постоянные числа; yi - случайное число.
Смешанный конгруэнтный метод. Этот метод отличается от предыдущего прибавлением к остатку от деления постоянного числа m:

yi=a*yi-1+m*(mod m),

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

· на периодичность;

· на случайность;

· на равномерность.

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

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

При поверке на равномерность используется тест проверки частот, так как гистограмма хорошо отражает равномерность распределения.

 

37. Моделирование случайной дискретной величины.

Моделирование дискретной с.в. в принципе ничем не отличается от моделирования случайного события. Дискретная с.в. d задается множеством возможных значений {d1, ... , dn} и их вероятностями p1, ... , p. Поэтому дискретная с.в. реализуется по тому же алгоритму рис.2.1, только вместо "Исход Ai" в нем нужно записать "d = di" для всех i = 1, ... , n.

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

Первый случай - это когда {0, 1, ... , n - 1} и исходы равновероятны: p1= ... = pn = 1/n. В этом случае все промежуточные операции, включая разбиение интервала (0,1) на n отрезков и поиск среди них того, в который попало значение z, сокращаются за счет применения функции ë xûвычисления целой части от x. И весь алгоритм сворачивается в одну формулу:

d = ë nz û . (3.1)

Действительно, в этом случае при (0,1/n) будет d = 0, при (1/n,2/n) будет d = 1 и т.д. Случаи, когда z попадает точно на границы отрезков, здесь не рассматриваются, так как их вероятность равна нулю.

Ясно, что (3.1) легко приспособить к близким ситуациям. Например, для моделирования игральной кости с числом очков от 1 до 6 можно ее "выбрасывание" реализовать по формуле

d = ë 6zû+ 1, (3.2)

где z получается от датчика БСВ, d - выпавшее число очков.

Применение (3.2) для 60 "выбрасываний кости" компьютером дало последовательность:

321236246263321315464215224214664122142366236246611664533544.

Здесь цифры 1,2,3,4,5,6 выпали соответственно 9,14,9,11,4 и 13 раз, т.е. в процентах это составило 15%, 23%, 15%, 18%, 7% и 22%.

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

В качестве примера построим генератор пуассоновской с.в. Пуассоновская с.в. может принимать значения {0, 1, ... , K, ...}, вероятности которых определяются по формуле

, (3.3)

где a - параметр распределения, a > 0.

Убедимся, что сумма вероятностей исходов равна единице:

. (3.4)

Разобьем мысленно интервал (0,1) на бесконечное число отрезков длиной p0 , p1 , ... , pk, ... . Согласно рис. 3.1 мы должны обратиться к датчику БСВ и для полученного значения z найти отрезок, в который оно попало. Проверить для первого отрезка условие ( p0) можно с помощью неравенства Г0, где Г0 - правая граница интервала (p0), т.е. Г0= р0= е. Если после отрезка (pk) нужно проверять отрезок (pk+1), то для этого используем неравенство z £ Гk+1, где Гk+1 -правая граница отрезка (pk+1) - получается по формуле Гk+1= Гk + pk+1. Вычисление pk+1 будем выполнять не непосредственно по (3.3), а по соответствующему рекуррентному выражению

, (3.5)

чтобы не считать факториалов и степеней.

Алгоритм, соответствующий высказанным соображениям, представлен на рис. 3.2. Переменные Г и р, изменяющиеся при повторении цикла, соответствуют величинам Гk+1 и pk+1. Полученный алгоритм имеет достаточно компактный вид. Что касается быстродействия алгоритма, то его можно охарактеризовать числом N повторений цикла. Очевидно, что N = d + 1, где d - вычисленное случайное значение пуассоновской с.в. Поскольку M(d) = a, то среднее число повторений цикла составляет

M(N) = M(d + 1) = a + 1. (3.6)

Нетрудно определить и дисперсию D(N):

D(N) = D(d + 1) = D(d) = a. (3.7)

Рис.3.2. Схема генератора пуассоновской с.в.

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

Рис. 3.3. Пуассоновская с.в. при а=3..5

 

38. Моделирование непрерывных случайных величин.

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

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


Рис. 2. Графики для определения значения случайного числа
по дискретной и интегральной функции распределения

Тогда искомое случайное число равно (рис. 2б). Это же правило применимо и при задании случайной непрерывной величины интегральной функцией распределения , как показано на рис. 2в. Оно вытекает из теоремы: если случайная величина имеет плотность распределения , то ее распределение
(2)
является равномерным на интервале .

Для некоторых законов распределения (экспоненциальный, Эрланга) получены простые аналитические зависимости . Так, для получения конкретного значения случайного числа с экспоненциальным законом распределения подставим в формулу (2) и плотность распределения:
.
После интегрирования получается .
Отсюда .

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

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

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

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

 

39. Моделирование случайных величин с определенным законом распределения.






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2024 pdnr.ru Все права принадлежат авторам размещенных материалов.