Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

методические рекомендации по выполнению работ на персональном компьютере перечень рекомендуемой литератур

Работа добавлена на сайт samzan.net:


Черновик

«ВОЕНМЕХ»

МОДЕЛИРОВАНИЕ СИСТЕМ

Лабораторный практикум

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

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


Лабораторная  работа  № 1

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ИМИТАЦИОННОЙ МОДЕЛИ НЕЛИНЕЙНОЙ ДИНАМИЧЕСКОЙ СИСТЕМЫ

Цель работы – приобретение навыков и изучение особенностей программной реализации математических моделей динамических систем с использованием численных методов.

Основные сведения из теории

Модель нелинейной динамической системы рассматривается в форме системы нелинейных нестационарных уравнений первого порядка:

,  i=1,2,…,n,                                     (1)

где X(t)=(x1(t),x2(t),…,xn(t)) - вектор переменных состояния, аргумент t - время.

При заданных начальных значениях переменных состояния , i=1,2,…,n, путем интегрирования системы (1) могут быть определены законы их изменения во времени на любом требуемом интервале [0; T].

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

Метод Эйлера предусматривает решение уравнений в дискретном времени на основе преобразования модели (1) в рекуррентные соотношения:

,  i=1,2,…,n;                (2)

tj+1=tj+h,   j=0,1,…,J,                                      (3)

где  - значение i-ой переменной состояния на j-ом шаге решения (для t=tj);  - значение правой части i-го уравнения системы (1) на j-ом шаге решения; h – шаг интегрирования; J – количество шагов интегрирования, требуемое для достижения правой границы рассматриваемого интервала времени t=T. В зависимости от используемого способа обеспечения точности решения шаг интегрирования h может быть постоянным или переменным.

Точность решения, получаемого приближенными численными методами, повышается с уменьшением шага интегрирования, но при этом, очевидно возрастает вычислительная трудоемкость решения задачи – количество шагов вычислений J и требуемое машинное время, а возможно и объем оперативной памяти при необходимости сохранения всего получаемого решения. Для моделей высокого порядка необоснованное уменьшение шага h может приводить к чрезмерному или недопустимому завышению требуемых ресурсов ЭВМ. Поэтому при реализации таких моделей вопрос выбора шага интегрирования требует самостоятельного решения с учетом необходимой точности получения результата и располагаемых вычислительных ресурсов.

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

Первый предусматривает контроль точности в процессе интегрирования с уточнением величины каждого шага (контроль погрешности на шаге).

Второй предусматривает использование постоянной величины шага для всего интервала интегрирования и оценку погрешности по значениям переменных состояния только на правой границе интервала интегрирования t=T. В случае недопустимой величины погрешности процесс интегрирования повторяется с уменьшением величины шага.

В рамках данной лабораторной работы предусматривается использование второго подхода с контролем точности по конечному значению одной из переменных состояния модели y=xk(T), указанной в индивидуальном варианте задания.

Для оценки погрешности вычисления y с некоторым шагом h интегрирование повторяется с шагом . Полученное с уменьшенным шагом значение y* принимается за эталонное. Тогда абсолютная погрешность вычисления y определяется как , относительная погрешность

.                                            (4)

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

1. Задается исходное значение шага интегрирования h.

2. Проводится решение системы дифференциальных уравнений на интервале [0, T] с шагом h.

3. Решение повторяется с шагом .

4. Проводится оценка погрешности по соотношению (4).

5. Если погрешность d не превышает допустимого значения, шаг h, считается достаточным для обеспечения требуемой точности.

В противном случае в качестве нового проверяемого значения шага h принимается  и производится переход к п.3.

Таким образом обеспечивается последовательное уменьшение шага интегрирования в  (m=1,2,…) раз до достижения требуемой точности решения.

Содержание задания

В соответствии с индивидуальным вариантом задания (таблицы 1-6) разработать и отладить программное приложение, обеспечивающее:

1. Решение системы дифференциальных уравнений на интервале [0; T] для T=10c. с любым шагом, задаваемым пользователем в пределах [0; T]. Вывод: графиков xi(t), i=1,2,…,n; значения xk(T) и относительной погрешности его определения d.

2. Анализ зависимости точности и трудоемкости решения задачи от шага интегрирования. Вывод графиков зависимостей относительной погрешности d и оценки трудоемкости от величины шага h.

3. Автоматический выбор величины шага интегрирования для достижения относительной погрешности не более 1%.

Варианты заданий

Модель 1

;

;

;

;

.

Таблица 1

№

p

a

m

u

cx

cy

g

m1

m2

x1(0)

x2(0)

x3(0)

x4(0)

x5(0)

k

1

106

0,6

2000

10

0,05

0,01

9,81

0,1

0,01

1800

0,8

0

0

0,8

4

2

3

4

5

6

7

8

9

Модель 2

Практические рекомендации

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

2. При использовании графических средств, требующих накопления в оперативной памяти массивов значений функций для построения графиков уменьшение величины шага интегрирования может привести к необоснованному увеличению времени работы программы или потере ее работоспособности. Так при шаге интегрирования h=10-6, довольно распространенном для рассматриваемого класса задач, на интервале интегрирования 10с для каждой переменной состояния в процессе численного решения системы (1) будет получено 107 значений. Сохранение в оперативной памяти таких массивов данных невозможно. Отметим также, что для предельно детального отображения графика на экране монитора при современных характеристиках разрешения последнего вполне достаточно не более 103 точек. Поэтому в случае необходимости накопления массивов значений переменных состояния в процессе интегрирования системы целесообразно сохранять в них значения, разделенные интервалом времени, например, 0,01с.


Лабораторная  работа  № 2

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА

Цель работы – приобретение навыков рациональной программной реализации автоматных моделей различного типа.

Основные сведения из теории

Математическая F-схема, или детерминированный автомат, является удобной формой описания логических закономерностей развития процессов в системе, но не учитывает фактор случайности. Поэтому она обычно используется для моделирования подсистем контроля и управления и позволяет решать задачи разработки, проверки и оценки качества реализуемых ими алгоритмов принятия решения, выбора закона управления или изменения структуры системы.

F-схема задается в форме следующей совокупности:

F=(X,Z,Y,j, y),                                           (5)

где Z=(z1,z2,…,zI) – множество состояний, или внутренний алфавит; X=(x1,x2,…,xJ) – конечное множество входных сигналов, или входной алфавит; Y=(y1,y2,…,yL) – конечное множество выходных сигналов, или выходной алфавит; j=j(z,x) - функция переходов, описывающая закономерности смены состояний; y=y(z,x) – функция выходов, описывающая закономерности формирования выходных сигналов. Если множество состояний является конечным, автомат называется конечным. Конечный автомат представляет собой абстрактную математическую схему. Поэтому природа состояний и сигналов безразлична.

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

С позиций теории управления конечный автомат может рассматриваться как "черный ящик" с одним входом и одним выходом. На вход подается сигнал x, а с выхода снимается сигнал y (рисунок 1). Сигналы x и y могут принимать только фиксированные значения. Возможные значения входного сигнала образуют дискретное конечное множество X, значения выходного – дискретное конечное множество Y.

Другая, расширенная, трактовка понятия автомата допускает наличие нескольких входов или выходов. Так например, допустим наличие у автомата M входных каналов с собственными алфавитами X(m)=(,,...,). Тогда алфавит X вводится как произведение алфавитов: X=X(1)×X(2)×…×X(M), то есть символами алфавита X объявляются все возможные сочетания элементов алфавитов X(m) по одному из каждого. Количество элементов в X в результате составит

.

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

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

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

Рассмотрим простейшие и наиболее широко используемые виды конечных автоматов.

1. Автомат Мили имеет функции переходов и выходов следующего вида:

z[n+1]=j(z[n],x[n]), y[n]=y(z[n],x[n]),

где n=0,1,2,... – номер такта. Таким образом, в автомате Мили новое состояние и выходной сигнал выбираются в зависимости от сочетаний текущего состояния и входного сигнала.

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

