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

Классификация случайных процессов

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

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

Рассмотрим ансамбль из N реализаций, определяющий некоторый случайный процесс: {x_k(t)}, k=1,N

Вычислим путём усреднения по ансамблю среднее значение процесса в некоторый момент времени t₁:

Получим корреляционную функцию случайного процесса, характеризующую взаимную зависимость его значений в различные моменты времени t₁ и t₁+τ:

Если m_x(t₁) и K_x(t₁,t₁+τ) не зависят от момента времени t₁, т.е. m_x(t₁)=m_x и K_x(t₁,t₁+τ)=K_x(τ), то случайный процесс называется стационарным.

Рассмотрим некоторую k-ю реализацию стационарного случайного процесса длительностью T.

Среднее значение и корреляционная функции этой реализации может быть получены путём усреднения по времени:

Если случайный процесс стационарен, а m_x(k) и K_x(τ,k), вычислительные по различным реализациям совпадают, то случайный процесс называется эргодическим.

Для эргодических процессов характеристики, вычисленные усреднением по времени, равны аналогичными по ансамблю, т.е. m_x(k)= m_x. K_x(τ,k)= K_x

Таким образом все свойства эргодических процессов можно определить по единственной реализации.

Основные формы описания непрерывных случайных процессов

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

• ПРВ его значений x для фиксированного момента времени t, т.е. f(x,t);
• Корреляционная функция случайного процесса K_x(t₁,t₂), характеризующая взаимную зависимость его значений в различные моменты времени.

На основе ПРВ f(x,t) может быть определены любые средние характеристики или моменты распределения, в частности,

математическое ожидание

дисперсия

корреляционная функция K_x(t₁,t₂) формально определяется через двумерную ПРВ случайного процесса

причем при t₁=t₂=t имеем K_x(t₁,t₂)=D_x(t)

Для стационарного процесса

m_x(t)=m_x=const

D_x(t)=D_x=const,

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

K_x(t₁,t₂)=K_x(t₂,t₁)=K_x(τ),

τ=t₂-t₁, K_x(0)=D_x

Для стационарного процесса вводится также функция спектральной плотности, как Фурье преобразование корреляционной функции.

где w - частоты случайных колебаний случайного процесса.

Соответственно имеют место соотношения

Таким образом, основными формами описания непрерывных процессов являются:

• распределения значений случайного процесса (f(x,t), m_x(t), D_x(t),…) в конкретный момент времени;
• зависимости значений случайного процесса в различные моменты времени (K_x(t₁,t₂) или K_x(τ) и S_x(w) для стационарного процесса).

Получение на ЦВМ реализации случайного процесса с заданными коррелирующими свойствами

Реализация x(t) непрерывного случайного процесса с коррел. свойствами стационарного белого шума может быть получена на ЦВМ с помощью генератора случайных чисел в виде последовательности дискретных значений x(i*Dt), где i=0,1,2,…, Dt – период дискретизации времени

Стационарный случайный процесс с постоянной спектральной плотностью S₀ называется стационарным белым шумом.

Его корреляционная функция

где - представление «дельта-функции» d(τ) интегралом Фурье.

Обычно корреляционная функция стационарного белого шума записывают в виде: K_x(τ)=G×d(τ), где G=S0=const – интенсивность стационарного белого шума

График корреляционной функции стационарного белого шума

K_x(0)=Dx

K_x(τ≠0)=0, так как s(t≠0)=0

График спектральной плотности

Как видно из графика корреляционной функции значения белого шума не зависит друг от друга (корреляция отсутствует)

Для получения реализации случайного процесса с заданной корреляционной функцией K_x(τ) используется специальные методы

1) Методы формирующего фильтра

Основан на использовании закономерностей преобразования линейным динамическим звеном (ЛДЗ) спектральной плотности случайного сигнала:

S_x(w)=|Ф(jw)|²S_g(w)

где S_x – спектральная плотность выходного сигнала

S_g - спектральная плотность входного сигнала

Ф(jw) – частотная передаточная функция ЛДЗ

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

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

ФФ представляется ДУ ЛДЗ и добавляется к исходной математической модели случайного воздействия. В случае численного интегрирования на ЦВМ полученной таким образом системы ДУ случайное воздействие, задаваемое в форме реализации x(t) непрерывного случайного процесса представляется в виде последовательности дискретных значений x(ih), где h – шаг интегрирования, i=0,1,2,… Другими словами происходит аппроксимация реализации непрерывного случайного процесса дискретной реализацией с периодом дискретизации Dt, равным шагу интегрирования h. Такая замена не является эквивалентной, поэтому требуется корректировка соотношении, по которому определяются передаточная функция ФФ. Для обоснования необходимых коррекции исходного соотношения рассмотрим корелляционную функцию и спектральная плотность дискретного случайного процесса, аппроксимирующего непрерывный белый шум с интенсивностью G₀. В силу того, что в течении периода дискретизации, которая = шагу интегрирования h дискретный процесс сохраняет своё значение

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

S0= D_x *h

2) Метод скользящего суммирования

Основан на использовании интеграла свертки

, где X(t) – реализация выходного сигнала – случайного сигнала с заданной корелляционной функцией

ξ(t) – реализация входного случайного сигнала (белого шума)

W(t) – весовая функция, которая определяется на основе обратного преобразования Лапласа передаточной функции формирующего фильтра

