Технология моделирования информационных систем. Методы моделирования систем

Рис. 4. Классификация математических моделей по зависимости переменных и параметров от времени.

 

На рис. 5 показана классификация  математических моделей еще по трем основаниям: по характеру изменения переменных; по особенностям используемого математического аппарата; по способу учета проявления случайностей.

Названия типов (видов) моделей в каждом классе достаточно понятны. Укажем лишь, что в сигнально-стохастических моделях случайными являются только внешние воздействия на систему.

Имитационные модели, как правило, можно отнести к следующим типам:

• по характеру изменения переменных — к дискретно-непрерывным моделям;
• по математическому аппарату — к моделям смешанного типа;
• по способу учета случайности — к стохастическим моделям общего вида.

Рис. 5. Классификация математических моделей.

Имитационные  модели информационных систем

Технология моделирования  случайных факторов

Генерация псевдослучайных  чисел (ПСЧ)

Имитационное моделирование ИС, как правило, предполагает необходимость учета различных случайных факторов — событий, величин, векторов (систем случайных величин), процессов.

В основе всех методов и приемов моделирования названных случайных факторов лежит использование случайных чисел, равномерно распределенных на интервале [0;1].

До появления ЭВМ  в качестве генераторов случайных  чисел применяли механические устройства — колесо рулетки, специальные игральные кости и устройства, которые перемешивали фишки с номерами, вытаскиваемые вручную по одной.

По мере роста объемов  применения случайных чисел для ускорения их моделирования стали обращаться к помощи электронных устройств. Самым известным из таких устройств был электронный импульсный генератор, управляемый источником шума, разработанный широко известной фирмой RAND Corporation. Фирмой в 1955 г. была выпущена книга, содержащая миллион случайных чисел, сформированных этим генератором, а также случайные числа в записи на магнитной ленте. Использовались и другие подобные генераторы — например, основанные на преобразовании естественного случайного шума при радиоактивном распаде. Все эти генераторы обладают двумя недостатками:

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

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

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

Программные генераторы ПСЧ должны удовлетворять следующим требованиям:

• ПСЧ должны быть равномерно распределены на интервале [0; 1] и независимы, т.е. случайные последовательности должны быть некоррелированы;
• цикл генератора должен иметь возможно большую длину;
• последовательность ПСЧ должна быть воспроизводима;
• генератор должен быть быстродействующим;
• генератор должен занимать малый объем памяти.

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

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

Мультипликативный метод

Основная формула мультипликативного генератора для расчета значения очередного ПСЧ по значению предыдущего имеет вид:

,

где а, т — неотрицательные целые числа (их называют множитель и модуль).

Как следует из формулы, для генерации последовательности ПСЧ необходимо задать начальное значение (корень) последовательности, множитель и модуль, причем период (длина) последовательности Р зависит от разрядности ЭВМ и выбранного модуля, а статистические свойства — от выбранного начального значения и множителя. Таким образом, следует выбирать перечисленные величины так, чтобы по возможности максимизировать длину последовательности и минимизировать корреляцию между генерируемыми ПСЧ. В специальной литературе приводятся рекомендации по выбору значений параметров метода, использование которых обеспечивает (гарантирует) получение определенного количества ПСЧ с требуемыми статистическими свойствами. Так, если для машины с двоичной системой счисления задать , , где — число двоичных цифр (бит) в машинном слове; Т — любое целое положительное число; V — любое положительное нечетное число, получим последовательность ПСЧ с периодом, равным . Заметим, что в принципе возможно за счет другого выбора модуля т увеличить длину последовательности до , частично пожертвовав скоростью вычислений. Кроме того, важно, что получаемые таким образом ПСЧ оказываются нормированными, т.е. распределенными от 0 до 1. От выбора корня последовательности ее длина не зависит (при равенстве остальных параметров).

Аддитивный метод

Основная формула для  генерации ПСЧ по аддитивному  методу имеет вид:

,

где т — целое число.

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

.

Смешанный метод

Данный метод несколько  расширяет возможности мультипликативного генератора за счет введения так называемого коэффициента сдвига с. Формула метода имеет вид:

.

За счет выбора параметров генератора можно обеспечить максимальный период последовательности ПСЧ .

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

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

Моделирование случайных событий

В теории вероятностей реализацию некоторого комплекса условий называют испытанием. Результат испытания, регистрируемый как факт, называют событием.

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

Моделирование случайного события заключается в " определении ("розыгрыше") факта его наступления.

Для моделирования случайного события А, наступающего в опыте с вероятностью , достаточно одного случайного (псевдослучайного) числа R, равномерно распределенного на интервале [0;1]. В случае попадания ПСЧ R в интервал событие А считают наступившим в данном опыте; в противном случае — не наступившим в данном опыте. На рис. 6 показаны оба исхода: при ПСЧ событие следует считать наступившим; при ПСЧ — событие в данном испытании не наступило. Очевидно, что чем больше вероятность наступления моделируемого события, тем чаще ПСЧ, равномерно распределенные на интервале [0;1], будут попадать в интервал , что и означает факт наступления события в испытании.

Рис. 6. Моделирование случайных событий.

 

Для моделирования одного из полной группы N случайных несовместных событий , ,…, , с вероятностями наступления соответственно, также достаточно одного ПСЧ R.

Напомним, что для таких  случайных событий можно записать:

.

Факт наступления одного из событий группы определяют исходя из условия принадлежности ПСЧ R тому или иному интервалу, на который разбивают интервал [0;1]. Так, на рис. 7 для ПСЧ считают, что наступило событие А2. Если ПСЧ оказалось равным , считают, что наступило событие .

Рис. 7. Моделирование полной группы несовместных событий.

 

Если группа событий  не является полной, вводят дополнительное (фиктивное) событие , вероятность которого определяют по формуле:

.

Далее действуют по уже  изложенному алгоритму для полной группы событий с одним изменением: если ПСЧ попадает в последний, -й интервал, считают, что пи одно из N событий, составляющих неполную группу, не наступило.

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

Для того чтобы провести моделирование двух зависимых случайных  событий А и В, необходимо задать следующие полные и условные вероятности:

; ; ; .

Заметим, что, если вероятность  наступления события В при условии, что событие А не наступило, не задана, ее можно определить по формуле:

.

Существуют два алгоритма моделирования зависимых событий. Один из них условно можно назвать "последовательным моделированием"; другой — "моделированием после предварительных расчетов".

Последовательное моделирование

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

Моделирование после предварительных  расчетов

Исход моделирования зависимых событий образует полную группу несовместных событий. На этом основан алгоритм моделирования, предусматривающий предварительный расчет вероятностей каждого из исходов и "розыгрыш" факта наступления одного из них, как для любой группы несовместных событий. Рис. 8 иллюстрирует разбиение интервала [0;1] на четыре отрезка, длины которых соответствуют вероятностям исходов наступления событий.

Рис. 8. Разбиение интервала [0;1] для реализации алгоритма