При табличном способе для функции переходов задается таблица переходов (таблица 7), а для функции выходов – таблица выходов (таблица 8). Строки таблиц соответствуют элементам входного алфавита, а столбцы – элементам внутреннего алфавита. Позиция таблицы переходов, соответствующая i-му столбцу и j-й строке, – это новое состояние, в которое переходит автомат, если в момент прихода входного сигнала xj он находился в состоянии zi, а аналогичная позиция таблицы выходов – формируемый при этом выходной сигнал.

Таблица 7

Таблица 8

Таблица переходов автомата Мили

Таблица выходов

Входные

сигналы

Состояния

Входные

сигналы

Состояния

z1

z2

z3

z1

z2

z3

x1

z2

z3

z1

x1

y1

y1

y3

x2

z1

z1

z3

x2

y2

y2

y1

При матричном способе обе функции задаются одной матрицей соединений C размерностью I×I, строки которой соответствуют исходным состояниям z[n], столбцы - состояниям на следующем такте z[n+1]. Элементы матрицы задаются в виде дроби, в числителе которой указывают входной сигнал, вызывающий соответствующий переход, а в знаменателе - формируемый при таком переходе выходной сигнал.  Вместо элементов,  соответствующих невозможному для данного автомата переходу, ставится прочерк:

.

При графическом способе автомат Мили задается графом (рисунок 2,а), вершины которого соответствуют возможным состояниям автомата. Каждая вершина имеет J исходящих дуг, соответствующих вариантам смены или сохранения состояний при различных  входных  сигналах xj (j=1,2,...,J).  Около  каждой  дуги  указывают соответствующие ей входной и выходной сигналы.

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

2. У автомата Мура функции переходов и выходов имеют вид

z[n+1]=j(z[n],x[n]), y[n]=y(z[n]).

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

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

Таблица 9

Таблица переходов автомата Мура

Выходные сигналы

Входные

сигналы

y1

y1

y3

y2

Состояния

z1

z2

z3

z4

x1

z3

z4

z3

z1

x2

z2

z3

z4

z4

Другие варианты задания автомата Мура – граф (рисунок 2,б) или матрица соединений C и вектор выходов Y:

,  .                             (6)

3. В автономном автомате отсутствуют входные сигналы:

F=(Z,Y,j,y), z[n+1]=j(z[n]), y[n]=y(z[n]).

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

Таблица 10

Таблица переходов автономного автомата

Состояние

z1

z2

z3

z4

z5

z6

z7

Состояние на следующем такте

z6

z4

z7

z3

z1

z2

z5

Выходной сигнал

y1

y2

y3

y2

y1

y1

y3

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

С точки зрения удобства реализации модели автономный автомат может рассматриваться как предельный случай автомата Мура при размерности множества входных сигналов J=1.

4. Автомат без памяти обеспечивает однозначное отображение входного алфавита X в выходной Y:

F=(X,Y,y),  y[n]=y(x[n])

и может быть задан вектором Y вида (6), размерность которого соответствует размерности множества X, или таблицей вида 11.

Таблица 11

Таблица выходов автомата без памяти

Входной сигнал

x1

x2

x3

x4

x

x6

x7

x8

Выходной сигнал

y1

y2

y3

y4

y2

y5

y4

y3

5. В автомате без выхода отсутствуют выходные сигналы:

F=(X,Z,j),  z[n+1]=j(z[n],x[n]).

Его функция переходов задается в форме таблицы вида 7, соответствующегографа или матрицы C вида (6).

Для детерминированного автомата функции переходов j и выходов y задаются однозначно и в процессе его функционирования не изменяются.

Содержание задания

В соответствии с индивидуальным вариантом задания (таблица 12):

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

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

Таблица 12

Номер

варианта

Тип  автомата         

Количество

входов         

Количество

состояний

Количество

выходов

1

Мура

4

4

2

2

Без выхода

3

6

--

3

Мили

2

4

2

4

Мура

5

4

2

5

Автономный

--

8

5

6

Мура

4

5

3

7

Мили

3

4

4

8

Автономный

--

7

4

9

Без выхода

3

4

--

10

Мура

4

4

3

11

Мили

4

3

4

12

Автономный

--

6

3

13

Мура

4

3

2

14

Мили

2

4

4

15

Без выхода

5

5

--

16

Мура

5

5

4

17

Без памяти

10

--

6

18

Мили

3

4

2

19

Мура

4

5

4

20

Без выхода

4

6

--

21

Мили

3

4

3

22

Без памяти

13

--

8

Практические рекомендации

1. Разработанное программное приложение должно обеспечивать наблюдение процессов смены состояний и формирования выходных сигналов автомата на произвольном количестве тактов.

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

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

- вводятся целочисленные переменные, например, z – номер состояния, x – номер входного сигнала, y – номер выходного сигнала;

- задаются целочисленные массивы констант, например, xz, соответствующий таблице переходов, и xy, соответствующий таблице выходов;

- моделирование смены состояния на очередном такте сводится к выполнению оператора присваивания z=xz(x,z), моделирование формирования выходного сигнала – к выполнению оператора присваивания y=xy(x,z).


Лабораторная  работа  № 3

ПОСТРОЕНИЕ ГЕНЕРАТОРА СЛУЧАЙНЫХ ЧИСЕЛ С ЗАДАННЫМ ЗАКОНОМ РАСПРЕДЕЛЕНИЯ

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

Основные сведения из теории

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

При любом принципе построения генератор случайных чисел должен обеспечивать получение последовательностей чисел x1,x2,…,xn,…, обладающих следующими свойствами:

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

2. Отдельные числа, входящие в последовательность, взаимно независимы.

3. Статистическая обработка последовательности должна приводить к получению характеристик, соответствующих определенному закону распределения.

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

Общий принцип построения программных генераторов состоит в том, что на первом этапе имитируется равномерный закон распределения в интервале [0; 1], а затем полученная последовательность преобразуется для обеспечения требуемого закона.

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

Авторство данного метода принадлежит Нейману, предложившему аппаратный генератор равномерного закона распределения на регистрах (рисунок 3).

Пусть в N-разрядном регистре содержится некоторое число

xi=d12-1+d22-2+…+dN2-N,

где N - четное.  После возведения этого числа в квадрат для размещения результата в общем случае потребовалось бы 2N разрядов. Новое число формируется из N средних разрядов результата с  по . Последовательность случайных чисел 1,2,…,n,… формируется путем циклического повторения такой процедуры.

Элемент получаемой последовательности xi имеет 2N возможных значений, каждое из которых при достаточно большой длине последовательности наблюдается с частотой . Таким образом, можно считать, что элементы последовательности  имеют равномерный дискретный закон распределения в интервале . Если принять N достаточно большим, можно считать получаемый закон распределения непрерывным с плотностью распределения вероятностей (ПРВ):

          

Необходимо иметь в виду, что в строгом смысле, получаемая последовательность случайной не является. Действительно, генератор рассмотренного типа реализует жесткий алгоритм преобразования чисел и представляет собой детерминированный конечный автономный автомат F=áZ,Y,j,yñ, объем внутреннего алфавита которого составляет 2N. Последовательность выходных сигналов такого автомата заведомо не является случайной. Числовые последовательности, формируемые на основе описанного подхода, называются псевдослучайными и имеют следующие особенности:

1. Цикличность - длительность цикла детерминированного автономного автомата не превышает количества элементов внутреннего алфавита.

2. Регулярность - генерируемая последовательность жестко зависит от начальной установки.

3.   Возможность получения "вырожденной" последовательности - например, если на очередном шаге получено значение x=0, все последующие значения также будут нулями.

Указанные особенности являются одновременно и основными недостатками генераторов псевдослучайных чисел. Однако при достаточно больших N и удачных схемных или программных решениях удается получить псевдослучайные последовательности длиной до 10+7 чисел, в которых указанные недостатки проявляются незначительно, а возможность получения "вырожденной" последовательности исключена.

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

,  i=1,2,...,

