Файл: Конспект лекций Для студентов специальности 080801. 65 - приклад.doc

Решая приведенную систему уравнений, получаем

Определяем значения V_k S_k для каждого из узлов сети:

Таким образом, минимальное среднее время пребывания одного требования составляет: R₀ = 1 + 0,088 + 0,32 = 2,2 с.

Поскольку V₁S₁>V₂S₂>V₃S₃, то потенциальным узким местом в сети является первый узел.

Основываясь на рассматриваемом методе операционного анализа, дадим ответ на некоторые вопросы.

1. Пусть измерениями определено, что X₀ = 0,715 требований/с, а вреднее время пребывания требования в сети составляет 5,2 с. Какое среднее количество устройств обслуживания взаимодействует с се­тью за все время наблюдения?

В соответствии с формулой (2.13) имеем:

2. Можно ли обеспечить среднее время пребывания требований в сети равным 8 с при 30 устройствах обслуживания? Какое макси­мальное среднее время обслуживания требования должен иметь узел 1, чтобы это стало возможным?

В соответствии с формулой (2.13) имеем:

Таким образом, при взаимодействии с сетью 30 устройств, сред­нее время пребывания требования в ней превысит 10с.

Обозначим через S^* допустимое среднее время обслуживания требования. Тогда можно записать

то есть максимально возможное среднее время обслуживания требо­вания узлом 1 составляет 0,047 с. На рис. 2.12 изображены графики для асимптоты среднего времени обслуживания требования.

Пример 2.4. Допустим, что в сеть, кроме требований от уст­ройств обслуживания, поступают еще и требования от узла 3, как по­ казано на рис. 2.13.

Из рис. 2.13 видно, что V₁ = V₃ = 1. Тогда V₁S₁ = 0,05 с, V_lS_l = 0,1 с.

Таким образом, потенциально узким местом для требований уз­ла 3 есть сам узел 3.

Загрузка узла 3, создаваемая требованиями от устройств обслу­живания, составляет

Вторая загрузка узла 3 создается требованиями, которые посту­пают от этого узла (Uз = 0,704).

Таким образом, узел 1 также используется практически полностью.

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

Глава 3. Вероятностное моделирование

3.1. Метод статистических испытаний

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

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

Пример 3.1. Пусть четыре стрелка одновременно стреляют по движущейся цели. Вероятность попадания в цель каждым стрелком равняется 0,5 (попал или не попал). Цель считается пораженной, если в нее попало два или более стрелка. Найти вероятность поражения цели.

Эту задачу можно легко решить методами теории вероятности. Вероятность поражения цели Р_пор = 1 - Р_непор.

Вероятность не поражения Р_непор определяют как число сочета­ний, когда в цель не попал ни один стрелок, плюс попал один из стрелков:

Решим эту задачу методом статистических испытаний. Проце­дуру розыгрыша реализуем подбрасываниям одновременно четырех монет. Если монета падает лицевой стороной, то считаем, что стрелок попал в цель. Обозначим через т число успешных испытаний. Сделаем N испытании, тогда в соответствии с теоремой Бернулли: Р_пор≈m/N.

Пример 3.2. Пусть есть некоторая цель, на которую бомбарди­ровщики сбрасывают п бомб. Каждая бомба поражает область в виде круга радиусом r (рис. 3.1). Цель считается пораженной, если одно­временно бомбами накрыто К процентов площади S. Найти вероят­ность поражения цели.

Аналитически решить эту задачу очень трудно. Покажем, как ее можно решить методом статистических испытаний.

Наложим координатную сетку на всю возможную область попа­дания бомб. Разыграем п точек - координат попадания бомб. Опишем возле каждой точки круг радиусом r (рис. 3.2) и определим заштри­хованную площадь поражения. Если заштрихованная площадь будет составлять К процентов и больше всей площади цели S, то цель счи­тается пораженной, а испытание успешным. В противном случае цель не будет поражена и испытание не успешное.

Выполним N испытаний. Тогда вероятность поражения цели Р_пор≈m/N, где т - количество испытаний, при которых цель была по­ражена.

Методом статистических испытаний можно оценить математи­ческое ожидание и другие вероятностные характеристики. Например, оценку математического ожидания площади поражения цели можно определить как M(s)=1/N∑S_i. При N ->°° эта оценка будет приближаться к математическому ожиданию в соответствии с законом больших чисел. В этом выражении S_i - площадь поражения в i-м испы­тании.

Алгоритм метода статистических испытаний такой:

1. Определить, что собой будет представлять испытание или ро­зыгрыш.

2. Определить, какое испытание является успешным, а какое -нет.

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

4. Обработать полученные результаты статистическими метода­ми и рассчитать статистические оценки искомых величин.

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

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

Для эффективного розыгрыша случайных величин используют генераторы случайных чисел. Такие генераторы строятся аппаратны­ми и программными методами. Наиболее применимыми являются программные методы, которые дают возможность получить последо­вательности псевдослучайных чисел по рекуррентным формулам. Обычно используется мультипликативный конгруэнтный метод, ре­куррентное соотношение для которого имеет вид:

где а и т - некоторые константы. Необходимо взять последнее псевдослучайное число X_i , умножить его на постоянный коэффициент a и взять модуль полученного числа по т, то есть разделить на т и по­лучить остаток. Этот остаток и будет следующим псевдослучайным числом Х_i+1 . Для двоичного компьютера m= 2^g-1, где g- длина раз­рядной сетки. Например, для 32-разрядного компьютера от = 2³¹ -1 = 2147483647, поскольку один разряд задает знак числа.

В языке GPSS World используется мультипликативный конгру­энтный алгоритм Лехмера с максимальным периодом, который гене­рирует 2147483647 уникальных случайных чисел без повторения. Эти числа генерируют специальные генераторы, которые обозначаются RN<№>, где № - номер генератора случайных чисел (может прини­мать значения от 1 до 7). При обращении к этим генераторам выда­ются целые случайные числа в диапазоне от 0 до 999 включительно. При использовании генераторов в случайных функциях распределе­ний случайные числа генерируются в диапазоне от 0 до 0,999999 включительно.