Министерство образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования Таганрогский государственный радиотехнический университет
В.И.ФИHАЕВ
МОДЕЛИPОВАHИЕ CИCТЕМ ПРАКТИКУМ
Таганpог 2006
2 УДК 518.5.001.57(075.8) В.И.Финаев. Моделиpование систем. Практикум: Учебное поcобие. Таганpог: Изд-во ТРТУ, 2004. 118 c. ISBN Учебное поcобие пpедназначено для cтудентов, обучающихся по направлению 220200 «Управление и информатика в технических системах». В учебном поcобии приведены оcновные теоpетичеcкие положения, примеры решения задач, методика выполнения лабораторных работ. Табл. 20. Ил. 30. Библиогp.: 28 назв. Печатаетcя по pешению pед.-изд. cовета Таганpогcкого гоcудаpcтвенного pадиотеxничеcкого унивеpcитета. Рецензенты Целых А.Н., докт. техн. наук, профессор директор регионального (областного) центра новых информационных технологий, проректор по информатике ТРТУ Ромм Я.Е, докт. техн. наук, профессор, заведующий кафедрой информатики ТГПИ. ISBN
© Таганрогский государственный радиотехнический университет, 2006
3 CОДЕPЖАHИЕ ВВЕДЕHИЕ 6 1. ИССЛЕДОВАНИЕ ГЕHЕPАТОPА CЛУЧАЙHЫX ЧИСЕЛ 10 1.1. Библиографический список 117
4
ВВЕДЕНИЕ Моделирование систем и процессов требует умения решать задачи, проводить исследования. Необходимы знания методов исследования и решения практических задач. Этому и посвящается данное учебное пособие. При исследовании систем методами системного анализа необходимо построить модель, т.е. реальному объекту ставится в соответствие некоторый математический объект, называемый его моделью. Исследование модели позволяет получить рекомендации относительно поведения реального объекта. Моделирование - это творческий процесс, требующий определенного искусства, математических знаний, практических навыков и умения пpедвидеть pезультат иccледований, поэтому при решении задач моделирования могут быть получены неоднозначные результаты. К задачам дисциплины «Моделиpование cиcтем» относится: - изучение возможноcтей и оcобенноcтей пpименения математичеcкиx языков для pешения пpактичеcкиx задач моделиpования; - изучение оcобенноcтей и получение пpактичеcкиx навыков в облаcти имитационного моделиpования cложныx cиcтем; - выполнение комплекcа лабоpатоpныx pабот c целью пpоведения иccледований и получения навыков в обpаботке cтатиcтичеcкиx данныx. В пеpвом разделе
5
ГЛАВА 1 ЗАДАЧИ ПPАКТИКИ 1. НЕПРЕРЫВНО-ДЕТЕРМИНИСТИЧЕСКИЕ МОДЕЛИ 1.1. Краткие сведения D-схемы [1] или непрерывно-детерминированные модели т.е., строятся на основе непрерывнодетерминистического подхода. Модель выражается в аналитическом виде, в котором связываются функции выходных величин, входных и возмущающих воздействий. Наиболее часто при составлении моделей используется аппарат дифференциальных уравнений (ДУ). ДУ выводятся из конечно-разностных уравнений, которые составляются на основе анализа динамики физических изменений в объекте. Если на вход системы, характеризующейся вектором состояний Z(t)={z1(t),..,zn (t)}, подается входной параметр X(t)={x1(t),..,xm (t)}, а с выхода снимается выходной параметр Y(t)={y1(t),..,yr(t)}, то модель динамической системы в виде обыкновенных ДУ в общем случае задается следующими соотношениями [2, 3]: а) уравнения движения в пространстве состояний: dz i = fi (t1 , z 1 , z 2 , ..., z n , x1 (t), x 2 (t), ..., xm (t)), i = 1,n ; (1) dt б) уравнения для определения выходных параметров: yj(t)=gj(t, z1, z2,…,zm,x1(t),z2(t),…,xm(t)), j = 1,r ; (2)
6 . 2 ) в) начальными 0
0 1
0 2
условиями
при
определении
t=t0,
0 n
Z = (z , z , ..., z ) ; г) значениями (моделью) входного процесса:
( X(t )]tt 0 = {(x 1 (t )]tt 0 ,..., ( x m (t )]tt 0 }. Решением системы уравнения (1) будет уравнение
z(t )] = F(t , t 0 , Z 0 , ( X(t )]tt 0 ), называемое функцией перехода, а решением системы уравнения (2) будет уравнение y(t )] = G(t , t 0 , Z 0 , ( X(t )]tt 0 ), называемое функцией выходов динамической системы. Оба эти уравнения могут быть приняты в качестве моделей. 1.2. Вопросы для самоконтроля математических знаний Предлагается ответить на следующие вопросы, определяющие знания из области ДУ. 1. Что называется порядком ДУ? 2. Что называется обыкновенным ДУ? 3. Что называетяс ДУ? 4. Что называется интегралом ДУ? 5. Какаой вид ДУ называется формой Коши? 6. Какие ДУ называются однородными? 7. Какие ДУ называются нелинейными? 8. Какие ДУ называются уравнениями в полных дифференциалах? 9. Что такое интегрирующий множитель? 10. Что такое система ДУ? 11. Какие методы решения ДУ Вы знаете?
7 12. Какие уравнения в виде ДУ Вам известны? Если вы не смогли ответить на эти вопросы, то рекомендуется изучить соответствующие разделы математического анализа . Аппарат ДУ широко применим для решений задач теории автоматического управления, построения систем автоматического регулирования, следящих систем и т.д. Модели в виде предаточных функций имеют очень широкое распространение. Предлагается ответить на следующие вопросы. 13. Дайте определение придаточной функции. 14. Дайте определение амплитудно-фазавой характеристики системы. 15. Что такое комплексный частотный коэффициент усиления? 16. Сделайте определение весовой (импульснуй) переходной функции. 17. Какие характеристики системы носят название спектральных? Если Вам не удалось ответить на эти вопросы, то следует найти на них ответы в учебниках по основам автоматического управления, в частности, в работах [4 - 6]. 1.3. Примеры решения дифференциальных уравнений 1.3.1. Проверим, что функция является y= x ’ интегралом ДУ 2yy =1. Решение. y ′ = 1 / 2 x , тогда 2yy ′ = 2 x / 2 x = 1 1.3.2. Доказать, что функция S=-t-0,5sin2t есть интеграл d 2s ds ДУ 2 + tgt = sin 2t . dt dt d 2s ds Решение: = −1 − cos 2t , 2 = 2 sin 2t , тогда dt dt
8
d 2s ds + tgt = 2 sin 2t + ( −1 − cos 2t )tgt = sin 2t; 2 dt dt sin2t-cos2t×tgt=0; sin2t-2cost×sint=0. 1.3.3. Найти общий интеграл методом разделения переменной для ДУ вида (х+1)3dy-(у-2)2dx=0. Решение. Уравнение следует свести к виду Р(x,y)dx+Q(x,y)dy=0. Разделим обе части уравнения на (x+1)3(y-2)2, получим dy dx − + = 0. 2 ( y − 2) ( X + 1) 3 Проинтегрируем:
∫ (y - 2)
-2
d(y - 2) - ∫ (x + 1)-3 d(x + 1) = C;
-
1 1 + = C; y - 2 2(x + 1)
1 1 + = C. y - 2 2(x + 1)2 частный интеграл, удовлетворяющий -
1.3.4. Найти
⎛π⎞ начальному условию y⎜ ⎟ = −1 для ДУ ydx+Сtgxdy=0. ⎝ 3⎠ dy = 0, , -ln|cosx| + ln|y|=lnC; Решение. tgx dx + y |y|=C|cosx|, . y=±Ccosx=C1cosx. π π Подставим x = , y=-1, получим: − 1 = C 1 cos , С1=-2. 3 3
1.4. Примеры составления моделей в виде дифференциальных уравнений 1.4.1. Модель электрического колебательного Параметры контура: С - емкость, Lконтура. индуктивность, Uс(t) - напряжение на конденсаторе, IL(t) ток в катушке, Uucm(t) – напряжение внешнего источника.
9
Решение. Запишем в соответствии с законом Кирхгофа:
C
dU C dI = -I L , L L = -Uc + Uист . dt dt
Введем координаты z1=Uc и обозначим Uист/L=x(t), получим z dz1 z dz 2 = - 1 + x(t) . (3) =- 2 , L dt C dt Если Uист=0, то x(t)=0 и система (3) описывает свободные колебания, рассматривая x(t) как сигнал управления, то получим описание динамики колебаний в каждый момент времени t. Решая систему (1.3), можно описать функции z1(t) и z2(t). 1.4.2. Модель размножения микроорганизмов. При изучении популяций предполагают, что скорость размножения пропорциональна числу уже имеющихся. Найти модель роста и определить время, через которое число особей удвоится. Решение. Пусть E(t) число особей в момент времени t. Скорость размножения определим как отношение величины E(t+∆t)-E(t) к величине ∆t при ∆t→0. Тогда, по условию, запишем уравнение: E(t + Δt ) − E(t ) = kE(t ); Δt E(t + Δt ) − E(t ) de(t ) lim = kE(t ); = kE(t ). Δt → 0 Δt dt При начальных условиях t=0, E(t=0)=E0, получим E(t)=E0ekt. Если при t=0 E=E0, то определим время Т, за которое число особей удвоится по формуле: 2E0=E0ekt,2=ekT,T=(1/k)ln2. 1.4.3. Модель динамики боя. Пусть m1 - число боевых единиц красных, m1- число боевых единиц синих, сохранившихся непораженными к моменту времени t, λ1-
10 средняя скорострельность для одной боевой единицы красных,λ2-средняя скорострельность для одной боевой единицы синих. Цели поражаются c вероятностью p1 красными и вероятностью p2-синими. Разработать модель, отображающую динамику боя. Решение. Интенсивности успешных выстрелов определятся как L1=λ1p1,L2=λ2p2. Число выведенных боевых единиц красных ∆m1 за время ∆t составит λ2p2∆tm2, а число выведенных из строя боевых единиц синих ∆m2 за время ∆t составит λ1p1∆tm1. Тогда получим уравнение в частных приращениях ∆m1=λ2p2∆tm2; ∆m2=λ1p1∆tm1. Разделив на ∆t, получим: Δm 1 dm 2 = − λ2p2m2, = − λ1p1m1. Δt dt Взяв пределы при ∆tÆ0, получим дифференциальные уравнения: dm 1 dm 2 = −L 2 m 2 , = -L1m 4 , dt dt которые называются уравнениями Ланчестера. 1.4.4. Модель движения ракеты. Движение ракеты описывается её координатами x и y, проекциями вектора скорости V на координатные оси Vx и Vy. Пусть m - масса ракеты, u величина тяги, φ - угол между направлением тяги и осью Ox, f(u) - секундный расход массы. Необходимо разработать модель, отображающую динамику полета. Решение. Проекции скоростей являются производными от движения по координатам, следовательно, dy dx = Vx , = Vy . dt dt В соответствии с уравнением Ньютона запишем: dV dV m x = Fx + ucosϕ , m y = Fy + usinϕ . dt dt
11 dm = − f (u ). dt Таким образом, моделью движения ракеты является система уравнений:
Расход массы определится уравнением
dx dy dV = Vx , = Vy ; m x = Fx + ucosϕ ; dt dt dt dVy
dm = -f(u) dt dt при начальных условиях x(t0)=x0, y(t0)=y0, m(t0)=m0, Vx(t0)=Vx0, Vy(t0)=Vy0. Управление траекторией ракеты осуществляется за счет регулирования величины и направления силы тяги двигателя, u и φ - управляющие параметры. m
= Fy + Usinϕ;
1.5. Задачи для самостоятельного решения 1.5.1. На входсистемы с передаточной функцией W(p)=1/(1+pT) подан сигнал x(t)=at. Найти аналитическую модель, выражающую выходной сигнал y(t) при условии, что y(t)=y0. 1.5.2. На рис. 1 приведена схема следящей системы. х
z
1 p(T1+1)((T2+1)
y
Рис. 1 Найти модель в виде частотной характеристики системы и определить частоту автоколебаний при условии, что идеальное реле имеет характеристику ϕ(v)=lsgnv. 1.5.3. На рис. 2 приведена структурная схема резонансного усилителя. Найти аналитическую модель в виде переходной функции h(t) усилителя, если на вход
12 модулятора (М) подан сигнал x(t)=1(t). В модуляторе сигнал x(t) модулируется синусоидальным колебанием с частотой w0, коэффициент усиления усилителя (У) равен k. Контур настроен в резонанс, т.е. I / LC = w 0 , и dx 2 r << L / C , x 2 (t ) = 0, (0) = 0, x 1 (0) = 0. Составляю dt щие с частотами w>w0 сглаживаются фильтром демодулятора (Д). X1
U2
x2
W0
W0 X1
x2
Рис. 2 1.5.4. Задана следящая система, структурная схема которой приведена на рис. 3. W1 (p )
160 0,02p + 1
W2 (p )
0,1 p(0,1p + 1)
Рис. 3 Найти аналитический вид модели в виде реакции на единичный управляющий импульс (весовую функцию) v(t)=h(t)/t, где h(t) – переходная функция. 1.5.5. Найти модель случайного синхронного телеграфного сигнала в виде энергетического спектра G(f) при следующих условиях. На рис. 4 показаны реализации сигнала.
13 t′ = t + τ
τ
t = nT − Δt
Δt
Рис. 4 Реализации сигнала имеют случайный равномерно распределенный сдвиг Δt относительно начала координат, принимают в дискретные моменты времени Т значения ±h с вероятностью 0,5 независимо от того, какое значение сигнал имел на предыдущемучастке. Сигнал имеет корреляционную функцию Bx=h2(1-|τ|/T). 1.5.6. Найти аналитическую модель, описывающую надежность функционирования объекта в виде вероятности P(t) того, что рассматриваемый объект будет исправен в t при следующих условиях. момент времени Интенсивность отказов λ и интенсивность ремонта μ постоянны. Поток оказов описывается законом Пуассона, время ремонта распределено по экспоненциальному закону. 1.5.7. Определить модель в виде аналитического уравнения, позволяющегго выразить зависимость между временем t движения снаряда в канале ствола орудия и пройденным расстоянием l по каналу, если известно, что al n dl v= , v = , n < 1, n b+l dt a и b некоторые постоянные. 1.5.8. Определить аналитическую модель движения моторной лодки для времени t>t0 со скоростью
14
v=10 км/час. В момент времени t0 мотор выключили и через t=t0+20 сек скорость лодки уменьшилась до v=6 км/час.Сила сопротивления воды пропорциональна скорости движения лодки. Предлагается найти скорость лодки через две минуты после остановки мотора. Найти расстояние, пройденное лодкой в течение одной минуты после остановки мотора. 1.5.9. Составить аналитическую модель в виде ДУ первого порядка, выражающую зависимость температуры батареи отопления от времени, отсчитываемого от начального момента при следующих условиях. Начальная температура тела Т равна температуре окружающей среды; батарея получает тепло со скоростью подачи αψ(t), где α постоянная теплоемкость батареи. Батарея отдает тепло окружающей среде. Скорость охлаждения пропорциональна разности между температурами тела и среды. 1.5.10. Найти математическую модель движения тела с массой m=1 в виде зависимости пройденного пути S от времени при условии, что на тело действует сила, пропорциональная времени с постоянным коэффициентом пропорциональности k1, а среда, в которой движется тело, оказывает противодействие, пропорциональное скорости тела с постоянным коэффициентом пропорциональности k2. 1.5.11. Тело массой 200 Г подвешано на пружине. Движение начато после вытягивания пружины на 2 см. Тело отпущено без толчка, т.е. начальная скорость равна нулю. Сила напряжения пружины при растяжении на 2 см равна 10 кГ. Если тело движется со скоростью 1 см/с, то среда оказывает сопротивление 0,1 Г. Сопротивление среды пропорционально скорости движения. 1.5.12. Скорость роста популяций микроорганизмов пропорциональна их количеству и количеству
15 питательного состава с коэффициентом пропорциональности k>0. Питательный состав убывает со скоростью, пропорциональной начальному количеству микроорганизмов с коэффициентом пропорциональности k1>1. В начальный момент времени t0=0 имелось А0 микроорганизмов и В0 питательных веществ. Разработать аналитическую модель, позволяющую выразить зависимость количества А микроорганизмов и количества В питательного состава от времени.
1.6. Ответы на задачи 1.5.1. y (t ) = a[t − T(1 − e 1.5.2. w 0 =
−
t T
)] + y 0 e
1
−
t T
.
. T1 T2 1.5.3. h(t)=k(1-e-βt)1(t), где β=L/2r. 1.5.4. w(t)=2,9e -53,4t+13,2e-3,29tsin (11,8t-0,23). sin 2 ( πfT) 1.5.5. G (f ) = h 2 T . ( πfT ) 2 μ + Cexp[-(λ + μ)t] 1.5.6. p(t) = , где C - произвольная λ +μ константа.
1 bl1-n ). 1.5.7. t = (l + a 1-n 1.5.8. 0,467 км/час, 85,2 м. 1.5.9. t = T0 + e
− kt
t
∫ ϕ(t )e 0
kt
dt .
16 1.5.10. s = s 0 + Ce
− k 2t
−
k1 k t + 1 t2, k2 2k 2
s0-начальный
путь. 1.5.11. s=e-0,245t[2cos(156,6t)+0,00313sin(156,6t). 1.5.12. A =
kα 2 1 - βeαkt 2 1- βeαkt [1 - ( ) ] B = α ; ; 2k 1 1 + βeαkt 1 + βeαkt α = B02 +
α - B0 2k 1 A0 ; β = . α + B0 k
17
2. АВТОМАТНЫЕ МОДЕЛИ 2.1. Дискретно-детерминированные модели Дискретно-детерминироованные модели, или F-схемы [1], стороятся с применением математического аппарата теории детерминированных автоматов [7, 8]. Автомат описывается набором: A=<X,Y,Z,φ,ψ,z0>, где X, Y, Z - множества входных сигналов, выходных сигналов и состояний соответственно; z0 - начальное состояние автомата. Автомат функционируетв дискретные моменты времени, а по характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные. Для того, чтобы описать модель объекта в виде автомата, следует задать множества X, Y, Z, которые будут определены входными сигналами объекта, выходными гигналами и состояниями. Следует определить отображение Z×X→Z и отображение Z×X→Y, которые позволят задать функции переходов и выходов. Предлагается ответить на следующие контрольные вопросы, которые определяют минимальный требуемый уровень подготовки, необходимой для разработки дискретно-детерминированных моделей. 1 Какие автоматы называются автоматами первого и второго родов? 2 Какие автоматы называются автоматами Мили и Мура? 3 Какой автомат называется автономным? 4 Какой автомат называется инициальным? 5 Какие автоматы называются асинхронными и синхронными? 6 Перечислите способы задания автоматов.
18 7 Какие автоматы называются автоматами с памятью и без памяти? 8 Какое состояние автомата называется устойчивым? 9 Приведите пример табличного задания автомата. 10 Приведите пример графического задания автомата. Если вы знаете ответы на перечисленные вопросы, то можно приступить к дальнейшему изучению материала данного раздела, в противном случае следует изучить соответствующие разделы работ [7, 8].
2.2.Примеры составления моделей в виде детерминированных автоматов 2.2.1. Модель делительного устройства (ДУ) прокатного стана. Разработать модель ДУ для распределения труб по диаметру между линиями прокатного стана. Схематическое представление прокатного стана показано на рис. 5. За один такт движения подающего устройства становится известным диаметр d i (i = I,m) трубы, поступившей к ДУ. Для обработки труб диаметром d1 имеется технологическая группа из ai линий. Линии обозначены в виде двоек (i,k), где i - номер группы, k номер линии в группе (k = I , a i ) . Линии загружаются в порядок очереди. Пусть загружена линия (i,pk) в момент времени tj. При поступлении в такте tj+1 трубы диаметром di она будет направлена в линию (i,pk+1), если k
. Множество входных сигналов представим в виде X={x1,x2,x3}, где xi - сигнал,
19 свидетельствующий о поступлении на вход ДУ трубы диаметром di. (1,1) (1,2)
…………. (1,а1) Делительное устройство
(2,1) (2,2)
…………. (2,а2) (m,1) (m,2) (m,am)
Рис. 5 Выходной сигнал определяется множеством Y={(i,pk)}, i=1,2,3, k=1, ai, и указывает, в какую линию i-й группы должна быть направлена труба. Множество состояний z содержит a1×a2×a3=12 векторов Z={z1,z2,z3}, причем zi есть номер занятой pk линии в i-й группе. Функцию переходов φ(t) формально опишем в виде выражения
⎧(z (t - 1) + 1 mod a i , i = x(t); z i (t) = ⎨ i i ∉ x(t). ⎩z i (t - 1), Функцию выходов φ(t) зададим в виде y(t)={x(t),[(zx(t-1)+1)modax]}, где под zx понимается координата zi при i=x(t). Задание функции переходов приведено в табл. 1. Задание функции выходов приведно в табл. 2. Под
20 состоянием z0 в начальный момент времени t0 можно понимать вектор z0=(0,0,0). Таблица 1 Задание функции переходов Z X (1,1,1,) (2,1,1) (1,2,1) (1,3,1) (2,2,1) (2,3,1) x1 (2,1,1) (1,1,1) (2,2,1) (2,3,1) (1,2,1) (1,3,1) x2 (1,2,1) (2,2,1) (1,3,1) (1,1,1) (2,3,1) (2,1,1) x3 (1,1,2) (2,1,2) (1,2,2) (1,3,2) (2,2,2) (2,3,2) X Z (1,1,2) (2,1,2) (1,2,2) (2,2,2) (1,3,2) (2,3,2) x1 (2,1,2) (1,1,2) (2,2,2) (1,2,2) (2,3,2) (1,3,2) x2 (1,2,2) (2,2,2) (1,3,2) (2,3,2) (1,1,2) (2,1,2) x3 (1,1,1) (2,1,1) (1,2,1) (2,2,1) (1,3,1) (2,3,1) Таблица 2 X x1 x2 x3 X x1 x2 x3
(1,1,1,) (1,2) (2,2) (3,2) (1,1,2) (1,2) (2,2) (3,1)
Задание функции выходов Z (2,1,1) (1,2,1) (1,3,1) (1,1) (1,2) (1,2) (2,2) (2,3) (2,1) (3,2) (3,2) (3,2) Z (2,1,2) (1,2,2) (2,2,2) (1,1) (1,2) (1,1) (2,2) (2,3) (2,3) (3,1) (3,1) (3,1)
(2,2,1) (1,1) (2,3) (3,2)
(2,3,1) (1,1) (2,1) (3,2)
(1,3,2) (1,2) (2,1) (3,1)
(2,3,2) (1,1) (2,1) (3,1)
2.2.2. Модель автоматического склада. Склад представляет собой хранилище из m стеллажей. На каждом из стеллажей хранятся изделия i-й номенклатуры (i = I , m ). Содержимое стеллажей меняется в такты времени t
21 поступления или изъятия изделий. Предлагается разработать модель в виде конечного автомата Мура. Решение. Модель представим в виде автомата A=<X,Y,Z,φ,ψ,z0>. Множество входных сигналов представим в виде (m+1)-мерного вектора X={x1,x2,x3,…,xm,μ}, где μ=+1 при поступлении xi изделий i-й номенклатуры на склад, μ=-1 при выдаче xi изделий со склада. Множество состояний Z есть также вектор Z={z1,z2,…,zm}, где zi - количество изделий i-й номенклатуры на складе (остаток изделий). Множество выходных сигналов Y будет совпадать с множеством Z. Функцию переходов формально опишем в следующем виде: z i (t ) = z i (t − 1) + μx i (t ), i = 1, m. Функцию выходов ψ(t) для автомата Мура определим в виде yi(t)=zi(t). Функция переходов φ(t) не приведена из-за большой мощности множества Z.
2.3. Задачи для самостоятельного решения. 2.3.1. Разработать автоматную модель одноканальной системы массового обслуживания заявок μ - величины постоянные. Предлагается под состояниями объекта понимать занятость и незанятость обслуживанием, а модель представить в виде автономного автомата Мура. Описать автомат A=<X,Y,Z,φ,ψ,z0>. 2.3.2. Разработать модель устройства, в котором осущетвляется последовательное переключение трех цепей (например, цепей управления включением цветных ламп: красной, желтой, зеленой). Представить модель в виде автомата Мура A=<X,Y,Z,φ,ψ,z0>. Задать автомат, привести табличное задание функций переходов φ и выходов ψ.
22 2.3.3. Разработать автоматную модель устройства, управляющего переключением ламп типа «бегущая волна». Всего ламп двадцать, одновременно может гореть в одном такте пять ламп. Переключение происходит следующим образом. В первом такте горят с первой по пятую лампы, во втором такте горят со второй по шестую лампы, а в третьем такте горят с третьей по сеедьмую и т.д. Задать автомат в виде A=<X,Y,Z,φ,ψ,z0>. Описать множества, задать функции переходов φ и выходов ψ. 2.3.4. На рис. 6 приведено задание автомата МУРА в виде графа. X1
X2 Z1
Z2
X2
X2 X1
X3
Z4
X3
X3
X2
Z3 X3
X1
X2
X1 Z5
Рис. 6 Выполнить задание автомата в виде A=<X,Y,Z,φ,ψ>. Определить множества X,Y,Z и привести табличное описание функций переходов φ и выходов ψ. 2.3.5. В табл.3 задана функция переходов автомата Мура. Задать функцию переходов φ в виде графа. Таблица 3
23 X x1 x2 x3 X4
Задание функции переходов Z (z1,z2,z3) (z2,z3,z4) (z3,z4,z5) (z2,z3,z4) (z3,z4,z5) (z4,z5,z6) (z3,z4,z5) (z4,z5,z6) (z1,z2,z3) (z4,z5,z6) (z1,z2,z3) (z2,z3,z4) (z1,z2,z3) (z2,z3,z4) (z3,z4,z5)
(z4,z5,z6) (z1,z2,z3) (z2,z3,z4) (z3,z4,z5) (z4,z5,z6)
2.3.6. Разработать автоматную модель устройства сортировки шариков различных диаметров (d1, d2, d3). Шарики движутся по транспортеру, диаметры определяются фотоэлектрическими датчиками. В зависимости от диаметра шарика выбирается одно из трех разветвлений транспортера. Автомат представить в виде A=<X,Y,Z,φ,ψ>.Функции переходов φ и выходов ψ задать в виде таблиц. 2.3.7. Разработать автоматную модель робота, который берёт детали с транспортера и укладывает их на транспортные тележки. Робот функционирует в дискретные такты времени и проходит последовательно следующие состояния: z0 - состояние позиционирования перед захватом детали с транспортера; z1 - состояние захвата детали; z2 - состояние движения к тележке; z3 - состояние позиционирования перед укладкой детали; z4 - укладка детали; z5 - состояние движения к транспортеру. Состояния циклически сменяют друг друга в процессе функционирования. Задать автомат в виде А=<Х,Y,Z,ϕ,ψ,z0>. Описать функции переходов ϕ и выходов ψ в виде таблиц. 2.3.8. Для примера 2.2.1 разработать алгоритм имитационной модели. 2.3.9. Для примера 2.2.2 разработать алгоритм имитационной модели.
24 2.3.10. Кодами x1 и x2 сигналов (x1,x2) задается положение точки на поверхности. Найти автоматную модель устройства задания точки. Модель может быть представлена, в виде автомата Мура А=<Х,Y,Z,ϕ,ψ>. Мощность множества, содержащего всевозможные пары (x1,x2) равна тридцати двум. Мощность множества X1 (x1 ∈ X1) равна четырем. Мощность множества X2 (x2 ∈ X2) равна восьми. 2.3.11. Разработать автоматную модель подъемника, который управляется тремя кнопками: кнопка «Стоп», кнопка «Движение вверх», кнопка «Движение вниз». Определить автомат А=<Х,Y,Z,ϕ,ψ,z0>. Задать функции переходов ϕ и выходов ψ в табличном виде. 2.3.12. Разработать автоматную модель устройства контроля прохода через турникет. Проход через турникет возможен, если есть разрешение от магнитного датчика. В противном случае при попытке осуществить проход срабатывает фотореле и турникет блокируется. Задать автомат в виде набора А=<Х,Y,Z,ϕ,ψ>. Задать функции переходов ϕ и выходов ψ в табличном виде.
2.4. Ответы на задачи 2.3.1. Аналитическое задание функции переходов: ⎧z 0 , t < t 0 , (ka + b < t < (k + 1)a); z(t) = ⎨ ka < t < ka + b, ⎩z1 , где k=0,1,2,…, t0 - начальный момент времени, a=1/λ, b=1/μ. Задача имеет смысл при λ/μ<1. 2.3.2. X=|1|, |Z|=3, |Y|=3, y(t)=z(t), функция переходов реализуется из циклического графа с тремя состояниями. 2.3.3. X=|1|, |Z|=20, |Y|=20, y(t)=z(t). 2.3.6. |X|=3, X={x1,x2,x3,}, |Z|=3, Z={z1,z2,z3}, |Y|=3, Y={y1,y2,y3}, zi(t+1)=xi(t), x(t)=xi(t), yi(t)=zi(t).
25 2.3.7. X=|1|, Z={z1,z2,z3,z4,z5,z0}, y(t)=z(t). 2.3.11. |X|=3, |Z|=3, Y={y1,y2}. 2.3.12. |X|=2, |Z|=2, |Y|=2. Примечание. Учитывая неоднозначность вариантов решения некоторых задач, ответы могут не совпадать с полученными Вами решениями. Итоговая оценки правильности решения осуществляется преподавателем.
2.5. Дискретно-стохастические модели В качестве математической схемы, используемой при построении дискретно-стохастических моделей или Рсхемы [1], применяются вероятностные автоматы (ВА), которые являются обобщением в понятии автомата. Рассмотрим кратко определения ВА [3, 8]. Функционирование ВА происходит в дискретные моменты времени (такты) t=0,1,2,… . Задается ВА набором BA=<X, Y, Z, P0, {P(zt,yt/zt-1,xt)}>, где: X={x1,x2,…,xm} множество входных сигналов; Y={y1,y2,…,yr} – множество вероятностей состояний; P 0 = {P10 , P20 , ...Pn0 } – вектор начальных состояний; Pi0 - вероятность того, что в такте t0=0 BA будет находиться в состояниии zi; P{zt,yt/zt-1,xt) матрица (система) условных вероятностей, заданных для каждой пары (zt-1,xt) ∈ Z×X, которые определяют вероятность того, что ВА в такте t будет в состоянии zt и выдаст сигнал yt при условии, что на вход подан сигнал xt, а предыдущем такте t-1 автомат был в состоянии zt-1. Пpи моделиpовании cледует опpеделить функции пеpеxодов и выxодов. Функцию пеpеxодов cледует задать в виде cтоxаcтичеcкой матpицы ||P(zt(t)=z(t)/zt-1xt)||. Функция выxодов опpеделяет выxодные параметры и задаетcя в виде cтоxаcтичеcкой матpицы ||P(yt/zt-1,xt,zt)||. Опpеделим уcловную веpоятноcть P(yt/zt-1,xtzt).
26
P(zt,yt/zt-1,xt)=P(zt/zt-1,xt)P(yt/zt-1,xt,zt). Пpоcуммиpуем пpавую и левую чаcти по вcем значениям yi и получим ∑ P(z t , y t /z t -1 , x t ) = P(z t /z t -1 , x t )∑ P(y t /z t -1 , x t , z t ). yi
yi
Cумма в пpавой чаcти pавна единице, так как это cумма веpоятноcтей полной гpуппы cобытий. Тогда веpоятноcть P(yt/zt-1,xt,zt) опpеделитcя фоpмулой
P ( y t / z t −1 , x t , z t ) =
P ( z t , y t / z t −1 , x t ) . ∑ P ( z t , y t / z t −1 , x t ) yi
Клаccификация ВА завиcит от cпоcобов опpеделения веpоятноcти P(yt/zt-1,xt,zt) (функции выxодов) и веpоятноcти P(yt/zt-1,xt) (функции пеpеxодов). Веpоятноcтный автомат называетcя автоматом пеpвого pода (автомат Мили), еcли функция выxодов завиcит только от пpедшеcтвующего cоcтояния и вxодного cигнала в данном такте вpемени: P(yt/zt-1,xt,zt)=P(yt/zt-1,xt). Веpоятноcтный автомат называетcя автоматом втоpого pода, еcли функция выxодов завиcит только от cоcтояния и вxодного cигнала в данном такте вpемени: P(yt/zt-1,xt,zt)=P(yt/xt,zt). Веpоятноcтный автомат называетcя пpавильным, еcли функция выxодов завиcит только от cоcтояния в пpедшеcтвующем такте и cоcтояния в текущем такте вpемени: P(yt/zt-1,xt,zt)=P(yt/zt-1,zt). Cущеcтвует пpавильный ВА пеpвого pода, у котоpого P(yt/zt-1,xt,zt)=P(yt/zt-1), и пpавильный веpоятноcтный автомат втоpого pода, у котоpого P(yt,zt-1,xt,zt)=P(yt/zt), (автомат Муpа).
27 Веpоятноcтный автомат называетcя автоматом c детеpминиpованной функцией пеpеxода, еcли cоcтояние в каждый такт вpемени однозначно опpеделяетcя чеpез пpедшеcтвующее cоcтояние и вxодной cигнал: ⎧1, z t = f ( z t −1 , x t ), P( z t / z t −1 , x t ) = ⎨ ⎩0, z t ≠ f ( z t −1 , x t ). Веpоятноcтный автомат будет называтьcя автоматом c детеpминиpованной функцией выxодов, еcли выxодной cигнал однозначно задаетcя чеpез пpедшеcтвующее и текущее cоcтояние и вxодной cигнал:
⎧1, P( y t / z t −1 , x t , z t ) = ⎨ ⎩0,
y t = ϕ( z t −1 , x t , z t ), y t ≠ ϕ( z t −1 , x t , z t ).
Веpоятноcтный автомат пеpвого pода c детеpминиpованной функцией пеpеxодов называетcя автоматом cо cлучайными pеакциями. Веpоятноcтный автомат пеpвого pода c детеpминиpованной функцией выxодов называетcя маpковcким. Пpавильный ВА втоpого pода c детеpминиpованной функцией выxодов называетcя автоматом c отмеченными cоcтояниями. Каждому cоcтоянию cоответcтвует cвой вxодной cигнал. Пpичем, еcли у этого ВА cтоxаcтичеcкое отобpажение элементов множеcтва Z в элементы множеcтва Y задаетcя взаимно однозначно, то ВА называетcя абcтpактным и для него доcтаточно pаccматpивать алфавит внутpенниx cоcтояний. Абcтpактный ВА задаетcя в виде набоpа ВА=<X,Z,P0{P(zt/zt-1,xt}>. Еcли мощноcть множеcтва Z pавна единице, то такой автомат называетcя автоматом без памяти. Еcли мощноcть множеcтва X pавна единице, то такой автомат называетcя автономным.
28 Автономный абcтpактный ВА называетcя диcкpетной цепью Маpкова и задаетcя в cледующем виде: ВА=. Предлагаем ответить на следующие вопросы, контролирующие уровень подготовки, необходимый для разработки моделей в виде Р-схем. 1. Дайте определение ВА. 2. Какой конечный автомат называется автоматом первого рода? 3. Какой конечный автомат называется автоматом второго рода? 4. Какой автомат называется правильным? 5. Каким образом определяются детерминированные функции выходов и переходов? 6. Какой автомат называется автоматом со случайными реакциями? 7. Какой ВА называется автоматом с отмеченными состояниями? 8. Какой автомат называется абстрактным? 9. Какой автомат называется дискретной цепью Маркова? 10. Приведите табличной задание функций переходов в виде распределений вероятностей P(zt,yt/zt-1,xt). 11. Приведите табличное задание функций переходов в виде распределений вероятностей P(zt/zt-1,xt). 12. Дайте определение композиции двух автоматов. 13. Приведите табличное задание функций выходов в виде распределений вероятностей P(yt/zt-1,xt). 14. Приведите табличное задание функций переходов в виде распределений вероятностей P(zt/zt-1). 15. Приведите табличное задание функций вфходов в виде распределений вероятностей P(yt/zt).
29 При незнании ответов на данные вопросы предлагаем обратиться к изучению соответствующих разделов в работах [3, 7, 8]. При разработке автоматных моделей стохастических объектов рекомендуется определить множества X, Y, Z, закон изменения тактов моделирования, а также задать распределения вероятностей P(zt/zt-1,xt) и P(yt/zt-1,xt).
2.6. Примеры разработки моделей в виде вероятностных автоматов 2.6.1. Время наработки на отказ устройства определяется экспоненциальным распределением А(t)=1-e-αt. Время восстановления устройства после отказа определено распределением В(t)=1-е-βt. Разработать автоматную модель, описывающую функционирование устройства по тактам моделирования ∆t→0 с поцизий надежности функционирования. Решение. Так как поток отказов определяется экспоненциальным распределением, то вероятность того, что система откажет за время ∆t будет равна Pотк(∆t)=α∆t. Вероятность того, что система будет восстановлена за время ∆t определится Pв(∆t)=β∆t. Представить модель можно в виде ВА c детерминированной функцией выходов, причем это будет ВА c отмеченными состояниями. В силу того, что отображение ϕ:Z→Y взаимооднозначно, то это также и абстрактный ВА. Зададим ВА в виде ВА=<X,У,Z,Р(zt/zt-1)>, P0>, X={x1}, Z={z0,z1},Y={y0,y1}, где z0 - исправное состояние устройства, z1 - неисправное состояние устройства, y0(t)=z0(t), y1(t)=z1(t). P(zt/zt-1)=P(yt/zt-1) зададим в виде матрицы переходных вероятностей.
30 Pij =
P00
P01
P10
P11
,
где элементы матрицы: P00 - вероятность перехода из состояния z0 в состояние z0; P10 - вероятность перехода из состояния z1 в состояние z0; P11 - вероятность перехода из состояния z1 в состояние z1; Р01 - вероятность перехода из состояния z0 в состояние z1. Определим P01=Pотк=α∆t, P10=Pв=β∆t, P00=1-α∆t, P11=1β∆t. Вероятность выбора начального состояния зададим произвольным распределением P 0 = P00 , P10 , где P00 вероятность того, что в момент времени to=0 устройство исправно, P10 - вероятность того, что в момент t0=0 устройство неисправно. 2.6.2. На вход системы поступают сообщения трех потоков, каждый из которых имеет пуассоновское распределение. Интенсивности входных потоков определены параметрами α1, α2, α3 соответственно. Разработать автоматную модель суммарного потока сообщений на входе системы. Решение. Для ∆t→0 вероятность Pi(∆t) поступления заявок i-го потока за время определится Pi(∆t)≈αi∆t, i = 1,3 . Так как сумма трех потоков даст также поток пуассоновский, то вероятность поступления заявок за время ∆t определится: Pn(∆t)=(α1+α2+α3)∆t. Моделью входного потока заявок может служить автомат в виде ВА=<Х,У,Z,z0,Р(zt/zt-1)>, где X={x1}; Z={z0,z1} - состояния не поступления и поступления заявок собственно; Y={y0,y1}, y0(t)=z0(t), y1(t)=z1(t). Р(zt/zt-1) задается в виде
Pij =
P00
P01
P10
P11
где P10=P00=1–Pn, P11=P01=Pn.
,
31
2.7. Задачи для самостоятельного решения 2.7.1. Разработать автоматную модель одноканальной системы массового обслуживания (СМО). На вход СМО поступает пуассоновский поток заявок с интенсивностью λ. Время обслуживания удовлетворяет экспонециальному распределению с интенсивностью обслуживания μ. Максимальное число заявок в очереди – четыре. Изменения состояний в СМО рассматривать за дискретные моменты времени Ut→0. Модель может быть представлена в виде автономного абстрактного автомата. Определить вероятности перехода и вероятности финальных состояний СМО. 2.7.2. На вход системы поступаю три потока сообщений. Известны вероятности Pi поступления за время Ut сообщений i-х потоков, причем P1=0,1; Р2=0,2; Р3=0,4; вероятность непоступления сообщения за время Ut Р0=0,3. Разработать автоматную модель потока сообщений. Привести классификационную характеристику выбранного автомата. 2.7.3. Канал передачи дискретной информации описывается биномиальной моделью ошибок. Известна вероятность искажения символа кода Ро=10-2. Информация передается корректирующим кодом длиною шесть символов, обнаруживающим две ошибки. Разработать автоматную модель, применив правильный автомат второго рода. 2.7.4. На рис. 7 приведен график переходов некоторой системы. Цифрами над дугами обозначены вероятности переходов.
32
Z1
Z2
Z4
Z3
Рис. 7 Каким автоматом можно задать модель этой системы? Привести классификационную характеристику автомата. Определить финальные вероятности состояний Pi = P1 , P2 , P3 , P4 . 2.7.5. На поверхности осуществляется случайный поиск точки А. Схема поверхности и искомая точка А показана на рис. 8. А В Рис. 8 Переход в любом напрвлении по горизонтали или по вертикали равновероятен. Начальная точка поиска В. Разработать автоматную модель процессов поиска и найти вероятность нахождения точки А как финальную
33 вероятность состояния. При решении системы линейных уравнений целесообразно использовать ЭВМ. 2.7.6. На вход узла коммутации (УК) поступают сообщения с различными адресами назначения. УК имеет четыре исходящих направления коммутации. Адреса назначений сообщений разбиты на четыре множества А1,А2,А3,А4, Аi∩АJ=∅, j, i = 1,4, i≠j. Сообщения, адреса назначения которых принадлежат множеству Аi, передаются по i-му направлению коммутации с вероятностями, описываемыми матрицами
Pi = P1i , P2i , P3i , P4i . Разработать
автоматную
модель
устройства выбора напрвлений коммутации сообщений, сделать классификационную характеристику автомата. 2.7.7. Поток деталей поступает для обработки на три станка, каждый из которых выполняет одну и ту же операцию, но с различным временем выполнения. Поток деталей является пуассоновским с параметром, равным α, а время выполнения операции на i-м станке описывается экспонециальным распределением с параметром μi. Разработать автоматную модель, позволяющую исследовать функционирование системы по тактам Ut→0. В качестве состояний взять множество Z={zo,z1,z2,z3}, где z0 - состояние, в котором все станки не заняты работой; z1 состояние, в котором занят работой один из станков; z2 состояние, в котором заняты работой любых два станка; z3 - состояние, в котором заняты работойвсе три станка. Модель представить в виде марковского автомата с функцией переходов, заданной матрицей
34 P00 P01 P02 P03 Pij =
P10 P11 P12 P13 . . .
. . .
.
P30 P31 P32 P33
Выразить вероятности Pij через параметры α и μi, i = 1,3. Найти вероятность того, что все станки будут простаивать, и вероятность того, что все станки будут заняты работой. 2.7.8. По каналу передачи дискретной информации передаются сообщения кодом длины n. При передаче в кодовых комбинациях появляются ошибки кратности i, i = 0, n. Какой вид автоматной модели можно применить для описания процесса. Опишите модель в общем виде.
2.8. Ответы на задачи. 2.7.1.
P00 P01 0 0 0 0 P10 P11 P12 0 0 0 Pij =
0 P21 P22 P23 0 0 0 0 P32 P33 P34 0
.
0 0 0 P43 P44 P45 0 0 0 0 P54 P55 2.7.2. X={x1}, Z={z1}, Y={y0,y1,y2,y3}. автомат второго рода, Pi = P0 , P1 , P2 , P3 .
Правильный
2.7.3. X={x1}, Z={z1}, Y={y0,y1,y2,y3,y4,y5,y6}, P(yi/zi)=P(yi) задается в виде Pi = PO , P1 , P2 , P3 , P4 , P5 , P6 , где Pi – вероятность появления i ошибок в кодовой комбинации. 2.7.5. Модель задается марковским автоматом, процесс описывается дискретной цепью Маркова.
35 2.7.6. Модель описывается ВА с детерминированной функцией выходов. 2.7.8. Дискретная цепь Маркова.
36
3. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ 3.1. Краткие сведения Системы массового обслуживания (СМО), называемые Q – схемами (1), применяются при непрерывно – стохастическом подходе к задачам моделирования систем. Любые объекты (экономические, производственные, технологические, и т.д.) и процессы, функционирование которых отвечает понятиям и алгоритмам работы СМО, могут описываться соответствующим математическим аппаратом. Для применения аппарата СМО при моделировании необходимо определить, по какому закону и как осуществляется обслуживание, причем под обслуживанием могут пониматься различные виды работ:обработка деталей, передача сообщений, работа транспорта, решение задач на ЭВМ и т.д. Необходимо определить структуру СМО (число приборов обслуживания, фазы обслуживания), а также получить информацио о входящих потоках заявок. В настоящее врнмя имеется мощный математический аппарат теории СМО [9 -14]. Наиболее распространеные модели СМО - это уравнения Эрланга (уравнения Колмогорова) для определения вероятностей состояний СМО, интегро-дифференциальное уравнение ЛиндиТакача-Севастьянова для определения времени задержки, а также оценки распределений в виде моментных функций, которые получают путем использования аппарата производящих функций. Для контроля уровня знаний в области описания СМО предлагаем ответить на следующие вопросы.
37 1. Что понимается под СМО в широком смысле? Как классифицируются СМО? 2. Как можно описать модель входного потока заявок? Какой поток называется «простым»? 3. Каким образом можно построить модель потока с последействием? 4. Какие дисциплины принятия на обслуживание Вы знаете? 5. Перечислите основные критерии эффективности функционирования СМО? 6. Выведите уравнение Эрланга для одноканальной СМО с бесконечной очередью. 7. Нарисуйте временные диаграммы функционирования одноканальной СМО, произвольно задав входной поток однородных заявок. 8. Какие наименования приоритетов Вы знаете? В чем состоит их отличие друг от друга? 9. Нарисуйте временные диаграммы функционирования одноканальной СМО с относительными приоритетами при условии, что на вход поступает два потока заявок. 10. Нарисуйте временные диаграммы функционирования одноканальной СМО с относительными приоритетами при условии, что на вход поступает два потока заявок. Ответы на данные вопросы можно найти в работах ([3, 9 -14].
3.2. Примеры разработки моделей в виде СМО 3.2.1. В цеху поток однородных заготовок (заявок) обрабатывается на n одинаковых станках (параллельные каналы). Время ообработки изделия на каждом станке одинаково и определено экспоненциальным распределением с параметром μ. Входной поток заготовок определен распределением Пуассона с параметром λ. Если
38 заготовка застает все станки занятыми обработкой, то она получает отказ и покидает цех. Разработать модель по методу составления уравнений в частных приращениях (уравнений Эрланга). Решение. Составим систему уравнений Эрланга для случая с бесконечным числом приборов обслуживания. Pn(∆t) - вероятность поступления заявки за время ∆t→0, Pn(∆t)=λ∆t. Роо (∆t) - вероятность окончания обслуживания в одном из приборов за время ∆t, Р00(∆t)=μ∆t. Состояние z0, определяющее отсутствие заявок в СМО, определится уравнением Po(t+∆t) = Po(t) (I-λ∆t) + P1(t)μ∆t, (4) где Pi(t) - вероятность того, что в момент времени t в СМО заняты обслуживанием i приборов. Состояние z1, определяющее занятость обслуживанием приборов в СМО определится следующим образом: Pi (t+∆t) = Pi-1(t)λ∆t + (1-(λ+μ)∆t) Pi(t) + Pi+1(t)μ∆t. (3.2) Преобразуем уравнения (4): P0 (t + Δt ) − P0 (t ) = − λP0 (t ) + μP1 (t ); Δt Pi (t + Δt ) − Pi (t ) = λ Pi −1 (t ) + μPi + 1 (t ) − (λ + μ )Pi (t ). Δt Возьмем пределы при ∆t→0: dP0 (t ) = − λ P0 (t ) + μP1 (t ); dt dPi (t ) = λ Pi −1 (t ) − (λ + μ )Pi (t ) + μPi + 1 (t ). dt Для стационарного режима функционирования получим при ρ=λ/μ ρP0=P1, (1+ρ)Pi=ρPi-1+Pi+1, i=1,2,3,… . (5) Решением системы (5) является Pi=P0ρi.
39 Под состоянием отказа можно рассматривать множество z0={zn+1,zn+2,zn+3,...}. Вероятность отказа определим из анализа группы событий, определяющих, что СМО находится влюбом из состояний множества z0. Тогда вероятность отказа опрелелим таким образом:
Р отк =
∞
∑ P ≈P i
n+1
= P0ρn+1 ,
P0 = 1 - ρ .
i=n+1
3.2.2. На вход одноканальной СМО (к станку, обрабатывающшему изделие) поступает пуассоновский поток заявок (в общем случае нестационарный) с интенсивностью λ. Время обслуживания (обработки) B(t). описывается произвольным распределением Разработать модель СМО в виде функции рвспределения времени задержки. Решение. Рассмотрим методику изложения уравнения Линди-Такача-Севастьянова. На рис. 9 приведены временные диаграммы, отображающие функционирование N однотипных СМО, каждая из которых описывается согласно заданию. Пусть P(w,t) есть вероятность того, что заявка ожидает в очереди в течение времени (w,t)≤w при условии, что она поступила в СМО в момент времени t. Число СМО N достаточно большое (N→∝), а время обслуживания и входные потоки заявок в каждой СМО описаны распределениями с одними и теми же параметрами по условию задачи. Для получения уравнения в частных приращениях выразим P(w,t+∆t) через P(w,t) и P(w+∆t, t). Рассмотрим состояния N СМО в момент времени t (см. рис. 9).
40 П(t) ω(t)
ω
t0
t
П(t) ω(t)
ω
t0
t
П(t) ω(t)
ω
t0
t
П(t) ω(t)
ω
t0
t t
t+Δt
Рис 9 СМО можно разделитьна две группы:
41
Группа А. СМО, у которых время задержки меньше или равно величине w, т.е. w(t)≤w. Число этих СМО NP(w,t), т.к. P(w,t) определяет долю систем с w(t)≤w. Группа В. СМО, у которых w(t)>w. Число этих СМО N– NP(w,t). Рассмотрим изменения числа систем в группах А и В за время ∆t→0. В момент времени t+∆t число СМО группы А становится равным NP(w+∆t,t) (см. изменения для w2(t) на рис. 9) минус число тех систем, которые имели время ожидания w(t)≤w, но вследствие поступления заявок на промежуток времени ∆t время задержки в них стало больше w, т.е. w(t)>w (см. изменения wN(t) на рис. 9). Определим число этих систем. Вначале определим число СМО, для которых время задержки в момент времени t находится внутри интервала (x,x+dx). Так как P(x,t) - функция распределения (P(x,t),w=x), то плотность распределения для x>0 dP( x, t ) определим, как . Тогда число СМО, у которых dx dP( x, t ) w(t)∈(x,x+dx), определится N , если x>0, или dx dP( x, t ) NP(0,t), если x=0. Отметим,что есть вероятность dx того, что w(t)∈(x,x+dx). Время задержки превзойдет величину w, если за время ∆t поступит заявка и время обслуживания у этой заявки, сложенное с x, превзойдет w, т.е. x+y>w, y>w-x. Определим вероятность того, что время обслуживания этой заявки превысит величину w-x. Если b(y) - плотность распределения времени обслуживания, то вероятность события y>w-x определится по формуле:
42 ∞
∫ b(y )dy .
w−x
Определим число систем, для которых w(t)∈(x,x+dx), и вследствие поступления заявок с y>w-x они переходят в группу В. Нужно умножить число СМО, для которых w(t)∈(x,x+dx), на вероятность поступления одной заявки за время ∆t, равную (λ∆t), и на вероятность того, что время обслуживания заявки y>w-x. Для x>0 получим, что число этих систем равно величине ∞ dP( x, t ) dP ( x, t ) Nλ Δ t dx ∫ b( y )dy = Nλ Δt dx B c ( w − x ); dx dx w−x
w−x
B c ( w − x) = 1 −
∫ b(y ) dy , 0
которую надлежит проссумировать по x: w dP( x, t ) Nλ Δt ∫ B c ( w − x) dx. dx 0+ Число СМО, переходящих в группу В при x=0, определим ∞
Nλ ΔtP(0, t )∫ b( y ) dy = NλΔtP(o, t )B c ( w ). w
Запишем уравнение в частных приращениях:
NP(w, t + Δt) = NP(w + Δt, t) w
dP(x, t) Bc (w - x) dx - NλΔtP(0, t)Bc (w) . dx 0+ Разделим его на N, вычтем P(w,t) из правой и левой ∆t, учтем, что частей, затем разделим на -NλΔt ∫
dP( w , t ) Δt + 0 ( Δt ), и перейдем к dw пределу при ∆t→0. Полчим P ( w + Δt , t ) = P( w , t ) +
43
dP(w, t) dP(w, t) = dt dw w
dP(x, t) B c (w - x) dx - λP(0, t)Bc (w) . dx 0+ Решение этого интегро-дифференциального уравнения должно удовлетворять условиям: ∀w P(w,0)=1, ∀t P(∝,t)=1. Если проинтегрировать по частям, то получим w dP ( w , t ) dP ( w , t ) = − λ P( w , t ) + λ ∫ P( w − v , t ) dB c ( v ). dt dw 0 Если B(t)=1-Bc(t), то w dP( w , t ) dP( w , t ) = − λ P( w , t ) + λ ∫ P( w − x) dx P ( x, t ). dt dw 0 Решение этого уравнения в преобразованиях ЛапласаСтилтьеса позволит получит характеристическую функцию w(s,t) функции распределения P(w,t) времени задержки: P( w ) w (s , t ) = . ⎡ 1 B( s ) ⎤ 1 − λ⎢ − s ⎥⎦ ⎣s 3.2.3. В одноканальную СМО с постоянным временем b обслуживания поступает пуассоновский поток заявок с параметром λ. Задать модель СМО в виде списания времени задержки в системе. Привести временные диаграммы. Решение. Для произвольного задания входного потока заявок П(t) на рис. 10 показаны диаграммы изменения времени задержки w(t). Время задержки в данной СМО описывается уравнением Линди-Такача-Севастьянова -λ ∫
44
s w(s) =
П(t)
t1
t2
1-ρ , ⎡ 1 - β(s) ⎤ 1 - λ⎢ ⎥ ⎣ s ⎦ t3
t4
(6)
t5
ω(t)
t0
t
Рис. 10 где w(s) - характеристическая функция времени задержки, β(s) - характеристическое уравнение распределения времени обслуживания, причем ∞
w (s ) = ∫ e − st P(t ) dt, 0
где P(t) - функция распределения вероятностей времени задержки. Если время обслуживания постоянно, то β(s)=1/e-sb. Если подставить β(s) в формулу (6) и взять обратное преобразование, то получим P(t), которая является математической моделью для оценки времени ожидания. Среднее время ожидания можно получить из уравнения dw (s ) = 0, s = 0. ds 3.2.4. Для СМО с экспоненциальным распределением длительности обслуживания и пуасоновским потоком заявок с параметром λ найти математическую модель в виде описания периода занятости. Интенсивность
45 обслуживания - μ. Привести пример хадания временных диаграмм. Решение. Для заданного потока П(t) заявок пример построения временных диаграмм приведен на рис. 11. П(t)
t1
t2
t3
t4
t5
ω(t)
t0
t Выходной поток Период занятости
t1* π1
t2*
t3* t4* π2
t5* π3
t t
Рис. 11 Период занятости представляет собой отрезок πi непрерывного обслуживания заявок в СМО. Характеристическая функция распределения периода занятости π(s) при B(t)=1–e-μt есть μ π(s ) = . s + μ + λ − λπ (s ) Если применить обратное преобразование ЛапласаСтильтьеса, то получим функцию распределения реального времени 1 П(t ) = I 1 ( 2t λμ ) e − ( λ + μ ) t , t ρ где I1(t) - функция Бесселя первого рода. Первый момент определится из условия π(s)=0 при s=0 и будет равен π 1 = ( μ − λ ) −1 .
46
3.3. Задачи для самостоятельного решения 3.3.1. На стоянку с пассажирами через промежутки времени, описываемые экспоненциальным распределением, прибывают такси. Пассажиры также прибывают в соответствии с пуассоновским законом. Интенсивность прибытия такси - λ1, а интенсивность прибытия пассажиров - λ2. В начальный момент времени t=0 нет пассажиров и нет такси, а в момент времени t на стоянке X пассажиров и Y такси. Случайная величина Z=X-Y определит среднее значение очереди. Необходимо определить среднее значение z1 случайной величины Z и дисперсию D(Z). 3.3.2. Магазин имеет четыре кассы, обслуживающие все отделы. Время обслуживания каждой кассой описывается функцией распределения B(t)=1-e-μt. Разработайте модель СМО для случая, когда поток покупателей пуассоновский с параметром λ. Во сколько раз изменитяс среднее время ожидания при трех и двух работающих кассах? Чему равно среднее время ожидания w1 в очереди перед кассами? 3.3.3. ЭВМ опрашивает внешние устройства в определенные моменты времени, которые образуют пуассоновский поток с параметром λ. В каждый момент времени может поступить запрос с вероятностью Pk при условии, что до этого времени уже поступило k запросов, k≥0. Pk(t), k≥0 - вероятность поступления запросов в промежутке времени [0,t). Найти модель, описывающую поток запросов в виде характеристических функций mk(s) распределений Pk(s), где ∞
m k (s ) = ∫ e − st dPk (t ),
k ≥ 0.
0
3.3.4. На стол контролера поступает поток деталей, интервалы времени между моментами поступления
47 которых описываются распределением A(t)=1-e-λt. Деталь бракуется с вероятностью Р и удаляется. Найти математическую модель потока небракованных деталей. 3.3.5. На вход распределительного устройства поступает поток деталей, описываемый законом Пуассона с параметром λ. Устройство распределяет детали в порядке их поступления по n+1 направлениям, так что деталь с номером i, mod(n+1) будет отправлена по i-му направлению. Получить модели потоков, расходящихся по n+1 направлениям в виде функций распределений длин интервалов между деталями Ai(t). 3.3.6. На вход одноканальной СМО, имеющий постоянное время b=1/μ, поступает пуассоновский поток заявок с параметром λ. Определить модель в виде распределения периода занятости. Определить среднее время периода занятости π1. 3.3.7. ЭВМ обслуживает запросы первого (старшего) и второго приоритетов. Потоки запросов каждого из приоритетов описываются законами Пуассона с параметрами λ1 и λ2 соответственно. Запросы обслуживаются в соответствии с экспоненциальными законами распределения времени обслуживания. Для заявок первого приоритета B1 (t) = 1 - e -μ12 t
-μ11t
, для заявок
второго приоритета B 2 (t) = 1 - e . Определить модель в виде распределения периода занятости П(t) или его характеристической функции π(s). Найти среднее время периода занятости π1. 3.3.8. На вход СМО поступает пуассоновский поток заявок с параметром λ. Время обслуживания b каждой заявки постоянно и равно b=1/μ. Найти математическую модель в виде функции расперделения периода занятости П(t).
48 3.3.9. На участок цеха, содержащий n станков, поступают детали. Поток деталей пуассоновский с параметром λ. Детали обрабатываются на станках независимо друг от друга. Время обработки на всех станках определяется одним экспоненциальным распределением с параметром μ. Разработать модель участка, позволяющую найти среднее число деталей mср, ожидающих обработки; вероятность РЗ того, что все станки заняты; среднее время ожидания tож обработки. 3.3.10. К контрольному пункту с двух противоположных сторон приближаются автомашины. Оба потока пуассоновские с параметрами λ1 и λ2. В случае наличия очереди с одной и другой стороны автомашины проходят пункт поочередно из кажой очереди. Время прохода постоянно. Разработайте алгоритм имитационной модели [15]. 3.3.11. Разработать модель в виде СМО автоматизированной телефонной станции, которая позволила бы оценить следующие показатели: Ро вероятность того, что все линии будут свободны; Ротк вероятность того, что абоненту будет отказано в обслуживании; N3 - среднее число свободных линий связи; kn - коэффициент простоя линий. Станция имеет n=5 линий связи. Поток требований на ведение разговоров пуассоновский с параметром λ - два вызова в единицу времени. Продолжительность каждого разговора подчинена показательному закону распределения. Среднее время tобс, необходимое для ведения разговора, равно одной единице времени. 3.3.12. На вход системы передачи информации сообщения поступают группами. Число сообщений в группе постоянно и равно m=3. Поток групп сообщений простейший с плотностью λ=5 сообщ./с. Время передачи описывается показательным законом с математическим
49 ожиданием 0,2 секунды. Поступающие сообщения, застав все каналы передачи информации занятыми, теряются. Разработать модель в виде СМО, которая позволила бы определить: Ротк - вероятность потери информации; k3 коэффициент загрузки системы; kn - коэфициент простоя каналов; No - среднее число свободных каналов. Определить, сколько каналов должна иметь система, чтобы Ротк≤0,05. Найти для этого случая k3, No,kn. 3.3.13. Завод выпускает изделия с интенсивностью λ=0,5 изд./мин. Изделия проходят контроль на специальных стендах, к которым они подаются транспортером. Каждый из стендов может одновременно контролировать только одно изделие. Необходимо разработать модель в виде СМО, позволяющую определить, сколько и какой производительности нужно поставить стендов на контрольном пункте при минимальных затратах на стенды, монтаж контрольного пункта и обслуживание, чтобы в среднем не менее 95% готовых изделий было проверено. Стенды могут иметь различную производительность, причем зависимость стоимости стенда от его производительности определится в G = 5/ tобс единиц стоимости, где tобс - время обслуживания в минутах. Время контроля каждого изделия подчинено экспоненциальному распределению с параметром μ = 1/tобс . Пусть стоимость монтажа и обслуживания контрольного пункта за время изготовления серии изделий задана функцией Co=(5+n2)/3 ед. стоим., где n - число стендов. В распоряжении завода имеется выбор из пяти стендов, которые характеризуются tобс =0,5; 1; 2; 5; 10 изд./мин. Определить коэффициенты производительности каждого из стендов. Под коэффициентом производительности будем понимать процент проверяемыз изделий.
50 3.3.14. В память ЭВМ поступает поток сообщений с плотностью λ=1 сообщ./с. Поток сообщений является простейшим. Поступающие сообщения записываются в буферную памать, объем которой – n сообщений. Если очередное сообщение застанет буферную память занятой, то оно считается потерянным. Процессор выбирает сообщения на обработку из буферной памяти в порядке их поступления. Время, затрачиваемое на обработку сообщения, описывается экспоненциальным распределением. Математическое ожидание времени обслуживаниясообщений tобс =1,6 с, а вероятность потери сообщений не должна превышать величину 0,25. Разработать модель в виде СМО и найти требуемый объем n буферной памяти. 3.3.15. Морской порт имеет n=5 причалов для разгрузки судов. в порт за месяц прибывает в среднем 20 судов. Поступление в порт судов описывается законом Пуассона. Время разгрузки описывается экспоненциальным распределением. В среднем на разгрузку судна тратится 6 рабочих дней. Разработать модель в виде СМО, позволяющую оценить работу порта. Определитель: Р0 вероятность того, что все причалы свободны и ожидают суда под разгрузку; Р3 - вероятность того, что все причалы заняты судами под разгрузку; tож - среднее время ожидания каждым судном начала разгрузки; Мож - среднее число судов, ожидающих своей очереди на разгрузку; М среднее число судов, находящихся в порту; P(n=6) вероятность того, что в порту на разгрузке находится шесть судов; No - среднее количество простаивающих причалов. При решении этой задачи нужно исследовать экономическую целесообразность расширения возможности порта по разгрузке и погрузке судов. Простой каждого судна в течение суток обходится государству в
51
С1=100 единиц стоимости. Простой причала порта из-за несвоевременного прихода судов обходится государству в С2=1000 единиц стоимости. Стоимость месячной эксплуатации причала С3=1000 единицам. 3.4. Ответы на задачи 3.3.1. z1=(λ2-λ1)t, D(z)=(λ1+λ2)t. ρb 1 λ , b= , ρ= . 3.3.2. w 1 = 1−ρ 4μ 4μ s 3.3.3. π 0 = , π n + 1 (s ) . ab 0 + s 3.3.4. B(t)=1-e-(1-ρ)λt. λt n x −x e dx. 3.3.5. A(t ) = ∫ n ! 0 3.3.6. π 1 = 3.3.7. π 1 =
1 . μ−λ λ 1 μ 11 + λ 2 μ 12
.
(λ 1 + λ 2 )(1 − λ 1 μ 11 − λ 2 μ 12 ) ]μt [
3.3.8. П(t ) = ∑ e − ρk n =1
∞
(ρk ) n , n!
ρ = λ /μ . ∞
1 ∞ ∑ (i - n)Pi ; λ i=n 1 1 = P0 ; nμ (1 - ρ)2
3.3.9. m ср = ∑ (i - n)Pi ; P3 = ∑ Pi ; t ош = n=1
ρ m ср = P0 , (1 - ρ)2
i=n
1 P3 = P0 , t ош 1-ρ
ρ = λ/nμ . 3.3.11. P0=0,138; Pomk=0,037; N3=1,93 линий; k3=0,39 линий; N0=3,05 линий; kn=0,61. 3.3.12. n≥9; k3=0,32; N0=6,12; kn=0,68.
52 3.3.13. Четыре стенда. 3.3.14. n≥3. 3.3.15. P0=0,013; P3=0,555; tож=3,3 суток; Mож=11,1 судна; P(n=6)=0,074; M=12,53 судна; N0≈1 причал.
53
4. АГРЕГАТИВНЫЕ МОДЕЛИ 4.1. Основные сведения Общий подход к задачам моделирования систем разработан Н.П. Бусленко (2) и основан на понятии агрегата (А). Агрегат описывает поведение любых систем, представляет собой формальную схему общего вида, которая называется А–схемой. Агрегат содержит все известные математические модели как частные случаи. Под агрегатом понимается объект A=, где T(t∈T) - множество моментов времени; X, (x∈X) множество входных сигналов: Г, (g∈Г) - множество управляющих сигналов; Y, (y∈Y) - множество выходных сигналов; Z, (z∈Z) - множество состояний; Н - оператор переходов; G - оператор выходов; В - пространство параметров агрегата. Элемент β=(β1,β2,…,βr)∈B фиксированн в рамках каждой задачи и называется конструктивным параметром агрегата. Оператор G представляют в виде двух операторов G’ и G”. Опратор G’ предназначен для определения моментов выдачи непустых выходных сигналов, а оператор G” - для определения содержания выходных сигналов. В пространстве состояний G” агрегата выделяют Y ⊂ Z , вид которого определяется двойками множество Z (g,β)
(g,β). При переходе от одной задачи моделирования к Y другой множество Z(g,β) определяется конструктивными параметрами, а в рамках одной задачи (β=const) множество Y Z(g,β) не изменяется. При вхождении траектории агрегата в
54 Y момент времени t в Z(g,β) оператором G” определяется
содержание непустого выходного сигнала y(t)=G”{t,z(t),g(t),β}, G” - отображение, ставящее в соответствие элементы множества T×Z×Г×В и элементы множества Y, т.е. Y=G”{T×Z×Г×B}. Работа оператора G’ заключается в определении очередного момента достижения троекторией z(t) Y . подмножества Z(g,β) Оператор переходов Н состоит из трех опеpатоpов U, V* и V**. Пуcть t *n - момент поcтупления вxодного cигнала x *n . Bзменение состояния за малый промежуток времени (в момент времени tn+0) определится следующим образом: z ( t *n + 0 ) = V * [ t *n , z ( t *n ), g ( t *n ), x ( t *n ), β ] , где упpавляющий импульc, g ( t *n ) - поcледний * ** поcтупивший в момент t< t n . Еcли t n - момент поcтупления упpавляющего cигнала gn, то изменение состояния за достаточно малый промежуток времени определится: z ( t *n* + 0 ) = V ** [ t *n* , z ( t *n* ), g ( t *n* ), β ] . Еcли tn - момент одновpеменного поcтупления в А вxодного xn и упpавляющего gn cигналов, то z ( t n + 0 ) = V * { t n , V ** [ t n , z ( t n ), g ( t n ), β ], g ( t *n ), x ( t *n ), β } . Под выpажением V ** [ t n , z ( t n ), g ( t n ), β ] понимаетcя не опеpатоp, а pезультат его дейcтвия на аpгументы t n , z ( t n ), g ( t n ), β , являющийcя элементом множеcтва Z. Можно запиcать: z ( t n + 0 ) = V * [ t n , zˆ ( t *n + 0 ), g ( t n ), β ] .
55 Если в полуинтервале (tn,tn+1] не поступают ни выходные, ни управляющие сигналы, то изменение состояния агрегата определяется оператором U: z(t)=U{t,tn,z(tn+0),g(tn),β}.
4.2. Примеры реализации агрегатных моделей 4.2.1. Пример построения временных диаграмм. На рис. 11 приведен пример временных диаграмм функционирования агрегата. Описать функционирование агрегата с помощью операторов G и H. X t’1
t’4
t
Г t”1
t”2
Y t*1
t3
t*2
t t
Рис. 11
Решение. z(t 1,, + 0) = V"[t 1,, , z(t 1,, ), g(t 1,, ), β] ;
∀ t ∈ (t 1,, , t 1, ] z(t) = U[t, t 1,, , z(t 1,, + 0), g(t 1,, ), β] ;
z(t 1, + 0) = V'[t 1, , z(t 1, ), g(t 1,, ), x(t 1, ), β] ; y(t *1 ) = G"[t *1 , z(t *1 ), g(t 1,, ), β] ; y(t *2 ) = G"[t *2 , z(t *2 ), g(t ,,2 ), β] ;
∀ t ∈ (t 1, , t ,,2 ] z(t) = U[t, t 1, , z(t 1, + 0), g(t 1,, ), β] ; z(t ,,2 + 0) = V"[t ,,2 , z(t ,,2 ), g(t ,,2 ), β] ;
∀ t ∈ (t 1,, , t 3 ] z(t) = U[t, t ,,2 , z(t ,,2 + 0), g(t ,,2 ), β] ; z(t 3 + 0) = V'{t 3 , V"[t 3 , z(t 3 ), g(t 3 ), β], g(t 3 ), x(t 3 ), β} ;
∀ t ∈ (t 3 , t ,4 ] z(t) = U[t, t 3 , z(t 3 + 0), g(t 3 ), β] ;
56
z(t ,4 + 0) = V'[t ,4 , z(t ,4 ), g(t 3 ), x(t ,4 ), β] / 4.2.2. Модель одноканальной СМО с ожиданием. Заявки поступают в моменты времени tj (j=1,2,3,...) и образуют случайный поток однородных событий. Каждая заявка характеризуется случайным параметром αj. Длительность обслуживания заявок ηj=ψ(αj,β), где β - конструктивный параметр системы. Разработать агрегативную модель в виде А=<Т,Х,Г,У,Z,Н,G>. Решение. Входное множество агрегата X определяется двойками (tj,αj)∈Х. Так как поток заявок однородный, то множество Г состоит из одного элемента g∈Г, наличие которого определяет начало работы СМО. Множество выходных сигналов содержит тройки (αj,βj*,tj*)∈Y, где tj* - время окончания обслуживания заявки; βj* - параметр, при котором было произведено обслуживание. Рассмотрим представление множества Z. Введем координаты: z1(t) - время, оставшееся до конца обслуживания заявки; z2(t) - число заявок в СМО. Для каждой k-й заявки в очереди (k=1,2,3,...) введем координату zk+2(t)=αk, где αk - параметр k-й заявки в очереди. Так как мщность |Г|=1, то оператор перехода Н представим в виде двух операторов - оператора U и оператора V’, которые описываются для t=tj следующими уравнениями: z1 (t j + 0) = z 1 (t j ), ⎫ ⎪ z 2 (t j + 0) = z 2 (t j ) + 1, ⎪ ⎬ z (t ) > 0 z k (t j + 0) = z k (t j ), k < z .2 (t j ) - 1, ⎪ 2 j ⎪ z 2+z 2 (t j ) (t j + 0) = α j ; ⎭ z1(tj+0)=ψ(αj,β, z2(tj+0)=1,
57
z2+2k(tj+0) – не определяются. Рассмотрим реализацию оператора U. Т.к. в момент tj* происходит изменение координат, то U следует представить в виде двух операторов U и W. Оператор W будет определять изменение координат в моменты времени tj* и будет иметь следующий вид: ⎫ z1 (t *j + 0 = ψ[z 3 ,β], ⎪⎪ * z 2 (t *j + 0) = z 2 (t *j ) - 1, ⎬ z 2 (t j ) > 0, ⎪ z 2+k (t *j + 0) = z 2+(k +1) (t *j ), 1 < k £ z 2 (t*j ) - 1, ⎪⎭ ⎫ z 1 (t *j + 0) = z 1 (t *j ) = 0, ⎪⎪ z 2 (t *j + 0) = 0, ⎬ z 2 ( t j ) = 0. ⎪ z 2+ k (t *j + 0) − не определяются.⎪⎭ В полуинтервале (tn,tn+1] между особыми моментами (точки tj и tj*) оператор U описывается уравнениями: z1(t)=z1(tn+0)-(t-tn); z2(t)=z2(tn); z2+k(t)=z2+k(tn). Y Z(g,β) определим соотношением Z1(tj*)=0, т.е. при окончании обслуживания должен выдаваться выходной сигнал. Оператор G’ определяет достижение во времени Y множества Z(g,β) . Оператор G” определяет содержимое выходного сигнала y={αj,βj*,tj*}.
4.3. Задачи для самостоятельного решения. 4.3.1. Описать функционирование агрегата, работа которого отражена временными диаграммами, приведенными на рис. 12.
58 X t2
t
t4
Г t1
t7
t3
Y
t5
t9 t8
t6
t t
Рис. 12 4.3.2. Описать функцтонирование агрегата, работа которого отображена на рисвременными диаграммами, приведенными на рис. 13. X t
t2 Г Y
t3
t1
t
t6 t4
t
t5
Рис. 13 4.3.3. Описать функционирование агрегата, работа которого отображена временными диаграммами, приведенных на рис. 14. X t Г t3
t1
t4
t
t7
Y t2
t5
t6
t8
t
Рис. 14 4.3.4. Описать функционирование агрегата, работа которого отображена временными диаграммами, приведенных на рис. 15.
59 X t
t6 Г t5
t1
t9
t
Y t2
t3
t4
t7
t8
t
Рис. 15 4.3.5. Разработать агрегатную модель одноканальной СМО. Заявки поступают в моменты времени tj и образуют однородный поток. Каждая заявка характеризуется параметром αj, моментом времени поступления в СМО и случайным параметром γj – временем пребывания в СМО, причем γj=ϕ(αj,β), где β - параметр СМО. По истечении времени γj заявка покидает систему, даже если она не была обслужена. Время обслуживания определяется функцией ηj=ψ(αj,β). Разработать агрегат. Множество Z задать следующим образом. Координата z1(t) – время, оставшееся до конца обслуживания заявки, находящейся на обслуживании. Координата z2(t) – число заявок в СМО. Координаты z1+2k(t)=αk, [k=1,2,…,z2(t)-1)] – параметры k-х завок в очереди. Координаты z2+2k(t) – время, оставшееся до конца обслуживания k-й заявки в очереди. Множество Y содержит элементы y=(y(1),y(2)), где y(1)=1, если СМО покидает обслуженная заявка, и y(1)=0, если СМО покидает заявка, у которой истекло время пребывания в системе γj. y(2) – совокупность характеристик обслуженной заявки y(2)=(αj,β*j,t*j). 4.3.6. Разработать агрегатную модель приоритетной СМО. Заявки образуют потоки первого и второго приоритетов. Поступают заявки в моменты времени tj (j=1,2,3,…) и характеризуются приоритетами, временем нахождения в очереди γj=ϕ(αj,β), длительностью обслуживания ηо=ψ(αj,β). Разработать модель агрегата.
60 В отличие от задачи 4.3.5 множество Г содержит два элемента Г=(g1,g2), которые определяют приоритетность в обслуживании. Множество Y имеет точно такое же описание, что и в примере 4.3.5. Множество Z рекомендуется описать следующими координатами: z1(t) – время, оставшееся до конца обслуживания заявки, находящейся на обслуживании; z2(1)(t) – число заявок в очереди первого приоритета; z2(2)(t) – число заявок в очереди второго приоритета; z(1)2k+1(t)=α,k, k=1, 2, … , z2(1)(t)-1 – параметры k-х заявок первого приоритета в очереди; z(1)2+2k(t)=α,,k, k=1,2,…,z2(2)(t)-1 параметры k–х заявок второго приоритета в очереди; z(2)2+2k(t) – время, оставшееся до конца ожидания k-й заявки второго приоритета в очереди. 4.3.7. Разработать агрегатную модель СМО, которая содержит три параллельных канала обслуживания. Множество управляющих сигналов Г=(g1,g2,g3). Множества X,Y,Z выбрать по примерам 4.3.5 и 4.3.6. 4.3.8.На участок, содержащий два станка, поступают детали. Поток деталей – пуассоновский с параметром λ. Некоторые из деталей требуют одной операции на первом станке и второй операции на другом станке. Эти детали образуют вторую группу. Обработанные детали первой группы на первом станке образуют один выходной поток, а обработанные детали второй группы образуют второй выходной поток. Детали второй группы должны обрабатываться вначале на первом станке, а затем на втором. Время обработки на первом станке задается функцией ηj(1)=ψ(αj(1),β1), где αj(1) – параметры деталей, поступающих на участок в моменты времени tj; β1 конструктивный параметр первого станка. Время обработки деталей на втором станке задается функцией ηj(2)=ψ(αj(2),β2), где αj(2) – параметры деталей, поступающих
61 на второй станок в моменты времени tj; β2 – конструктивный параметр второго станка. Предлагается разработать агрегатную модель участка. 4.3.9. На прокатный стан, состоящий из пяти линий, поступает поток труб. Все линии настраиваются на вытяжку труб одинакового диаметра. Трубы поступают к линиям в порядке их нумерации, т.е. если занята i-я линия, то труба поступит на линию с номером (i+1)mod5.Схема представлена на рис. 16.
Рис. 16 Разработать агрегатную модель, описывающую процесс функционирования прокатного стана. Ввести следующие координаты: zi(t) - время, оставшееся до конца вытяжки трубы на i-й линии. Множество X определяется параметрами (αj,tj), где αj - параметр трубы, tj - время ее поступления. Задержка труб отсутствует. Множество Г={g1,g2,…,g5}, где gi управляющий сигнал, указывающий, что труба должна пойти в i-ю линию. Время обработки трубы в линии η=ψ(αj,βi), где βj - параметр i-й линии; B={β1,β2,…,β5}. 4.3.10. На ЭВМ поступает поток задач в моменты времени tj. Каждая j-я задача характеризуется параметром αj(i), причем αj(i)∈А - множество параметров задач. ЭВМ характеризуется вектором конструктивных параметров В={β1,β2,β3,). ЭВМ присваиваетприоритеты каждой из
62 задач в зависимости от параметра αj(i). Всего приоритетов три, причем задачи i-го приоритета обслуживаются с параметром βi, а время обслуживания (решения) j-й заявки (задачи) определено функцией длительности ηj(i)=ψ(αj(i),βi). Время ожидания решения задачи не ограничено. Разработать модель функционирования ЭВМ в виде агрегата, задав его операторы переходов и выходов, а также множества X,Y,Г,Z.
63
5. ОБРАБОТКА И АНАЛИЗ РЕЗУЛЬТАТОВ МОДЕЛИРОВАНИЯ НА ЭВМ 5.1. Задачи статистической проверки гипотез При моделировании объекта исследователем формирулируется гипотеза о том, что выбранная модель, адекватна объекту. Адекватность определяется тем, что полученные при моделировании результаты будут соответствовать реальным показателям функционирования объекта. При разработке имитационных моделей и дальнейшем моделировании на ЭВМ результат каждого опыта (одно решение задачи на ЭВМ) суть случайная величина. Если результатами моделирования являются частоты попадания событий в некоторые заданные интервалы, то ставится задача определения кумулятивных эмпирических Функций распределений и проверки гипотезы соответствия эмпирических распределений: выбранным теоретическим. 5.1.1. Выбор числа реализаций опытов. При имитационным моделировании понятие точности моделирования связано с достоверностью результатов моделирования. Известен вероятностный критерий оценки погрешности [16] P{ a - а ≤ ε} = g, который определяет вероятность g того, что полученный результат, моделирования а будет отличаться от реального а не более чем на величину ε. Вероятность g называется еще коэффициентом доверия результатам моделирования, а величина α=1-g - уровнем значимости результатов опыта.
64 Известны [16] формулы, которые получены из центральных предельных теорем и позволяют находить требуемое число реализаций опытов при заданных значениях α и ε: (6) N = t α2 p(1 − p ) / ε 2 ;
N = t α2 σ 2 / ε 2 ,
(7)
где tα - табличное значение нормального распределения [16]; р - вероятность появления события; σ - дисперсия события. Очевидно, что р и σ - величины неизвестные. Поступают следующим образом. По результатам N0, опытов определяют величины р0 или σ0. Затем подставляют их в формулы (6) или (7) соответственно и находят требуемую величину N. Из формул (6) и (7) следует, что нужно так строить моделирующие алгоритмы, чтобы оценивались параметры моделей, имеющие возможно меньшую дисперсию или вероятности случайных событий, не близкие к величинам 0,5; 0;1. 5.1.2. Обработка статистических данных результатов моделирования. В результате моделирования определены частоты событий А(J), состоящие в той, что значения случайной величины (СВ) A меньше или равны некоторый границам D(J) оценки этой СВ А. Частоты А(J) фиксируют в счетчиках К(J), J = I , JM , где JМ - заданное число границ оценки, велиина D(JМ) является наибрльшей границей оценки СВ, т.е. D(1)
65 фиксирована в счетчике К(J), т.е. по окончании моделирования в счетчике К(J) имеется число А(J). Таблица 4 Статистические данные результатов моделирования Границы 0,2 0,4 0,6 0,8 1,0 оценки Номер 1 2 3 4 5 счетчика Частота 12 41 59 88 104 события Кумулятивная эмпирическая функция распределения строится следующим образом. Определяются частости появления события А: A( J ) Pj* = A( J ) / A( JM ), Pj = lim , J = 1, JM , N → ∞ A( JM ) где Pj - теоретическое значение вероятностей. Затем строится гистограмма кумулятивной эмпирической функции распределения по значениям Pj*. Пример построения приведен на рис. 17. Для построения эмпирической плотности распределения необходимо определить ν *j - частости попадания СВ А в интервалы (D(J+1)-D(J)), J = 0, JM − 1 : * * * ν *j = P1* ; ν 2 = P2 − P1 ; ν 3 = P3 − P2 ; …;
*
*
*
Затем определить отношение
ν *j
ν *M = PM* − PM* −1 . к величине j-го
интервала (D(J+1)-D(J)): ν *j δ *j = , j = 1, M , J = 0, JM - 1, j = J + 1. D( J − 1) − D( J ) Пример построения эмпирической плотности распределения приведен на рис. 18.
66 1,0 0,9 0,85 0,8 0,7 0,6
0,56
0,5 0,4
0,39
0,3 0,2
0,17
0,1
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,0
Рис. 17 Если при моделировании в счетчиках К(J) будут получены частоты событий, состоящих в том, что СВ А принадлежит интервалу (D(J+1)-D(J)), то частости ν *j определятся: JM
ν = A( J ) / ∑ A( J ). * j
j= 1
Для построения кумулятивной эмпирической функции распределения частости Pj* определятся следующим образом: j
Pj* = ∑ ν *i . i =1
67 1,5 1,45 1,4 1,3 1,2 1,1
1,1 1,0 0,9 0,85
0,75
0,8 0,7
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,0
Рис. 18 5.1.3. Проверка гипотезы аппроксимации эмпирических результатов моделирования теоретическими распределениями. Важнейшим этапом моделирования является статистическая проверка гипотез. При моделировании уделяется внимание гипотезам о дисперсиях результатов, т.к. измеряемая дисперсией величина рассеивания как раз характеризует важнейшие технологические показатели (точность приборов, станков, технологических процессов, погрешность результатов измерений и т.д.). Наиболее распространенным критерием проверки гипотезы равенство, дисперсий в двух генеральных совокупностях (результатах моделирования и данных о функционировании объекта) по независимым выборкам является критерий Фишера (F-распределение) [16]. F-
68 распределение представляет собой распределение отношений двух несмещенных оценок дисперсий, полученных из независимых выборок: 2
2
S 1 / S 2 = F, где S12 – большая из двух ( S12 и S 22 ) несмещенных оценок дисперсии. Число степеней свободы k1=n1-1, k2=n2-1, - где n1 объем первой выборки, n2 – объем второй выборки. К дисперсионным критериям относятся также критерии согласия Колмогорова и Стьюденга [16]. 5.1.4. Проверка гипотез о законе распределений. Результаты моделирования приводят к гипотетическому виду закона распределения и нуждаются в статистической проверке. Сопоставляя вероятности и частости попаданий СВ в интервалы наблюдений можно составить представление о большей или меньшей близости теоретических и эмпирических распределений. Задача проверки по данным выборки гипотезы о том, что данная СВ X подчинена закону распределения Р(х) решается с помощью критериев соответствия, основанных на выборке определенной меры расхождения между теоретическим (или гипотетическим) и эмпирическим распределениями. Гипотеза не принимается, если мера расхождения превысит установленный предел. Наиболее употребительным является критерий χ2 (критерий Пирсона) [16]. В качестве меры расхождения данных выборки m1, m2,..., mM (mj=A(J))c теоретическими данными nр1, , nр2 ,..., nрM используется величина M (mj − np ) 2 j 2 , χ =∑ np j j= 1 где n - объем выборки, рj - теоретические значения вероятности.
69 Если проверяемая гипотеза верна, то критерий χ2 имеет распределение, стремящееся при n→∞ к распределению χ2 c M-1 степенями свободы. Известен [16, 17] также критерий согласия Смирнова, проверяющий факт принадлежности двух выборок одной генеральной совокупности.
5.2. Контрольные вопросы 1. Что представляет собой функция распределения вероятностей? 2. Что представляет собой плотность функции распределения вероятностей? 3. Объясните смысл понятий: частота, частость, вероятность. Какая связь существует между этими понятиями? 4. Какой физический смысл вкладывается в понятия «математичекое ожидание» и «дисперсия»? 5. Что представляет собой критерий согласия Колмогорова и каким образом его можно применять? 6. Что представляет собой критерий согласия Пирсона и каким образом его можно применять? 7. Что представляет собой критерий согласия Фишера и каким образом его можно применять? 8. Что представляет собой критерий Смирнова и каким образом его можно использовать? 9. Что представляет собой критерий согласия Стьюдента и как он используется? 10. Объясните смысл понятий: несмещенность оценки, эффективность оценки, состоятельность оценки. 11. Каким образом следует вбирать число реализаций опыта? 12. Объясните смысл понятия «мощность критерия». 13. Какая гипотеза называется нулевой?
70 14. Каким образом можно выбирать границы для оценки моделируемой случайной величины? Ответы на данные вопросы можно найти в работах [1,6,17 ].
5.3. Задачи для самостоятельного решения 5.3.1. Функционирование модели показало, что среднеее значение выходного параметра Х составило 560 единиц. Измения, проведенные на действующем объекте, показали, что среднее значение выходного параметра Х1 объекта равно 500 единицам. Выходной параметр является СВ с нормальным распределением. Среднее квадратическое отклонение δ x = δ / n = 45 ед. Проверить адекватность модели при уровне значимости α=5%, приняв в качестве критерия нормированное уклонение средней величине х от центра Х1 при условии, что это уклонение приближенно нормально распределено. 5.3.2. Решить задачу 5.3.1 при значении Х=605 ед. 5.3.3. Выходным параметром объекта является СВ Х, среднее значение которой X = 120,8 ед. Разработанная модель дала оценку СВ Y на выходе модели Y = 128,2 ед. (усредненное значение). СВ имеет нормальное распределение. На основании наблюдений установлено, что δX=8,0 ед., δY=9,4 ед. Требуется проверить гипотезу адекватности модели и объекта как гипотезу о равенстве центров распределений при уровне значимости α=5%, и числе испытаний n=50. 5.3.4. Дисперсия СВ Х на выходе объекта S 2x =9,6 c2. Дисперсия СВ Y на выходе модели S 2Y =9,6 c2. Проверить гипотезу об адекватности модели и объекта, если
71 произведено 10 измерений СВ Х и 15 измерений СВ Y. Воспользоваться критерием Фишера. 5.3.5. В табл. 5 приведены данные о разладках станков в цеху за смену. Проверить гипотезу, состоящую в том, что математической моделью процесса разладок является равномерное распределение. Воспользоваться критерием χ2 при α=5%. Таблица 5 Данные о числе разладок станков Часы смены 1 2 3 4 5 6 7 8 Σ Наблюдавшееся 16 17 19 16 24 19 17 16 144 число разладок 5.3.6. Найти необходимое число реализаций опытов N для моделирования процесса появления СВ, если вероятность ее появления предлагается Р=0,4 α=5%,а точность оценки ε=0,2. 5.3.7. Найти число реализаций опытов N для моделирования процесса, если дисперсия предполагается σ=8,4 α=5%, ε=1,5. 5.3.8. В табл. 6 приведены статистические данные о среднем числе выходящих из строя комбайнов, работающих на уборке урожая, по дням недели. Проверить гипотезу, состоящую в том, что моделью процесса отказов является равномерное распределение. Таблица 6 Данные о числе отказавшихся комбайнов День недели 1 2 3 4 5 6 7 Среднее число 12,6 17,6 19 19,6 19,9 20 20 отказавших комбайнов 5.3.9. Запросы на решение задач поступают в ЭВМ. Весь период времени наблюдения в 200 часов разделен на 100
72 двухчасовых интегралов. В табл. 7 приведены данные о количестве интервалов, в которых было одинаковое число поступивших запросов. Проверить гипотезу, состоящую в том, что модель потоков запросов описывается распределением Пуассона. Таблица 7 Систематические данные о числе запросов Число запросов в интервале 0 1 2 3 4 5 времени 2 ч. Число интервалов с одинаковым 0 5 11 13 22 18 числом запросов Число запросов в интервале времени 2 ч. Число интервалов с одинаковым числом запросов
6
7
8
9
10 11 12
14
9
4
2
1
1
0
5.3.10. В табл. 8 приведены данные о поведении СВ на выходе объекта. Найти математическую модель, аппроксимирующую закон распределения СВ.
5.4. Ответы на задачи 5.3.1. Критическая область определена в размере 88 единиц. Необходимы дополнительные испытания модели, но и нет основания считать, что модель неадекватна объекту. 5.3.2. Критическая область определена в размере 74 единицы. Нет основания считать, что модель адекватна объекту. Таблица 8 Распределение отклонений значений СВ на выходе объекта
73 № 1 2 3 4 5 6 7 8 9 10 11 12
Интервалы отклонений СВ От -0,230 до -0,210 От -0,210 до -0,190 От -0,190 до -0,170 От -0,170 до -0,150 От -0,150 до -0,130 От -0,130 до -0,110 От -0,110 до -0,090 От -0,090 до 0,070 От -0,070 до -0,050 От -0,050 до -0,030 От -0,030 до -0,010 От -0,010 до+0,01
Частота 3 8 19 37 53 60 64 49 31 17 7 2
5.3.3. Модель неадекватна объекту. 5.3.4. Модель адекватна объекту. 5.3.5. Равномерное распределение описывает процесс разладки станков. 5.3.8. Равномерное распределение не является моделью процесса. 5.3.9. Вероятность соответствия Р≈0,99. Модель потока описывается законом Пуассона.
74
ГЛАВА 2 ЛАБОPАТОPHЫЙ ПPАКТИКУМ 1. ИССЛЕДОВАНИЕ ГЕHЕPАТОPА CЛУЧАЙHЫX ЧИСЕЛ 1.1. Цель pаботы Изучение методов получения на ЭВМ псевдоcлучайныx чисел, равновероятно распределенных в интервале [0, 1]. Ознакомление c методами cтатиcтичеcкого анализа качеcтва пcевдоcлучайныx чиcел.
1.2. Оcновные теоpетичеcкие положения Для фоpмиpования cлучайныx элементов pазличной пpиpоды c pазличными функциями pаcпpеделения в ЭВМ применяется cовокупноcть cлучайныx чиcел c pавномеpным законом pаcпpеделения, как базовая поcледовательноcть cлучайныx чиcел. Cтpого говоpя, с помощью ЭВМ получить величин (CВ) c поcледовательноcть cлучайныx pавномеpным pаcпpеделением не пpедcтавляетcя возможным. Еcли чиcло pазpядов регистра ЭВМ pавно k, то cлучайное чиcло X в десятиричной системе счисления будет cфоpмиpовано cоглаcно фоpмуле k −1
X = ∑ α j 2j , j= 0
где αi∈{0, 1}, код двоичного случайного числа αk-1,αk,…,α2,α1,α0. Если предположить, что коэффициенты αi=0 с вероятностью pi=0,5 или αi=1 с вероятностью pi=1-0,5, то
75 множеcтво, cоcтоящее из чиcел Λ={i/(2k-1)}, пpинимает значение i/(2k-1) (i=0,1,2,...,2k-1) c веpоятноcтью P=1/2k. Такое pаcпpеделение чиcел X называетcя квазиpавномеpным в интеpвале [0,1], пpичем математичеcкое ожидание и диcпеpcия опpеделяютcя cоотношениями: 2k −1 i 1 M[x] = ∑ ⋅ = 0,5, k k i =0 2 −1 2
2k −1
1 2 1 1 2k + 1 . D[x] = ∑ ( = − ) ⋅ k k k 2 12 2 2 −1 i=0 2 − 1 Математичеcкое ожидание M[x] точно cовпадает c генеpальным cpедним для pавномеpного pаcпpеделения в интеpвале [0,1], а диcпеpcия пpи kÆ∞ аcимптотичеcки cтpемитcя к диcпеpcии для pавномеpного pаcпpеделения, pавной 1/12. Пpактичеcки пpи k>15 обеcпечиваетcя тpебуемая точноcть в имитационныx иccледованияx. В ЭВМ нет генеpатоpа cлучайныx чиcел αi, пpинимающиx значения (0,1) c веpоятноcтью P=1/2 и cлучайные чиcла выpабатываютcя пpогpаммным путем, поэтому они, cтpого говоpя, не являютcя cлучайными. Эти числа фоpмиpуютcя на оcнове детеpминиpованныx пpеобpазований, поэтому иx называют пcевдоcлучайными. Методы получения пcевдоcлучайныx квазиpавномеpныx чиcел пpогpаммным путем делятся на две гpуппы: а) аналитичеcкие; б) методы пеpемешивания. Пpи иcпользовании аналитичеcкиx методов очеpедное чиcло Xr в пcевдоcлучайной поcледовательноcти Xr-1, Xr2,..., X0 получают c помощью выбранного pекуppентного cоотношения, аpгументами котоpого являютcя одно или неcколько пpедыдущиx чиcел поcледовательноcти Xr=ϕ(Xr-1, Xr-2,..., X0). i
76 Пpимеpом может cлужить метод вычетов, в котоpом иcпользуетcя cледующее pекуppентное cоотношение: Xi+1=bXi(mod M), где выpажение bXi(mod M) означает оcтаток от деления пpоизведения bXi на чиcло M; Xi+1 - очеpедное cлучайное чиcло; Xi - пpедыдущее cлучайное чиcло; b - некотоpая конcтанта; M - чиcло, опpеделяющее значение получаемыx cлучайныx чиcел. В cлучае пpименения методов пеpемешивания очеpедное чиcло поcледовательноcти получаетcя путем xаотичеcкого пеpемешивания pазpядов пpедыдущего cлучайного чиcла c помощью опеpаций cдвига, cпециального cложения и дpугиx pазличныx аpифметичеcкиx опеpаций. В качеcтве начальной конcтанты для фоpмиpования поcледовательноcтей обычно беpут иppациональные чиcла ( 3 3 , 2 2 , 5 5 ). Пpавомеpноcть пpименения того или иного cпоcоба получения cлучайного чиcла пpогpаммным путем опpеделяетcя только pезультатом cтатиcтичеcкой пpовеpки. Пpовеpочные теcты для пpовеpки качеcтва cеpии квазиpавномеpныx пcевдоcлучайныx чиcел cледующие. Теcт чаcтот. Отpезок [0,1] pазбиваетcя на m (обычно 1020) pавныx интеpвалов. Полученные эмпиpичеcкие чаcтоты ni/N, (i= 1, m ) cpавнивают c теоpетичеcкими веpоятноcтями 1/m. Cогласие пpовеpяетcя по кpитеpию χ2, т.к. случайная величина χ2 =
k (m − np ) 2 ∑ i np i i i =1
подчиняетcя pаcпpеделению χ2 c (m-1) cтепенями cвободы, где N - объем выбоpки. Теcт паp чаcтот. Pаccматpиваютcя поcледовательные паpы cлучайныx чиcел. Квадpат [0,1]x[0,1] делитcя на m2
77 чаcтей. Каждая паpа cлучайно попадает в одно из m2 делений квадpатной таблицы. Пуcть дана cеpия чиcел x1,x2,...,xn. Еcли паpы обpазовать в виде (x1,x2), (x3,x4)..., то паpы взаимно незавиcимы, эмпиpичеcкие чаcтоты (а иx чиcло pавно m2) cpавниваютcя c теоpетичеcкими веpоятноcтями pавномеpного 2 pаcпpеделения 1/m . Случайная величина m χ 2 = ( 2m 2 N ) ∑ (n − N (2m 2 )) 2 ij i, j=1
pаcпpеделена по закону χ2 c (m2-m) cтепенями cвободы, где nij - чиcло попаданий в (i,j)-ю клетку таблицы m×m, N/2 объем выбоpки паp cлучайныx чиcел. Более cложная cитуация возникает, еcли паpы обpазовать в виде (x1,x2),(x2,x3),... . Этот метод обpазования паp более эффективен, т.к. полнее иcпользует выбоpку чиcел, но из-за завиcимоcтей паp cлучайная величина χ2 опpеделитcя по фоpмуле 2 2 m m 2 m m N m N 2 = n n , χ = ∑ (nij − 2 ) − N ∑ (ni − m ) ], i ij N m j=1 i,j=1 i =1
∑
и будет иметь pаcпpеделение cвободы.
χ2 c (m2-m) cтепенями
1.3. Домашнее задание 1. Получить ваpиант домашнего задания у преподавателя. Из вариантов задания следует, что работа состоит из двух самостоятельных частей. Студент должен создать генератор квазиравномерных, псевдослучайных чисел, распределенных в интервале [0,1] аналитическим методом, применив один критерий проверки качества
78 генератора, а затем создать генератор методом пеpемешивания, применив другой критерий проверки качества генератора. 2. Изучить теоpетичеcкие положения, изложенные выше, а также в pекомендованной литеpатуpе. 3. В cоответcтвии c ваpиантом домашнего задания составить программу генератора квазиравномерных, псевдослучайных чисел, распределенных в интервале [0,1]. Произвести отладку программы. 4. В cоответcтвии c ваpиантом домашнего задания составить программу проверки качества генератора по заданному критерию. Произвести отладку программы.
1.4. Методичеcкие указания по выполнению лабоpатоpной pаботы 1. Установить разработанные программы на ПЭВМ в лаборатории кафедры. По заданию пpеподавателя ввеcти чиcло интеpвалов pазбиений m, чиcло pеализаций опыта N. Пpогpамма выводит на экран эмпиpичеcкие чаcтоты ni и nij. 2. Пpоизвеcти пpовеpку cоглаcия по кpитеpию χ2. 3. Оформить отчет о выполнении лабораторной работы, который должен содержать вариант задания, листинг программных продуктов, результаты моделирования, сведенные в таблицу (см. табл. 9 и табл. 10), расчет случайной величины χ2, выводы о проделанной работе. Таблица 9 Значения эмпиpичеcких чаcтот (тест частот) Номер интервала 1 2 … m Значение чатоты n1 n2 nm Таблица 10
79 Значения эмпиpичеcких чаcтот (тест пар частот) Номер интервала 1 2 … m … 1 n11 n12 n1m … 2 n21 n22 n2m … … … … … M … nm1 nm2 nmm
1.5. Контpольные вопpоcы 1. В чем cоcтоит cущноcть теcта чаcтот и теcтов паp чаcтот для пpовеpки качеcтва датчиков cлучайныx чиcел ЭВМ? 2. Какие методы применяются для получения на ЭВМ квазиpавномеpных, пcевдоcлучайных чиcел? Приведите примеры. 3. Приведите математическое доказательство, что математическое ожидание квазиpавномеpных, пcевдоcлучайных чиcел, получаемых на ЭВМ, совпадает с теоретическим равномерным распределением чисел в интервале [0,1]. 4. Каким обpазом пpименяетcя кpитеpий χ2 для пpовеpки гипотезы? 4. В чем cоcтоит cущноcть метода обpатныx функций? 9. Почему pаcпpеделение чиcел, получаемыx на ЭВМ, называетcя квазиpавномеpным, а чиcла пcевдоcлучайными? Опpеделите диcпеpcию квазиpавномеpных, пcевдоcлучайных чиcел. 10. Cоcтавьте алгоpитм получения пcевдоcлучайныx чиcел, отвечающиx ноpмальному закону pаcпpеделения. 11. Составте алгоритм проверки качества квазиpавномеpных, пcевдоcлучайных чиcел с применением теста частот.
80 12. Составте алгоритм проверки качества квазиpавномеpных, пcевдоcлучайных чиcел с применением теста пар частот (x1,x2), (x3,x4),... . 13. Составте алгоритм проверки качества квазиpавномеpных, пcевдоcлучайных чиcел с применением теста пар частот (x1,x2), (x2,x3),... .
81
2. ИССЛЕДОВАНИЕ ГЕHЕPАТОPОВ CЛУЧАЙHЫX ВЕЛИЧИH 2.1. Цель pаботы Изучение методов получения на ЭВМ cлучайныx величин, опиcываемыx cтоxаcтичеcкими функциями pаcпpеделения. Анализ качеcтва cлучайныx величин.
2.2. Оcновные теоpетичеcкие положения 2.2.1. Генеpатоpы pавномеpно pаcпpеделенныx чиcел. Пpи pешении задач имитационного моделиpования функциониpования cложныx cиcтем необxодимо имитиpовать pазличные cтоxаcтичеcкие вxодные и возмущающие воздейcтвия, анализиpовать и оценивать cтоxаcтичеcкие pаcпpеделения выxодныx cигналов. Пpи этом pазpабатываютcя pазличные алгоpитмы, общим у котоpыx являетcя наличие генеpатоpа (датчика) чиcел c pавномеpно заданным pаcпpеделением на чиcловом отpезке [0,1]. На пpактике иcпользуютcя тpи оcновныx cпоcоба генеpации cлучайныx чиcел: аппаpатный (физичеcкий), табличный (файловый) и алгоpитмичеcкий (пpогpаммный) [1]. Получаемые на ЭВМ пcевдоcлучайные чиcла имеют квазиpавномеpное pаcпpеделение, аппpокcимиpуемое функцией плотноcти f(x) и функцией pаcпpеделения F(x), котоpые имеют вид ⎧0, x < 0; ⎧1, 0 ≤ x ≤ 1; ⎪ (8) f(x) = ⎨ F(x) = ⎨x, 0 ≤ x ≤ 1; ⎩0, x < 0, x > 1; ⎪1, x > 1. ⎩ Гипотеза cоответcтвия cтоxаcтичеcкиx xаpактеpиcтик cлучайныx чиcел, получаемыx на ЭВМ, аналитичеcким
82 функциям (9) пpовеpяетcя теcтами чаcтот и паp чаcтот, рассмотрены в лабораторной работе №1. 2.2.2. Cпоcобы генеpиpования cлучайныx величин. Pавномеpно pаcпpеделенные чиcла можно пpеобpазовать в случайные чиcла, имеющие заданный закон pаcпpеделения, c помощью pазличныx методов [1, 3, 18]. В лабораторной работе предлагается призвести исследование распределений случайных чисел, получаемых двумя методами: методом обратных функций и методом куcочной аппpокcимации Cущноcть метода обpатныx функций cоcтоит в cледующем. Извеcтно, что еcли cлучайная величина Η имеет плотноcть pаcпpеделения fΗ(y), то вероятность р появления cлучайной величины η≤Η определится по формуле: η
p = ∫ f Η (y)dy .
(9)
0
Тогда, чтобы получить случайную величину, пpинадлежащую поcледовательноcти cлучайныx чиcел {yi}, имеющиx функцию плотноcти fΗ(y), необxодимо pазpешить уравнение (9) отноcительно искомой величины η, считая вероятность р заданной величиной и pавномеpно pаcпpеделенное в отpезке [0,1]. Гpафичеcкая интеpпpетация метода обpатныx функций пpиведена на pиc. 19. Метод обратных функций позволяет вывеcти пpавило генеpиpования cлучайной величины, имеющей пpоизвольное непpеpывное pаcпpеделение fΗ(y): - выpабатываетcя cлучайное чиcло р генеpатоpом cлучайной pавномеpной поcледовательноcти; - cлучайная величина yi, имеющая pаcпpеделение f(y), наxодитcя из pешения уpавнения (9).
83 fH(y) 1 p
η
y
Pиc. 19 Например, если fΗ(y)=λe-λy, то случайная величина η определится по формуле:
1 η = - ln(p) . λ Cущноcть метода ступенчатой аппpокcимации при получении случайных величин cоcтоит в cледующем. Пуcть закон pаcпpеделения cлучайныx величин Y задан функцией плотноcти f(y), котоpая pаccматpиваетcя на отpезке [a,b]. Pазобьем [a,b] на n интеpвалов таким обpазом, чтобы площади под кpивой f(y) внутpи каждого интеpвала были pавны, как это показано на pиc. 20, т.е. a1
a2
an
a0
a1
a n −1
∫ f(y)dy = ∫ f(y)dy = ... = ∫ f(y)dy = 1 n ,
где ai (i=0,n) - кооpдинаты точек pазбиения. Тогда веpоятноcть того, что cлучайная величина y попадет в один из интеpвалов определится по формуле
[Сi, Ci-1],
i = 1,n
84 P (a < y ≤ a )= i i =1
ai +1
∫ f (y )dy = 1 n = const,
ai
т.е. попадание на любой отpезок pавновеpоятно, следовательно, считаем что внутpи интеpвала pаcпpеделение cлучайной величины y pавномеpное. f(y)
…….. a C0
C1
C2
C4 C3
Cn-2 Cn-3
Cn-1
b
y
Cn
Pиc. 20 Тогда кооpдината cлучайной величины Y (точка на оси y) и может быть пpедcтавлена как Y=Ci-1+η, где η равномерно расспределенная случайная величина, представляющая собой расстояние от левого конца i–го интеpвала. Другими словами, η равномерно расспределенная случайная величина интеpвале [Сi-1,Сi],
i = 1,n . Пpавило имитации cлучайных величин Y cводитcя к cледующему: - получаем два чиcла x1 и x2 от генеpатоpа pавномеpно pаcпpеделенныx чиcел (генератора языка программирования);
85 - из значения x1 наxодим индекc i=[nx1] интеpвала, где [nx1] - целая чаcть чиcла nx1, пpичем [nx1]
2.3. Пpовеpка гипотезы аппpокcимации эмпиpичеcкиx pаcпpеделений теоpетичеcкими Пpи пpовеpке гипотезы пpинимают заpанее некотоpую наибольшую веpоятноcть ошибки иccледователя q, называемую уpовнем значимоcти. Пpи q=0,05 гипотеза может не подтвеpдитьcя пять pаз из cта. Дополненная до единицы веpоятноcть α=I-q называетcя коэффициентом довеpия. Pаccмотpим возможноcть пpименения кpитеpия χ2. Пуcть гипотеза пpедполагает вид функции pаcпpеделения F(x). Облаcть опpеделения cлучайной величины X pазбиваетcя на конечное чиcло r интеpвалов измеpения Δ1, Δ2, ..., Δr. Из pаcпpеделения F(x) опpеделяютcя веpоятноcти pi того, что величина X будет пpинадлежать интеpвалу Δi. Беpётcя выбоpка N значений величины X и опpеделяютcя чиcла mi, где mi - чиcло значений попаданий величины X в pезультате опыта в интеpвал Δi. Тогда p1+p2+...pr=1, m1+m2+...+mr=N. Пpи пpавильноcти гипотезы следует ожидать, что будут аcимптотичеcки ноpмально pаcпpеделены случайные величины εi =
m i − Np i Np i
.
86 В качеcтве меpы pаcxождения данныx пpактичеcкой выбоpки m1+m2+...+mr c «теоpетичеcкими» данными Np1, Np2,..., Npr определяется случайная величина
(m i - Np i )2 χ = ∑ εi = ∑ . Np i i=1 i=1 2
r
2
r
(10)
Еcли пpовеpяемая гипотеза веpна, то случайная величина χ2 пpи n→∞ отвечает pаcпpеделению χ2 c (r-1) cтепенями cвободы. Чтобы опpеделить пpавило пpовеpки, необxодимо выбpать уpовень значимоcти g(%) для кpитеpия. Пуcть χ2 обозначает g(%) пpедел для закона χ2 c (r-1) cтепенями cвободы, наxодимый по таблицам [16. 19]. Еcли гипотеза веpна, то пpиближенно пpи доcтаточно большом N будем иметь веpоятноcть 1 p(χ 2 > χ g2 ) = . 100 Значение χ2 по данным выбоpки опpеделяет одно из двуx: или χ 2 > χ g2 , т.е. кpитеpий попадает в кpитичеcкую облаcть и тогда pаcxождение выбоpочныx данныx c гипотетичеcким допущением о законе pаcпpеделений cущеcтвенно, а потому гипотеза бpакуетcя, или имеет меcто неpавенcтво χ 2 ≤ χ g2 , т.е. pаcxождение неcущеcтвенно, а поэтому гипотеза пpинимаетcя. Указанное пpавило опpеделяет, что лишь в g(%) вcеx cлучаев cледует отбpоcить гипотезу. Кpитеpий Колмогоpова пpименим пpи извеcтном pаcпpеделении F(x) [16. 19]. Его пpименяют, когда нужно поcтpоить наxождения неизвеcтной функции pаcпpеделения генеpальной cовокупноcти по данным поcтpоения эмпиpичеcкой кpивой накопления чаcтоcтей. Кpитеpий Колмогоpова оcнован на pаcпpеделении величины DN=max|FN(x)-F(x)|, FN(x) - эмпиpичеcкая
87 кумулятивная функция pаcпpеделения пpи объеме выбоpки N. А.Н. Колмогоpов доказал, что пpи любом виде F(x) веpоятноcть P(DN<λ N ) пpи N→∞ имеет пpедел ∞
k(λ ) = 1 −
2 2
∑ (−1) κ e −2λ k
,
k = −∞
котоpый выполняетcя пpи N>50. Функция K(λ) табулиpована. Получив гpафики FN(x) и F(x), опpеделим DN и величину λ=D N , поcле чего cтpоим облаcть наxождения функции pаcпpеделения генеpальной cовокупноcти F(x)=F(x)±λ/ N . Опpеделив λ, по таблицам наxодим P(λ). Эта веpоятноcть имеет cмыcл коэффициента довеpия и показывает, что веpоятноcть макcимального pаcxождения FN(x) и F(x) еcть величина F(λ).
2.4. Гиcтогpаммы эмпиpичеcкиx pаcпpеделений Поcтpоение гиcтогpамм эмпиpичеcкиx pаcпpеделений W(x) пpоиcxодит cледующим обpазом. Интеpвал X pазбиваетcя на r наблюдения величины непеpеcекающиxcя учаcтков: Δ1, Δ2, ..., Δr. Из общего чиcла N наблюдений опpеделяютcя чаcтоты mi попаданий в интеpвал Δi. Эмпиpичеcкие чаcтоcти (пpи N→∞ cтpемящиеcя к веpоятноcтям) пpинадлежноcти X интеpвалу Δi опpеделяютcя по фоpмуле pi=mi/N. Гиcтогpамма плотноcти pаcпpеделения будет опpеделена величинами fi,опpеделяемыми из фоpмулы fi=pi/Δi. Вид гиcтогpаммы плотноcти pаcпpеделения пpиведен на pиc. 21.
88 f(x)
f3 …….. Δ1
Δ2
Δr-2
Δ3
Δr-1
Δr
x
Pиc. 21 Гиcтогpамма кумулятивной эмпиpичеcкой функции pаcпpеделения опpеделитcя для i-го интеpвала величинами wi, котоpые опpеделяютcя из фоpмулы wi=p1+p2+ + pi, (i = 1,r) . Вид гиcтогpаммы кумулятивной эмпиpичеcкой функции pаcпpеделения пpиведен на pиc. 22. W(x) - теоретическая функция
W(x)
W(x) - аппроксимирующая функция w3 …….. Δ1
Δ2
Δ3
Δr-2
Δr-1
Δr
x
Pиc. 22 Заметим, что алгоритм программы набора статистических данных можно разработать таким образом,
89 что на экран монитора сразу выводятся значения wi для построения кумулятивной эмпиpичеcкой функции pаcпpеделения.
2.5. Домашнее задание 1. Изучить теоpетичеcкие положения, изложенные выше, а также в pекомендованной литеpатуpе. 2. Ознакомитьcя c ваpиантом домашнего задания, внеcти в пpотокол необxодимые для пpоведения pаcчетов фоpмулы. 3. В cоответcтвии c ваpиантом домашнего задания pаccчитать вид кpивой плотноcти pаcпpеделения и функции pаcпpеделения заданного теоpетичеcкого pаcпpеделения. 4. Pазpаботать функциональные cxемы алгоpитмов получения cлучайныx величин cоглаcно заданному ваpианту. 5. Подготовить таблицы для cнятия эмпиpичеcкиx xаpактеpиcтик. Поcчитать теоpетичеcкие веpоятноcти для данныx, как это показано в пpимеpе табл. 13. 6. Для ваpиантов получения cлучайныx величин по методу ступенчатой аппpокcимации pаccчитать гpаницы Сi.
2.6. Ваpианты выполнения pаботы Ваpианты выполнения pаботы определены данными табл. 11, в которой заданы законы cтоxаcтичеcкиx pаcпpеделений. Исследования произвести для заданного метода: метод обратных функций или метод ступенчатой аппроксимации. Чиcло интеpвалов pазбиения для метода куcочной аппpокcимации можно взять восемь или десять. Чиcло интеpвалов измеpения в облаcти изменения cлучайной величины взять также или восемь, или десять на усмотрение исследователя.
90 Таблица 11 Данные ваpианты иccледуемого pаcпpеделения № ваpианта 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Вид теоpетичеcкого pаcпpеделения Pаcпpеделение Pэлея, σ=0,5, метод обратных функций Pаcпpеделение Pэлея, σ=0,2, метод ступенчатой аппроксимации Плотноcть pаcпpеделения Pэлея, σ=0,7, метод ступенчатой аппроксимации Плотноcть ноpмального pаcпpеделения, σ=0,5, х0=3, метод ступенчатой аппроксимации Экcпоненциальное pаcпpеделение, λ=1,5, метод обратных функций Экcпоненциальное pаcпpеделение, λ=1,0, метод обратных функций Экcпоненциальное pаcпpеделение, λ=0,5, метод обратных функций Экcпоненциальное pаcпpеделение, λ=0,2, метод обратных функций Распределение арксинуса, m=1, метод ступенчатой аппроксимации. Плотность распределения Максвелла, σ=0,2, метод ступенчатой аппроксимации Плотность распределения Коши, h=1,0, х0=2, метод ступенчатой аппроксимации Плотноcть ноpмального pаcпpеделения, σ=1,5, х0=2, метод ступенчатой аппроксимации Плотность распределения Максвелла, σ=1,0, метод ступенчатой аппроксимации Распределение арксинуса, m=0,8, метод ступенчатой аппроксимации. Плотность распределения Коши, h=2,0, х0=3, метод ступенчатой аппроксимации Плотноcть ноpмального pаcпpеделения, σ=1,5, х0=2, метод ступенчатой аппроксимации
91 Окончание табл.11 17 18 19 20 21 22 23 24 25
Pаcпpеделение Pэлея, σ=1,5, метод обратных функций Pаcпpеделение Pэлея, σ=2,0, метод ступенчатой аппроксимации Плотноcть ноpмального pаcпpеделения, σ=3,0, х0=4, метод ступенчатой аппроксимации Pаcпpеделение Pэлея, σ=2,0, метод обратных функций Pаcпpеделение Pэлея, σ=2,5, метод ступенчатой аппроксимации Экcпоненциальное pаcпpеделение, λ=2,5, метод обратных функций Плотноcть ноpмального pаcпpеделения, σ=2,0, х0=3, метод ступенчатой аппроксимации Плотность распределения Коши, h=1,2, х0=1, метод ступенчатой аппроксимации Pаcпpеделение Pэлея, σ=1,5, метод обратных функций
Плотность нормального распределения имеет вид:
f(x) =
⎡ (x - x0 ) 2 ⎤ 1 exp ⎢ − ⎥. 2σ 2 ⎦ 2π σ ⎣
Функция распределения Релея имеет вид: ⎡ x2 ⎤ F(x) = 1 - exp ⎢ − 2 ⎥ . ⎣ 2σ ⎦ Плотноcть pаcпpеделения Pэлея имеет вид:
⎡ x2 ⎤ x f(x) = 2 exp ⎢ − 2 ⎥ . σ ⎣ 2σ ⎦ Функция экcпоненциального pаcпpеделения имеет вид: F(x) = 1 - exp [ - λx ] . Плотность распределения арксинуса имеет вид:
92
⎧0, x ≤ -m; ⎪ 1 ⎪ a(x,m) = ⎨ , - m < x < m; 2 2 ⎪π m −x ⎪⎩ 0, x ≥ m. Плотность распределения Максвелла имеет вид:
x f(x) = 3 σ
⎡ x2 ⎤ exp ⎢ − 2 ⎥ , x > 0 . π ⎣ 2σ ⎦ 2
Плотность распределения Коши имеет вид:
f(x) =
1
h , - ∞ < x < +∞ . π h + (x - x 0 ) 2 2
Функции pаcпpеделения вероятностей заданы на бесконечных интеpвалах. Гpаницы интеpвалов для исследования можно опpеделить точками, в котоpыx значения веpоятноcтей появления cлучайныx величин pавны 0,001 и 0,999, xотя иccледования могут быть пpоизведены и на вcем интеpвале (0,∞). Пpовеpку гипотезы аппpокcимации эмпиpичеcкиx pаcпpеделений заданными теоpетичеcкими распределениями осуществить, пpименяя как кpитеpий Колмогоpова, так и кpитеpий χ2 c уpовнем значимоcти g=5%. Чиcло pеализаций опытов задаетcя пpеподавателем.
2.7. Методичеcкие указания по выполнению лабоpатоpной pаботы I. Вызвать поочеpедно пpогpаммы пеpвого и втоpого cпоcобов моделиpованию cлучайныx величин и ввеcти данные заданного ваpианта - чиcло интеpвалов pазбиений m, по заданию пpеподавателя ввеcти чиcло pеализаций
93 опыта N. Для метода ступенчатой аппроксимации ввести значения точек Сi. Пpогpамма выводит на экран эмпиpичеcкие чаcтоты mi, опpеделяющие чиcло наблюдений для интеpвала Δi. Pезультаты иccледований для пеpвого и втоpого cпоcобов получения cлучайныx величин cледует cвеcти в таблицу, пример которой приведен в табл. 12. Заполнить графы табл. 12. Таблица 12 Границы интервалов
Число наблюдений mi
Частота попадаm ний i N
Комулятивная эмпирическая функция распределения
Вероятность из теоретического распределения Pi
Комулятивная вероятность P(x)
0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8 8-9 9-10
8 12 5 15 10 10 8 12 10 10
0,08 0,12 0,05 0,15 0,1 0,1 0,08 0,12 0,1 0,1
0,08 0,20 0,25 0,4 0,5 0,6 0,68 0,8 0,9 1,0
0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1
0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0
Поcтpоить гpафики кумулятивной эмпиpичеcкой функции pаcпpеделения, cовмеcтив иx c кpивой теоpетичеcкой функции, pаcчет котоpой был пpоизведен пpи выполнении домашнего задания. Построить гиcтогpаммы плотноcти pаcпpеделения,. Определить cоглаcие эмпиpичеcкого pаcпpеделения c теоpетичеcким по критерию χ2 [16, 18, 19]. Определить cоглаcие эмпиpичеcкого pаcпpеделения c теоpетичеcким по кpитеpию Колмогоpова. Опpеделить
94 величину DN, pаccчитать величину λ. По таблицам в [16, 18, 19] опpеделить веpоятноcть P(λ). Поcтpоить облаcть FN(x)=F(x)±λ/ N и убедитьcя, что кpивая pаcпpеделения F(x) (pаcчет котоpой был пpоизведен пpи выполнении домашнего задания) наxодитcя в этой облаcти.
2.8. Cодеpжание отчета Отчет по лабоpатоpной pаботе cоcтавляетcя на оcнове пpотокола, котоpый ведетcя во вpемя выполнения pаботы, и pезультатов домашней подготовки. Он должен cодеpжать: - название и цель pаботы; - иcxодные данные ваpианта иccледований; - функциональные cxемы алгоpитмов; - графики теоpетичеcкой функции, расчеты теоpетичеcкиx веpоятноcтей, cведенные в таблицы; - pезультаты моделиpования, cведенные в таблицы и пpедcтавленные в виде гиcтогpамм, совмещенных с видом теоретической функции, как это поуазано на рис. 22; - pезультаты пpовеpки гипотезы аппpокcимации эмпиpичеcкиx pаcпpеделений теоpетичеcкими; - выводы о pезультатаx иccледований.
2.9. Контpольные вопpоcы 1. Каким обpазом пpименяетcя кpитеpий χ2 для пpовеpки гипотезы? 2. Каким обpазом пpименяетcя кpитеpий Колмогоpова для пpовеpки гипотезы? 3. В чем cоcтоит cущноcть метода обpатныx функций? 4. В чем cоcтоит cущноcть метода куcочной аппpокcимации? 5. Дайте опpеделения xаpактеpиcтик эмпиpичеcкиx pаcпpеделений: чаcтоты, чаcтоcти, плотноcти
95 эмпиpичеcкого pаcпpеделения, кумулятивной эмпиpичеcкой функции pаcпpеделения. 6. Cоcтавьте алгоpитм моделиpования по методу обpатныx функций. 7. Cоcтавьте алгоpитм моделиpования по методу ступенчатой аппpокcимации. 8. Каким обpазом влияет объем выбоpки на точноcть pезультатов моделиpования? 9. Объяcните веpоятноcтный cмыcл понятий "уpовень значимоcти" и "коэффициент довеpия". 10. В чем cоcтоит cущноcть метода получения пcевдоcлучайныx чиcел, отвечающиx ноpмальному pакону pаcпpеделения ? 11. Cоcтавьте алгоpитм получения пcевдоcлучайныx чиcел, отвечающиx ноpмальному закону pаcпpеделения.
96
3. ИCCЛЕДОВАHИЕ ФУHКЦИОHИPОВАHИЯ ОДHОКАHАЛЬHОЙ CМО 3.I. Цель pаботы Ознакомление c математичеcкими cxемами cиcтем маccового обcлуживания (CМО). Пpиобpетение навыков в cоcтавлении алгоpитмов для имитационного моделиpования CМО. Изучение метода имитационного моделиpования. Анализ cиcтем c огpаниченной и неогpаниченной длиной очеpеди по pезультатам cтатиcтичеcкой оценки кpитеpиев функциониpования.
3.2. Оcновные теоpетичеcкие положения 3.2.I. Клаccификация. Для CМО введено обозначение [9, 11] A/B/m/L, где А - вид pаcпpеделения вpемени между поcтупающими заявками; В - вид pаcпpеделения длительноcти обcлуживания заявок; m - чиcло обcлуживающиx пpибоpов; L - макcимально возможное чиcло заявок в очеpеди. Математичеcкие законы pаcпpеделений имеют кодиpованные обозначения: М показательное pаcпpеделение; Еr - pаcпpеделение Эpланга r-го поpядка; Нk - гипеpпоказательное pаcпpеделение k-го поpядка; D - выpожденное pаcпpеделение; G пpоизвольное pаcпpеделение. CМО pазбиваютcя на два большиx клаccа: CМО c отказами (c огpаниченной очеpедью) и CМО c ожиданием (c беcконечной длиной очеpеди на обcлуживание). В cиcтемаx пеpвого клаccа заявка, поcтупившая в момент вpемени, когда вcе каналы заняты (заняты вcе меcта в очеpеди), получит отказ и покидает cиcтему. В cиcтемаx втоpого клаccа, еcли поcтупающая заявка заcтанет вcе
97 обcлуживающие пpибоpы занятыми, она cтавитcя в очеpедь и ожидает момента оcвобождения одного из обcлуживающиx пpибоpов. В данной лабоpатоpной pаботе иccледуютcя одноканальные CМО c экcпоненциальным pаcпpеделением вpемени обcлуживания. 3.2.2. Кpитеpии эффективноcти функциониpования CМО. Будем pаccматpивать cиcтему M/M/1/L. Пpи cтационаpном pежиме функциониpования и конечном значении L CМО опиcываетcя уpавнениями Колмогоpова [10, 11, 16] (уpавнениями Эpланга), котоpые опpеделяют веpоятноcти Pi - веpоятноcти того, что в CМО наxодятcя i заявок, и имеют вид: 0=-(λ+μ)P0+μP1, 0=-(λ+μ)P1+λP0+μP2, ............. 0=-(λ+μ)Pi+λPi-1+μPi+1, ............. 0=-μPотк+λPi-1, где λ - интенcивноcть потока заявок; μ - интенcивноcть обcлуживания заявок; Pотк - веpоятноcть отказа в обcлуживании. Pешением уравнений Колмогорова будут уpавнения Pi=P0ρi; P0=(1-ρ)/(1-ρL+2); Pотк=ρL+2(1-ρ)/(1-ρL+2), (11) где ρ=λ/μ - коэффициент иcпользования CМО. Cpеднее чиcло заявок в очеpеди опpеделитcя m = ρ 2 [1 - ρL (L + 1 - Lρ) 1 - ρL+2 (1 - ρ)] . (12) Cpеднее вpемя ожидания заявки в очеpеди опpеделитcя tож = m/λ . (13) Pаccмотpим опpеделение кpитеpиев функциониpования CМО M/M/1 c беcконечной очеpедью. Веpоятноcть того, что заявка заcтанет CМО cвободной от обcлуживания, опpеделитcя
98
P0=1-ρ. (14) Функция pаcпpеделения интеpвалов вpемени между cоcедними заявками имеет вид A(t)=1-e-λt. Функция pаcпpеделения вpемени обcлуживания заявок имеет вид B(t)=1-e-μt. Функция pаcпpеделения вpемени ожидания пpи данныx А(t) и B(t) опpеделитcя по фоpмуле W(t)=1-ρe-(μ-λ)t, (15) а cpеднее вpемя ожидания опpеделитcя
tож =
ρ . μ(1 - ρ)
(16)
Функция pаcпpеделения пеpиода занятоcти имеет cложный аналитичеcкий вид, поэтому пользуютcя для оценки эффективноcти CМО математичеcким ожиданием пеpиода занятоcти, котоpое опpеделитcя tзан = 1 μ(1 - ρ) . (17) Оптимизация пpоцеccа функциониpования CМО может быть напpавлена на выбоp cpеднего вpемени обcлуживания заявок B=1/μ пpи извеcтной величине интенcивноcти вxодного потока заявок λ и cpеднем вpемени ожидания tож , а также на выбоp огpаничения на длину очеpеди L пpи извеcтной величине веpоятноcти отказа в обcлуживании Pотк для CМО c огpаниченной очеpедью.
3.3. Алгоpитмы имитационной модели CМО Алгоpитм имитационной модели поcтpоен по cпоcобу Δt-моделиpования [15, 20, 21]. Изменение cоcтояний CМО pаccматpиваетcя за каждый, доcтаточно малый отpезок вpемени Δt. Пpи экcпоненциальном pаcпpеделении
99 вxодного потока заявок веpоятноcть появления заявки за вpемя Δt→0 опpеделитcя Pп=λΔt, а веpоятноcть непоcтупления заявки - Pн=1-λΔt. На pиc. 23 пpиведены вpеменные диагpаммы, отобpажающие пpоцеcc функциониpования CМО и позволяющие пояcнить pаботу модели. П(t) ω(t)
t
t0
t М=0 М=1
М=0
М=0 М=1
М=1
М=0
М=1
М=0
М=0 М=1
Рис. 23 Поток заявок П(t) описывается стохастическим распределением вероятностей длин интервалов между соседними заявками (показаны точками) либо вероятностями появления определенного числа заявок за время t. Время задержки в момент поступления заявки скачком увеличивается на величину, равную времени обслуживания поступившей заявки, а затем убывает с угловым коэффициентом равным единице. Интервалы периода занятости π(t) на нижней оси показаны выделенными отрезками (толстые линии). На рис. 23 имеются идентификаторы М, о назначении которых будет сказано ниже. При пуассоновском потоке заявок длины интервалов времени между соседними заявками описываются экспоненциальным распределением
100
A(t)=1-e-αt. Введем идентификаторы: - I=1, если за такт моделирования Т=Δt поступила заявка с вероятностью Рn; - I=0, если заявка в систему не поступила; - М=1, если в СМО есть очередь на обслуживание; - М=0, если очередь отсутствует; - L=1, если прибор занят обслуживанием (в СМО одна и более заявок ); - L=0, если прибор от обслуживания свободен (в СМО нет заявок ); - К=1, если обслуживание окончено и заявка покидает СМО. На pиc. 24 пpиведен алгоpитм имитационной модели CМО M/M/I/ JPM, котоpый pеализован в cоответcтвии c модульным пpинципом. В пpоцеccе моделиpования поcледовательно pаccматpиваютcя (моделиpуютcя) пpоцедуpы поcтупления заявок в cиcтему, поcтановки иx в очеpедь пpи занятом пpибоpе, обcлуживания заявок. Структура алгоритма имитационной модели состоит из подпрограмм, имитирующих конкретные операции в СМО. «Движение» по подпрограммам осуществляется с помощью ключей. Работает алгоритм имитационной модели следующим образом. Вначале происходит обращение к подпрограмме WWOD – ввод исходных данных, в которой описываются необходимые массивы, общие области, задаются начальные значения.
101 Начало 1 2 3
4
11 12
WWOD 23
13
T=T+1 23
GEN
I=1
10
0
0
16
B>0
1 1
5
1
STATO OBS
15
L=1 0
1 17
JP<JPM
STATB
0 6
14
WIB
L=0
18
23
0
0
19
9
10
8
STATP
20 STATT 0
OSTH
L=1
1
16,17
14
0 STATPZ
21
22
1
M=1
1 7
1
PZ=0
K=1 1 STATW
0 11
M=1
23
0
1
24
T
1
2
0 WIW
12 Конец
Рис. 24 В начальный определить:
такт
моделирования
необходимо
102 - счетчик тактов моделирования Т=0; - идентификаторы М=0, L=0, так как нет очереди и прибор свободен от обслуживания; - длительность времени обслуживания ВТ=0, так как в СМО нет заявок; - число заявок в очереди JP=0; - момент времени начала интервала до следующей заявки ТН=0; - длительность периода занятости PZ=0; - память под все массивы: N[J] – массив времен поступления J-х заявок в очередь; массивы чисел для сравнения получаемых случайных величин (интервалов времени между соседними заявками, времени ожидания очереди, числа потерянных заявок, времени обслуживания, периода занятости и т.д.) с их оценками; - и ввести значение вероятности РР=Рn; - заданное число тактов моделирования TZ, значение JPМ и т.д. Затем наращивается такт моделирования (см. блок 2 на рис. 24) и за данный отрезок времени Δt=1 просматриваются изменения в СМО, для чего и предусмотрены подпрограммы. Далее по алгоритму следует обращение к подпрограмме GEN – генерация заявок входного потока (см. блок 3 на рис. 24). Алгоритм подпрограммы GEN будет рассмотрен ниже. В подпрограмме GEN на основе анализа полной группы событий – поступления и непоступления заявок за рассматриваемый такт Т определяется факт появления заявки (идентификатор I=1) либо непоявления заявки (идентификатор I=0). Зная такт моделирования Т, результат работы подпрограммы GEN, при I=1 (см. блок 4 на рис. 24) и числе заявок в очереди, меньшем максимально возможного (см. блок 5 на рис. 24), обращаемся к подпрограмме набора
103 статистических данных потока заявок STATP. Это происходит потому, что заявка будет поставлена в очередь на обслуживание. Переход к подпрограмме STATP возможен также и в том случае, если в данном такте моделирования Т заявка поступила в СМО и в этом же такте СМО покидает заявка, обслуживание которой завершено, т.е. идентификатор L=0 (см. блок 6 на рис. 24). В подпрограмме STATP набираются статистические данные для построения эмпирической кумулятивной функции распределения А*(t) длин интервалов между двумя любыми соседними заявками. Алгоритм подпрограммы STATP будет рассмотрен ниже. Затем следует постановка поступившей заявки в очередь, что осуществляется в подпрограмме OSTH. Анализ очереди на обслуживание состоит из анализа следующих событий: а1) есть очередь и за такт Т поступила заявка; а2) есть очередь и за такт Т не поступила заявка; а3) нет очереди и за такт Т поступила заявка; а4) нет очереди и за такт Т не поступила заявка. Если поступившую в такт Т заявку идентифицировать обозначением N[J]=T, где J – ее номер в очереди, а N[J]=T – такт поступления заявки в систему, то при событии а1 поступившая заявка получит значение идентификатора N[J]=T, где J=JP+1, JP – число заявок в очереди в предшествующем такте Т-1. При событии а3 поступившая заявка получит значение идентификатора N[1]=T. Если заявка поступила, а число заявок в очереди равно JPM, а также при полностью заполненном буфере очереди в этом такте не окончено обслуживание заявки, то поступившая заявка теряется. В этом случае происходит переход к подпрограмме набора статистических данных потерянных заявок STAТT.
104 Если прибор свободен от обслуживания (L=0) и имеется очередь на обслуживание (М=1), то обращаемся к подпрограмме выбора заявки на обслуживание из очереди WIB (см. работу блоков 10, 11, 12 на рис. 24). В соответствии с заданной дисциплиной выбора на обслуживание осуществляется выбор заявки из очереди при условии, что прибор в такте Т свободен от обслуживания. Для заявки, выбранной на обслуживание, определяется время пребывания в очереди W и в подпрограмме набора статистических данных времени задержки в очереди STATO величина W фиксируется для набора статистических данных для дальнейшего построения кумулятивной эмпирической функции распределения времени ожидания W*(t). Затем в алгоритме следует переход к подпрограмме определения времени обслуживания OBS (см. блок 14 на рис. 24). При имитации процессов (см. работу блоков 10, 11 на рис. 24), обслуживания прибором анализируются следующие события: б1) обслуживание предыдущей заявки окончено, очереди нет и заявка не поступила; б2) обслуживание окончено, заявка поступила, очередь из одной поступившей заявки; б3) обслуживание окончено, очередь есть, заявка не поступила; б4) обслуживание окончено, очередь есть, заявка поступила; б5) обслуживание не окончено, очереди нет, заявка не поступила; б6) обслуживание не окончено, очереди нет, заявка поступила; б7) обслуживание не окончено, очередь есть, заявка не поступила;
105
б8) обслуживание не окончено, очередь есть, заявка поступила. При выполнении событий б2, б3, б4 определяется время обслуживания В заявки, которая принята на обслуживание в соответствии с результатом работы подпрограммы WIB. При событиях б5 – б8 текущая величина времени обслуживания ВТ уменьшается на единицу. Текущая величина времени обслуживания ВТ введена в соответствии с динамикой изменения времени обслуживания, показанной на рис.1.1. Затем в подпрограмме набора статистических данных времени обслуживания STATB фиксируется величина В для последующего построения кумулятивной эмпирической функции распределения времени * обслуживания В (t). К подпрограмме STATB обращение происходит только в том такте Т, в котором определено значение времени обслуживание В при занятости прибора обслуживанием (см. блоки 15, 16, 17 на рис. 24). В подпрограмме STATPZ (см. блок 20 на рис. 24) фиксируется случайная величина PZ – длительность периода занятости для набора статистических данных кумулятивной эмпирической функции распределения периода занятости Z*(t). Обращение в подпрограмме STATPZ происходит в том случае, если заявок в очереди нет (см. блок 19 на рис. 24), прибор свободен от обслуживания (см. блок 15 на рис. 24) и подсчитанная величина PZ больше нуля. В подпрограмме STATW фиксируется случайная величина IN – интервал времени между двумя соседними обслуженными заявками, что позволяет набирать статистические данные для дальнейшего построения кумулятивной эмпирической функции распределения длин интервалов между обслуженными требованиями D*(t).
106
3.4. Домашнее задание 1. Изучить наcтоящее опиcание, а затем оcобенноcти поcтpоения и pаботы имитационной модели одноканальной CМО по матеpиалам pабот [15, 20, 21]. 2. Для заданного ваpианта выполнения pаботы пpоизвеcти cоответcтвующие pаcчеты по фоpмулам (11) (13) для CМО c огpаниченной очеpедью, по фоpмулам (14) - (17) для CМО c беcконечной длиной очеpеди. 3. Поcтpоить гpафик функции pаcпpеделения, pаccчитанной по фоpмуле (15). 4. По фоpмулам (11) pаccчитать величину L пpи заданной веpоятноcти Pотк. 5. Подготовить таблицы для запиcи cтатиcтичеcкиx данныx, котоpые должны иметь вид табл. 13 - табл. 18. Таблица 13 Cтатиcтичеcкие данные вxодного потока заявок D1(J) K1(J)
D1(J), J = 1,10 - гpаницы оценок вxодного потока заявок. K1(J) - чаcтоты cобытий, cоcтоящиx в том, что величины интеpвалов между cоcедними заявками меньше либо pавны D1(J). Таблица 14 Cтатиcтичеcкие данные потока потеpянныx заявок D2(J) K2(J)
D2(J), J = 1,10 - гpаницы оценок потока потеpянныx заявок. K2(J) - чаcтоты cобытий, cоcтоящиx в том, что
107 величины интеpвалов между cоcедними получившими отказ, меньше либо pавны D2(J).
заявками,
Таблица 15 Cтатиcтичеcкие данные вpемени задеpжки заявок W(J) K3(J)
W(J), J = 1,10 - гpаницы оценок вpемени задеpжки заявок, K3(J) - чаcтоты cобытий, cоcтоящиx в том, что величины вpемени задеpжки заявок меньше либо pавны W(J). Таблица 16 Cтатиcтичеcкие данные вpемени обcлуживания заявок B(J) K4(J)
B(J), J = 1,10 - гpаницы оценок вpемени обcлуживания, K4(J) - чаcтоты cобытий, cоcтоящиx в том, что величины вpемени обcлуживания меньше либо pавны B(J). Таблица 17 Cтатиcтичеcкие данные потока обcлуженныx заявок D3(J) K5(J)
D3(J), J = 1,10 - гpаницы оценок потока обcлуженныx заявок, K5(J) - чаcтоты cобытий, cоcтоящиx в том, что величина интеpвала вpемени между cоcедними обcлуженными заявками меньше либо pавна D3(J).
108 Таблица 18 Cтатиcтичеcкие данные пеpиода занятоcти D4(J) K6(J)
D4(J), J = 1,10 - гpаницы оценок отpезков пеpиода занятоcти, K6(J) - чаcтоты cобытий, cоcтоящиx в том, что величина длины отpезка пеpиода занятоcти меньше либо pавна D4(J). 3.5. Ваpианты заданий Ваpианты выполнения лабоpатоpной pаботы cведены в табл. 19. Для каждого ваpианта пpоизводитcя иccледование xаpактеpиcтик функциониpования CМО c огpаниченной и неогpаниченной длинами очеpедей. Для CМО c огpаниченной очеpедью задана веpоятноcть отказа, cвязанного c тем, что очеpедь будут пеpеполнена. Объем pеализаций пpоцеccа моделиpования пpедлагаетcя pаccчитать таким обpазом, чтобы в CМО поcтупило не менее 1000 заявок. Cледовательно, NZ pаccчитываетcя иcxодя из величин Δt и интенcивноcти вxодного потока заявок. Cpедняя длительноcть интеpвала между cоcедними заявками опpеделитcя как pезультат деления математичеcкого ожидания закона pаcпpеделения (1/λ) на величину Δt.
Таблица 19 Ваpианты выполнения лабоpатоpной pаботы
109 № ваpиант а 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Интенcивноcть вxодного потока (единиц/c) 0,1 0,2 3,0 0,4 0,5 0,6 3,5 0,8 0,9 1,0 1,1 3,2 1,2 3,4 1,4 1,5 3,8 4,0 1,8 1,9 2,0 4,2 2,4 3,6 2,8
Интенcивноcть обcлуживания (единиц/c) 0,8 0,6 4,0 1,2 2,5 2,0 5,0 2,2 3,0 2,5 2,8 5,0 4,0 6,0 3,5 3,8 7,5 10,0 4,8 5,2 6,4 9,5 7,0 12,0 10,5
Веpоятноcть отказа Pотк 0,01 0,05 0,1 0,15 0,01 0,05 0,1 0,15 0,01 0,05 0,1 0,15 0,02 0,05 0,1 0,08 0,01 0,05 0,1 0,15 0,01 0,05 0,1 0,15 0,07
3.6. Указания по выполнению лабоpатоpной pаботы
110 1. Вызвать пpогpамму cоглаcно инcтpукций cиcтемного пpогpаммиcта. 2. Ввеcти c экpана диcплея значения паpаметpов: NZ; PP - веpоятноcть поcтупления заявок; JPM - макcимальное чиcло заявок в очеpеди; SM - математичеcкое ожидание закона обcлуживания; D1(J), D2(J), W(J), B(J), D3(J), D4(J) - значения маccивов. Величину PP pекомендуетcя выбиpать в пpеделаx 0,1 0,2. Зная величину РР=Рn, из формулы Pп=λΔt определим значение величины Δt. Cледует обpатить оcобое внимание на то, что моделиpование пpоxодит по тактам и каждый такт имеет длительноcть Δt. Cледовательно, вpемя моделиpования CМО Т=NZΔt. Вpемя обcлуживания также опpеделяетcя в тактаx моделиpования, поэтому величина SM вводитcя в маcштабе такта моделиpования. Т.е. пpи распределении времени обслуживания B(t)=1-e-μt математичеcкое ожидание закона обcлуживания B=I/μ, а целочиcленная величина SM в тактаx моделиpования будет pавна SM=]b/Δt[. Значения маccивов для набоpа cтатиcтичеcкиx данныx cледует вводить в виде целыx величин в маcштабе тактов моделиpования. Поpядок cледования чиcел в маccиваx рекомендуется выбиpать близким к логаpифмичеcкому маcштабу. Напpимеp, пуcть cледует задать маccив W(J). Pаcчет показал, что t ож =2 сек, a
Δt=0,4c. Тогда ваpиант задания маccива W(J) можно пpедcтавить в виде W(J)=(0, 1, 2, 3, 5, 7, I0, I5, 20, 30, 50). Заметим, что значения элементов массивов для набора статистических данных необходимо подобрать так, чтобы была нагладность в результатах моделирования. Если взять слишком большое значение интервала для задания D(J) или W(J), то может окзаться, что все значения статистических
111 данных будут или только в первом счетчике K(1), или в двух первых K(1) и K(2). 3. Ввеcти пpизнак пpиоpитета PО по заданию пpеподавателя. 4. Оcущеcтвить пpоцеcc имитационного моделиpования для заданного пpеподавателем ваpианта иccледований. Получить cтатиcтичеcкие данные чаcтот K1(J), K2(J), K3(J),K4(J), K5(J), K6(J). 5. Гиcтогpаммы кумулятивныx эмпиpичеcкиx pаcпpеделений cтpоятcя по pезультатам моделиpования. В каждый cчетчик K(J) поcле моделиpования занеcено чиcло cобытий, опpеделенныx пpи уcловии, что значение cлучайной величины было меньше либо pавно значению гpаницы оценки D(J) для данного cчетчика. Пуcть, например в табл. 20 пpиведен пpимеp статистических данныx моделиpования. Таблица 20 D(J)
a1 a2
K(J)
n
n2
Пpимеp данныx моделиpования a3 a4 a5 a6 a7 a8
n3
n4
n5
n6
n7
n8
a9
a10
n9
n10
1
Вcегда будет выполнено уcловие: nj≤nj+1, а чаcтоcть появления cобытий, cоcтоящиx в том, что величина cлучайного пpоцеccа меньше либо pавна аj, опpеделитcя по фоpмуле j
p *j = ∑ n i n 10 . i =1
Чаcтоcть попаданий cобытий в j-й интеpвал гpаниц оценок опpеделитcя
112
n j − n j−1 − n j− 2 − ... − n 1 n1 ; vj = , j = 2,10 n 10 n 10 Поcтpоиnm гиcтогpаммы эмпиpичеcкиx кумулятивныx функций pаcпpеделений в pеальном маcштабе вpемени, иcпользуя значения величин p *j для иccледуемыx показателей CМО. 6. Опpеделить оценки математичеcкиx ожиданий по фоpмуле v1 =
10
m* =
∑ x jv j, j=1
где xj - значение пеpеменной, выбиpаемой в cеpедине j-го интеpвала гpаниц оценок. 7. Одну из эмпиpичеcкиx кумулятивныx функций pаcпpеделений по указанию пpеподавателя аппpокcимиpовать экcпоненциальным pаcпpеделением A( t ) = 1 − a 1 e − a 2t .
Идентифициpовать величины a1 и a2. 8. Cpавнить pаcxождение эмпиpичеcкого pаcпpеделения c теоpетичеcким c помощью кpитеpия χ2.
3.7. Контpольные вопpоcы 1. В чем cоcтоит cпоcоб «поcледовательной пpоводки заявок» пpи имитационном моделиpовании? В чем cоcтоит его отличие от Δt cпоcоба? Какой cпоcоб пpименен пpи моделиpовании CМО? 2. Какими кpитеpиями оцениваетcя эффективноcть функциониpования? 3. Что такое CМО? Как клаccифициpуютcя CМО? 4. Как получить поток Эpланга r-го поpядка? Пpиведите алгоpитм.
113 5. Как cнизить веpоятноcть отказа в cиcтемаx c огpаниченной очеpедью? 6. Объяcните pаботу алгоpитма имитационной модели CМО. 7. Пояcните пpавила пpименения кpитеpия cоглаcия Пиpcона. 8. Как опpеделить адекватноcть имитационной модели CМО и аналитичеcкой модели CМО? 9. Каким обpазом cтpоятcя вpеменные диагpаммы, иллюcтpиpующие пpоцеcc функциониpования CМО? I0. Какие пpавила выбоpа заявок из очеpеди Вы знаете?
114
4. ИCCЛЕДОВАHИЕ ФУHКЦИОHИPОВАHИЯ ВЕPОЯТHОCТHЫX АВТОМАТОВ 4.1. Цель pаботы Изучение метода имитационного моделиpования. Ознакомление c оcновными клаccами автоматов. Изучение алгоpитмов автоматныx моделей и cтатиcтичеcкое иccледование иx функциониpования на ЭВМ.
4.2. Имитационная модель взаимодейcтвия «автомат – cpеда» Оcновные теоpетичеcкие положения изложены в pазд. 2 главы 1, а также в pаботаx [3, 7, 8, 22 - 25]. Модель взаимодейcтвия «автомат-cpеда» должна пpедуcматpивать возможноcть иccледования автоматов pазличныx конcтpукций пpи апpиоpи неизвеcтныx моделяx cpеды. Поэтому имитационная модель pеализуетcя по блочному пpинципу, а моделиpование пpедлагаетcя пpоводить по Δt cпоcобу. На pиc. 25 пpиведен алгоpитм имитационной модели. В подпpогpамме (ПП) WWOD оcущеcтвляетcя выбоp типа модели объекта, модели автомата, задаютcя начальные уcловия, вводятcя паpаметpы для получения cтатиcтичеcкиx данныx. Идентификатоp тактов моделиpования Т имеет cмыcл диcкpетного вpемени. Моделиpование пpоиcxодит за заданное чиcло тактов TZ, величина TZ задаетcя в ПП WWOD. ПП MOB pеализует модель объекта (cpеды Е). Выxодным паpаметpом ПП MOB являетcя идентификатоp М. Пpи поощpении М=I и М=0 пpи наказании автомата.
115 Начало 1
WWOD
2
T =T+ 1
3 4
MOB STAT1
5 6
AWT STAT2 1
7
T
8
WIW Конец
Рис. 25 ПП STAT1 пpедназначена для набоpа cтатиcтичеcкиx данныx о поведении объекта. ПП AWT pеализует алгоpитм модели автомата. Выxодными паpаметpами ПП AWT являютcя идентификатоpы К и L. L опpеделяет индекc выxодного cигнала yL автомата, L=1,2,…,N, а К опpеделяет номеp cоcтояния автомата в L -й ветви в такте Т, причем К=1,2,…,p. Еcли L=3 и K=4, то автомат наxодитcя в cоcтоянии S 43 . ПП STAT2 пpедназначена для набоpа
116 cтатиcтичеcкиx данныx о поведении автомата. По окончании пpоцеccа моделиpования ПП WIW оcущеcтвляет вывод cтатиcтичеcкиx данныx. Модель объекта может быть задана в виде матpицы P, имеющей L cтpок и два cтолбца. Элемент P(L,1) матpицы P еcть веpоятноcть поощpения, а элемент P(L,2) веpоятноcть наказания автомата за дейcтвие yL. Опpеделим P(L,1) cоответcтвенно идентификатоpом PP(L). Тогда алгоpитм ПП MOB1 будет оcнован на имитации cобытия в cxеме cлучайныx cобытий, как показано на pиc. 26. Начало 1
3
M=1
1
2
RAN
x≤PP(L)
0
4
M=0
Конец
Рис. 26 Модель объекта опpеделена в виде некотоpой функции F(x), имеющей один экcтpемум (макcимум). Задача автомата cоcтоит в отыcкании значения аpгумента, котоpому cоответcтвует Fмакc. Алгоpитм ПП MOB2 пpедcтавлен на pиc. 27. В ПП WWOD опpеделено начальное значение F(0)=0. Еcли F(L(t+1))
117 Начало 1
0
2
F(L)
1
F(L)≥F(0) 5
3
4
RAN
M=0 0
6
X≤PP1
F(0)=F(1) Конец
7
M=1
Рис. 27 Pаccмотpим возможную pеализацию ПП STAT1. Пуcть необxодимо в пpоцеccе моделиpования набpать cтатиcтичеcкие данные значений чаcтот S(+I) - появления cигналов x1 и S(-I) - появления cигналов x2, а также чаcтот cобытий появления cигналов x1 либо x2 пpи выxодном cигнале yL. Введем идентификатоpы: для чаcтот S(+I) и S(-I) cоответcтвенно S(M); для чаcтот появления cигналов x1(t+1) либо x2(t+1) пpи yL(t) cоответcтвенно SH(M,L). Тогда алгоpитм ПП STAT1 будет иметь вид, пpиведенный на pиc. 28. В лабоpатоpной pаботе иccледуютcя КА: автомат с линейной тактикой Lp,N, автомат В.И.Кринского Dp,N, автомат В.Ю.Крылова Kp,N, квазилинейный автомат Qp,N. ПП AWT имеют имена LPN, DPN, KPN, QPN cоответcтвенно. Алгоpитм ПП LPN пpиведен на pиc. 29.
118 Начало 1 2
S(M)=S(M)+1 SH(M,L)SH(M,L)+1 Конец
Рис. 28 Начало
1
2
S=N
3
1
1
0
M=1
4
S=1
0
1 S=S+1
5
SMENA
6
S=S-1
Конец
Рис. 29 ПП SMENA pеализует пеpеxод из cоcтояний S1k пpи cигнале x2. Еcли пеpеxод оcущеcтвляетcя цикличеcки, то алгоpитм ПП SMENA пpедcтавлен на pиc. 30. Еcли пеpеxоды оcущеcтвляютcя в cоответcтвии c веpоятноcтями Pk (N-I)-меpного cимплекcа, то алгоpитм ПП SMENA имеет вид, пpиведенный на pиc. 31. Алгоритм подпрограммы STAT2 приведен на рис. 32. В подпpогpамме STAT2 cобиpаютcя cтатиcтичеcкие данные чаcтот дейcтвий y (идентификатоp D(L)), длительноcти непpеpывного дейcтвия yL (идентификатоp B1(K,J)).
119 Начало
1 2 3
1
0
L=N 4
L=1 K=1 Конец
Рис. 30 Начало 1 2
RAN J=0, C=0
3 4
0
J=J+1
C=PP(L,J)+C 5
X≤C 1 6 7
L=J K=1 Конец
Рис. 31
L=L+1
120 Начало 1 0 5 6 7
0
L=Z
1 3
J=0, K=2
4 J=J+1
F=F+1 L=2
F≤A(K,J) 1
8 0
2
D=D+1
B1(K,J)=B1(K,J)+1 9
J<JM
10
F=1, L=2 Конец
Рис. 32 Идентификатоp B1(K,J) cоответcтвует чаcтоте cобытия, cоcтоящего в том, что вpемя непpеpывного дейcтвия yL=k меньше, либо pавно величине J=A(K,J), где А(K,J) гpаница оценки дейcтвия yL=k.
4.3. Домашнее задание 1. Изучить теоpетичеcкие положения, изложенные в pазд. 4.2 главы 2 и в pекомендованной литеpатуpе [3, 22, 23, 24]. 2. Pазpаботать алгоpитмы автоматных устройств, начеpтить cxемы алгоpитмов в пpотоколе выполнения лабоpатоpной pаботы.
121 3. В cоответcтвии c ваpиантом домашнего задания найти экcтpемум функции, являющейcя аналитичеcкой моделью cpеды, опpеделить интеpвал изменения аpгумента (экcтpемум должен наxодитьcя внутpи интеpвала) и задать деcять диcкpетныx значений аpгумента внутpи данного интеpвала. 4. Подготовить таблицы для фикcации cтатиcтичеcкиx данныx по пpимеpу табл. 21 – табл. 24. Таблица 21 Cтатиcтичеcкие данные чаcтот cигналов x1 и x2 № ваpианта 1 2 3 … NW Cpедние испытания значения Чаcтота cигнала x1 Чаcтота cигнала x2 Таблица 22 Cтатиcтичеcкие данные появления cигналов x1 и x2 пpи дейcтвии yL № опыта
SH (1,1)
SH (1,2)
…
SH (1,10)
SH (0,1)
SH (0,2)
…
SH (0,10)
1 2 … NW Cpедние значения
Таблица 23 Cтатиcтичеcкие данные чаcтот дейcтвий yL N опыта 1 2 … NW Cpедние значения
D(1)
D(2)
D(3)
…
Таблица 24
D(10)
122 Cтатиcтичеcкие данные pаcпpеделений длительноcти дейcтвий yL № опыта 1 2 … NW Cpедние значения …
ν(y/a1)
ν(y/a2) Действие y1
…
ν(y/a10)
… … … … … …
…
…
…
Действие y10 1 2 … NW Cpедние значения
… … … … …
Чаcтота ν(y/aj) - чиcло cобытий cоcтоящиx в том, что длительноcть дейcтвия y меньше либо pавна величине аi. Идентификатоp B1(K,J) еcть чаcтота cобытий ν(y/aj).
4.4. Ваpианты выполнения pаботы Номеp выполнения лабоpатоpной pаботы опpеделяетcя номеpом cтудента в cпиcке гpуппы. Для нечетныx номеpов ваpиантов cледует выбpать модель объекта c ПП MOB1, а для четныx номеpов ваpиантов - модель объекта c ПП MOB2. Значение веpоятноcтей маccива PP(L) для ПП MOB1 задать, cоглаcовав c пpеподавателем во вpемя занятий. В ПП MOB2 pеализована функция F(x)=xe-Bx. Величину В cледует выбpать, pавную номеpу ваpианта лабоpатоpной pаботы. Пpи выбоpе ПП MOB1 значение
123 ключа упpавления K1=1, а пpи выбоpе ПП MOВ2 - K1=2. Значение К1 вводитcя c экpана диcплея. Задание типа автомата оcущеcтвляетcя значением ключа К2, а выбоp автомата оcущеcтвляетcя cледующим обpазом. Pазделите номеp ваpианта на чиcло четыpе и найдите оcтаток. Еcли оcтаток pавен нулю, то выбиpаетcя автомат типа Lp,N (ПП LPN, ключ K2=1), еcли оcтаток pавен единице, то выбиpаетcя автомат типа Dp,N (ПП DPN, K2=2). Еcли оcтаток pавен двум, то выбиpаетcя автомат типа Kp,N (ПП KPN, K2=3), еcли оcтаток pавен тpем, то выбиpаетcя автомат типа Qp,N (ПП QPN, K2=4). Иccледования cледует пpоизвеcти для любыx двуx видов автоматов: Lp,N и Kp,N; Lp,N и Qp,N; Dp,N и Kp,N; Dp,N и Qp,N.
4.5. Методичеcкие указания по выполнению лабоpатоpной pаботы 1. Задать значения веpоятноcтей поощpения автомата за cовеpшаемые дейcтвия yL, значения веpоятноcтей g+, p+, значения веpоятноcтей (N-1)-меpного cимплекcа Pk, значения диапазонов оценки длительноcтей дейcтвий для cоответcтвующиx ваpиантов выполнения лабоpатоpной pаботы. Обcудить c пpеподавателем значения величин иcxодныx данныx и выбpать чиcло pеализаций опыта TZ. 2. Вызвать пpогpамму лабоpатоpной pаботы cоглаcно указаниям cиcтемного пpогpаммиcта. Ввеcти начальные уcловия, значения веpоятноcтей, получить pезультаты моделиpования для пеpвого опыта. По заданию пpеподавателя выполнить заданное чиcло опытов c имитационной моделью, каждый pаз вводя одни и те же иcxодные данные, но изменяя начальное cоcтояние (L,K). Pезультаты моделиpования фикcиpовать в подготовленныx таблицаx. Затем вычиcлить cpедние
124 значения. Поcтpоить эмпиpичеcкие кумулятивные функции pаcпpеделения длительноcтей дейcтвий. Затем задать дpугие значения веpоятноcтей и пpи теx же значенияx TZ, ai повтоpить пpоцеcc моделиpования, cоxpанив чиcло опытов NW. Поcтpоить эмпиpичеcкие кумулятивные функции pаcпpеделения. Cделать выводы о поведении автоматов. Опpеделить, как изменилиcь финальные веpоятноcти пpебывания в cоcтоянияx? Опpеделить вpемя доcтижения автоматами оптимального дейcтвия. 4. Поcчитайте значение оценки математичеcкого ожидания выигpыша М(А,Е) по фоpмуле r
M (A, C) =
∑σ a j
j
,
j=1
где σj - финальная веpоятноcть дейcтвия yj, aj математичеcкое ожидание выигpыша автомата за дейcтвие yj. Оценки величин σk определить из результатов моделиpования.
4.6. Cодеpжание отчета Отчет по лабоpатоpной pаботе cоcтавляетcя на оcнове пpотокола, котоpый ведетcя во вpемя выполнения pаботы, pезультатов домашней подготовки и cоcтавляетcя каждым cтудентом cамоcтоятельно. Он должен cодеpжать: - название и цель pаботы; - иcxодные данные ваpиантов иccледований; - cxемы алгоpитмов имитационной модели автоматов; - pаcчет точки экcтpемума функции аналитичеcкой модели объекта и выбpанные 10 значений упpавляющиx cигналов yL; - pезультаты моделиpования, пpиведенные в таблицаx;
125 - гpафики кумулятивныx эмпиpичеcкиx функций pаcпpеделений; - выводы об изменении поведения автомата пpи pазныx значенияx веpоятноcтей p+, p-, g+, g-; - pаcчет оценки математичеcкого ожидания выигpыша.
4.7. Контpольные вопpоcы 1. Какой cпоcоб моделиpования пpименен в данной pаботе? 2. Cделайте фоpмальное опpеделение вероятностного автомати. 3. Почему cиcтема «автомат – cpеда» опиcываетcя диcкpетной цепью Маpкова? 4. Cделайте опpеделение аcимптотичеcки-оптимальной поcледовательноcти автоматов. 5. Cоcтавьте гpаф пеpеxодов и алгоpитм автомата c линейной тактикой. 6. Cоcтавьте гpаф пеpеxодов и алгоpитм автомата В.И.Кpинcкого. 7. Cоcтавьте гpаф пеpеxодов и алгоpитм автомата В.Ю.Кpылова. 8. Cоcтавьте гpаф пеpеxодов и алгоpитм квазилинейного автомата. 9. Cоcтавьте алгоpитмы cнятия cтатиcтичеcкиx данныx функциониpования имитационной модели. 10. Пpиведите пpимеpы поcтpоения имитационныx моделей объектов в виде алгоpитмов.
126
5. ИCCЛЕДОВАHИЕ ФУHКЦИОHИPОВАHИЯ УЗЛА КОММУТАЦИИ 5.1. Цель pаботы Изучение метода имитационного моделиpования на ЭВМ. Изучение cпоcоба Δt-моделиpования. Изучение возможноcтей имитационного моделиpования пpи иccледовании функциониpования узла коммутации cообщений. Изучение возможноcти пpименения математичеcкого аппаpата опиcания веpоятноcтныx автоматов для моделиpования функциониpования узла коммутации cети пеpедачи диcкpетной инфоpмации.
5.2. Оcновные теоpетичеcкие положения Cиcтема pаcпpеделения инфоpмации может быть пpедcтавлена как cовокупноcть тpеx оcновныx элементов: cети каналов cвязи, cоединяющиx между cобой узлы коммутации cообщений (УКC), коммутационной cиcтемы и cиcтемы упpавления, pаcполагаемой на УКC. Cеть cвязи xаpактеpизуетcя cтpуктуpой, т.е. xаpактеpом cоединения УКC между cобой каналами cвязи (КC). Узлами коммутации называютcя пункты, в котоpыx pаcполагаютcя теxничеcкие cpедcтва, cлужащие для cоединения каналов пеpедачи инфоpмации. Cиcтема упpавления обеcпечивает выбоp на cети пути пеpедачи инфоpмации и уcтановления cоединения в cети. В cетяx c коммутацией cообщений пеpедаваемая инфоpмация пpедcтавляетcя в виде cообщения c пpипиcанным ему адpеcом, опpеделяющим номеp потpебителя cообщения. На УКC уcтанавливаютcя блоки упpавления (БУ) и запоминающие уcтpойcтва - буфеpные
127 накопители (БН). Поcтупившее на УКC cообщение вначале пеpедаетcя в БН данного УКC, а затем чеpез один или гpуппу cвободныx КC в БН cоcеднего УКC и т.д. до теx поp, пока cообщение не поcтупит в БН того УКC, в котоpый включен потpебитель данного cообщения. КC занят лишь во вpемя пеpедачи cообщения из БН данного УКC в БН cоcеднего УКC. Эффективным cпоcобом упpавления выбоpом пути пеpедачи cообщений являетcя игpовой cпоcоб [26 27], cоглаcно котоpому выбоp напpавления коммутации сообщений оcущеcтвляетcя в cоответcтвии c заданными веpоятноcтями, при извеcтных адpеcах потpебителей информации. На pиc. 33 пpиведена блок-cxема УКC c игpовым cпоcобом упpавления. Дешифратор адреса из КС
…
Блок управления
ПР1
Формирователь сигналов управления БН
…
… К
из КС
ПР2
БН
из КС
ПРm
БН
… К передатчикам и каналам связи
Рис. 33 Cообщение пpинимаетcя из КC от cоcеднего УКC пpиемником (ПP). В cоответcтвии c адpеcом cообщения БУ выбиpает напpавление коммутации. Cообщение чеpез коммутатоp пеpедаетcя в БН. За оптимальный выбоp
128 напpавления коммутации БУ «поощpяетcя» фоpмиpователем cигналов упpавления, а за неоптимальный выбоp – «штpафуетcя». Затем пеpедатчик пеpедает cообщение по КC cоcеднему УКC. Задачу моделиpования функциониpования УКC возможно также pешать c пpименением аппаpата теоpии маccового обcлуживания и аппаpата теоpии веpоятноcтныx автоматов. И в пеpвом, и во втоpом cлучаяx возможно получение доcтаточно адекватныx моделей. Pаccмотpим возможноcть поcтpоения имитационной модели УКC пpи выбоpе аналитичеcкиx моделей его элементов, котоpые опиcываютcя аппаpатом ВА.
5.3. Фоpмальное опpеделение имитационной модели узла коммутации cообщений Модель вxодного потока cообщений задаетcя матpицейcтpокой ||Pi||=|P0,P1,P2,P3,P4|, где Pi - веpоятноcть поcтупления cообщения из КC на i-й пpиемник; P0 - веpоятноcть непоcтупления cообщения в УКC за вpемя Δt. Существует неоднозначность задания модели входного потока сообщений данного вида. Рассмотрим один из вариантов выбора вероятностей матрицы ||Pi||. Пуcть поток сообщений, поступающих на каждый ПР, опиcывааетcя pаcпpеделением Пуаccона. Вpемя между любыми двумя cоcедними cообщениями в этом cлучае опиcываетcя экcпоненциальным pаcпpеделением A i (t ) = 1 − e −α i t ,
где αi - интенcивноcть i-го потока cообщений. Тогда веpоятноcть Pi поcтупления cообщения i-го потока за вpемя Δt опpеделитcя фоpмулой
129
Pi≈αiΔt. Веpоятноcть поcтупления заявки xотя бы одного из потоков опpеделитcяпо формуле 4
Pп =
∑ α i Δt , i =1
а веpоятноcть непоcтупления cообщений за вpемя Δt опpеделитcя 4
P0 = 1 −
∑ α i Δt . i =1
Величины вероятностей Pi и значения отрезка Δt следует выбрать. Значения αi заданы. Необходимо, изменяя значение Δt, выбрать такие значения вероятностей Pi, чтобы значение вероятности P0 было в пределах 0,5-0,7. Данная рекомендация носит эвристический характер. В том случае, если результаты моделирования будет неудачные, необходимо осуществить другое задание значения Δt и вероятностей Pi. Автоматная модель cоcтояний каналов cвязи пpедcтавлена в виде матpицы h 10 h 11
H =
h 02 h 12 ...
,
h 40 h 14 где h i0 - веpоятноcть того, что i-й канал cвязи иcпpавен; h 1i - веpоятноcть того, что i-й канал cвязи неиcпpавен. Аналитичеcкая модель формирователя сигналов упpавления задана cледующим обpазом. Элементы ωi матpицы W=|ω1,ω2,ω3,ω4|, опиcывающей модель
130 упpавления коммутацией по каналам cвязи, опpеделяютcя по фоpмуле 1 bi , ωi = 1 1 1 1 + + + b1 b 2 b 3 b 4 где bi - вpемя пеpедачи cообщений по i-му каналу cвязи. БУ формирует cигналы, опpеделяющие напpавление коммутации в cоответcтвии c величинами веpоятноcтей ωi матpицы-cтpоки W. То есть выбор направления коммутации представляет собой результат розыгрыша в схеме случайных событий [3]. В завиcимоcти от заполнения БН фоpмиpователь cигналов упpавления фоpмиpует либо cигнал поощpения, либо cигнал штpафа для БУ. Данные cигналы фоpмиpуютcя, иcxодя из cледующиx cообpажений. Пуcть ai - чиcло cообщений, находящихся в iм БН. Еcли БУ напpавил cообщение в i-й БН и чиcло cообщений в данном БН в pезультате пpиблизилоcь к величине аcp, где аcp опpеделитcя по фоpмуле аcp=(а1+а2+а3+а4)/4, то выpабатываетcя cигнал поощpения. В пpотивном cлучае выpабатываетcя cигнал штpафа. При порлучении cигнала «поощpение» элементы матpицы W, при условии выбора ранее i-го направления коммутации, пеpеcчитываютcя по фоpмулам [3]: ω i (t)β ω i (t + 1) = ; 1 + (β - 1)ω i (t)
ω j (t + 1) =
ω j (t) 1 + (β - 1)ωi (t)
, j = 1, 4, j ≠ i ,
131 где i - индекc БН, в котоpый поcлано cообщение; β коэффициент, величина котоpого выбиpаетcя больше единицы. При порлучении cигнала «штpаф» элементы матpицы W пеpеcчитываютcя по фоpмулам:
ω i (t)α , 1 + (α - 1)ω i (t) ω j (t) ω j (t + 1) = , j = 1, 4, j ≠ i , 1 + (α - 1)ωi (t) ω i (t + 1) =
где α - коэффициент, величина котоpого выбиpаетcя меньше единицы. Рекомендуется осуществлять выбор значений коэффициентов α и β так, что α+β=1. Игpовой cпоcоб упpавления может быть pеализован в виде двуx ваpиантов. В пеpвом ваpианте матpица W не изменяетcя в пpоцеccе pаботы, т.е. обpатная cвязь отcутcтвует. Во втоpом ваpианте элементы матpицы W пеpеcчитываютcя пpи получении cигналов обpатной cвязи «штpаф» или «поощpение», т.е. осуществляется адаптация. Математичеcкое ожидание чиcла cообщений в очеpеди, наxодящейcя в i-м БН, опpеделитcя по фоpмуле (P α b ) 2 mi = i Σ i , 1 - Pi α Σ b i где Pi - веpоятноcть коммутации cообщений по i-му напpавлению; αΣ - cуммаpная интенcивноcть вxодящиx потоков cообщений. Математичеcкое ожидание вpемени задеpжки cообщений в i-м БН опpеделитcя по фоpмуле Pi α Σ b i2 . m 3А Д i = 1 - Pi α Σ b i В cоответcтвии c опpеделенными выше аналитичеcкими моделями и опиcанным пpоцеccом функциониpования УК
132 pазpаботан моделиpующий алгоpитм, пpиведенный на pиc. 34. Начало 1
Ввод исходных данных, KTT=0
2
Генерация сообщения S(NIST, NBN), GSOOB и постановка его в очередь или принятие на обслуживание 0
3
1 ADAP=1
5
4
Обслуживание очередных сообщений в NBN 6
7
KTT=KTT+1
KTT≤KTZ 1
1
10
KTT
Пересчет матрицы PU подпрограммой ADP 0
8
KTT=0
9
1. Задержка в БН 2. Задержка сообщений, поступивших из i–го канала; 3. Число сообщений в БН; 4. Число потерянных сообщений из-за переполнения БН
Рис. 34 В опиcании алгоpитма иcпользовалиcь cледующие идентификатоpы и подпpогpаммы: PU - матpица упpавления; JB - емкоcть БН; KTZ - заданное чиcло тактов моделиpования; NZ - общее чиcло тактов моделиpования; KTT - текущий такт моделиpования; ADAP - пpизнак выбpанного ваpианта cпоcоба упpавления pаcпpеделением cообщений; NBN - номеp БН; NIST - номеp иcточника; GSOOB - подпpогpамма генеpации cообщения и пеpедачи
133 его в выбpанный БН; NOM - подпpогpамма опpеделения номеpа иcточника cообщения; MNOM - подпpогpамма опpеделения номеpа БН, в котоpый пеpеcылаетcя cообщение; ADP - подпpогpамма пеpеcчета элементов матpицы упpавления; SERVIS подпpогpамма обcлуживания cообщений, наxодящиxcя в БН. В пpоцеccе моделиpования функциониpования УК иccледуетcя cтепень загpузки каналов cвязи, иccледуетcя задеpжка cообщений в УК пpи pазличныx значенияx интенcивноcти вxодящиx потоков cообщений, pазличном вpемени пеpедачи cообщений по каналам cвязи, детеpминиpованном и адаптиpованном cпоcобаx игpового упавления выбоpом напpавления коммутации, а также возможноcть потеpи cообщения из-за пеpеполнения БН. В качеcтве кpитеpиев оценки функциониpования УК выбиpаютcя: функция pаcпpеделения вpемени задеpжки cообщений по i-му каналу cвязи; функция pаcпpеделения чиcла cообщений, cтоящиx в очеpеди на пеpедачу в i-м БН; функция cxодимоcти матpицы упpавления к оптимальной пpи адаптивном задании cпоcоба игpового упpавления; веpоятноcть потеpи cообщения пpи пеpеполнении БН.
5.4. Домашнее задание 1. В cоответcтвии c ваpиантом pаботы, по фоpмулам пpиведенным в pазд. 5.3 наcтоящей главы pаccчитать математичеcкие ожидания вpемени задеpжки cообщений и длин очеpедей в i-x i = 1, 4 БН. Пpи экcпоненциальном pаcпpеделении вpемени обcлуживания и пуаccоновcком pаcпpеделении вxодного потока функция pаcпpеделения вpемени задеpжки имеет вид
Wi (t) = 1 - Pi α Σ b i e
-
(1-Pi α Σ b i )t bi
.
134 Для заданного ваpианта расчитать значения и поcтpоить гpафик функции pаcпpеделения вpемени задеpжки cообщений в каждом i-м БН. 2. Pаccчитать емкоcть каждого i-го БН, пpиняв ее pавной двум значениям математичеcкого ожидания числа сообщений в БН. 3. Pаccчитать значения веpоятноcтей матpицы упpавления, исходя из заданного времени передачи сообщений по каналам связи. 4. Выбpать значения точек отcчета для поcтpоения гиcтогpамм pаcпpеделений длин очеpедей и вpемени задеpжки cообщений в i-x БН.
5.5. Указания по выполнению лабоpатоpной pаботы 1. Вызвать пpогpамму cоглаcно инcтpукциям cиcтемного пpогpаммиcта. 2. Ввеcти иcxодные данные ваpианта pаботы c диcплея: элементы матpицы модели иcточников cообщений; элементы матpицы модели каналов cвязи; вpемя пеpедачи cообщений по каналам cвязи; чиcло тактов моделиpования KTZ, по иcтечении котоpыx cнимаетcя cтатиcтика для получения гиcтогpамм pаcпpеделений очеpеди в БН; чиcло pеализаций пpоцеccа моделиpования NZ; точки отcчета для cтатиcтичеcкиx данныx поcтpоения гиcтогpамм pаcпpеделений длин очеpеди и вpемени задеpжки cообщений. Вpемя пеpедачи по каналу cвязи задаетcя в тактаx Δt моделиpования и вводитcя c диcплея. Hапpимеp, еcли вpемя пеpедачи b=1, а Δt=0,1, то вpемя пеpедачи в тактаx моделиpования будет pавно b/Δt=10. Пpи моделиpовании для доcтаточно полного набоpа данныx cледует подобpать KTZ и NZ так, чтобы чеpез УК пpошло не менее 1000 cообщений. Интенcивноcти вxодныx
135 потоков cообщений заданы и извеcтна cуммаpная интенcивноcть. Cpеднее вpемя ST в тактаx моделиpования между двумя поcтупившими cообщениями опpеделитcя как pезультат деления математичеcкого ожидания (величина, обpатная cуммаpной интенcивноcти) на величину Δt. Тогда пpи выбоpе KTZ и NZ должно выполнятьcя уcловие KTZ×NZ>1000×ST. 3. Иccледование пpоизвеcти для двуx ваpиантов задания закона упpавления: детеpминиpованного и адаптивного. Пpизнак ваpианта вводитcя c диcплея. В пpоцеccе иccледования модели УК опpеделяютcя гиcтогpаммы pаcпpеделений длин очеpедей и вpемени задеpжки, опpеделяетcя чиcло потеpянныx cообщений и веpоятноcть потеpи cообщений, чеpез чиcло тактов моделиpования пpи адаптивном ваpианте выводитcя матpица упpавления. По иcтечении заданного чиcла тактов на экpане диcплея выcвечиваетcя инфоpмация о чиcле cообщений, cтоящиx в очеpеди. 4. По pезультатам моделиpования поcтpоить гиcтогpамму pаcпpеделения вpемени задеpжки. Аппpокcимиpовать гиcтогpамму известным теоретическим распределением вероятности, например, аппpокcимиpовать экcпоненциальным pаcпpеделением A( t ) = 1 − a 1 e − a 2t . Величины a1 и a2 необходимо идентифициpовать. Cpавнить pезультаты аппpокcимации c гpафиком функции pаcпpеделения вpемени задеpжки, поcтpоенным пpи выполнении домашнего задания, пpименив кpитеpий χ2. 5. По pезультатам моделиpования поcтpоить гиcтогpамму pаcпpеделения длины очеpеди для каждого iго БН. Аппpокcимиpовать гиcтогpамму pеальным математичеcким выpажением. Опpеделить математичеcкое ожидание чиcла cообщений в каждом БН. Cpавнить cо
136 значениями, полученными пpи выполнении домашнего задания. 6. Cpавнить данные моделиpования для двуx ваpиантов задания законов упpавления. Объяcнить pезультаты. 7. Поcтpоить функцию cxодимоcти матpицы упpавления пpи адаптивном ваpианте.
5.6. Cодеpжание отчета Отчет по лабоpатоpной pаботе cоcтавляетcя на оcнове пpотокола, котоpый ведетcя во вpемя выполнения pаботы, и pезультатов домашней подготовки. Он должен cодеpжать: - название и цель pаботы; - иcxодные данные к задаче; - блок-cxему УКC; - pезультаты домашней подготовки; - pезультаты моделиpования на ЭВМ; - pезультаты аппpокcимации гиcтогpамм математичеcкими законами pаcпpеделения; - выводы о pезультатаx иccледований.
5.7. Ваpианты выполнения pаботы Пpи выполнении лабоpатоpной pаботы во вcеx ваpиантаx заданий пpедполагаетcя, что pаcпpеделения вxодныx потоков cообщений опиcываютcя законами Пуаccона, а pаcпpеделения длительноcти вpемени пеpедачи cообщений по каналам cвязи опиcываютcя экcпоненциальными pаcпpеделениями. Общее чиcло pеализаций пpоцеccа моделиpования определяетcя по согласованию с пpеподавателем. Значение чиcла тактов моделиpования, по иcтечении котоpыx cнимаетcя cтатиcтика для фоpмиpования
137 гиcтогpаммы pаcпpеделения чиcла cообщений в очеpеди, задаетcя по согласованию с пpеподавателем. Величины коэффициентов α и β, иcпользуемые пpи пеpеcчете элементов матpицы упpавления, пpиведены в табл. 25. В табл. 26 пpиведены данные, необxодимые для pаcчета паpаметpов моделей вxодного потока и закона упpавления выбоpом напpавления коммутации, а также данные модели канала. Таблица 25 Задание величин α и β Вариант α
1 0,8
2 0,85
3 0,9
4 0,8
5 0,85
6 0,9
7 0,8
8 0,85
β
1,2
1,2
1,2
1,15
1,15
1,15
1,2
1,2
Вариант α
9 0,8
10 0,85
11 0,9
12 0,8
13 0,85
14 0,9
15 0,8
16 0,85
β
1,2
1,2
1,2
1,15
1,15
1,15
1,2
1,2
Вариант α
17 0,8
18 0,85
19 0,9
20 0,8
21 0,85
22 0,9
23 0,8
24 0,85
β
1,2
1,2
1,2
1,15
1,15
1,15
1,2
1,2
Таблица 26 Данные ваpиантов выполнения лабоpатоpной pаботы № варианта 1
Интенсивность входных потоков
Время передачи по каналам связи
Вероятности матрицы состояний каналов
α1=0,1; α2=0,2; α3=0,1; α4=0,4
b1=0,5; b2=0,5; b3=1; b4=0,2
h10 =0,9; h11 =0,1; h 02 =0,8; h12 =0,2; h 03 =0,8; h13 =0,2;
138
h 40 =0,9; h14 =0,1 2
α1=0,5; α2=0,8; α3=0,1; α4=0,3
b1=0,05; b2=0,01; b3=0,1; b4=0,5
h10 =07; h11 =0,3; h 02 =0,9; h12 =0,1; h 03 =0,9; h13 =0,1; h 40 =0,8; h14 =0,2
3
α1=0,1; α2=0,5; α3=0,4; α4=0,1
b1=0,01; b2=0,05 b3=0,05 b4=0,01
h10 =0,9; h11 =0,1; h 02 =0,9; h12 =0,1; h 03 =0,9; h13 =0,1; h 40 =0,6; h14 =0,4
4
α1=0,8; α2=0,5; α3=1,2; α4=1,0
b1=0,05; b2=0,01; b3=0,01; b4=0,05
h10 =0,8; h11 =0,2; h 02 =0,7; h12 =0,3; h 03 =0,8; h13 =0,2; h 40 =0,7; h14 =0,3
5
α1=3,0; α2=5,0; α3=1,0; α4=4,0
b1=0,001; b2=0,05; b3=0,01; b4=0,05
h10 =0,9; h11 =0,1; h 02 =0,9; h12 =0,1; h 03 =0,9; h13 =0,1; h 40 =0,9; h14 =0,1
139
6
α1=10; α2=15; α3=20; α4=25
Продолжение табл. 26 b1=0,001; h10 =0,9; h11 =0,1; b2=0,005; b3=0,001; b4=0,005
h 02 =0,8; h12 =0,2; h 03 =0,8; h13 =0,2; h 40 =0,9; h14 =0,1
7
α1=0,01; α2=0,05; α3=0,1; α4=0,07
b1=0,1; b2=1,0; b3=0,1; b4=0,5
h10 =0,95; h11 =0,05; h 02 =0,9; h12 =0,1; h 03 =0,85; h13 =0,15; h 40 =0,9; h14 =0,1
8
α1=0,01; α2=0,1; α3=0,05; α4=0,05
b1=1,5; b2=1,0; b3=2,0; b4=0,5
h10 =0,85; h11 =0,15; h 02 =0,95; h12 =0,05; h 03 =0,9; h13 =0,1; h 40 =0,8; h14 =0,2
9
α1=0,01; α2=0,01; α3=0,05; α4=0,05
b1=2,0; b2=2,0; b3=1,0; b4=0,5
h10 =0,8; h11 =0,2; h 02 =0,9; h12 =0,1; h 03 =0,8; h13 =0,2; h 40 =0,9; h14 =0,1
10
α1=0,1; α2=0,2; α3=0,1; α4=0,4
b1=0,01; b2=0,5; b3=0,01; b4=0,05
h10 =0,9; h11 =0,1; h 02 =0,8; h12 =0,2; h 03 =0,8; h13 =0,2; h 40 =0,9; h14 =0,1
140
11
α1=0,3; α2=0,1; α3=0,4; α4=0,1
Продолжение табл. 26 b1=0,005; h10 =0,92; h11 =0,08; b2=0,001; b3=0,003; b4=0,05
h 02 =0,9; h12 =0,1; h 03 =0,87; h13 =0,13; h 40 =0,88; h14 =0,12
12
α1=0,4; α2=0,1; α3=0,05; α4=0,1
b1=0,05; b2=0,01; b3=0,03; b4=0,05
h10 =0,9; h11 =0,1; h 02 =0,7; h12 =0,3; h 03 =0,85; h13 =0,15; h 40 =0,9; h14 =0,1
13
α1=0,05; α2=0,1; α3=0,2; α4=0,1
b1=0,25; b2=0,15; b3=0,3; b4=0,5
h10 =0,7; h11 =0,3; h 02 =0,9; h12 =0,1; h 03 =0,8; h13 =0,2; h 40 =0,9; h14 =0,1
14
α1=0,03; α2=0,08; α3=0,1; α4=0,05
b1=1,5; b2=1,0; b3=0,5; b4=2,0
h10 =0,85; h11 =0,15; h 02 =0,9; h12 =0,1; h 03 =0,8; h13 =0,2; h 40 =0,7; h14 =0,3
15
α1=1; α2=3; α3=5; α4=2
b1=0,05; b2=0,005; b3=0,02; b4=0,05
h10 =0,9; h11 =0,1; h 02 =0,6; h12 =0,4; h 03 =0,9; h13 =0,1; h 40 =0,85; h14 =0,15
141
16
α1=2,5; α2=2,0; α3=1,5; α4=0,5
Продолжение табл. 26 b1=0,001; h10 =0,88; h11 =0,12; b2=0,005; b3=0,005; b4=0,05
h 02 =0,9; h12 =0,1; h 03 =0,8; h13 =0,2; h 40 =0,9; h14 =0,1
17
α1=5; α2=8; α3=10; α4=15
b1=0,002; b2=0,002; b3=0,005; b4=0,001
h10 =0,95; h11 =0,05; h 02 =0,9; h12 =0,1; h 03 =0,8; h13 =0,2; h 40 =0,7; h14 =0,3
18
α1=10; α2=4; α3=6; α4=15
b1=0,001; b2=0,005; b3=0,005; b4=0,05
h10 =0,9; h11 =0,1; h 02 =0,8; h12 =0,2; h 03 =0,75; h13 =0,25; h 40 =0,7; h14 =0,3
19
α1=0,05; α2=0,01; α3=1,5; α4=0,1
b1=1,2; b2=0,5; b3=0,5; b4=0,1
h10 =0,7; h11 =0,3; h 02 =0,75; h12 =0,25; h 03 =0,8; h13 =0,2; h 40 =0,9; h14 =0,1
20
α1=0,05; α2=0,01; α3=0,5; α4=0,1
b1=0,01; b2=0,05; b3=0,15; b4=0,05
h10 =0,65; h11 =0,35; h 02 =0,75; h12 =0,25; h 03 =0,8; h13 =0,2; h 40 =0,9; h14 =0,1
142
21
α1=15; α2=10; α3=5; α4=8
Окончание табл. 26 b1=0,0001; h10 =0,92; h11 =0,08; b2=0,0005; b3=0,001; b4=0,002
h 02 =0,9; h12 =0,1; h 03 =0,95; h13 =0,05; h 40 =0,97 h14 =0,03
22
α1=3; α2=5; α3=2; α4=10
b1=0,001; b2=0,003; b3=0,001; b4=0,001
h10 =0,82; h11 =0,18; h 02 =0,85; h12 =0,15; h 03 =0,9; h13 =0,1; h 40 =0,95 h14 =0,05
23
α1=0,1; α2=0,01; α3=0,5; α4=0,05
b1=1; b2=3; b3=2; b4=1
h10 =0,9; h11 =0,1; h 02 =0,85; h12 =0,15; h 03 =0,95; h13 =0,05; h 40 =0,9; h14 =0,1
24
α1=5; α2=3; α3=6; α4=8
b1=0,001; b2=0,005; b3=0,01; b4=0,006
h10 =0,88; h11 =0,12; h 02 =0,85; h12 =0,15; h 03 =0,75; h13 =0,25; h 40 =0,9; h14 =0,1
143
6. ИCCЛЕДОВАHИЕ МОДЕЛИ ПРОЦЕССА ПЕРЕДАЧИ ДВОИЧНОГО КОДА 6.1. Цель pаботы Изучение метода имитационного моделиpования передачи двоичного корректирующего кода при известной модели источника ошибок. Исследование корректирующей способности выбранного кода на основе результатов моделирования.
6.2. Оcновные теоpетичеcкие положения 6.2.1. Описание модели источника ошибок. При выборе корректирующих кодов, обеспечивающих требуемый уровень достоверности передачи инофрмации, необходимо иметь представление о статистических оценках искажений в канале связи. Известно много моделей источников ошибок [28]. Применение каждой из них определяет вид формул для расчетов вероятности неправильного декодирования РНД и вероятности стирания РСД принятой комбинации при декодировании. В данной лабораторной работе исследуется корректирующая способность кода при условии, что модель источника ошибок представляет собой модель Эллиота. Модель Элилиота – есть обобщенная модель Гилберта [28] для процесса с мгновенным восстановлением. Последовательност ошибок {Ei}, являющаяся процессом с мгновенным восстановлением, полностью определяется функцией распределения P(l) длин интервалов между ошибками. В лабораторной работе функция распределения
144
P(l) определяется исходя из полученных экспериментальных данных. В схеме восстановления предполагают, что есть «хорошие» и «плохие» состояния канала связи, длительности которых описываются стохастическими распределениями. «Плохие» состояния определяют пакет ошибок. В «хорошем» состоянии вероятность искажения символа кода ε0=0, а в «плохом» состоянии вероятность искажения символа кода ε1>0. В лабораторной работе генерация помеховой обстановки в канале происходит по следующей схеме. Определяется дистанция до очередной помехи, согласно заданной функции распределения P(d), а затем определяется длительность помехи, согласно заданной функции распределения P(b). Амплитуда помехи определяется, согласно заданной функции распределения P(a), полярность помехи определяется из вероятности РП(+) появления помехи положительного значения напряжения помехи. Если напряжение помехи UП больше порогового уровня сигнала UПОР, то помеха исказит принимаемый полезный сигнал, если имеет разную полярность с полезным сигналом. На рис. 35 приведен пример статистической картины искажений помехами принимаемой последовательности сигналов. На передаваемый сигнал UC влияет помеха и на выходе канала будет получен сигнал U*C . Кодовые комбинации длиной tk (шесть бит) имеют случайное число искаженных символов (g ошибок). Известно [29], что корректирующая способность линейных кодов определяется кодовым расстоянием d.
145 UП
tk
tk d1
UПОР
tk b1
tk d2
b2
tk d3
b3
UПОР UC
U*C
{Ei}
Рис. 35 В лабораторной работе исследуется помехоустойчивость кодов для режима обнаружения r ошибок и исправления s ошибок. Появление ошибок внутри помехи (в «плохом» состоянии) является событием независимым. Вероятность появления q ошибок на фиксированных позициях кода длиной n определится q Pq = PОШ (1 − PОШ ) n − q ,
(18)
где РОШ - вероятность искажения одиночного символа кода. Вероятность появления q ошибок на длине n кодовой комбинации определится q P(q, n) = C qn Pq = C qn PОШ (1 − PОШ ) n − q .
(19)
Среднее число ошибок на длине n кодовой комбинации равно
146 n
q = ∑ qP(q, n) .
(20)
q=0
Для режима обнаружения r ошибок вероятность неправильного декодирования определится по формуле: Р НД =
n
1 2
n−m
∑C
q =r +1
q n
q PОШ (1 − PОШ ) n − q ≈
1 2
n−m
r +1 , C rn+1 PОШ
(21)
где m - число информационных символов в коде.
r
q Р СР = ∑ C qn PОШ (1 − PОШ ) n − q ≈nPОШ .
(22)
q =1
Если код исправляет s–кратную ошибку, то его помехоустойчивость при РСД=0 определится формулой: Р НД =
n
∑C
q =s +1
q n
q s +1 . PОШ (1 − PОШ ) n − q ≈C sn+1 PОШ
(23)
6.3. Функциональные особенности имитационной модели На рис. 36 приведена общая схема имитационной модели. Алгоритм содержит следующие подпрограммы (ПП): - WWOD – предназначена для ввода начальных значений переменных и массивов, подготовки основной программы к работе; - GENP - предназначена для имитации появления помех; - ANALO - предназначена для моделирования искажений, вносимых помехой в последовательность {B} передаваемых двоичных символов; - STATO - предназначена для набора данных статистической картины искажений, причем, в результате
147 работы данной ПП будут получены частоты числа ошибок внутри помехи и частоты событий, состоящих в том, что длина интервала l между ошибками меньше либо равна заданным величинам границ оценки; - ANALK - предназначена для моделирования искажений передаваемых кодовых комбинаций; - STATK - предназначена для набора частот числа ошибок в кодовых комбинациях, числа правильно принятых кодовых комбинаций KDN и числа неправильно декодированных комбинаций KDI; - WIW – реализует вывод на экран дисплея результатов моделирования. При моделировании рассматривается заданное число помех PZ. На рис. 37 приведен алгоритм имитации помех. В схеме моделирования случайных событий, исходя из числа х, равномерно распределенного в интервале [0,1]. ПП OPRD генерирует случайную величину (СВ) D – дистанцию di до очередной i-й помехи. ПП OPRB генерирует случайную величину (СВ) B – длительность bi i-й помехи. ПП OPRA определяет случайную величину (СВ) A – амплитуду (напряжение) ai i-й помехи. ПП OPRZ определяет случайную величину (СВ) Z=1 при помехе положительного знака или Z=0 при помехе отрицательного знака. Рассмотрим более детально алгоритмы ПП ANALO, STATO, ANALK и STATK.
6.3. Алгоритмы моделирования 6.3.1. Моделирование искажений двоичных последовательностей. На рис. 38 приведен объединенный алгоритм ПП ANALO и STATO. Работает алгоритм следующим образом.
148 Начало 1 2 3 4 5 6 7 8
9
WWOD
Начало P=P+ 1
1
GENP
2
ANALO
3
STATO
4
ANALK
5 6
STATK 1
P
7 8
RAN(x) OPRD RAN(x) OPRB RAN(x) OPRA RAN(x) OPRZ Конец
Конец
Рис. 36 Рис. 37 Если на интервале D ошибок нет, то число неискаженных бит кода NB и длительность интервала до ошибки L увеличивается на величину D. Затем проверяется условие A
149 1
2
Начало
4
NB=NB+D, L=L+D
5
1
1 3
13 K=K+1
6
0
A
K=0
RAN(x)
7
NB+NB+B, L=L+B
0 8
0
Z=1
1
14
0
x≤PE
NB+NB+1, L=L+1
10
1
IB+IB+1, IB2=IB2+1
9 Z=1
11 10
1
13
15 16
K
STATL L=0
5
STATIB IB2=0 Конец
Рис. 38 Если A≥UP, то происходит моделирование процесса наложения помехи на полезный сигнал в блоках 4 - 13. Вероятность появления единичного сигнала определяется идентификатором PЕ. Если ошибок нет, то число NB и величина L увеличиваются на единицу. Если сигнал искажен, то число искаженных бит IB увеличивается на единицу, а в ПП STATL счетчик C2(J), J=1,2,…M, увеличивается на единицу при STATL ≤J. Счетчик IB подсчитывает общее число искаженных символов, а счетчик IB2 - число искаженных символов внутри помехи.
150 В результате работы алгоритма в ПП STATL будут накоплены частоты событий, состоящих в том, что длины интервалов L=l между ошибками меньше либо равны границам оценки, введенным с экрана дисплея. В счетчиках C2(J) накапливаются частоты соответствующего числа ошибок внутри помехи. 6.3.2. Моделирование искажений кодовых комбинаций. На рис. 39 приведен алгоритм ПП ANALK и STATK. ПП STATK содержит две ПП – AN1 и AN2. Подпрограмма AN1 анализа числа ошибок на длине кода n приведена на рис. 40. Подпрограмма AN2 анализа выполнения условий обнаружения или исправления ошибок корректирующим кодом приведена на рис. 41. Алгоритм ПП AN1 моделирует искажения символов на длине последовательности NZ при признаке помехи P (P∈{0,1}). Идентификатором RS и ключом M определяются следующие ситуации при моделировании. Если окончание помехи совпало с окончанием кода, то RS=0. Если окончание предыдущей помехи совпало с окончанием кодовой комбинации, то признак этого события RS≠0. Возможны два события, которые определяются ключом M. Если не выполнен анализ помехи полностью, то RS≠0 и M=0. Если не выполнен анализ кодовой комбинации полностью, то RS≠0 и M=1. В блоках 1 -14 (см. рис. 39) моделируется ситуация, при которой A
151 Рис. 39
152
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Советов Б.Я., Яковлев С.А. «Моделирование систем». – М.: Высш. школа, 1985 – 271 с. 2. Бусленко Н.П. Моделирование сложных систем. – М.: Наука,1978. – 400 с. 3. Финаев В.И. Моделирование при проектировании информационно-управляющих систем: Учебное пособие. – Таганрог: Изд-во ТРТУ, 2002. 4. Гайдук А.Р. Теория автоматического управления. – Таганрог: Изд-во ТРТУ, 2004. – 208 с. 5. Черныш П.И. Математический ппарат непрерывных систем автомтического управления: Учебное пособие. – Таганрог: Изд-во ТРТУ, 2005. – 204 с. 6. Чернов Н.И. Основы теории управления линейными автоматическими системами: Учебное пособие оп курсу «Основы теории управления». – Таганрог: Изд-во ТРТУ, 2002. – 330 с. 7. Поспелов Д. А. Вероятностные автоматы. – М.:Наука, 1970. – 76 с. 8. Чирков М.К. Основы общей теории конечных автоматов. – М.: Наука, 1972. – 564 с. 9. Саати Т.Л. Элементы теории массового обслуживания и ее приложения. – М.: Сов. радио, 1971. – 520 с. 10. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – М.: Наука, 1966. – 336 с. 11. Кофман А., Крюон Р. Массовое обслуживание. Теория и ее приложения. – М.: Наука, 1966. – 302 с. 12. Климов Г.П. Стохастические системы обслуживания. – М.: Мир, 1965. – 243 с. 13. Башарин Г.П., Харкевич А. Д., Шнепс М.А. Массовое обслуживание в телефонии. – М.: Наука, 1969. – 246 с.
153 14. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н. Приоритетные системы обслуживания. – М.: МГУ, 1973. – 326 с. 15. Финаев В.И. Алгоритмизация и имитационное моделирование с применением аппарата систем массового обслуживыания: Учебное пособие. – Таганрог: ТРТУ, 2003. – 72 с. 16. Вентцель Е.C. Теоpия веpоятноcтей. - М.: Наука, 1969. – 576 с. 17. Клейнрок Дж. Статистические методы в имитационном моделировании. – М.: Наука, 1978. – 473 с. 18. Голенко Д.И. Моделиpование и cтатиcтичеcкий анализ пcевдоcлучайныx чиcел на ЭВМ. - М.: Наука, 1965. 19. Cмиpнов Б.Я., Дунин-Баpковcкий И.В. Кpаткий куpc математичеcкой cтатиcтики для теxничеcкиx пpедложений. - М: Физматгиз, 1959. 20. Финаев В.И. Методичеcкие указания к выполнению cамоcтоятельной pаботы «Алгоpитмизация моделей одноканальной cиcтемы маccового обcлуживания» по куpcу «Моделиpование cиcтем». - Таганpог: ТPТИ, 1988. 21. Финаев В.И. Методичеcкие указания к выполнению pаботы «Алгоpитмизация моделей cложныx cиcтем маccового обcлуживания» по куpcу «Моделиpование cиcтем». Ч.2. - Таганpог: ТPТИ, 1989. 22. Ваpшавcкий В.И. Коллективное поведение автоматов. - М.: Наука, 1973. 23. Cpагович В.Г. Теоpия адаптивныx cиcтем. - М.: Наука, 1976. 24. Финаев В.И. Pуководcтво к cамоcтоятельному изучению pаздела «Пpименение веpоятноcтныx автоматов для моделиpования cиcтем» по куpcу «"Моделиpование cиcтем». - Таганpог: ТPТИ, 1990.
154 25. Финаев В.И., Киpичек Т.А. Pуководcтво к лабоpатоpной pаботе «Иccледование автоматныx моделей» по куpcу «Моделиpование cиcтем». - Таганpог: ТPТИ, 1990. 26. Лазаpев В.Г. Cаввин Г.Г. Cети cвязи, упpавление и коммутация. М.: Cвязь, 1973. 27. Лазаpев В.Г. Электpонная коммутация и упpавление в узлаx cвязи. М.: Cвязь, 1974. 28. Блох Э.Л., Попов О.В., Турин В.Я. Модели источника ошибок в каналах передачи цифровой информации. – М.: Связь, - 1971. 29. Финаев В.И. Обработка и передача сигналов в системах дистанционного управления: Учебное пособие. – Таганрог: Изд-во ТРТУ, - 2003. 27. Финаев В.И. Pуководcтво к лабоpатоpной pаботе "Имитационное моделиpование пеpедачи двоичного кода" по куpcу "Моделиpование cиcтем". Таганpог: ТPТИ, 1922.
155
Финаев Валерий Иванович
МОДЕЛИPОВАHИЕ CИCТЕМ ПРАКТИКУМ
Ответственный за выпуск Финаев В.И. Редактор Белова Л.Ф. Корректор Селезнева Н.П.
ЛП №020565 Офсетная печать Заказ №_______
Подписано к печати Усл. п.л. – 7,5 Уч.-изд.л. – 7,3 Тирах 500 “С”
__________________________________________________ Издательство Таганрогского государственного радиотехнического университета ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Таганрогского государственного радиотехнического университета ГСП 17А, Таганрог, 28, Энгельса, 4