При моделировании интеграл свёртки реализуется в виде суммы:

Отметки i=0,1,2,3,4 на осях t соответствуют дискретным моментам времени t_i=i*Dt, Dt – период дискретизации

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

x(1)=W(0)* ξ(1);

x(2)=W(1)* ξ(1)+W(0)* ξ(2)

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

В этом случае:

1) в расчетную формулу вместо несущ-й весовой функции W(τ) подставляют КФ K_x(τ):

2) вычисляют математическое ожидание m_x* и D_x* полученной реализации x*(n) случайного процесса, а также масштабный коэффициент , оценивающий степень несовпадения W(τ) и K_x(τ).

3) производят коррекцию полученной реализации x*(n) случайного процесса путём уменьшения центрированной составляющей

(x*(n)-m_x*) в раз, т.е. пропорционально отношению средне-квадратических отклонений полученной и искомой реализаций. В результате получается искомая реализация x(n) случайного процесса с заданной КФ K_x(τ) произвольного вида

Основные понятия исследования операций и системного анализа. Классификация задач исследования операций и принятия решений. Примеры формализации задач принятия решений.

Источник: лекция Кругликова «Исследования операций»

Исследование операций.

Сложная задача делится на этапы, каждый из которых решается как отдельная задача.

Системный подход

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

Система – совокупность взаимосвязанных элементов

1. Определить границы системы, т.е. нужно сформулировать цель данной системы.

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

S={S₁, S₂, … S_n}

Системы делятся на статические и динамические. Динамическая система изменяет своё состояние во времени. Для системы: автономные и неавтономные.

Автономная динамическая система S(t)

Неавтономная динамическая система может управлятся извне. U – вектор управляющих воздействий. S(t+dt)=Z[S(t), U(t)]

оператор

Системы: детерминированные и вероятностные (стохастические)

Модели:

1. Статические
2. Динамические
1. Детерминированные
2. Вероятностные

i. Дискретные

ii. Непрерывные

1) S={S₁,S₂, … S_n}

размерность

2) линейные / нелинейные

Пример:

(a) Плата с 6 микросхемами (самая простая модель)

1. нужно уменьшить длину проводников. Число сочетаний расположения микросхем на плате:

Длина проводников:

-соединение напрямую

1. определить коэффициенты связности между микросхемами.

Матрица размерностью 12´3 шаг Dx=2, Dy=1

(б) f(x) – функция

max -?

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

Источник: лекция Кругликова «Исследования операций»

1. Стоимостной критерий

2. Критерий технической эффективности

3. Надежность

4. Экологичность

5. Утилизация

Метод экспертных оценок

W₁, W₂, …, W_k

W(x) = a₁W₁(x)+…+ a_kW_k(x) – обобщение

z₁, z₂, … z_S – средние значения (оценка)

Метод уступок

W₁(x), W₂(x), …, W_k(x)

W_c(x₁, x₂) – стоимость

W_n(x₁, x₂) – производительность

(x₁, x₂) Î D

точка B – более эффективна точки А по обоим

точка С – также эффективнее точки А критериям

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

1. W_c(x₁, x₂) – Min

(x₁, x₂) Î D

Решение: (x₁^*, x₂^*, W_c^*)

Делаем уступку: W_c= W_c^*+D W_c (чтобы повысить производительность)

1. W_c(x₁, x₂) – Max

(x₁, x₂) Î D

Дополнительное условие: W_c(x₁, x₂) - W_c^* £ D W_c

(x₁^*, x₂^*, W_п^*)

Недостаток: отсутствие объективности в выборе величины уступки

Задача целочисленного программирования:

1. W(x) – Max

x Î D

g_i(x) £ b_i, i=1,2,…m

x³0

(x^*, W^*)

округление [x^*]=x’ W’=W(x’)

Пример:

(1)

(2) 4x₁+9x₂ £ 36 x₂ ³ 0

Линия уровня: W(x₁, x₂) = const

0) x₁=3,6 - нулевое приближение

x₂=2,3

W^*= 14,5

Решение не удовлетворяет условиям целочислинности

Дополнительные ограничения: x₁ £ 3, x₁ ³ 4

x₂ £ 2, x₂ ³ 3 =>

задача разветвилась на 2

1) x₂ ≤ 2 => x₁^*=4,2 x₂^*=2

2) x₂ ³ 3

3) x₁ £ 4 => x₁^*=4 x₂^*=2 W^*=14

4) x₁ ³ 5 => x₁^*=5 x₂^*=1,3 W^*=14,2

Max W(x₁, x₂)

{x₁, x₂}Î D

x₁, x₂ ³ 0

x₁, x₂ – целые

Задача о рюкзаке:

1 – положили предмет

0 – положили предмет

Важна ценность, которая должна быть Max, и вес груза

W(x₁, x₂) = 0,32x1+x2

(1) 2,3x₁+10x₂ £ 49,5

A(2,8; 4,3)

(2) 21x₁+8,4x₂ £ 9,5

B(3,4) Ï D

C(3,3); 3,96

D(2,4); 4,64

[1] Некоторые операторы языка ассемблера, например, такие, как операторы ввода/вывода, отображаются в несколько машинных команд.

[2] Название метода раскрутки произошло от фразы “to pull oneself up by one’s bootstrap”, т.е. "вытянуть себя за шнурки", аналогично легендарному методу барона Мюнхгаузена