МС лекции (Лекции), страница 3

3.1. Общая характеристика метода Монте - Карло

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

(4-1)

Каждое значение случайной величины X представляется в машине двоичным числом, которое поступает с выхода датчика случайных чисел на сумматор. Для статистического моделирования рассматриваемой задачи требуется N-кратное повторение решения.

Рассмотрим еще один пример. Производится десять независимых выстрелов по мишени. Вероятность попадания при одном выстреле задана и равна P. Требуется определить вероятность того, что число попаданий будет четным, т.е. 0, 2, 4, 6, 8, 10. Вероятность того, что число попаданий будет 2k, равна:

(4-2)

Откуда искомая вероятность

(4-3)

Если эта формула неизвестна, то можно осуществить физический эксперимент, произведя несколько партий выстрелов (по 10 в каждой) по реальной мишени. Но проще выполнить математический эксперимент на вычислительной машине следующим образом. Датчик случайных чисел выдаст в цифровом виде значение случайной величины , подчиняющейся равномерному закону распределения в интервале [0,1]. Вероятность неравенства равна p, т.е.

Для пояснения целесообразно обратиться к рис. 4-1, на котором весь набор случайных чисел представляется в виде точек отрезка [0,1]. Вероятность попадания случайной величины , имеющей равномерное распределение в интервале [0,1], в интервал [0,P] (где ) равна длине этого отрезка, т.е. P. Поэтому на каждом такте моделирования полученное число сравнивают с заданной вероятностью P. Если , то регистрируется попадание в мишень, в противном случае – промах. Далее проводят серию из десяти тактов и подсчитывают четное или нечетное число попаданий. При большом числе серий (100 – 1000) получается вероятность, близкая к той, которая определяется по формуле (3).

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

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

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

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

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

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

Так, задача распределения n видов ресурсов между отраслями для n > 3 не может быть точно решена на существующих ЭВМ из-за большого объема перебора вариантов. Однако таких задач возникает очень много в кибернетике, например, синтез конечных автоматов. Если искусственно ввести вероятностную модель-аналог, то задача существенно упростится, правда, решение будет приближенным, но его можно получить с помощью современных вычислительных машин за приемлемое время счета.

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

3.2. Получение последовательности случайных чисел

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

Сущность метода Монте-Карло при моделировании случайных чисел состоит в следующем. Необходимо найти значение a некоторой изучаемой величины. С этой целью выбирают такую случайную величину Х, математическое ожидание которой равно a: м[Х] = a.

Практически поступают так: вычисляют (разыгрывают) N возможных значений x_i случайной величины Х, находят их среднее арифметическое (4-1)

и принимают м[Х] в качестве оценки (приближенного значения) a* искомого числа a:

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

Требуется разыграть случайную величину, X т.е. вычислить последовательность ее возможных значений x_i (i = 1,2,…), зная закон распределения Х.

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

надо:

1). Разбить интервал (0,1) оси 0t на n частичных интервалов:

2). Выбрать (из таблицы случайных чисел) случайное число r_j. Если r_j попало в интервал , то разыгрываемая величина приняла возможное значение x_i.

Тема 2. Теория массового обслуживания.

Содержание

Задачи теории массового обслуживания (ТМО). Типы систем массового обслуживания (СМО) в соответствии с классификацией Кендалла. Простейший поток и поток Эрланга.

Процесс обслуживания как марковский процесс. Уравнения Колмогорова. Матрица переходов. Характеристики СМО.

Аналитические модели различных типов СМО, расчет характеристик сети СМО.

Методические указания

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

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

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