Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса (стр. 2 из 7)
( 
).Если λij не зависит от t, то есть от того, в какой момент начинается Δt, то непрерывная цепь Маркова называется однородной, в противном случае она называется неоднородной.
Однородная цепь Маркова характеризуется тем, что все потоки, переводящие систему из одного состояния в другое, являются простейшими, то есть стационарными пуассоновскими потоками. При этом время непрерывного пребывания цепи в каждом состоянии распределено по экспоненциальному закону.
Для неоднородной цепи промежутки времени между соседними событиями распределены не по показательному закону.
Если непрерывная цепь Маркова является однородной и между любыми её двумя состояниями существует маршрут, то она эргодичная. Кроме того, если вероятности состояний системы pj не зависят от времени наблюдения системы и совпадают с её начальными вероятностями состояний
и стационарными вероятностями, т.е. 
, то режим цепи является стационарным.Отметим, что понятия «стационарность управляющих потоков» и «стационарный режим» совершенно разные и из первого не следует второе. Таким образом, однородная непрерывная цепь Маркова определяется начальным распределением вероятностей
, матрицей интенсивностей [λij] простейших потоков, где λij=pijλi, вектором экспоненциально распределённых времён пребывания в состояниях с параметрами {1/μ1, 1/μ2, …, 1/μn}.Главное отличие полумарковского процесса от цепи Маркова состоит в отказе от требования, чтобы распределения времени пребывания в каждом состоянии подчинялись показательному закону. Обычно полумарковский процесс задаётся начальным распределением вероятностей
, матрицей переходных вероятностей [pij] и совокупностью произвольных функций распределения времени пребывания в состояниях 
.В моменты переходов из одного состояния в другое полумарковский процесс обладает марковским свойством. Если рассматривать полумарковский процесс только в моменты переходов, то получающаяся при этом марковская цепь с дискретным временем называется вложенной марковской цепью (так как она содержится в полумарковском процессе). Вложенная цепь имеет то же пространство состояний S и тот же вектор P(0) начального распределения вероятностей состояний, что и полумарковский процесс, а матрицей переходов вложенной цепи является матрица P=[pij] полумарковского процесса.
Для эргодических полумарковских процессов, как и для эргодических марковских цепей, характерно наличие стационарного режима.
2. Метод Монте-Карло
Различные методы и приборы для определения параметров и характеристик случайных процессов можно объединить в две группы. Первую группу составляют приборы для определения корреляционных функций (корреляторы), спектральных плотностей (спектрометры), математических ожиданий, дисперсий, законов распределения и прочих случайных процессов и величин.
Все приборы первой группы можно разделить на две подгруппы. Одни определяют характеристики записанных случайных сигналов за достаточно большое время, намного превышающее время реализации самого случайного процесса. Другие (они в последнее время вызывают наибольший интерес) позволяют получать характеристики случайного процесса оперативно, в такт с поступлением информации при натурных испытаниях новых систем управления, так как, пользуясь их показаниями, можно непосредственно изменять процесс управления и в ходе эксперимента наблюдать за результатами этих изменений.
Вторая группа содержит методы и приборы, предназначенные для исследования случайных процессов и главным образом систем управления, в которых присутствуют случайные сигналы, на универсальных цифровых и аналоговых вычислительных машинах. Иногда для таких исследований приходится создавать специализированные вычислительные машины цифрового, аналогового или чаще всего аналого-цифрового (гибридного) типа, так как существующие типовые машины не приспособлены для решения некоторых задач.
Широко применяется на практике метод Монте-Карло (метод статических испытаний). Его основная идея чрезвычайно проста и заключается по существу в математическом моделировании на вычислительной машине тех случайных процессов и преобразований с ними, которые имеют место в реальной системе управления. Этот метод в основном реализуется на цифровых и, реже, на аналоговых вычислительных машинах.
Можно утверждать, что метод Монте-Карло остаётся чистым методом моделирования случайных процессов, чистым математическим экспериментом, в известном смысле лишённым ограничений, свойственным другим методам. Рассмотрим данный метод применительно к решению различных задач управления.
2.1 Общая характеристика метода Монте-Карло
Как уже указывалось, идея метода Монте-Карло (или метода статистического моделирования) очень проста и заключается в том, что в вычислительной машине создаётся процесс преобразования цифровых данных, аналогичный реальному процессу. Вероятностные характеристики обоих процессов (реального и смоделированного) совпадают с какой-то точностью.
Допустим, необходимо вычислить математическое ожидание случайной величины X, подчиняющейся некоторому закону распределения F(x). Для этого в машине реализуют датчик случайных чисел, имеющий данное распределение F(x), и по формуле, которую легко запрограммировать, определяют оценку математического ожидания:
.Каждое значение случайной величины xi представляется в машине двоичным числом, которое поступает с выхода датчика случайных чисел на сумматор. Для статистического моделирования рассматриваемой задачи требуется N-кратное повторение решения.
Рассмотрим ещё один пример. Производится десять независимых выстрелов по мишени. Вероятность попадания при одном выстреле задана и равна p. Требуется определить вероятность того, что число попаданий будет чётным, т.е. 0, 2, 4, 6, 8, 10. Вероятность того, что число попаданий будет 2k, равна:
,откуда искомая вероятность
(1)Если эта формула известна, то можно осуществить физический эксперимент, произведя несколько партий выстрелов (по десять в каждой) по реальной мишени. Но проще выполнить математический эксперимент на вычислительной машине следующим образом. Датчик случайных чисел выдаст в цифровом виде значение случайной величины ξ, подчиняющейся равномерному закону распределения в интервале [0,1]. Вероятность неравенства ξ<p равна p, т.е.
P {ξ<p}=p.
Для пояснения целесообразно обратиться к рис. 1, на котором весь набор случайных чисел представляется в виде точек отрезка [0,1]. Вероятность попадания случайной величины ξ, имеющей равномерное распределение в интервале [0,1], в интервал [0, p] (где
) равна длине этого отрезка, т.е. p. Поэтому на каждом такте моделирования полученное число ξ сравнивают с заданной вероятностью p. Если ξ<p, то регистрируется попадание в мишень, в противном случае – промах. Далее проводят серию из десяти тактов и подсчитывают чётное или нечётное число попаданий. При большом числе серий (100–1000) получается вероятность, близкая к той, которая определяется по формуле (1).Различают две области применения метода Монте-Карло. Во-первых, для исследования на вычислительных машинах таких случайных явлений и процессов, как прохождение элементарных ядерных частиц (нейтронов, протонов и пр.) через вещество, системы массового обслуживания (телефонная сеть, система парикмахерских, система ПВО и пр.), надёжность сложных систем, в которых выход из строя элементов и устранения неисправностей являются случайными процессами, статистическое распознавание образов. Это – применение статистического моделирования к изучению так называемых вероятностных систем управления.
Этот метод широко применяется и для исследования дискретных систем управления, когда используются кибернетические модели в виде вероятностного графа (например, сетевое планирование с β-распределением времени выполнением работ) или вероятностного автомата.
Если динамика системы управления описывается дифференциальными или разностными уравнениями (случай детерминированных систем управления) и на систему, например угловую следящую систему радиолокационной станции воздействуют случайные сигналы, то статическое моделирование также позволяет получить необходимые точностные характеристики. В данном случае с успехом применяются как аналоговые, так и цифровые вычислительные машины. Однако, учитывая более широкое применение при статистическом моделировании цифровых машин, рассмотрим в данном разделе вопросы, связанные только с этим типом машин.
Вторая область применения метода Монте-Карло охватывает чисто детерминированные, закономерные задачи, например нахождение значений определённых одномерных и многомерных интегралов. Особенно проявляется преимущество этого метода по сравнению с другими численными методами в случае кратных интегралов.