Xreferat.com » Рефераты по математике » Методы и алгоритмы построения элементов систем статистического моделирования

Методы и алгоритмы построения элементов систем статистического моделирования

height="22" />- поглощающие, а два - Методы и алгоритмы построения элементов систем статистического моделирования- невозвратные (рис.10):

Методы и алгоритмы построения элементов систем статистического моделирования

Рис. 8.10. Система с четырьмя состояниями

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

Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования

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

Методы и алгоритмы построения элементов систем статистического моделирования

Фундаментальная матрица после вычислений примет вид:

Методы и алгоритмы построения элементов систем статистического моделирования

Тогда, согласно формуле (9), матрица вероятностей поглощения вычисляется так:

Методы и алгоритмы построения элементов систем статистического моделирования.

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

Методы и алгоритмы построения элементов систем статистического моделирования

Таким образом, если процесс начался в Методы и алгоритмы построения элементов систем статистического моделирования, то вероятность попадания его в Методы и алгоритмы построения элементов систем статистического моделирования равна Методы и алгоритмы построения элементов систем статистического моделирования, а в Методы и алгоритмы построения элементов систем статистического моделирования - Методы и алгоритмы построения элементов систем статистического моделирования. Отметим одно интересное обстоятельство: несмотря на то, что, казалось бы, левое поглощающее состояние (“левая яма”) находится рядом с Методы и алгоритмы построения элементов систем статистического моделирования, но вероятность попадания в нее почти в два раза меньше, чем в “удаленную яму” - Методы и алгоритмы построения элементов систем статистического моделирования. Этот интересный факт подмечен в теории ДМЦ, и объясняется он тем, что Методы и алгоритмы построения элементов систем статистического моделирования, то есть процесс имеет как бы “правый уклон”. Рассмотренная выше модель называется в теории ДМЦ моделью случайного блуждания. Такими моделями часто объясняются многие физические и технические явления и даже поведение игроков во время различных игр.

В частности, в рассмотренном примере объясняется тот факт, что более сильный игрок может дать заранее значительное преимущество (“фору”) слабому противнику и все равно его шансы на выигрыш будут более предпочтительными.

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

Методы и алгоритмы построения элементов систем статистического моделирования(10)

где

Методы и алгоритмы построения элементов систем статистического моделирования - диагональная матрица, т.е. матрица, полученная из М путем оставления в ней лишь диагональных элементов и замены остальных элементов нулями. Например, приведенная выше матрица (7а) будет иметь вид:

Методы и алгоритмы построения элементов систем статистического моделирования

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

Методы и алгоритмы построения элементов систем статистического моделирования

Аналогичным образом определяема и дисперсия для общего количества раз пребывания в том или ином состоянии Методы и алгоритмы построения элементов систем статистического моделирования. Обозначим ее Методы и алгоритмы построения элементов систем статистического моделирования:

Методы и алгоритмы построения элементов систем статистического моделирования(11)

4.2. Эргодические цепи

Как указывалось выше под эргодической ДМЦ понимается цепь, не имеющая невозвратных состояний. Таким образом, в такой цепи возможны любые переходы между состояниями. Напомним, что эргодические цепи могут быть регулярными и циклическими. Ранее определение таких цепей было дано.

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

Степени Методы и алгоритмы построения элементов систем статистического моделирования при Методы и алгоритмы построения элементов систем статистического моделирования стремятся к стохастической матрице Методы и алгоритмы построения элементов систем статистического моделирования. Каждая строка матрицы Методы и алгоритмы построения элементов систем статистического моделированияпредставляет один и тот же вероятностный вектор Методы и алгоритмы построения элементов систем статистического моделирования(12) все компоненты которого положительны.

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

Методы и алгоритмы построения элементов систем статистического моделирования(13)

которое в развернутом виде будет выглядеть так:

Методы и алгоритмы построения элементов систем статистического моделирования(13а)

К уравнениям (8.13а) можно дополнительно добавить условие нормировки:

Методы и алгоритмы построения элементов систем статистического моделирования(14)

Тогда любое из уравнений в (8.14) можно исключить.

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

Методы и алгоритмы построения элементов систем статистического моделирования(15)

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

Методы и алгоритмы построения элементов систем статистического моделирования(16)

где

Методы и алгоритмы построения элементов систем статистического моделирования - фундаментальная матрица (15);

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

D - диагональная матрица с диагональными элементами, Методы и алгоритмы построения элементов систем статистического моделирования;

Е - матрица, все элементы которой равны единице.

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

Методы и алгоритмы построения элементов систем статистического моделирования(17)

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

4.3. Управляемые марковские цепи

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

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

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

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

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

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

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

Стратегией p называется последовательность решений:

Методы и алгоритмы построения элементов систем статистического моделирования(18)

где

Методы и алгоритмы построения элементов систем статистического моделирования- вектор управления.

Задание стратегии означает полное описание конкретных решений, принимаемых на всех шагах процесса в зависимости от состояния, в котором находится в этот момент процесс.

Если в последовательности (векторе) p все Методы и алгоритмы построения элементов систем статистического моделирования одинаковы, то такая стратегия называется стационарной, т.е. не зависящей от номера шага. Стратегия Методы и алгоритмы построения элементов систем статистического моделирования называется марковской, если решение Методы и алгоритмы построения элементов систем статистического моделирования, принимаемое в каждом конкретном состоянии, зависит только от момента времени n, но не зависит от предшествующих состояний.

Оптимальной будет такая стратегия, которая максимизирует полный ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода определения оптимальных стратегий: рекуррентный и итерационный.

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

Методы и алгоритмы построения элементов систем статистического моделирования (19)

где

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

Методы и алгоритмы построения элементов систем статистического моделирования шагов, если система находится в состоянии i;

Методы и алгоритмы построения элементов систем статистического моделирования - непосредственно ожидаемый доход, т.е. доход на одном шаге, если процесс начался с i-го состояния;

Методы и алгоритмы построения элементов систем статистического моделирования - величина полного ожидаемого дохода за n прошедших шагов, если процесс начинался с j-го состояния (i¹ j).

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

Конкретное применение метода будет рассмотрено далее на примере.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: