|
Реферат: Методы и алгоритмы построения элементов систем статистического моделирования (Математика)
Факультет повешения квалификации преподавателей
при КГТУ им. А.Н. Туполева
Направление : Электроника и вычислительная техника
Секция : Моделирование
Выпускная работа
« Методы и алгоритмы построения элементов систем
статистического моделирования»
Выполнил : аспирант Аджели М. А.
Руководитель : профессор Захаров В. М.
Оценка : _______________
Подпись : _______________
Казань, 1999г.
Содержание
Введение
1. Метод статистического моделирования систем
2. Моделирование случайных величин и процессов
3. Основные понятия марковских процессов
4. Математический аппарат дискретных марковских цепей
Введение
В настоящее время нельзя назвать область человеческой деятельности, в
которой в той или иной степени не использовались бы методы моделирования.
Особенно это относится к сфере управления различными системами, где
основными являются процессы принятия решений на основе получаемой
информации.
Метод моделирования широко применяют в таких областях, как
автоматизация проектирования и организации в автоматизированных системах
научных исследований, в системах исследования и проектирования, в системах
массового обслуживания, анализ различных сторон деятельности человека,
автоматизированное управление производственными и другими процессами. Важно
подчеркнуть, что моделирование используется при проектировании, создании,
внедрении, эксплуатации систем, а также на различных уровнях их изучения,
начиная от анализа работы элементов и кончая исследованием системы в целом
при их взаимодействии с окружающей средой.
1. Метод статистического моделирования систем
На этапе исследования и проектирования систем при построении и
реализации машинных моделей (аналитических и имитационных) широко
используется метод статистического моделирования (Монте-Карло), который
базируется на использовании случайных чисел, т.е. возможных значений
некоторой случайной величины с заданным распределением вероятностей.
Статистическое моделирование представляет собой метод получения с помощью
ЭВМ статистических данных о процессах, происходящих в моделируемой системе.
Для получения представляющих интерес оценки характеристик моделируемой
системы S с учетом воздействий внешней среды Е статистические данные
обрабатываются и классифицируются с использованием методов математической
статистики,
Сущность метода статистического моделирования сводится к построению
для процесса функционирования исследуемой системы S некоторого
моделирующего алгоритма, имитирующего поведение и взаимодействие элементов
системы с учетом случайных входных воздействий и воздействий внешней среды
Е, и реализации этого алгоритма с использованием программно-технических
средств ЭВМ.
Различают две области применения метода статистического моделирования:
- для изучения стохастических систем;
- для решения детерминированных задач.
Основной идеей, которая используется для решения детерминированных
задач методом статистического моделирования, является замена
детерминированной задачи эквивалентной схемой некоторой стохастической
системы, выходные характеристики последней совпадают с результатом решения
детерминированной задачи. При такой замене погрешность уменьшается с
увеличением числа испытаний (реализации моделирующего алгоритма) N.
В результате статистического моделирования системы S получается серия
частных значений искомых величин или функций, статистическая обработка
которых позволяет получить сведения о поведении реального объекта или
процесса в произвольные моменты времени. Если количество реализации N
достаточно велико, то полученные результаты моделирования системы
приобретают статистическую устойчивость и с достаточной точностью могут
быть приняты в качестве оценок искомых характеристик процесса
функционирования системы S.
При статистическом моделировании систем одним из основных вопросов
является учет стохастических воздействий. Количество случайных чисел,
используемых для получения статистически устойчивой оценки характеристики
процесса функционирования системы S при реализации моделирующего алгоритма
на ЭВМ, колеблется в достаточно широких пределах в зависимости от класса
объекта моделирования, вида оцениваемых характеристик, необходимой точности
и достоверности результатов моделирования. Для метода статистического
моделирования на ЭВМ характерно, что большое число операций, а
соответственно большая доля машинного времени расходуются на действия со
случайными числами. Кроме того, результаты статистического моделирования
существенно зависят от качества исходных (базовых) последовательностей
случайных чисел. Поэтому наличие простых и экономичных способов
формирования последовательностей случайных чисел требуемого качества во
многом определяет возможность практического использования машинного
моделирования системы.
Понятие «статистическое моделирование» тесно связано с понятием «метод
Монте-Карло» и почти ему тождественно.
Для решения задач методом Монте-Карло необходимо получать на ЭВМ
последовательность выборочных значений случайной величины с заданным
распределением. Такой процесс принято называть моделированием случайной
величины. Случайные величины обычно моделируют с помощью преобразований
одного или нескольких независимых значений случайной величины а, равномерно
распределенной в интервале (0,1). Независимые случайные величины,
равномерно распределенные в интервале (0,1).
Можно выделить следующие этапы моделирования случайных величин:
. генерирование N реализации случайной величины с требуемой функцией
распределения;
. преобразование полученной величины, определяемой математической моделью;
. статистическая обработка реализации.
Особенностью первого этапа является то, что все методы для получения
заданного распределения используют преобразование равномерно распределенной
величины.
Конструктивно задаются случайная величина, равномерно распределенная в
интервале (0,1), [pic](0,l), далее производится отображение [pic] [pic] и
получается новая случайная величина [pic] с распределением, определяемым
решаемой задачей, в общем случае [pic] может быть довольно сложным.
Далее следует получение некоторых характеристик. При параметрических
оценках вычисляется некоторая функция [pic]. При непараметрическом задании
функций распределения обычно вычисляются плотности или функции
распределения. Чаще всего находят оценки математической ожидания.
Погрешность оценки определяется дисперсией (если она известна) по числу
экспериментов N.
В результате можно выделить следующие этапы (рис. 4.1):
- подготовка исходных данных (блок 1),
- генерирование равномерно распределенных случайных чисел (блок 2),
- преобразования для получения заданного закона распределения (блок 3);
- выполнение дополнительных преобразований в соответствии с проблем ной
областью (блок 4);
- статистическая обработка (блок 5).
Рис. 4.1. Технологический процесс в Монте-Карло системах
где:
- ПИД - подготовка исходных данных,
- ГРРСЧ - генерирование равномерно распределенных случайных чисел;
- ГПЗ - генерирование произвольного (заданного) закона распределения;
- ДПр - дополнительные преобразования;
- СО - статистическая обработка.
Имитационные системы имеют следующие функциональные блоки:
- имитации входных процессов;
- имитации правил переработки входной информации исследуемой системы;
- накопления информации в результате моделирования;
- анализа накопленной информации;
- управления имитирующей системы.
Традиционный подход использует все классы задач, что и в методе Монте-
Карло. Рассмотрим подробнее аналитический подход задания экзогенных
переменных (первый случай). Они являются выходными другой подсистемы
макросистемы и сами представляют собой макромодель. В рассматриваемом
случае характеристики заданы аналитически.
Информационно технологическая блок-схема представлена на рис. 4.2.
Рис. 4.2. Технологический процесс имитационной системы
ГСП - генерирование случайных (входных) процессов;
ИС - имитационная система.
На первом этапе находят наиболее подходящие методы и алгоритмы для
описания аналитических функций распределения и проводят вычисления (блок 1)
для определения исходных данных, например, при аппроксимационных методах -
координаты узлов, коэффициентов и т.п.
Во втором и третьем блоках производится генерирование случайных чисел
с равномерным распределением (, и экзогенных случайных процессов (.
Блок 4 имитирует работу исследуемой системы, результаты его работы
накапливаются для последующей статистической обработки. В последнем, пятом,
блоке осуществляется статистическая обработка.
При моделировании систем на ЭВМ программная имитация случайных
воздействий любой сложности сводится к генерированию некоторых стандартных
(базовых) процессов и к их последующему функциональному преобразованию. В
качестве базового может быть принят любой удобный в случае моделирования
конкретной системы S процесс (например, пуассоновский поток при
моделировании Q-схемы). Однако при дискретном моделировании базовым
процессом является последовательность чисел [pic], представляющих собой
реализации независимых, равномерно распределенных на интервале (0,1)
случайных величин [pic] или – в статистических терминах- повторную выборку
из равномерно распределенной на (0,1) генеральной совокупности значений
величины (.
Непрерывная случайная величина ( имеет равномерное распределение в
интервале (а,b), если ее функция плотности (рис. 4.3,а) и распределение
(рис. 4.3,6) соответственно примут вид:
Рис. 4.3. Равномерное распределение случайной величины
[pic]
2. Моделирование случайных величин и процессов
Под статистическим моделированием понимается воспроизведение с помощью
ЭВМ функционирования вероятностной модели некоторого объекта.
Задачи статистического моделирования состоят в том, чтобы научиться
воспроизводить с помощью ЭВМ поведение таких моделей, например:
- с помощью специальных методов и средств вырабатывать программы
реализации случайных чисел;
- с помощью этих чисел получать реализацию случайных величин или случайных
процессов с более сложными законами распределения;
- с помощью полученных реализации вычислять значения величин,
характеризующих модель, и производить обработку результатов
экспериментов;
Устанавливать связь алгоритмов моделирования с алгоритмами решения
задач вычислительной математики с помощью метода Монте-Карло и строить так
называемые «фиктивные» модели, т.е. модели, не имеющие связи с объектом
моделирования, но удобные в вычислительном отношении и позволяющие
вычислять нужные нам характеристики объекта.
Моделирование случайных процессов строится на основе базовых
распределений случайных величин.
Одним из таких процессов является марковские процессы.
3. Основные понятия марковских процессов
Марковские случайные процессы названы по имени выдающегося русского
математика А.А. Маркова (1856-1922), впервые начавшего изучение
вероятностной связи случайных величин и создавшего теорию, которую можно
назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились
исходной базой общей теории случайных процессов, а также таких важных
прикладных наук, как теория диффузионных процессов, теория надежности,
теория массового обслуживания и т.д. В настоящее время теория марковских
процессов и ее приложения широко применяются в самых различных областях
таких наук, как механика, физика, химия и др.
Благодаря сравнительной простоте и наглядности математического
аппарата, высокой достоверности и точности получаемых решений особое
внимание марковские процессы приобрели у специалистов, занимающихся
исследованием операций и теорией принятия оптимальных решений.
Несмотря на указанную выше простоту и наглядность, практическое
применение теории марковских цепей требует знания некоторых терминов и
основных положений, на которых следует остановиться перед изложением
примеров.
Как указывалось, марковские случайные процессы относятся к частным
случаям случайных процессов (СП). В свою очередь, случайные процессы
основаны на понятии случайной функции (СФ).
Случайной функцией называется функция, значение которой при любом
значении аргумента является случайной величиной (СВ). По- иному, СФ можно
назвать функцию, которая при каждом испытании принимает какой-либо заранее
неизвестный вид.
Такими примерами СФ являются: колебания напряжения в электрической
цепи, скорость движения автомобиля на участке дороги с ограничением
скорости, шероховатость поверхности детали на определенном участке и т.д.
Как правило, считают, что если аргументом СФ является время, то такой
процесс называют случайным. Существует и другое, более близкое к теории
принятия решений, определение СП. При этом под случайным процессом понимают
процесс случайного изменения состояний какой-либо физической или
технической системы по времени или какому-либо другому аргументу.
Нетрудно заметить, что если обозначить состояние [pic] и изобразить
зависимость [pic], то такая зависимость и будет случайной функцией.
СП классифицируются по видам состояний [pic] и аргументу t. При этом
СП могут быть с дискретными или непрерывными состояниями или временем.
Например, любой выборочный контроль продукции будет относиться к СП с
дискретными состояниями ([pic]- годная, [pic]- негодная продукция) и
дискретным временем ([pic], [pic]- времена проверки). С другой стороны,
случай отказа любой машины можно отнести к СП с дискретными состояниями, но
непрерывным временем. Проверки термометра через определенное время будут
относиться к СП с непрерывным состоянием и дискретным временем. В свою
очередь, например, любая осциллограмма будет записью СП с непрерывными
состояниями и временем.
Кроме указанных выше примеров классификации СП существует еще одно
важное свойство. Это свойство описывает вероятностную связь между
состояниями СП. Так, например, если в СП вероятность перехода системы в
каждое последующее состояние зависит только от предыдущего состояния, то
такой процесс называется процессом без последействия (рис.1).
Зависимость [pic] называют переходной вероятностью, часто говорят, что
именно процесс[pic] без последействия обладает марковским свойством,
однако, строго говоря, здесь есть одна неточность. Дело в том, что можно
представить себе СП, в котором вероятностная связь существует не только с
предшествующими, но и более ранними ([pic]) состояниями, т.е.
[pic] (1)
Рис. 1. Схема процесса без последействия
Такие процессы также рассматривались А.А. Марковым, который предложил
называть их в отличие от первого случая (простой цепи) - сложной цепью. В
настоящее время теория таких цепей разработана слабо и обычно применяют так
называемый процесс укрупнения состояний путем математических
преобразований, объединяя предшествующие состояния в одно.
Это обстоятельство должно обязательно учитываться при составлении
математических моделей принятия решений.
Выше мы совершили незаметный терминологический переход от понятия СП к
“марковской цепи”. Теперь эту неясность следует устранить. Отметим, во-
первых, что случайный процесс с дискретными состояниями и временем
называется случайной последовательностью.
Если случайная последовательность обладает марковским свойством, то
она называется цепью Маркова.
С другой стороны, если в случайном процессе состояния дискретны, время
непрерывно и свойство последействия сохраняется, то такой случайный процесс
называется марковским процессом с непрерывным временем.
Марковский СП называется однородным, если переходные вероятности
[pic] остаются постоянными в ходе процесса.
Цепь Маркова считается заданной, если заданы два условия.
1. Имеется совокупность переходных вероятностей в виде матрицы:
[pic]. (2)
2. Имеется вектор начальных вероятностей
[pic], ….. (3)
описывающий начальное состояние системы.
Матрица (2) называется переходной матрицей (матрицей перехода).
Элементами матрицы являются вероятности перехода из i-го в j-е состояние
за один шаг процесса. Переходная матрица (2) обладает следующими
свойствами:
a) [pic],
(3a)
б) [pic].
Матрица, обладающая свойством (3a), называется стохастической. Кроме
матричной формы модель марковской цепи может быть представлена в виде
ориентированного взвешенного графа (рис. 2).
Рис. 2. Ориентированный взвешенный граф
Вершины графа обозначают состояние [pic], а дуги- переходные
вероятности.
Множество состояний системы марковской цепи, определенным образом
классифицируется с учетом дальнейшего поведения системы.
1. Невозвратное множество (рис. 3).
Рис. 3. Невозвратное множество
В случае невозвратного множества возможны любые переходы внутри этого
множества. Система может покинуть это множество, но не может вернуться в
него.
2. Возвратное множество (рис. 4).
Рис. 4. Возвратное множество
В этом случае также возможны любые переходы внутри множества. Система
может войти в это множество, но не может покинуть его.
3. Эргодическое множество (рис. 5).
Рис. 5. Эргодическое множество
В случае эргодического множества возможны любые переходы внутри
множества, но исключены переходы из множества и в него.
4. Поглощающее множество (рис. 6)
Рис. 6. Поглощающее множество
При попадании системы в это множество процесс заканчивается.
Кроме описанной выше классификации множеств различают состояния
системы:
а) существенное состояние (рис.7): возможны переходы из [pic] в [pic]
и обратно.
Рис. 7. Существенное состояние
б) несущественное состояние (рис. 8): возможен переход из [pic] в
[pic], но невозможен обратный.
Рис. 8. Несущественное состояние
В некоторых случаях, несмотря на случайность процесса, имеется
возможность до определенной степени управлять законами распределения или
параметрами переходных вероятностей. Такие марковские цепи называются
управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ)
особенно эффективным становится процесс принятия решений, о чем будет
сказано впоследствии.
Основным признаком дискретной марковской цепи (ДМЦ) является
детерминированность временных интервалов между отдельными шагами (этапами)
процесса. Однако часто в реальных процессах это свойство не соблюдается и
интервалы оказываются случайными с каким-либо законом распределения, хотя
марковость процесса сохраняется. Такие случайные последовательности
называются полумарковскими.
Кроме того, с учетом наличия и отсутствия тех или иных, упомянутых
выше, множеств состояний марковские цепи могут быть поглощающими, если
имеется хотя бы одно поглощающее состояние, или эргодическими, если
переходные вероятности образуют эргодическое множество.
В свою очередь, эргодические цепи могут быть регулярными или
циклическими. Циклические цепи отличаются от регулярных тем, что в процессе
переходов через определенное количество шагов (циклов) происходит возврат в
какое-либо состояние. Регулярные цепи этим свойством не обладают. Если
просуммировать все вышесказанные определения, то можно дать следующую
классификацию марковских процессов (рис. 9):
Рис. 9. Классификация марковских процессов
4. Математический аппарат дискретных марковских цепей
В дальнейшем рассматриваются простые однородные марковские цепи с
дискретным временем. Основным математическим соотношением для ДМЦ является
уравнение, с помощью которого определяется состояние системы на любом ее k-
м шаге. Это уравнение имеет вид:
[pic] (4)
и называется уравнением Колмогорова-Чепмена.
Уравнение Колмогорова-Чепмена относится к классу рекуррентных
соотношений, позволяющих вычислить вероятность состояний марковского
случайного процесса на любом шаге (этапе) при наличии информации о
предшествующих состояниях.
Дальнейшие математические соотношения зависят от конкретного вида
марковской цепи.
2.1. Поглощающие марковские цепи
Как указывалось выше, у поглощающих ДМЦ имеется множество, состоящее
из одного или нескольких поглощающих состояний.
Для примера рассмотрим переходную матрицу, описывающую переходы в
системе, имеющей 4 возможных состояния, два из которых являются
поглощающими. Матрица перехода такой цепи будет иметь вид:
[pic] (5)
Практически важным является вопрос о том, сколько шагов сможет пройти
система до остановки процесса, то есть поглощения в том или ином состоянии.
Для получения дальнейших соотношений путем переименования состояний матрицу
(8.5) переводят к блочной форме:
[pic] (6)
[pic]
Такая форма позволяет представить матрицу (6) в каноническом виде:
[pic] (6а)
где [pic] - единичная матрица;
[pic] - нулевая матрица;
[pic] - матрица, описывающая переходы в системе из невозвратного
множества состояний в поглощающее множество;
[pic] - матрица, описывающая внутренние переходы в системе в
невозвратном множестве состояний.
На основании канонической формы (6а) получена матрица, называемая
фундаментальной:
[pic] (7)
В матрице (7) символ (-1) означает операцию обращения, то есть
[pic] (8)
После соответствующих преобразований матрица (7) примет вид:
[pic] (7а)
Каждый элемент матрицы (7а) соответствует среднему числу раз попадания
системы в то или иное состояние до остановки процесса (поглощения).
Если необходимо получить общее среднее количество раз попадания
системы в то или иное состояние до поглощения, то фундаментальную матрицу
М необходимо умножить справа на вектор-столбец, элементами которого будут
единицы, то есть
[pic] (8а)
где [pic].
Для иллюстрации приведем конкретный числовой пример: пусть известны
значения переходных вероятностей матрицы [pic] с одним поглощающим
состоянием: [pic]; [pic]; [pic]; [pic]; [pic]; [pic]; [pic]; [pic].
Переходная матрица в блочной системе будет выглядеть так:
[pic]
В данном случае
[pic]; [pic]; [pic] ; [pic]
Проделаем необходимые вычисления:
[pic];
[pic];
[pic] .
В данном случае компоненты вектора [pic] означают, что если процесс
начинается с состояния [pic], то общее среднее число шагов процесса до
поглощения будет равно 3,34 и, соответственно, если процесс начинается с
состояния [pic], то - 2,26.
В конкретных задачах, конечно, более информативным результатом будет
не количество шагов, а какие-либо временные или экономические показатели.
Этот результат легко получить, если связать пребывание в каждом состоянии с
соответствующими характеристиками. Очевидно, набор этих характеристик
составит вектор, на который нужно умножить [pic] слева.
Так, если задать в нашем примере время пребывания в состоянии
[pic] [pic], а в состоянии [pic]- [pic], то общее время до поглощения будет
равно:
[pic]
В случаях, когда марковская цепь включает несколько поглощающих
состояний, возникают такие вопросы: в какое из поглощающих состояний цепь
попадет раньше (или позже); в каких из них процесс будет останавливаться
чаще, а в каких - реже? Оказывается, ответ на эти вопросы легко
получить, если снова воспользоваться фундаментальной матрицей.
Обозначим через [pic] вероятность того, что процесс завершится в
некотором поглощающем состоянии [pic] при условии, что начальным было
состояние [pic]. Множество состояний [pic] снова образует матрицу, строки
которой соответствуют невозвратным состояниям, а столбцы - всем поглощающим
состояниям. В теории ДМЦ доказывается, что матрица В определяется следующим
образом:
[pic] (8.9)
где
М - фундаментальная матрица с размерностью S;
R - блок фундаментальной матрицы с размерностью r.
Рассмотрим конкретный пример системы с четырьмя состояниями [pic],
два из которых- [pic]- поглощающие, а два - [pic]- невозвратные (рис.10):
Рис. 8.10. Система с четырьмя состояниями
Для наглядности и простоты вычислений обозначим переходные вероятности
следующим образом:
[pic]; [pic]; [pic]
Остальные значения вероятностей будут нулевыми. Каноническая форма
матрицы перехода в этом случае будет выглядеть так:
[pic]
Фундаментальная матрица после вычислений примет вид:
[pic]
Тогда, согласно формуле (9), матрица вероятностей поглощения
вычисляется так:
[pic].
Поясним вероятностный смысл полученной матрицы с помощью конкретных
чисел. Пусть[pic], а[pic]. Тогда после подстановки полученных значений в
матрицу [pic]получим:
[pic]
Таким образом, если процесс начался в [pic], то вероятность попадания
его в [pic] равна [pic], а в [pic] - [pic]. Отметим одно интересное
обстоятельство: несмотря на то, что, казалось бы, левое поглощающее
состояние (“левая яма”) находится рядом с [pic], но вероятность попадания
в нее почти в два раза меньше, чем в “удаленную яму” - [pic]. Этот
интересный факт подмечен в теории ДМЦ, и объясняется он тем, что [pic], то
есть процесс имеет как бы “правый уклон”. Рассмотренная выше модель
называется в теории ДМЦ моделью случайного блуждания. Такими моделями часто
объясняются многие физические и технические явления и даже поведение
игроков во время различных игр.
В частности, в рассмотренном примере объясняется тот факт, что более
сильный игрок может дать заранее значительное преимущество (“фору”) слабому
противнику и все равно его шансы на выигрыш будут более предпочтительными.
Кроме указанных выше средних характеристик вероятностного процесса с
помощью фундаментальной матрицы можно вычислить моменты и более высоких
порядков. В частности, дисперсия числа пребывания в том или ином состоянии
- D определяется с помощью следующей матрицы:
[pic] (10)
где
[pic] - диагональная матрица, т.е. матрица, полученная из М путем
оставления в ней лишь диагональных элементов и замены остальных элементов
нулями. Например, приведенная выше матрица (7а) будет иметь вид:
[pic]
В свою очередь, матрица М представляет собой матрицу, полученную из М
путем возведения в квадрат каждого ее элемента, то есть для (7а) будем
иметь:
[pic]
Аналогичным образом определяема и дисперсия для общего количества раз
пребывания в том или ином состоянии [pic]. Обозначим ее [pic]:
[pic] (11)
2.2. Эргодические цепи
Как указывалось выше под эргодической ДМЦ понимается цепь, не имеющая
невозвратных состояний. Таким образом, в такой цепи возможны любые переходы
между состояниями. Напомним, что эргодические цепи могут быть регулярными и
циклическими. Ранее определение таких цепей было дано.
Поскольку согласно данному выше определению в эргодической ДМЦ на
любом шаге должны быть возможными любые переходы, то очевидно при этом, что
переходные вероятности не должны равняться нулю. Оказывается, из этого
условия вытекают некоторые замечательные свойства регулярных ДМЦ:
1. Степени [pic] при [pic] стремятся к стохастической матрице [pic].
2. Каждая строка матрицы [pic] представляет один и тот же вероятностный
вектор
[pic] (12)
все компоненты которого положительны.
Вектор (12) в теории ДМЦ занимает особое место из-за наличия многих
приложений и называется вектором предельных или финальных вероятностей
(иногда - стационарным вектором). Финальные вероятности определяют с
помощью векторно-матричного уравнения
[pic] (13)
которое в развернутом виде будет выглядеть так:
[pic] (13а)
К уравнениям (8.13а) можно дополнительно добавить условие нормировки:
[pic] (14)
Тогда любое из уравнений в (8.14) можно исключить.
Так же, как и в случае поглощения ДМЦ многие характеристики
эргодических цепей определяются с помощью фундаментальной матрицы, которая
в этом случае будет иметь вид:
[pic] (15)
Для эргодических цепей характеристикой, имеющей важное практическое
значение, является продолжительность времени, за которое процесс из
состояния [pic] впервые попадает в [pic], так называемое время первого
достижения. Матрица средних времен достижения определяется по формуле:
[pic] (16)
где
[pic] - фундаментальная матрица (15);
[pic] - диагональная матрица, образованная из фундаментальной заменой
всех элементов, кроме диагональных, нулями;
D - диагональная матрица с диагональными элементами, [pic];
Е - матрица, все элементы которой равны единице.
Матрица дисперсий времени первого достижения имеет несколько более
сложный вид:
[pic] (17)
где кроме уже упомянутых обозначений встречается новое - ([pic],
обозначающее диагональную матрицу, полученную из матричного произведения
матриц [pic].
2.3. Управляемые марковские цепи
Как указывалось выше, под управляемыми марковскими процессами понимают
такие, у которых имеется возможность до определенной степени управлять
значениями переходных вероятностей. В качестве примеров таких процессов
можно привести любые торговые операции, у которых вероятность сбыта и
получения эффекта может зависеть от рекламы, мероприятий по улучшению
качества, выбора покупателя или рынка сбыта и т.д.
Очевидно, что при создании математических моделей в данном случае
должны фигурировать следующие компоненты:
- конечное множество решений (альтернатив) [pic], где [pic] - номер
состояния системы;
- матрицы переходов [pic]соответствующие тому или иному принятому k-му
решению;
- матрицы доходов (расходов) [pic], также отражающие эффективность
данного решения.
Управляемой цепью Маркова (УЦМ) называется случайный процесс,
обладающий марковским свойством и включающий в качестве элемента
математической модели конструкцию (кортеж) [pic]. Решение, принимаемое в
каждый конкретный момент (шаг процесса), назовем частным управлением.
Таким образом, процесс функционирования системы, описываемой УЦМ,
выглядит следующим образом:
- если система находится в состоянии [pic] и принимается решение [pic],
то она получает доход [pic];
- состояние системы в последующий момент времени (шаг) определяется
вероятностью [pic], то есть существует вероятность того, что система
из состояния [pic] перейдет в состояние [pic], если выбрано решение
[pic].
Очевидно, общий доход за n шагов является случайной величиной,
зависящей от начального состояния и качества принимаемых в течение хода
процесса решений, причем это качество оценивается величиной среднего
суммарного дохода (при конечном времени) или среднего дохода за единицу
времени (при бесконечном времени).
Стратегией ( называется последовательность решений:
[pic] (18)
где
[pic]- вектор управления.
Задание стратегии означает полное описание конкретных решений,
принимаемых на всех шагах процесса в зависимости от состояния, в котором
находится в этот момент процесс.
Если в последовательности (векторе) ( все [pic] одинаковы, то такая
стратегия называется стационарной, т.е. не зависящей от номера шага.
Стратегия [pic] называется марковской, если решение [pic], принимаемое в
каждом конкретном состоянии, зависит только от момента времени n, но не
зависит от предшествующих состояний.
Оптимальной будет такая стратегия, которая максимизирует полный
ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода
определения оптимальных стратегий: рекуррентный и итерационный.
Первый, рекуррентный, метод применяется чаще всего при сравнительно
небольшом числе шагов n. Его идея основана на применении принципа
Беллмана и заключается в последовательной оптимизации дохода на каждом шаге
с использованием рекуррентного уравнения следующего вида:
[pic] (19)
где
[pic] - полный ожидаемый доход;
[pic] шагов, если система находится в состоянии i;
[pic] - непосредственно ожидаемый доход, т.е. доход на одном
шаге, если процесс начался с i-го состояния;
[pic] - величина полного ожидаемого дохода за n прошедших шагов,
если процесс начинался с j-го состояния (i(j).
Таким образом, данный метод, по существу, аналогичен методу
динамического программирования, отличием является лишь то, что на каждом
шаге учитывается вероятность попадания системы в то или иное состояние.
Поэтому этот метод называют стохастическим динамическим программированием.
Конкретное применение метода будет рассмотрено далее на примере.
Второй - итерационный метод оптимизации применяется при неограниченном
числе этапов (шагов) процесса. Этот метод использует свойство эргодичности
марковской цепи и заключается в последовательном уточнении решения путем
повторных расчетов (итераций). При этих уточнениях находят решение,
обеспечивающее в среднем минимум дохода при большом числе шагов. Оно уже не
будет зависеть от того, на каком шаге производится оценка оптимальной
стратегии, то есть является справедливым для всего процесса, независимо от
номера шага. Важным достоинством метода является, кроме того, и то, что он
дает возможность определить момент прекращения дальнейших уточнений.
Главное отличие итерационного метода от рассмотренного ранее,
рекуррентного, заключается в том, что в данном случае используется матрица
предельных (финальных) вероятностей, где вследствие свойства эргодичности
переходные вероятности постоянны на всех шагах процесса. Поскольку матрица
доходов состоит также из постоянных, не зависимых от n величин, то можно
предположить, что с ростом n общая величина доходов будет возрастать
линейно.
Представим графически линейную зависимость суммарного дохода от числа
шагов [pic] (рис. 11).
Для наглядности график (см. рис. 11) изображен для УМЦ с двумя
состояниями [pic] и [pic]. На графике прямая [pic] показывает зависимость
суммарного дохода, если система “стартовала” из состояния [pic].
Соответственно, прямая [pic] изображает ту же зависимость для состояния
[pic]. Обе прямые могут быть описаны линейными уравнениями [pic]:
[pic] (20)
где
g - угловой коэффициент прямой [pic];
[pic] - доход в i-том состоянии в конце процесса.
Легко заметить, что при таком представлении зависимости [pic] величина
непосредственно ожидаемого дохода q (см. формулу (19)) заменяется g.
Отличие здесь лишь в том, что g является величиной постоянной для всего
процесса, в то время как q меняется на каждом шаге. Величина [pic]
показывает, на сколько в среднем отличается доход, когда процесс
заканчивается в том или ином состоянии. В теории марковских цепей [pic]
называют весом, так как разница [pic] при двух состояниях показывает
средний выигрыш от того, в каком состоянии мы находимся в конце процесса
(независимо от выбранной стратегии).
Рис. 11. Зависимость суммарного дохода от числа шагов
Таким образом, подводя итоги общих рассуждений, можно сказать, что
свойство эргодичности позволяет нам считать справедливым приближенное
равенство:
[pic] (21)
На этом предположении и основан итерационный метод. Суть его сводится
к тому, что при разных стратегиях путем последовательных приближений
определяются значения сумм
[pic] (22)
Таким образом, если ранее (при рекуррентном методе) искалась
стратегия, обеспечивающая на каждом шаге максимум суммы непосредственно
ожидаемого дохода и дохода на предшествующих шагах, то здесь находится
стратегия, обеспечивающая максимум средней прибыли и относительного веса
сразу для всего процесса. При этом производятся последовательные расчеты -
итерации, на каждом этапе которых уточняются значения угловых коэффициентов
и весов, обеспечивающие максимум доходов.
-----------------------
СО
ДПр
ГПЗ
ГРРСЧ
ПИД
СО
ИС
ГСП
ГРРСЧ
ПИД
f(x)
0
a
b
x
x
b
a
0
F(x)
1/(a-b)
1
a)
b)
Si
Si+1
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
Марковские
процессы
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
с дискретным временем
с непрерывным временем
однородные
неоднородные
управляемые
неуправляемые
марковские цепи
полумарковские цепи
простые
сложные
поглощающие
эргодические
регулярные
циклические
Реферат на тему: Методы и приемы решения задач
1. Дополнительное построение
Продли медиану
Характеристика метода. Довольно часто, когда в условии задачи фигурирует
медиана треугольника, бывает полезным продлить ее за точку, лежащую на
стороне треугольника, на отрезок, равный самой медиане. Полученная новая
точка соединяется с вершиной (вершинами) исходного треугольника, в
результате чего образуются равные треугольники. Равенство соответствующих
элементов этих треугольников помогает найти неизвестную величину или
доказать предложенное утверждение.
Задача. Докажите, что треугольник является равнобедренным, если совпадают
проведенные из одной и той же вершины медиана и биссектриса.
Решение. Рассмотрим треугольник ABC (рис. 1). Пусть отрезок BM – его
медиана и биссектриса. Продлим BM на отрезок MD = BM. Образовались равные
треугольники AMB и MCD (1-й признак равенства треугольников).
Из равенства этих треугольников имеем:
(1) AB = CD и (2) ? 1 = ? 3.
Используя равенство (2) и то, что ? 1 = ? 2 (по условию), получим, что
треугольник BCD равнобедренный, а, следовательно, BC = CD. Используя
полученный вывод и равенство (1) доказываем, что AB = BC, откуда следует
истинность утверждения задачи.
2. Принцип непрерывности
Характеристика метода. Пусть величина k (угол, длина, площадь) зависит от
положения точки X на отрезке (ломаной или другой линии). Если при одном
положении X на отрезке k < 0, а при другом положении X на отрезке k > 0, то
найдется такое положение X на этом отрезке, при котором k = 0.
Задача. В равностороннем треугольнике ABC проведена медиана AA1. Есть ли
такая точка X на AA1, из которой отрезок BC виден под прямым углом.
Решение. Будем искать такое положение точки X, при котором ? BXC = 90°.
Начнем мысленно перемещать точку X по отрезку AA1 от A к A1. Обозначим
величину угла BXC за ?. Когда точка X находится достаточно близко от точки
A (рис. 2), тогда ? мало отличается от 60°, а поэтому ?< 90°. Когда точка X
находится достаточно близко от (рис. 3), тогда ?.
мало отличается от 180°, а поэтому ?> 90°. Значит при каком-то положении
точки X на AA1 ?.
= 90°.
3. Метод доказательства «от противного»
Характеристика метода. Имеем для доказательства утверждения вида A ?B (A –
условие, B – заключение). Суть доказательства данным методом состоит в
следующем:
1) Предполагаем, что заключение B не выполняется.
2) Путем логических рассуждений приходим к тому, что условие A не
выполняется, т. е. получаем противоречие с условием.
3) Дальнейший анализ показывает, что причина полученного противоречия
кроется в первоначальном предположении.
4) Делаем вывод, что это предположение неверно и, следовательно,
заключение B выполняется (что и требовалось доказать).
Задача. Какое наибольшее число острых углов может быть в выпуклом
многоугольнике?
Решение. Легко показать, что три острых угла в многоугольнике может быть
(например, в треугольнике). Все попытки построить какой-нибудь выпуклый n-
угольник с четырьмя острыми углами оказываются тщетными. Возникает
гипотеза: максимальное количество острых углов выпуклого многоугольника –
три. Докажем ее.
1) Пусть найдется выпуклый многоугольник с большим числом углов,
например, с четырьмя.
2) В этом случае сумма четырех острых углов будет меньше, чем 90°•4 или
180°•2. Сумма же остальных n – 4 углов будет меньше, чем 180°•(n – 4).
Тогда сумма всех углов n-угольника меньше, чем 180°•2 + 180°•(n – 4) =
180°•(n – 2), а это невозможно для выпуклого n-угольника (сумма его углов
равна 180°•(n – 2)).
3) Полученное противоречие кроется в исходном предположении.
4) Наше предположение относительно существования четырех (а как
показывает анализ рассуждений и большего количества) острых углов
неверно. Следовательно, максимальное количество острых углов выпуклого n-
угольника – три.
Доказательство выдвинутой гипотезы завершает решение задачи.
4. Метод доказательства «от противного» – 2
Характеристика метода. Имеем для доказательства утверждения вида
A ? B (*)
(A – условие, B – заключение). Идея доказательства опирается на
равносильность теоремы (*) и теоремы противоположной для обратной к данной,
т. е. теоремы
B ? ? (**)
Суть доказательства данным методом состоит в следующем:
1) Составляем теорему вида (**).
2) Доказываем составленную теорему.
3) Основываясь на описанной выше равносильности делаем вывод, что теорема
(утверждение) (*) верна.
Задача. Какое наибольшее число острых углов может быть в выпуклом
многоугольнике?
Решение. Легко показать, что три острых угла в многоугольнике может быть
(например, в треугольнике). Все попытки построить какой-нибудь выпуклый n-
угольник с четырьмя острыми углами оказываются тщетными. Возникает
гипотеза: максимальное количество острых углов выпуклого многоугольника –
три. Докажем ее.
1) Составим теорему, противоположную для обратной к данной: если в
многоугольнике максимальное число острых углов больше трех, то он не
выпуклый.
2) Доказательство: если в многоугольнике острых углов больше трех, то
количество тупых углов, смежных к ним (и взятых по одному при вершине)
будет так же больше трех. В этом случае сумма всех смежных углов, взятых
по одному при вершине, для данного многоугольника будет больше 360°.
Известно, что у выпуклого многоугольника данная сумма равна 360°, поэтому
данный многоугольник – не выпуклый.
3) Доказав утверждение, сформулированное в пункте 1), мы тем самым
доказали и нашу гипотезу.
5. Метод доказательства через контрпример
Характеристика метода. Данный метод применяется в ситуации, когда надо
показать ложность утверждения вида
A ? B. (*)
В этом случае создается (строится) объект (фигура, формула), который
обладает свойствами, входящими в условие A, но не обладает свойствами,
присутствующими в заключении B. Существование такого объекта показывает
ложность утверждения (*).
Конечно, редко встречаются задачи, где явно требуется доказать ложность
некоторого утверждения, но иногда, например после выдвижения гипотезы,
легче попытаться опровергнуть ее через контрпример, а потом, в случае
неудачи, начать доказывать, чем сразу приступать к доказательству.
Задача. Справедливо ли утверждение: если диагонали четырехугольника
перпендикулярны, то это ромб?
Решение. Построим контрпример. На рис. 4 изображен четырехугольник,
диагонали которого перпендикулярны, но который не является ромбом.
Существование такого объекта доказывает ложность исходного утверждения.
6. Метод вспомогательных фигур
Bспомогательный треугольник
Характеристика метода. При помощи некоторого дополнительного построения
(продление отрезка, геометрическое преобразование и др.) получают
треугольник, который дает возможность получить решение задачи. Обычно такой
треугольник обладает двумя важными для решения задачи свойствами:
1) его элементы некоторым образом связаны с элементами, фигурирующими в
условии задачи;
2) для его элементов легче найти характеристики, позволяющие получить
решение, чем для фигур непосредственно заданных условием.
Задача. Доказать, что средние линии треугольника параллельны его сторонам и
вдвое меньше их.
Решение. Пусть точки K, L, M – середины сторон AB, BC, CA треугольника ABC
соответственно (рис. 5). Продолжим отрезок KL за точку L на отрезок NL = KL
и получим вспомогательный треугольник NLC. Тогда D KBL = D NLC (по двум
сторонам и углу между ними). Поэтому BK = CN и ?B = ?4. Следовательно, AK =
CN (так как AK = KB и KB = CN) и AK || CN (так как ? B = ?4). Поскольку AK
= CN и AK || CN, то KN = AC и KN || AC. Поэтому ?3 = ?A, ?1 = ?C и KL =
0,5AC. Значит, углы треугольника KBL равны углам треугольника ABC, а
стороны его вдвое меньше сторон треугольника ABC. Это же верно и для
треугольников AKM, MCL, KML, так как они равны треугольнику KBL.
P.S. Кроме описанного метода, при решении данной задачи используется
известное дополнительное построение – продление отрезка на отрезок, равный
самому себе.
7. Метод введения вспомогательного элемента
Вспомогательный отрезок
Характеристика метода. Длину некоторого отрезка рассматриваемой в задаче
фигуры полагают равной, например, x и затем находят искомую величину. При
этом в одних случаях вспомогательная величина в процессе решения задачи
«исчезает» (сокращается), а в других ее нужно определить через данные
условия и поставить в полученное для искомой величины выражение.
Задача. Найдите площадь выпуклого четырехугольника, диагонали которого
перпендикулярны и равны d1 и d2.
Решение. Заметим, что диагонали разбивают четырехугольник на треугольники.
Удобно представить его площадь в виде суммы площадей треугольников ABC и
ACD (рис. 6). При этом площадь каждого из указанных треугольников будем
вычислять по известной формуле
S=1/2Ah
причем в качестве основания каждого треугольника выберем диагональ d1. В
этом случае высоты треугольников будут давать в сумме диагональ d2, а в
отдельности будут неизвестны.
Для использования в решении формулы (*) введем вспомогательный отрезок –
высоту OD треугольника ACD, длину которого обозначим за x. Тогда длина
высоты OB треугольника ABC будет равна (d2 – x). Вычислим теперь площадь
четырехугольника ABCD:
S=1/2d1x + 1/2d1(d2-x)=1/2d1d2
В результате получили правило: площадь выпуклого четырехугольника с взаимно
перпендикулярными диагоналями равна их полупроизведению.
8. Метод площадей
Характеристика метода. Из названия следует, что главным объектом данного
метода является площадь. Для ряда фигур, например для треугольника, площадь
довольно просто выражается через разнообразные комбинации элементов фигуры
(треугольника). Поэтому весьма эффективным оказывается прием, когда
сравниваются различные выражения для площади данной фигуры. В этом случае
возникает уравнение, содержащее известные и искомые элементы фигуры,
разрешая которое мы определяем неизвестное. Здесь и проявляется основная
особенность метода площадей – из геометрической задачи он «делает»
алгебраическую, сводя все к решению уравнения (а иногда системы уравнений).
Само сравнение выражений для площади фигуры может быть различным. Иногда
площадь фигуры представляется в виде суммы площадей ее частей. В других
случаях приравниваются выражения, основанные на различных формулах площади
для одной и той же фигуры, что позволяет получить зависимость между ее
элементами.
Суть метода площадей не ограничивается только описанным выше приемом.
Иногда бывает полезно рассмотреть отношение площадей фигур, одна из которых
(или обе) содержит в себе искомые элементы.
Задача. Найти формулу для площади произвольного треугольника.
Решение. Пуст S – площадь треугольника ABC (рис. 7). Проведем высоту BD и
получим прямоугольные треугольники ABD и CBD. Очевидно, что S = SABD +
SBCD. Воспользуемся теперь известным правилом нахождения площади
прямоугольного треугольника и получим:
Заметим, что данное решение было проведено для остроугольного треугольника.
В случае же тупоугольного треугольника результат не изменится, отличие
будет лишь в исходном соотношении для площади S = SABD – SBCD.
Таким образом, сформулируем правило: площадь произвольного треугольника
равна половине произведения стороны треугольника на высоту, проведенную к
этой стороне.
9. Аналитико – синтетический метод.
Анализ – логический приём, метод исследования, состоящий в том, что
изучаемый объект мысленно (или практически) разбивается на составные
элементы (признаки, свойства, отношения), каждый из которых исследуется в
отдельности как часть расчлененного целого.
Синтез – логический прием, с помощью которого отдельные элементы
соединяются в единое целое (другими словами обратный анализу).
Не следует отделять эти методы друг от друга, так как они составляют
единый аналитико-синтетический метод. Так при решении сложной задачи она с
помощью анализа разбивается на ряд более простых задач, а затем при помощи
синтеза происходит соединение решений этих задач в единое целое.
Пример: (использование анализа при решении иррациональных уравнений)
[pic]-[pic]=[pic]
1) рассмотрим левую часть: [pic] | |