где a,b - положительные числа, m=2l, l - разрядность представления целого числа в ЦВМ. Символическое обозначение  указывает на выполнение вычислений «по модулю m», то есть от результата вычислений сохраняется только двоичный код, занимающий младшие l разрядов.

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

Метод обратных функций основан на использовании известного результата теории вероятностей: независимо от вида непрерывного закона распределения при известных его ПРВ f(x) и функции распределения вероятностей (ФРВ) F(x) случайная величина

                                           (7)

распределена по равномерному закону в интервале [0; 1].

Действительно, в соответствии с (7) значения x и R связаны взаимно однозначной зависимостью. Поэтому для любых A и B 

,

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

Если удается получить аналитическое выражение для функции F-1(R), обратной к ФРВ F(x), процедура генерирования случайных чисел xi будет выглядеть следующим образом:

а) с помощью стандартного генератора получают равномерно распределенные в интервале [0; 1] числа xi;

б) числа xi получают по формуле xi=F-1(xi).

Например, для экспоненциального закона распределения (x>0)

f(x)=le-lx, F(x)=1-e-lx, .

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

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

Пусть требуется построить генератор случайных чисел, имеющих закон распределения с ПРВ f(x)=2cos2x и интервал возможных значений (интервал распределения)  (рисунок 4,а).

Функцию распределения находим интегрированием ПРВ:

.

График ФРВ показан на рисунке 4,б.

Находим обратную функцию: ,  .

Поскольку R может принимать значения в диапазоне [0; 1], то его граничным значениям будут соответствовать:

при R=0 ;

при R=1 .

Следовательно, для обеспечения требуемого закона в требуемом диапазоне распределения моделирующее соотношение должно иметь вид:

.

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

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

-3≤x≤-1: ,

F(-3)=0, F(-1)=0,25;

-1≤x≤1: ,   F(-1)=0,25,  F(1)=0,75;

1≤x≤3: ,

F(1)=0,75, F(3)=1.                                                            (8)

График ФРВ показан на рисунке 5,б.

Найдем обратную функцию к ФРВ, рассматривая те же интервалы (соответствие границ интервалов для x и F(x)=R можно проследить по соотношениям (8)):

0≤R≤0,25: ,  ;

0,25<R≤0,75: ,   ;

0,75<R≤1: ,  .

В итоге моделирующий алгоритм можно записать следующим образом:

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

Закон распределения реализаций случайной величины x1,x2,…,xn, составляющих выборку некоторой длины n, называется выборочным, или статистическим. Получение выборочной ФРВ F*(x) или ПРВ  является одной из основных задач обработки результатов статистического моделирования. Возможны два варианта постановки такой задачи:

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

2. Вид закона распределения неизвестен. В таком случае для его получения применяются непараметрические методы.

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

Классические непараметрические методы восстановления закона распределения по случайной выборке x1,x2,…,xn позволяют получить аппроксимации ПРВ или ФРВ кусочно-постоянными функциями.

Для аппроксимации ПРВ обычно используются статистические ряды или гистограммы.

При построении статистического ряда выборка разбивается на разряды:

                              

[xj,xj+1], x1=xmin, xj+1=xj+Dx, j=1,2,...,m; xm+1=xmax.

Количество разрядов m обычно выбирается в соответствии с условиями:

при ,  при n>500.

Длина разряда постоянна: . Разность xmax-xmin называется размахом выборки. Все попавшие в j-й разряд значения x далее считаются одинаковыми и равными среднему значению для данного разряда vj.

Статистический ряд составляется в форме таблицы 13.

Таблица 13

Статистический ряд

Номер разряда

Границы разряда

Среднее значение

Число наблюдений в разряде

Частота разряда

1

x1¸ x2

v1

n1

p1*

2

x2¸ x3

v2

n1

p2*

…

…

…

…

…

j

xj¸ xj+1

vj

nj

pj*

…

…

…

…

…

m

xm¸ xm+1

vm

nm

pm*

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

По статистическому ряду могут быть найдены оценки математического ожидания и дисперсии случайной величины x:

,

.

Гистограмма представляет собой графическую интерпретацию статистического ряда (рисунок 6).

Весьма точной аппроксимацией выборочной ФРВ является статистическая функция распределения Fx*(x), определяемая как частота наблюдения реализаций xi, не превышающих x: , где nx - количество значений .

Для ее построения вся выборка сортируется в порядке возрастания x: . Теперь отношения порядковых номеров j к объему выборки n дают значение Fx*(x) для интервалов [xj,xj+1] (рисунок 7):

.

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

, ui=x-xi,

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

Поэтому обычно подбирают некоторый теоретический закон распределения вероятностей (аналитическое выражение для ПРВ или ФРВ), достаточно близкий к выборочному, чтобы можно было рассматривать его как аппроксимацию истинного закона распределения исследуемой случайной величины. Затем проверяют соответствие теоретического закона истинному на основе критерия согласия теоретического и выборочного законов распределения (проверка статистической гипотезы).

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

- неверный подбор теоретического закона;

- недостаточный объем выборки.

Процедура проверки статистической гипотезы с помощью критерия согласия состоит в следующем:

- вычисляется значение некоторой меры расхождения подобранного теоретического и выборочного законов распределения;

- оценивается вероятность того, что при данном числе опытов n и при правильном подборе теоретического закона эта мера могла бы принять значение, большее или равное полученному.

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

Малая величина полученного критерия согласия свидетельствует о том, что скорее всего теоретический закон распределения подобран неверно (статистическая гипотеза отвергается). При достаточно большой величине критерия согласия нет оснований отвергать подобранный теоретический закон (статистическая гипотеза принимается).

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

В качестве меры расхождения теоретического и выборочного законов распределения используется величина

,

где n - объем выборки; m - количество разрядов; nj - число наблюдений в разряде; pj* - частота разряда; pj - вероятность попадания в j-й разряд  случайной величины x, распределенной по подобранному теоретическому закону.

Вероятность  является функцией cq2 и числа степеней свободы распределения c2: r=m-s-1, где s - количество параметров теоретического закона, оценивавшихся по выборке. Например, для нормального закона в общем случае s=2, а если mx или sx было заранее известно, s=1. Аналитические зависимости для закона распределения c2 известны, но на практике удобнее пользоваться таблицами (при  таблица 14).


Таблица 14

Распределение c2

r 

P=0,2

P=0,1

P=0,05

P=0,01

r  

P=0,2

P=0,1

P=0,05

P=0,01

1

1,6

2,7

3,8

6,6

16

20,5

23,5

26,3

32,0

2

3,2

4,6

6,0

9,2

17

21,6

24,8

27,6

33,4

3

4,6

6,3

7,8

11,3

18

22,8

26,0

28,9

34,8

4

6,0

7,8

9,5

13,3

19

23,9

27,2

30,1

36,2

5

7,3

9,2

11,1

15,1

20

25,0

28,4

31,4

37,6

6

8,6

10,6

12,6

16,8

21

26,2

29,6

32,7

38,9

7

9,8

12,0

14,1

18,5

22

27,3

30,8

33,9

40,3

8

11,0

13,4

15,5

20,1

23

28,4

32,0

35,2

41,6

9

12,2

14,7

16,9

21,7

24

29,6

33,2

36,4

43,0

10

13,4

16,0

18,3

23,2

25

30,7

34,4

37,4

44,3

11

14,6

17,3

19,7

24,7

26

31,8

35,6

38,9

45,6

12

15,8

18,5

21,0

26,2

27

32,9

36,7

40,1

47,0

13

17,0

19,8

22,4

27,7

28

34,0

37,9

41,3

48,3

14

18,2

21,1

23,7

29,1

29

35,1

39,1

42,6

49,6

15

19,3

22,3

25,0

30,6

30

36,3

40,3

43,8

50,9

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

1. Определяется значение cq2 и в строке таблицы распределения c2, соответствующей рассматриваемому r, находятся ближайшие к полученному cq2 значения.

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

В зависимости от значения P принимается одно из возможных решений:

- при  считается, что согласия между теоретическим и выборочным распределениями нет; теоретический закон отвергается и должен быть заменен другим, подлежащим аналогичной проверке;

- при  считается, что теоретическое распределение согласуется с выборочным, то есть подобрано верно;

- при 0,01<P<0,1 считается, что согласие между теоретическим и выборочным распределениями не обеспечивается скорее всего вследствие недостаточного объема выборки; рекомендуется увеличить объем выборки и повторить проверку в надежде на смещение значения P в другой интервал.

4. Если при 0,01<P<0,1 увеличение объема выборки невозможно или не дает ожидаемого эффекта, с несколько большим риском принимается, что границей областей согласия и несогласия теоретического и выборочного законов является P=0,05.

Критерий согласия Колмогорова применяется в том случае когда по случайной выборке восстановлена статистическая функция распределения F*(x). В качестве меры расхождения здесь рассматривается максимум абсолютной величины разности теоретической и выборочной (статистической) ФРВ:

,

где F(x) - теоретическая ФРВ.

Критерием согласия является вероятность того, что случайная величина  при данном объеме выборки n и правильном выборе теоретического закона могла бы принять значение, не меньшее :

.                                    (9)

При  вероятности (9) рассчитываются в соответствии с законом распределения Колмогорова. Наиболее важные для практики их значения представлены в таблице 15.

Таблица 15

Распределение Колмогорова

l

1,0

1,1

1,2

1,3

1,4

1,5

1,6

1,7

1,8

1,9

P

0,270

0,178

0,112

0,068

0,040

0,022

0,012

0,006

0,003

0,002

Если теоретический закон распределения подобран, порядок применения критерия Колмогорова аналогичен рассмотренному выше для критерия Пирсона. В качестве граничного для области согласия теоретического и выборочного законов принято рассматривать значение P=0,1. Ему соответствует l=1,22. Таким образом, при  считается, что теоретическое распределение согласуется с выборочным.

Содержание задания

В соответствии с индивидуальным вариантом задания (таблица 16):

1. Построить программный генератор случайных чисел с заданным законом распределения. Рекомендуется использовать метод обратных функций.

2. Оценить величину математического ожидания и дисперсии по выборкам объемом 50, 100, 1000, 105 и сравнить с точными величинами, полученными аналитически.

3. Оценить соответствие полученного закона заданному, используя указанный критерий согласия: Пирсона (1) или Колмогорова (2).

При выполнении пункта 3 предусмотреть:

  •  построение гистограммы (в случае применения критерия Пирсона) или статистической функции распределения (в случае применения критерия Колмогорова);
  •  использование выборок указанных с п. 2 объемов.

Таблица 16

№

вар

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

Критерий согласия

№ вар

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

Критерий согласия

1

1

12

1

2

 

2

13

2

3

2

14

1

4

 

1

15

2

5

 

2

16

1

6

2

17

1

7

1

18

2

8

 

1

19

1

9

 

1

20

 

2

10

1

21

2

11

2

22

1

Практические рекомендации

1. Лабораторные работы №№ 3-8 следует рассматривать как состоящие из двух основных этапов.

На первом этапе строится предусмотренный заданием генератор или имитационная модель.

На втором этапе выполняется статистическая обработка и анализ результатов использования построенного генератора или модели. При этом необходимо соблюдать принцип «черного ящика», то есть использование при статистической обработке каких-либо сведений о количественных параметрах источника данных или описывающих его работу аналитических соотношений недопустимо.

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

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

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

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

3. При проверке качества построенного генератора с помощью критерия Пирсона обеспечить вывод на экран вместе с гистограммой, полученной для выборочного закона pj*, (j=1,2,…,m), гистограммы для теоретического (заданного) закона распределения pj, (j=1,2,…,m), а также оценок математического ожидания и дисперсии, их точных значений и величины меры расхождения cq2.

4. При проверке качества построенного генератора с помощью критерия Колмогорова обеспечить совместный вывод на экран графиков статистической Fx*(x) и теоретической Fx(x) функций распределения (рисунок 8), а также оценок математического ожидания и дисперсии, их точных значений, меры расхождения Dр и полученного значения lр.

5. При определении величины меры расхождения статистической Fx*(x) и теоретической Fx(x) функций распределения Dр следует учитывать два возможных варианта взаимного расположения их графиков.

В случае, показанном на рисунке 8, на участке, где имеет место максимальное расхождение графиков статистической и теоретической функций распределения (область А), график статистической функции Fx*(x) расположен выше графика Fx(x). При этом Dр соответствует разности значений этих функций при некотором выборочном значении генерируемой случайной величины xj: .

В случае, показанном на рисунке 9, на участке, где имеет место максимальное расхождение графиков статистической и теоретической функций распределения (область Б), взаимное расположение графиков противоположное. При этом Dр соответствует некоторому значению аргумента функций распределения, стремящемуся слева к xj, и должно определяться как .

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

 и  

с последующим выбором максимальной из них.


Лабораторная  работа  № 4

ПОСТРОЕНИЕ ГЕНЕРАТОРА СЛУЧАЙНОГО ПРОЦЕССА МЕТОДОМ ФОРМИРУЮЩЕГО ФИЛЬТРА

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

Основные сведения из теории

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

Случайным процессом X(t) называют функцию времени t, которая при каждом фиксированном значении аргумента является случайной величиной. Если эта функция скалярная, случайный процесс называют скалярным или одномерным.

Реализацией x(t) случайного процесса X(t) называют конкретный вид процесса, который непосредственно наблюдался на некотором отрезке времени от 0 до T (рисунок 10,а). Реализация случайного процесса, очевидно, является детеминированной функцией. При многократном наблюдении случайного процесса может быть получено множество реализаций (рисунок 10,б). Увеличение объема этого множества (теоретически до бесконечности) дает все более полное представление о свойствах случайного процесса.

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

Одномерная, или первая, ПРВ случайного процесса f(x,t) описывает распределение его значений для фиксированного момента времени t, или сечения процесса в момент времени t (например, t1 или t2 на рисунке 10,б). На основе одномерной ПРВ для рассматриваемого момента времени могут быть определены любые средние характеристики, или моменты распределения, в частности, математическое ожидание

                                (10)

и дисперсия

,             (11)

где - центрированный случайный процесс (процесс с тождественно равным нулю математическим ожиданием), M[…] - математическое ожидание функции, заключенной в квадратные скобки.

Корреляционная функция одномерного случайного процесса Kx(t1,t2) характеризует взаимную зависимость его значений, соответствующих различным моментам времени (рисунок 10,б), и вводится через двумерную ПРВ:

             (12)

причем при t1= t2= t  имеем Kx(t,t)= Dx(t).

В частном случае стационарного случайного процесса:

mx(t)=mx=const, Dx(t)=Dx=const, f(x,t)= f(x),

а корреляционная функция становится функцией одного аргумента:

Kx(t1,t2)=Kx(t2– t1)=Kx(τ),  τ=t2– t1, Kx(0)=Dx.

Смысл соотношений (10)-(12) состоит в определении характеристик случайного процесса усреднением по бесконечному множеству реализаций.

Если стационарный случайный процесс обладает свойством эргодичности (среднее по множеству реализаций совпадает со средним по времени), перечисленные его характеристики могут быть найдены всего по одной реализации и без использования плотности распределения:

,                                      (13)

                (14)

                     (15)

где x(t) - детерминированная реализация случайного процесса X(t). Соотношения (13)-(15), очевидно, более удобны для практики.

Следствием их являются, в частности, оценки моментов распределения случайного процесса:

- математического ожидания   ;                                             (16)

- дисперсии  ;                                                        (17)

- корреляционной функции  .      (18)

В соотношениях (16)-(18) выполняется усреднение значений случайного процесса, полученных последовательными измерениями одной реализации процесса с шагом Dt: x1=x(Dt), x2=x(2Dt),…, xi=x(iDt),… В соотношении (18) индекс j соответствует значению аргумента корреляционной функции: t=jDt.

Для стационарного случайного процесса вводится также весьма удобная для построения расчетного аппарата функция спектральной плотности

                                     (19)

характеризующая распределение мощности, или интенсивности, случайных колебаний X(t) по различным частотам. Соответственно имеют место соотношения:

, .

Таким образом, для одномерного случайного процесса X(t) вместо многомерной ПРВ используются две группы характеристик, описывающих его с двух взаимно дополняющих точек зрения:

- с точки зрения распределения значений X(t) в конкретный момент времени (f(x,t), mx(t), Dx(t)...);

- с точки зрения зависимости значений X(t) в разные моменты времени (Kx(t1, t2) или Kx(τ), Sx(ω) для стационарного процесса).

Связь между этими двумя группами характеристик сводится только к формальному совпадению значений дисперсии, определяемых по (11) и через  Kx(τ) или Sx(ω).

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

Kx(t1, t2) = G(t1)δ(t1- t2),

где G(t1) - интенсивность белого шума.

Для стационарного белого шума G(t)=G=const и может быть определена спектральная плотность:

.

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

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

Sx(ω)=|W(jω)|2Sg(ω),                                            (20)

где Sg(ω) и Sx(ω) – спектральные плотности входного и выходного сигналов динамического звена, W(jω) – частотная передаточная функция звена.

Если на вход динамического звена поступает стационарный белый шум (t) со спектральной плотностью S ()=S0, соотношение (20) примет вид:

Sx()=|W(j)|2S0.

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

,

где спектральная плотность входного сигнала может быть найдена по заданной его корреляционной функции Kx(τ)  в соответствии с соотношением (19).

Пусть, например, задана корреляционная функция генерируемого процесса

Kx()=Dxe-| |.

Определим его спектральную плотность:

Теперь найдем передаточную функцию формирующего фильтра:

откуда  или , где , .

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

или в нормальной форме:

.                                      (21)

При программной реализации генераторов случайных процессов используются стандартные генераторы псевдослучайных чисел с равномерным или нормальным законом распределения. Такие генераторы обычно обеспечивают получение последовательностей чисел с достаточно низкой взаимной зависимостью. Если рассматривать такую последовательность 1,2,…,i,…,n как последовательность значений процесса (t), зарегистрированных в моменты времени t1<t2<<ti<<tn с постоянным шагом t: (t1)=1, (t2)=2,  (ti)=i, (tn)=n, ti+1=ti+t, будет получена модель дискретного белого шума. При t0 перейдем к модели непрерывного белого шума. При программной реализации шаг t всегда конечен. Его величину приходится учитывать при расчете параметров формирующего фильтра.

При использовании в качестве источника белого шума генератора равномерного закона распределения в диапазоне [0; 1] следует учесть, что генерируемая последовательность случайных чисел характеризуется математическим ожиданием mx=0,5 и дисперсией Dx=1/12≈0,833. Эти значения параметров соответствуют математическому ожиданию и интенсивности моделируемого непрерывного белого шума.

Программная реализация формирующего фильтра обычно выполняется с некоторым шагом h, величина которого определяется целью генерирования случайного процесса. Например, это может быть шаг интегрирования модели вида (1) динамической системы, для которой данный случайный процесс является входным сигналом. Соответственно и уравнения формирующего фильтра реализуются в форме (2). Таким образом фактически применяется аппроксимация непрерывного случайного процесса дискретным. Такой дискретный процесс имеет период  дискретизации, равный шагу интегрирования h, и сохраняет свое значение в течение периода. Определим корреляционную функцию и спектральную плотность дискретного случайного процесса, аппроксимирующего непрерывный белый шум с интенсивностью G0:

K*()=G01()-G01(-h),

.

Поэтому если в качестве источника белого шума используется генератор случайных чисел с некоторым законом распределения, характеризуемым дисперсией D, то при расчете параметров формирующего фильтра следует брать значение S0=Dh. При использовании стандартного генератора псевдослучайных чисел с равномерным законом распределения в интервале [0; 1] следует брать S0=h/12.

Содержание задания

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

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

Таблица 17

№ варианта

D

a

h

№ варианта

D

a

h

1

2

5

0.001

21

5

0.6

0.02

2

1

0.1

0.05

22

0.5

1.5

0.01

3

0.5

2

0.002

23

2

3

0.01

4

0.1

10

0.001

24

1

0.5

0.01

5

1

1

0.01

25

0.1

7.5

0.005

6

2

0,3

0.02

26

2

1.5

0.005

7

4

0.2

0.05

27

3

10

0.002

8

2

4

0.005

28

1

20

0.001

9

5

1

0.002

29

5

0.5

0.02

10

1

0.5

0.05

30

2

10

0.005

11

10

2

0.005

31

2

3

0.001

12

2

0.6

0.05

32

1

0.3

0.005

13

1

4

0.001

33

2

1.5

0.002

14

1

0.6

0.01

34

1

6

0.001

15

0.2

2

0.005

35

1

20

0.002

16

2

2

0.01

36

1

4

0.01

17

1

7.5

0.002

37

2.5

15

0.002

18

2

5

0.005

38

2

4

0.002

19

1

5

0.002

39

1

6

0.005

20

2.5

1

0.05

40

0.4

1.5

0.01

Практические рекомендации

1. Формирующий фильтр представляет собой динамическое звено. Известно, что для линейных динамических звеньев в стационарном режиме работы (установившийся процесс) имеет место следующая зависимость между математическими ожиданиями входного g и выходного x сигналов: mx=kфmg. Следовательно, при отличном от нуля mg математическое ожидание выходного сигнала и погрешность его оценки по соотношению (16) могут достигать существенных значений, что повлияет на результаты оценки корреляционной функции по (18). Поэтому при отсутствии требований к величине математического ожидания генерируемого сигнала рекомендуется использовать на входе фильтра центрированный белый шум. При использовании в качестве источника белого шума x(t) генератора равномерного закона распределения в диапазоне [0; 1], математическое ожидание для которого составляет 0,5, следует воспользоваться основным соотношением для получения центрированного случайного процесса: .

2. См. рекомендацию 1 к лабораторной работе №3.

3. Анализ соотношения (18) для оценки корреляционной функции по выборке значений наблюдаемой реализации случайного процесса показывает, что с увеличением значения параметра j количество выборочных значений, учитываемых при расчете, снижается. Их минимальное количество составит n-jmax+1, где  в соответствии с заданием. По известным оценкам приемлемая точность восстановления значений корреляционной функции может быть обеспечена по выборке объемом не менее 104. Длина генерируемых и обрабатываемых реализаций случайного процесса должна соответствовать такому требованию.

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

Таким образом, в течение переходного процесса представленный выше порядок расчета фильтра и соотношения (16)-(18) для оценки характеристик генерируемого процесса, некорректны.

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

Для фильтра в форме апериодического звена 1-го порядка можно учесть известные оценки продолжительности переходного процесса по математическому ожиданию 3Tф и дисперсии 1,5Tф.


Лабораторная  работа  № 5

ПОСТРОЕНИЕ ГЕНЕРАТОРА СЛУЧАЙНОГО ПРОЦЕССА С ЗАДАННЫМИ ЗАКОНОМ РАСПРЕДЕЛЕНИЯ И КОРРЕЛЯЦИОННОЙ ФУНКЦИЕЙ

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

Основные сведения из теории

В наиболее общей постановке задача имитации одномерного стационарного случайного процесса X(t) сводится к тому, что получаемые реализации процесса должны подчиняться закону распределения с заданной ПРВ f(x) и иметь заданную корреляционную функцию Kx().

Решение задач формирования заданного закона распределения и обеспечения заданных корреляционных свойств по отдельности подробно рассмотрено выше в рамках лабораторных работ № 3 и № 4. Теперь, когда требуется совместное их решение, проанализируем взаимное влияние необходимых преобразований.

Получение требуемого закона распределения случайной последовательности (реализации случайного процесса) можно рассматривать как преобразование исходной последовательности нелинейным безынерционным звеном. Для метода обратных функций статическая характеристика такого звена будет иметь вид (u)=F-1(u), где F-1 – обратная функция к ФРВ обеспечиваемого закона. Для других методов статическая характеристика эквивалентного нелинейного звена также может быть сформирована в соответствии с алгоритмом метода. В зависимости от вида (u) безынерционная нелинейность может изменить корреляционную функцию преобразуемого сигнала, в большинстве случаев – несущественно.

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

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

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

1 этап – преобразование равномерного закона распределения белого шума в стандартизованный нормальный закон распределения;

2 этап – обеспечение требуемых корреляционных свойств с помощью формирующего фильтра;

3 этап – преобразование нормального закона распределения генерируемого процесса в равномерный;

4 этап – обеспечение требуемого закона распределения.

Рассмотрим подробнее эти этапы.

Первый этап требует построения генератора стандартизованного нормального закона распределения с ПРВ

,  mu=0,  Du=1.

Связь любой случайной величины X с нормальным законом распределения и стандартизованной нормальной случайной величины U выражается следующими соотношениями:

, X=mx+Usx.                                     (22)

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

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

.

На практике это в достаточной степени подтверждается при n=12.

Поэтому процедура получения стандартизованного нормального закона выглядит следующим образом:

а) с помощью стандартного генератора получают 12 равномерно распределенных в интервале [0; 1] чисел xi;

б) числа zj со стандартизованным нормальным законом распределения получают по формуле, являющейся следствием (22):

,  .

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

От указанного недостатка свободна, например, следующая процедура:

а) с помощью стандартного генератора получают два равномерно распределенных в интервале  [0; 1] числа xi и xi+1;

б) вычисляют V1=2xi–1, V2=2xi+1–1, s=V12+V22;

в) если , повторяют пункты а) и б);

г) вычисляют  и получают два распределенных по стандартизованному нормальному закону  числа zj =V1r, zj +1=V2r.

На втором этапе должно быть обеспечено преобразование некоррелированной псевдослучайной последовательности z1, z2,…, zi,…, zn формирующим фильтром. Расчет формирующего фильтра выполняется в соответствии с рекомендациями к лабораторной работе №4, причем S0=h, а Dx следует брать равной единице для сохранения на выходе фильтра стандартизованного нормального закона распределения как наиболее удобного для дальнейшего преобразования сигнала.

На третьем этапе путем нелинейного преобразования

,                          (23)

где Fu(x) – ФРВ стандартизованного нормального закона, F(x)– интеграл вероятностей. В соответствии с (7) получаемая в результате такого преобразования псевдослучайная последовательность будет иметь равномерный в интервале [0; 1] закон распределения. Преобразование (23) является безынерционным и не оказывает существенного влияния на уже обеспеченные корреляционные свойства генерируемого процесса.

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

,           (24)

рекомендуемый при отсутствии больших значений аргумента (x2<∞). Необходимое количество суммируемых членов ряда предлагается определять самостоятельно.

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

Содержание задания

Построить программный генератор непрерывного случайного процесса с заданным законом распределения (в соответствии с вариантом задания к лабораторной работе № 3) и заданной корреляционной функцией (в соответствии с вариантом задания к лабораторной работе № 4, кроме значения дисперсии).

Проверку характеристик процесса (закона распределения и корреляционнной функции) выполнять в соответствии с требованиями к лабораторным работам № 3 и № 4 после каждого этапа преобразования процесса.

Практические рекомендации

1. При выполнении данной лабораторной работы следует учесть все практические рекомендации к лабораторным работам № 3 и № 4.

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

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

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


Лабораторная  работа  № 6

ПРОВЕРКА СТАЦИОНАРНОСТИ И ЭРГОДИЧНОСТИ СЛУЧАЙНОГО ПРОЦЕССА

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

Основные сведения из теории

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

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

Однородность этих выборок подтвердит наличие свойства стационарности случайного процесса. Для проверки однородности случайных выборок рекомендуется использовать критерий Колмогорова-Смирнова.

Критерий однородности Колмогорова-Смирнова по своей форме аналогичен критерию согласия Колмогорова. При проверке гипотезы об однородности двух случайных выборок x1,x2,…,xn и y1,y2,…,ym в качестве меры расхождения рассматривается величина

,

где Fx,*n и Fy,*m - статистические функции распределения, восстановленные соответственно по первой и второй выборкам (рисунок 11). Далее используется закон распределения Колмогорова (таблица 15) для случайной величины .

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

Содержание задания

Для полученного при выполнении лабораторной работы №5 случайного процесса проверить наличие свойств стационарности и эргодичности по критерию Колмогорова-Смирнова с построением графиков восстановленных с целью проверки функций распределения.

Практические рекомендации

1. См. рекомендацию 1 к лабораторной работе №3.

2. При проверках стационарности и эргодичности процесса с помощью критерия Колмогорова-Смирнова обеспечивать совместный вывод на экран графиков статистических функций распределения Fx,*n и Fy,*m, получаемых по двум рассматриваемым выборкам (рисунок 11), меры расхождения Dm,n и расчетного значения .

3. Рекомендацию 5 к лабораторной работе № 3 здесь следует применить к выборочным значениям, использованным для восстановления обеих функций распределения.


Лабораторная  работа  № 7

СТАТИСТИЧЕСКОЕ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ОДНОКАНАЛЬНОЙ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ОТКАЗАМИ

 

Цель работы – приобретение навыков и знакомство с особенностями построения имитационных моделей систем с дискретными состояниями и непрерывным временем, организации статистического имитационного моделирования и оценки его точности.

Основные сведения из теории

Понятие «система массового обслуживания» применяется для систем, выполняющих обработку, или обслуживание, поступающих на вход заявок (требований).

Совокупность поступающих на вход заявок называют входным потоком. Если моменты поступления отдельных заявок случайны, на входе системы имеет место случайный поток заявок.

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

В качестве исходных данных при составлении моделей СМО рассматриваются характеристики входных потоков, количество и характеристики производительности каналов, количество мест в очереди.

К числу основных характеристик СМО, для определения которых строятся математические модели, относятся:

- вероятность обслуживания заявки, или относительная пропускная способность;

- вероятность отказа в обслуживании заявки;

- абсолютная пропускная способность – среднее число заявок, обслуживаемое в единицу времени:

- среднее число занятых каналов.

Математические модели СМО строятся в классе моделей систем с дискретными состояниями и непрерывным временем.

При построении математических моделей таких систем вводится конечное множество дискретных состояний X=(x0,x1,…,xn) таким образом, чтобы выполнялись следующие условия:

- в любой рассматриваемый момент времени система обязательно находится в одном из состояний, составляющих множество X;

- система не может одновременно находиться в двух или более состояниях из множества X.

Для одноканальной СМО с отказами очередь отсутствует и множество X включает в себя два состояния:

x0 – канал свободен;

x1 – канал занят обслуживанием заявки.

Логика процесса смены состояний описывается ориентированным графом,  вершины   которого  соответствуют  состояниям  системы,  а дуги – возможным переходам в другие состояния.

Для рассматриваемой СМО граф смены состояний показан на рисунке 12.

Исходящая из вершины x0 дуга соответствует переходу на обслуживание очередной заявки. Входящая – завершению обслуживания заявки и освобождению канала.

Входной поток заявок рассматривается как простейший, характеризующийся следующими свойствами:

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

2. Ординарность - невозможность одновременного наступления двух или более событий.

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

4. Стационарность – независимость характеристик потока от времени.

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

,

где  - среднее число событий на интервале времени Dt.

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

Пуассоновский  поток,  обладающий свойством стационарности, называется простейшим. Его интенсивность постоянна во времени: l(t) = l = const.

Интервал времени между событиями пуассоновского потока подчиняется экспоненциальному закону распределения с ПРВ f(x)=le-lx (x>0).

Основной характеристикой отдельного канала СМО является производительность (интенсивность потока обслуживания) m  – среднее число заявок, обслуживаемых в единицу времени. Для процесса обслуживания заявок в канале принимаются те же закономерности, что и для входного потока заявок. В частности, m(t) = m = const. Соответственно интервал времени, требуемый на обслуживание заявки, рассматривается как случайная величина с экспоненциальным законом распределения f(x)=me-mx (x>0).

