книги / Моделирование систем управления
..pdfРаспределение л близко к нормальному уже при малых п.
Для прикладных задач п = 8-12, а иногда и меньше (4-5). В случае малоразрядных квазиравномерных случайных величин Ç, необходимо учитывать, что дисперсии Ç, равны
1 . 2 4 1
^ ~ 12 2 * - l ’
где А - разрядность вычислительной машины. Следовательно, дисперсия суммы £ равна
2* +1
12 2 * - Г Чтобы добиться более точного воспроизведения нормального закона,
кроме увеличения п можно воспользоваться специальными преобразова ниями.
Если обозначить
* 1 я
4 =7=14,. |
|
л/и 1 |
|
где - случайная величина, равномерно распределённая в |
интервале |
[- A,Â], то случайная величина |
|
л=4* - ^10 4 * -4*з ) |
(5.7) |
будет иметь распределение, достаточно близкое к нормальному уже при п =5. Если применить преобразование
- |
41 |
-10Ç* +156*). |
(5.8) |
|
1344Q.* |
||||
|
|
|
то практически нормальное распределение получим при и = 2.
Вопрос, какое преобразование применять: (5.6), (5.7) или (5.8) - для достижения заданной точности аппроксимации, можно решить в результа те оценки затрат машинного времени, необходимого для реализации ука занных преобразований.
5.3.5. Моделирование приближённого способа преобразования случайных чисел на основе кусочной аппроксимации
законов распределения Пусть закон распределения задан плотностью / ц(х) или функцией
распределения вероятности ^(х ), а интервал возможных значений - [с, (fl. Если область возможных значений не ограничена, то перейдём к соответ
ствующему усечённому распределению. |
|
Разобьём [с, d\ на п интервалов [с*, сы] (А = 0, 1 , я |
-l), с0 = с; |
сп= d. Тогда случайную величину ц можно представить в виде |
|
Л = с*+ Ль |
(5-9) |
где с к- абсцисса левой границы к-го интервала; т|* - случайная величина из интервала [ск, с*н].
Пусть распределение плотности вероятности случайной величины щ имеет вид, представленный на рис. 5.6.
Соотношение (5.9) под сказывает правило формирова ния случайного числа т|. Для того чтобы сформировать слу чайное число, необходимо:
1. Определить случай ным образом величину с*.
2. Из интервала [с*, c*+i] выбрать случайное число т\к.
3. Сформировать случайное число т| по (5.9).
Теперь задача свелась к тому, чтобы, во-первых, наиболее удобным способом разбить интервал [с, d\ на интервалы [с*, см ]\ во-вторых, наибо
лее целесообразно аппроксимировать функцию плотности f A(x) |
на интер |
||
валах [cki сж ]. |
|
|
|
|
При заданной абсолютной погрешности AF воспроизведения функ |
||
ции |
распределения |
F n(x) необходимое число дискретных |
значении |
п= |
1 |
|
|
------. |
|
|
|
|
2AF |
|
|
|
Для машинной реализации наиболее удобной является такая разбив |
||
ка интервала [с, d\, |
при котором вероятность попадания случайной вели |
чины т] на любой интервал [ск, постоянна, т.е. не зависит от к.
Что же касается аппроксимации функции / ц(х) в пределах каждого интервала [с*, c*+i], то в простейшем случае на интервале функцию / ц(х) можно аппроксимировать постоянной величиной ср**. Это означает, что случайная величина % равномерно распределена в интервале [с*, с*ц].
Величины ски ф** вычисляются заранее и помещаются в память ма шины, т.е. в оперативной памяти машины помещается таблица (с*), содер жащая для каждого к= 1,2,..., п значения параметра с* и в общем случае некоторые вероятностные характеристики величины т|*. Существенно, что бы скв таблице располагались в порядке возрастания.
Для расчёта ск и ф** можно поступить следующим образом. Пусть
количество интервалов [ск, Скн], |
на |
которые разбивается [с, d], равно п. |
Функция плотностных) равнаffa ) = nfn(x): |
||
Вероятность выбора любого интервала [ск, ск+{\ равна — , т.е. |
||
|
СЫ |
п |
р*= |
1 |
|
I |
/ w ^ = i . |
С,
По этой формуле определяются последовательно все необходимые значения с*. На интервале небольшой длины [с*, с*н] функцию^*) можно достаточно точно аппроксимировать функцией ср** = const, и формула (5.10) преобразуется в вид:
ф** = п
Алгоритм получения случайного числа т) можно представить сле дующим образом. Из совокупности с равномерным распределением в [0,1] выбираем два числа: Çv-i и Çv.
Çv-i служит для разыгрывания номера £ в соответствии с формулой
и определения соответствующего номеру Означения с*. |
|
^определяет место в интервале [с*,сж ],т.е. ц* = с* + |
-<*), |
и далее формируется число ц (5.9). Рассмотренный приём приближённого преобразования случайных чисел требует небольшого количества опера ций, причём количество операций не зависит от п, т.е. не зависит от точно сти аппроксимации закона распределения. Точность аппроксимации зави сит от объёма данных ск и /к.
Недостаток приближённого способамоделирования
Точность аппроксимации неодинакова во всей области [с, d\. Она за висит от величины^*). При малых/п(х) точность аппроксимации падает. Поэтому число интервалов приходится выбирать с учётом обеспечения за данной точности на интервале с наименьшими значениями что увели чивает объём таблиц ckif^(x).
Можно применить приём комбинирования различных способов ап проксимации fifpc) на различных интервалах [с*, сы], но это уже связано с увеличением количества операций для получения случайного числа ц, т.к. составляющая цкдолжна быть пересчитана в соответствии с выбран ным законом распределения на интервале.
Рассмотрим способы разыгрывания случайных величин более под робно на примерах.
Пример 1. Используя метод Неймана для разыгрывания непрерывной случайной величины, получить последовательность чисел в соответствии с распределением, указанным на рис. 5.7 (40 чисел).
Определим точность обеспечения закона распределения. Площадь А = (6 - а)М= 1,5; площадь В = 1,0; £(д, Ь).
Расчет произведен в следующей последовательности:
1.Выбираем пару случайных чисел у' и у".
2.Находим Çi ~ а +у\b - à)\ Ç2 =
3. Если точка с координата ми (Çj, Ç2) попадает в площадь Д, то она принадлежит распределе
нию/^*).
4. Точность обеспечения за кона распределения можно опре делить по формуле:
р = - = -----!------= — = 0,67.
А М ( Ь - а ) 1,5
Пример 2. Используя метод Неймана для разыгрывания непрерыв ной случайной величины, получить последовательность случайных чисел в соответствии с распределением, указанном на рис. 5.8 (40 чисел).
|
Опишем кривую плотности |
||
|
вероятности. |
Исходная |
функция |
|
состоит из двух ветвей. Обозна |
||
|
чим их Ы х) и Уг(х)- Вся площадь |
||
|
под кривой, |
ограниченной функ |
|
|
циями у\(х) |
и Уг(х\ |
равна 1 |
|
(т.к. площадь под кривой плотно |
||
|
сти вероятности равна полной ве |
||
|
роятности), т.е.: |
|
|
|
) yi(x)dx+ )y2(x)dx=1. |
||
Определимых) и уг(х): |
0,2 |
0,6 |
|
|
|
|
|
/! (* ) - * ,(* - 0.2)2, |
|
|
|
Уг(х) =Ы х -1 ,2 )\ |
|
|
|
В соответствии с рисунком у j(0,6) ~уг(0,6) = 3. |
|
|
|
Тогда |
|
|
|
(0,6 - 0,2) |
0,4Z |
|
|
у 2т |
- = 8,333. |
|
|
кп = |
|
|
|
(0,6 -1,2)2 |
0,62 |
|
|
Определим площадь под кривой S = Sx + S2 (она должна быть равна 1).
0,6
51 = Jl8,75(x - 0 ,2 )2dx = 0,4,
0,2
1»2
52 = |8,333(x -1,2) 2dx « 0,6.
0,2
Далее проводится разыгрывание случайных чисел по алгоритму в примере 1.
5.4.Имитационное моделирование
5.4.1.Сущность имитационного моделирования
Термин «имитационное моделирование» означает, что исследуются такие математические модели, с помощью которых результат нельзя зара нее вычислить или предсказать, поэтому для предсказания поведения ре альной сложной системы необходим эксперимент (имитация) на модели при заданных исходных данных.
Имитация представляет собой численный метод проведения на ЭВМ экспериментов с математическими моделями, описывающими поведение сложных систем в течение заданного времени.
Поведение компонентов сложной системы (СС) и их взаимодействие в имитационной модели обычно описывается набором алгоритмов, реали зуемых на некотором языке моделирования. Все эти описания представ ляют собой программную имитационную модель, которую необходимо сначала отладить и испытать, а затем использовать для постановки экспе римента на ЭВМ. Поэтому под процессом имитации на ЭВМ понимают конструирование модели, испытание модели и применение модели для изучения некоторого явления или проблемы.
При построении имитационной модели вычисляется некоторый функционал, определяемый по множеству реализаций процесса функцио нирования изучаемой сложной системы и характеризующий поведение имитируемого объекта. Наиболее важным для исследователя функциона лом является показатель эффективности системы. Имитируя различные реальные ситуации на имитационных моделях, исследователь получает возможность решить следующие задачи:
1.Оценить эффективность различных принципов управления системой.
2.Сравнить варианты структуры системы.
3.Определить начальные условия и влияние изменения параметров системы на показатели эффективности системы при имитации ее поведе ния.
5.4.2. Цифровое моделирование больших систем
При проектировании сложных объектов, например, технологических комплексов, АСУ производством, вычислительных комплексов и т.д., воз никают задачи, требующие исследования количественных закономерно стей функционирования этих объектов. Для решения таких задач исполь зуются расчётные и экспериментальные методы. Ранее от расчетов не тре бовалось особо высокой точности, т.к. погрешность вычислений компен сировалась увеличением объема натурного эксперимента, созданием ряда опытных образцов и «доведения» изделия в результате доработок.
Если проводится разработка большого комплекса, то использование натурного эксперимента становится проблематичным из-за увеличения за трат времени и средств. Это обусловлено такими особенностями больших систем, как:
-большое число элементов системы;
-сложный характер связей между элементами;
-сложность функций, выполняемых системой;
-наличие сложноорганизованного управления;
-необходимость учёта воздействия окружающей среды;
-высокая степень автоматизации работ в системе и применение ЭВМ в качестве основного управляющего звена.
В существующем многообразии созданных и проектируемых систем класс сложных систем невозможно выделить с достаточной точностью. Отнесение какой либо системы к разряду сложных или простых весьма ус ловно и, в основном, определяется той задачей, которая ставится перед ис
следователем при изучении той или иной системы. Таким образом, одна и та же система, в зависимости от целей ее анализа, рассматривается как сложная или как простая.
Для исследования сложных систем используются аналитические
иимитационные модели.
Ваналитических моделях процессы функционирования элементов
сложной системы записываются в виде некоторых функциональных соот ношений (алгебраических, интегральных, дифференциальных) или логиче ских условий.
Для исследования аналитической модели могут быть применены следующие способы:
1.Аналитический способ - получение в обобщённом виде явных за висимостей для искомых величин.
2.Численный способ - если нет возможности решить имеющееся уравнение в общем виде, но можно получить численный результат при конкретных начальных данных.
3.Качественный способ применяется, когда нет решения в явном виде, но можно найти некоторые свойства решения, например, оценить его устойчивость.
При моделировании на ЭВМ вместо аналитического способа иссле дования используется алгоритмическое описание процесса функциониро вания модели.
Наиболее полное, а в некоторых случаях и исчерпывающее, исследо вание можно провести в том случае, если получены явные зависимости, связывающие искомые величины с параметрами системы и начальными условиями. Однако их удается получить лишь для сравнительно простых систем. Поскольку обобщенная система достаточно сложна, аналитическое исследование сталкивается с непреодолимыми трудностями. Поэтому,
стремясь получить аналитическое решение, идут на упрощение первона чальной модели, чтобы иметь возможность изучать некоторые общие свойства системы.
В зависимости от используемого математического аппарата и при меняемых методов формализации различают следующие виды аналитиче ских моделей: модели математического про1раммирования, сетевые моде ли, модели физических явлений, модели массового обслуживания, модели теории игр и т.д.
В имитационных моделях моделирующий алгоритм приближённо воспроизводит процесс-оригинал в смысле его функционирования во вре мени, причем имитируются элементарные явления, составляющие про цесс, с сохранением их логической структуры и последовательности про текания во времени.
Сущность рассматриваемого метода моделирования состоит в реали зации на ЭВМ специального алгоритма, который воспроизводит формали зованный процесс сложной системы. Моделирующий алгоритм позволяет по исходным данным, содержащим сведения о начальном состоянии про цесса (входной информации) и его параметрах, получить информацию
осостояниях процесса в произвольные моменты времени.
Вмоделирующем алгоритме можно выделить подалгоритмы трёх основных типов, которые выполняют одну из следующих функций:
1.Моделирование какого-либо элементарного подпроцесса иссле дуемого процесса.
2. Учёт взаимодействия элементарных подпроцессов и объединение их в единый процесс.
3. Обеспечение согласованной работы отдельных подалгоритмов при реализации модели на ЭВМ.
Влияние случайных факторов на течение процесса имитируется с помощью случайных чисел с заданными или вырабатываемыми в про цессе моделирования вероятностными характеристиками.
5.4.3. Примеры имитационных моделей
При моделировании процессов необязательно преобразовывать ма тематическую модель в специальную систему уравнений относительно ис комых величин. В ряде случаев достаточно имитировать сами явления, описываемые математической моделью, с сохранением их логической структуры, последовательности чередования во времени, а иногда и физи ческого содержания, с помощью моделирующих установок или ЭВМ.
В противоположность аналитическим и численным методам, содер жание операций, осуществляемых при имитационном моделировании, сла бо зависит от того, какие величины выбрали в качестве искомых.
Пример 1. Рассматривается модель стратегии обслуживания автобу са. Пусть Е - основное состояние автобуса (автобус исправен и осуществ
ляет N рейсов за смену); А - состояние, когда автобус нуждается в мелком профилактическом ремонте (длительность ремонта - один рейс); В - со стояние, когда автобус нуждается в немедленном текущем ремонте дли тельностью в одну смену.
Предположим, что а - вероятность перехода автобуса из состояния Е в состояние А, b - вероятность перехода автобуса из состояния А в состоя ние В. Требуется выбрать одну из следующих стратегий обслуживания автобуса:
1.Стратегия а - как только автобус переходит в состояние А, он ремонтируется.
2.Стратегия р - автобус работает до тех пор, пока не перейдёт в со стояние В.
Лучшая стратегия - та, которая даёт наибольшее число рей сов вдень.
Предполагается, что каждый день автобус выходит на линию в со стоянии Е, т.е. при любой стратегии автобус, заканчивающий N рейсов в состоянии А или В9 ночью ремонтируется.
При моделировании формируется выборка случайного числа Ç и с помощью соответствующей таблицы имитируется состояние, в котором находился автобус в конце рейса. Вначале имитируется один рейс при стратегии а, потом - при р и т.д., после чего подсчитывается среднее чис ло рейсов в день, фактически выполненных автобусом при стратегиях а и р, и их разность.
Метод имитации позволяет производить изменения в модели про стым изменением схемы алгоритма. Полученные результаты обрабатыва ются статистическими методами, и на основе статистических данных при нимается решение о преимуществе одной стратегии перед другой.
Пример 2. Имеется головной компьютер локальной сети и машина на рабочем месте, которая в системе клиент-сервер встает в очередь на об служивание запроса. Если сервер свободен, то он обслуживает клиента, если нет - клиент становится в очередь.
Основа задачи - случайный процесс прихода заявок на обслужива ние. Промежутки между приходами любой последовательной пары зая вок - независимые случайные события, распределённые по некоторо му закону.
В теории массового обслуживания широко используется семейство функций Пуассона
(kt)n -e~u
Рп(0 =
ni
гдер - вероятность появления события; п - произвольное целое; X - некоторая константа.
Второй случайный процесс в этой задаче, никак не связанный с пер вым, определяется последовательностью случайных событий - длительно стей обслуживания каждой заявки.
Втабл. 5.1 в колонке «а» записаны случайные числа - промежутки между приходами заявок на обслуживание (некоторая относительная дли тельность, сформированная по принятому случайному закону).
Вколонке «Ь» записаны случайные числа - длительности обслужи вания (также некоторые относительные числа).
Для определенности взято ятах = 10 и Ьпш= 5.
с-условное время прихода заявок; d - момент начала обслуживания;
е |
- |
конец обслуживания; / - общее время нахождения заявки в системе; |
g |
- |
длительность времени, затраченного заявкой в очереди, в ожидании |
обслуживания; h - время, проведенное сервером в ожидании заявки. Заполнение таблицы ведется по соотношениям:
с\ = 0, сж = ^ + ам> d] = 0, dM = max(c/+b е,),
т.к. начало обслуживания заявки определяется либо временем ее прихода, если сервер свободен, либо временем ухода предыдущей заявки,
е, = di + b i'f = а - chgi = 0, gM =fni - bi+h h\ = 0, hi+l = dM - eh
|
|
|
|
|
|
|
Таблица 5.1 |
|
№ п/п |
а |
Ъ |
с |
d |
е |
/ |
8 |
h |
1 |
0 |
4 |
0 |
0 |
4 |
4 |
0 |
0 |
2 |
2 |
1 |
2 |
4 |
5 |
3 |
2 |
0 |
3 |
10 |
5 |
12 |
12 |
17 |
5 |
0 |
7 |
4 |
1 |
2 |
13 |
17 |
19 |
6 |
4 |
0 |
5 |
б |
3 |
19 |
19 |
22 |
3 |
0 |
0 |
Вопросы, возникающие при обработке результатов моделирования:
1.Каково среднее время нахождения в очереди на обслуживание?
2.Каково среднее значение величины А?
3.Каково распределение случайных величин g и h при заданных распределениях а и Ы
Располагая функцией распределения (пусть даже эмпирической), можно ответить на любой вопрос о характере процесса ожидания в очере ди, например: какова вероятность длительности ожидания в очереди доль ше ml Ответ: вероятность равна отношению площади криволинейной тра пеции, ограниченной графиком плотности вероятности распределения, прямымих = /я и у = 0, к площади всей фигуры.
Пример 3. Рассмотрим одну из самых простых систем массового об служивания.
Система состоит из и линий (каналов, пунктов обслуживания), каж дая из которых может обслужить потребителей. В систему поступают за явки, причём моменты их поступления - случайные. Каждая заявка посту пает на линию № 1. Бели в момент поступления k-н заявки (Г*) эта линия
свободна, то она приступает к обслуживанию заявки, что продолжается /3 минут (/3- время занятости линии). Если в момент 7* линия № 1 занята, то заявка мгновенно передаётся на линию № 2, и т.д. Наконец, если все п ли ний в момент Ткзаняты, то система выдаёт отказ.
Требуется определить, сколько (в среднем) заявок обслужит система за время Г и сколько отказов она даст.
Первый вопрос, возникающий при рассмотрении такой системы, со стоит в том, что представляет собой поток поступающих заявок. Этот во прос должен специально изучаться.
Простейшим потоком (например, поток Пуассона) называется такой поток заявок, когда промежуток времени т между двумя последователь
ными заявками есть |
случайная |
величина, |
распределённая в интервале |
|
(0, оо) с плотностью |
|
|
|
|
|
р(х) = |
|
|
|
Это экспоненциальное распределение. |
|
ао |
||
00 |
оО |
|сО |
|
|
|
| |
|||
Щх) = \xp(x)dx = \хагГш(Ьс = - хе'“ |
+ Je'"*dx = -------= - |
|||
о |
о |
0 |
о |
а о а |
(интегрируем по частям: n = x,d v = at™ ), а - плотность потока заявок.
Розыгрыш т |
|
|
|
|
|
S |
|
jae axdx = yi |
1 |
1 |
|
и 1 |
|
||
0 |
|
|
|
т= - - l n ( l - y ) , |
|
а л |
|
т = — in у. |
|||
а |
|
а |
|
Схемарасчёта. Для каждой линии будем записывать момент, когда |
|||
эта линия освобождается. Момент освобождения /-й линии - г,. |
|||
Начальный момент расчёта - |
поступление первой заявки - Т\ - О, |
т.е. все U= Г - все линии свободны. Время окончания расчёта ТК0И~Т\^Т. Первая заявка поступает на линию Ха 1, т.е. в течение /3 линия будет занята. Поэтому t\ - должны заменить на новое t\ = T\ + *3, добавить 1
к счётчику выполненных заявок и перейти к выполнению второй заявки. Пусть рассмотрено к заявок. Тогда надо разыграть момент поступле
ния (М )-й заявки, тогда по формуле т = - — In у вычисляем дляоче-
а
редного у
Тогда
TkH tjç.
Проверяется условие, свободна ли линия в этот момент времени Если условие выполнено, то, значит, к моменту 7*+| линия уже ос-