Интенсивность l и производительность канала m задаются как исходные количественные характеристики модели СМО.

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

,

,

p0+p1=1,

где p0 и p1 – вероятности пребывания системы в состояниях соответственно x0 и x1 в рассматриваемый момент времени.

Поступающая в систему заявка получает отказ в обслуживании, если единственный канал занят (состояние x1). Следовательно, для одноканальной СМО с отказами вероятности обслуживания p и отказа в обслуживании заявки q совпадают с вероятностями состояний: p=p0, q=p1.

Для стационарной модели (l = const, m = const) могут быть найдены финальные вероятности, соответствующие установившемуся процессу смены состояний. В установившемся процессе вероятности состояний постоянны, и система уравнений Колмогорова сводится к системе алгебраических уравнений:

,

,

p0+p1=1.

Ее решение: , .

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

Имитационное моделирование предусматривает непосредственное воспроизведение процесса функционирования СМО во времени - последовательности моментов времени поступления заявок и моментов времени завершения обслуживания заявок в канале с возможностью регистрации фактов поступления заявок на обслуживание или отказов в обслуживании. Наблюдение имитируемого процесса на достаточно большом интервале времени позволяет оценить значения требуемых характеристик СМО.

Рассмотрим принципы построения имитационной модели одноканальной СМО с отказами.

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

для интервала времени до поступления заявки ;                 (25)

для интервала времени до окончания обслуживания ,      (26)

где xi, xj – случайные числа с равномерным законом распределения в интервале [0; 1].

Укрупненный алгоритм моделирования процесса в рассматриваемой СМО выглядит следующим образом:

1. Вводятся и обнуляются счетчики времени t, количества поступивших в систему заявок N, количества обслуженных (поставленных на обслуживание) заявок M.

2. С помощью (25) генерируется интервал времени Dt1 от начала работы системы до поступления первой заявки. Поскольку исходное состояние системы x0 (канал свободен), первая заявка поступает на обслуживание, соответственно N и M увеличиваются на единицу, для текущего времени устанавливается значение t=Dt1.

3. Генерируются значения интервалов времени Dti до поступления очередной заявки с помощью (25) и до окончания обслуживания заявки в канале Dtj с помощью (26). Значение N увеличивается на единицу. Значение текущего времени увеличивается на Dti.

4. Если Dti < Dtj, то к моменту поступления следующей заявки обслуживание предыдущей не завершено. Поступающая заявка получает отказ в обслуживании. Соответственно значение M не изменяется.

5. Если Dti  Dtj, то к моменту поступления следующей заявки канал освобождается. Заявка поступает на обслуживание. Значение M увеличивается на единицу.

6. Пункты 3-5 повторяются необходимое количество раз.

В результате обеспечивается моделирование процесса в СМО на некотором интервале времени [0, T], где , за который в систему поступает N заявок. При достаточно больших значениях T имеет место N≈lT.

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

Оценка вероятности обслуживания определяется как

,                                                     (27)

оценка вероятности отказа в обслуживании –

.                                                 (28)

Соотношения (27)-(28) соответствуют классической задаче оценки вероятности P(А)=pА случайного события А на основе схемы Бернулли. В соответствии с законом больших чисел и предельными теоремами можно принять (с достоверностью, близкой к 1), что при достаточно больших N оценка этой вероятности p*А является непрерывной случайной величиной, распределенной по нормальному закону со следующими  математическим ожиданием и среднеквадратическим отклонением:

,

                                   (29)

С учетом (29) найдем вероятность того, что при определенном n оценка будет отличаться от истинной вероятности не более, чем на D:

P(|p*А – pA| < ∆) = P(pA – ∆ < p*А < pA + ∆) = F(pA + ∆) – F(pA – ∆),        (30)

где F(x) - функция распределения вероятностей (ФРВ) случайной величины p*А. Графически вероятность (30) соответствует заштрихованной площади под кривой ПРВ случайной величины p*А (рисунок 13).

Соотношение (30) обычно представляют в следующей форме:

,                             (31)

где

- стандартизованная нормальная случайная величина;  определяется по (29); Pд - доверительная вероятность;  - коэффициент доверительного интервала.

Доверительная вероятность может быть определена через интеграл вероятностей:

.

На основе (31) с учетом (29) при достаточно большом N можно с доверительной  вероятностью Pд оценить погрешность определения p*А:

                                    (32)

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

.                                (33)

В большинстве случаев Pд выбирают в соответствии с правилом "трех сигм": aд=3, Pд=0,997≈1.

Отметим следующие особенности полученных результатов:

1. Из соотношений (32)-(33) хорошо видна "цена" точности статистического моделирования. Повышение точности в m раз требует увеличения количества опытов в m2 раз.

2. Определяемое по (33) количество опытов не гарантирует требуемую точность |e|< eдоп.. В строгом смысле никакое конечное количество опытов не может обеспечить такой гарантии, так как, с одной стороны, соотношения (32)-(33) соответствуют определенной доверительной вероятности Pд<1, и с другой стороны, все полученные результаты основаны на теоретических соотношениях, справедливых для конечных n только с некоторой вероятностью.

3. В формулах (32)-(33) употребляется значение истинной вероятности pА, которое в рассматриваемой задаче заведомо неизвестно. Поэтому прямое использование этих соотношений невозможно.

На практике эта проблема может решаться двумя способами.

Первый основан на том, что при фиксированной eдоп. зависимость Nтреб.(pА) в соответствии с (33) имеет максимум при pА=0,5 (рисунок 14). Следовательно, оценка требуемого количества опытов по априорному значению pА=0,5, а именно,  опытов, обеспечит для любого окончательного результата точность не хуже заданной. Недостаток этого способа состоит в том, что трудоемкость эксперимента оказывается завышенной. Так например, если истинное значение pА=0,9, то Nтреб. окажется завышенным в  раза.

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

Рекомендуемый принцип построения итерационного алгоритма статистического моделирования для оценки вероятности некоторого события А сводится к следующей последовательности действий:

1. Проведение начальной серии опытов объемом N и регистрацию количества случаев появления события A NА.

2. Вычисление оценки вероятности:

.

3. Получение оценки погрешности результата:

.

4. При выполнении условия e*≤eдоп. завершение моделирования и оформление окончательных результатов.

5. При e*>eдоп. получение оценки требуемого количества опытов:

.

6. Определение объема дополнительной серии опытов N'.

7. Проведение дополнительной серии опытов и регистрация количества случаев появления события A  N'А.

8. Уточнение оценки вероятности:   

,

и переход к пункту 3.

С точки зрения рациональной организации статистического эксперимента особое внимание следует обратить на п. 6 – определение объема дополнительной серии опытов. Здесь следует иметь в виду, что все оценки, получаемые по малым начальным сериям опытов, очевидно, имеют значительную погрешность. Это относится и к оценке N*треб..

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

Если заниженная оценка N*треб. превышает объем проведенной серии опытов, алгоритм позволит ее впоследствии скорректировать.

Если оценка N*треб. получается завышенной, то прямое определение объема дополнительной серии опытов по очевидному соотношению N’= N*треб.-N может привести к итоговому завышению трудоемкости эксперимента, что противоречит основной цели применения итерационного подхода. Наиболее рациональным способом решения этой проблемы является реализация интерактивного подхода: предоставление пользователю программной статистической модели всей информации о текущих оценках и возможности управления объемами дополнительных серий опытов.

Содержание задания

В соответствии с индивидуальным вариантом задания (таблица 18) построить имитационную статистическую модель одноканальной системы массового обслуживания с отказами. Процесс смены состояний системы считать марковским, поток заявок - простейшим. Интенсивность потока заявок l и производительность канала m заданы в таблице вариантов.

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

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

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

Таблица 18

гр. И322

№ варианта

l, с-1

m, с-1

x

1

0.1

0.01

p

2

1.5

0.5

q

3

10

20

p

4

1

2

q

5

5

10

q

6

2

1

p

7

20

10

q

8

0.4

0.2

p

9

12

6

q

10

1

0.5

q

11

0.2

0.08

p

12

1

1.5

p

13

30

10

q

14

1

0.6

p

15

0,2

0,05

p

16

10

2

q

17

25

10

p

18

5

1

q

19

20

5

q

20

5

1

p

21

2.5

0.5

q

22

0.1

0.2

q

Условные обозначения:

p - вероятность обслуживания заявки,

q - вероятность отказа в обслуживании.

Практические рекомендации

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

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

3. Для связи величин объемов дополнительных серий опытов c интервалами времени моделирования вместо истинного значения интенсивности входного потока заявок допустимо использование ее оценки .


Лабораторная  работа  № 8

СТАТИСТИЧЕСКОЕ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ МНОГОКАНАЛЬНОЙ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ОГРАНИЧЕННОЙ ОЧЕРЕДЬЮ

 

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

Основные сведения из теории

Для n-канальной СМО с очередью на m мест (m<<∞) множество состояний X включает в себя n+m+1 состояния:

x0 – все каналы и места в очереди свободны;

x1 – обслуживанием занят один канал, все места в очереди свободны;

xk (k≤n) – обслуживанием заняты k каналов, все места в очереди свободны;

xk (n<k≤n+m) – обслуживанием заняты все n каналов, заняты r=k-n мест в очереди.

Граф смены состояний такой СМО показан на рисунке 15.

Основные принципы и допущения, положенные в основу моделей СМО, рассмотрены в описании лабораторной работы № 7.

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

Если обслуживанием заявок параллельно заняты k каналов (k≤n), интенсивность обслуживания составляет km, где m - производительность одного канала.

Система уравнений Колмогорова для вероятностей состояний СМО, описываемой графом на рисунке 15, имеет вид:

,

…

,     1<k<n,

…

,

…

,    1<r<m,

…

,

.

Перейдем к системе алгебраических уравнений для установившегося процесса смены состояний:

,

,

…

,     1<k<n,

…

,

…

,    1<r<m,

…

,

.

Выразим все финальные вероятности через p0:

,

,  ,

…

,     1<k≤n;                                       (34)

,  ,  ;

…

,    1<r≤m;                                  (35)

.                       (36)

При известных параметрах СМО l, m, n и m уравнение (36) позволяет найти вероятность p0. Далее по (34) и (35) могут быть найдены вероятности остальных состояний.

Вероятность отказа в обслуживании заявки совпадает с pn+m (заняты все каналы и все места в очереди):

.

Вероятность обслуживания заявки: p=1-q.

Укрупненный алгоритм имитационного моделирования процесса в рассматриваемой СМО с учетом рекомендаций к лабораторной работе № 7 можно построить следующим образом:

1. Вводятся и обнуляются счетчики времени t, количества поступивших в систему заявок N, количества обслуженных (поставленных на обслуживание) заявок M, количества занятых каналов k, количества занятых мест в очереди r.

2. На основе моделирующего соотношения  генерируется интервал времени Dt1 до поступления в систему заявки.

3. Если k=0, значения N, M и k увеличиваются на единицу, значение текущего времени увеличивается на Dt1.

Если k>0 генерируется интервал времени до окончания обслуживания заявки на основе моделирующего соотношения  и моделируются следующие варианты развития процесса в СМО:

при Dti < Dtj значение N увеличивается на единицу, значение текущего времени увеличивается на Dti, а также:

при k<n заявка поступает на обслуживание в свободный канал, значения M и k увеличиваются на единицу;

при k=n и r<m заявка занимает свободное место в очереди, значения M и r увеличиваются на единицу;

при k=n и r=m поступающая заявка получает отказ в обслуживании, значения счетчиков M, k и r не изменяются;

при Dti > Dtj значение текущего времени увеличивается на Dtj, а также:

при r=0 один из занятых каналов освобождается до момента поступления следующей заявки, значение k уменьшается на единицу;

при r>0 одна из заявок переходит из очереди на обслуживание, освобождая место в очереди до момента поступления следующей заявки, значение r уменьшается на единицу.

4. Пункты 2-3 повторяются необходимое количество раз.

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

Содержание задания

В соответствии с индивидуальным вариантом задания (таблица 19) построить имитационную статистическую модель n-канальной системы массового обслуживания с очередью на m заявок. Процесс смены состояний системы считать марковским, поток заявок - простейшим. Интенсивность потока заявок l и производительность канала m соответствуют варианту задания к лабораторной работе № 7. Значения n и m указаны в таблице вариантов.

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

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

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

Таблица 19

гр. И322

№ варианта

n

m

x

1

3

1

p

2

2

2

q

3

2

2

p

4

3

1

q

5

3

1

p

6

2

2

q

7

3

1

q

8

3

1

p

9

2

2

q

10

3

1

q

11

2

2

p

12

2

2

q

13

2

2

p

14

3

1

p

15

3

1

q

16

2

2

q

17

3

1

p

18

2

2

q

19

2

2

q

20

3

1

p

21

3

1

p

22

2

2

q

Условные обозначения:

p - вероятность обслуживания заявки,

q - вероятность отказа в обслуживании.

Практические рекомендации

1. См. рекомендации к лабораторной работе №7.


Литература

1. Емельянов В.Ю. Методы моделирования стохастических систем управления. – СПб: БГТУ, 2004.

2. Королев С.Н. Марковские модели массового обслуживания. – СПб.: БГТУ, 2002.

3. Шапорев С.Д. Прикладная статистика: учебное пособие. – СПб: СМИО Пресс, БГТУ,  2003.

4. Шапорев С.Д., Родин Б.П. Случайные процессы: учебник для вузов. - СПб: БГТУ, 2010.


СОДЕРЖАНИЕ

стр.

Лабораторная работа № 1. Программная реализация имитационной модели нелинейной динамической системы   .   .   .   .   .   .   .   .   .

3

Лабораторная работа № 2. Имитационное моделирование детерминированного конечного автомата   .   .   .   .   .   .   .   .   .   .   .   .   .   .

Лабораторная работа № 3. Построение генератора случайных чисел с заданным законом распределения   .   .   .   .   .   .   .   .   .   .   .   .   .

Лабораторная работа № 4. Построение генератора случайного процесса методом формирующего фильтра   .   .   .   .   .   .   .   .   .   .   .   .   

Лабораторная работа № 5. Построение генератора случайного процесса с заданными законом распределения и корреляционной функцией   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

Лабораторная работа № 6. Проверка стационарности и эргодичности случайного процесса   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

Лабораторная работа № 7. Статистическое имитационное моделирование одноканальной системы массового обслуживания с отказами   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

Лабораторная работа № 8. Статистическое имитационное моделирование многоканальной системы массового обслуживания с ограниченной очередью   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

Литература   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .




1. ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ ИНСТИТУТ НЕФТИ И ГАЗА Кафедра Автоматизация и упр1
2. Словообразование1
3. Понятия «бизнес-тур» и «деловой туризм»
4. Слово и человек в жизни
5. I Психологические основы формирования самооценки и коммуникативных умений в младшем школьном возрасте
6. задание- Создайте новый стиль для Вашего фрагмента так чтобы он имел название Ваша фамилия; Устано
7.  Расчет производственной программы потребных основных фондов и численности работающих
8. Audi
9. Забудь чему тебя учили и начинай учиться заново
10. Судебник 1497 год
11. Использование маркетингового подхода при выживании ВУЗов в современных условиях
12. культурным потенциалом
13. Реферат- Валентина Степановна Гризодубова
14. Четыре апостола картина немецкого художника Альбрехта Дюрера
15. Строение кровеносной системы у разных классов животных
16. 29 05 2013 г протокол 12 Вопросы к экзамену по дисциплине Хозяйственное право для студентов спец
17.  При причинении вреда здоровью- для определения степени тяжести вреда здоровью и решения ряда других вопр
18. исторически сложившийся тип вид журналистского произведения
19. состояние полного физического духовного и социального благополучия а не только отсутствие болезней и физи
20. Московский государственный университет экономики статистики и информатики МЭСИ на основании лицензии н

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