Метод Монте-Карло

Графы

Собственные значения матрицы

Пусть задана квадратная матрица А. Если существует столбец x¹0 и число l такие, что

А х = lx.

то они называются собственным столбцом (вектором) и собственным значением матрицы А. Тривиальный случай x = 0 отбрасывается сразу (в этом случае равенство выполняется для любого l).

Квадратная матрица второго порядка имеет не больше двух различных собственных значений. У квадратной матрицы n -го порядка не больше n различных собственных значений.

Для планирования комплекса работ некоторого производства можно применять сетевое планирование или метод графов. Сетевое планирование используется в основном для определения наискорейшего времени выполнения всего комплекса работ.

Основными понятиями графа являются работы и события.

Виды работ:

1. выполнение (фактическое) какой – либо работы, четко описанной и, имеющей ответственного исполнителя;

2. ожидание – работа, не требующая материальных затрат, для которой необходимо время;

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

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

Среди всех событий выделяют два, которые являются исходным и завершающим для всего комплекса работ. Любой граф должен быть построен по определенным правилам:

1. в графе должно быть только одно исходное и одно завершающее событие;

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

3. в графе не должно быть «хвостовых событий» (кроме исходного), т.е. не должно быть события, которому не предшествует ни одна работа;

4. в графе не должно быть замкнутых контуров и петель, т.е. путей, соединяющих некоторое событие с ним же самим;

5. любые два события должны быть непосредственно связаны не более чем одной работой;

Путь сетевого графика – любая последовательность прохождения событий от начального события до конечного события. Наибольший по длине из всех путей называется критическим путем. L _кр = max{ L _i }.

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

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

Если событие j имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j находят по формуле:

Поздний срок свершения события i находят по формуле:

Резерв времени R(i) i-ого события определяется как разность между поздним и ранним сроками его свершения:

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

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

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

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

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

В основе общей схемы метода лежит центральная предельная теорема, согласно которой всякую неизвестную величину можно рассматривать как математическое ожидание некоторой случайной величины x, то есть Mx=m, с дисперсией Dx=b².

В силу указанной теоремы имеет место соотношение

где - значения случайной величины x, получаемые в каждом из N испытаний. Это соотношение определяет неизвестное число m и одновременно дает оценку погрешности. Следовательно, с увеличением числа испытаний (реализаций) повышается точность решения.

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

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

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

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

Например, если Dx=0,10 и =0,01, N=4000 реализаций.

Применяя метод Монте-Карло, можно составить прогноз рассматриваемой случайной величины на некоторый промежуток времени, который в 10-20 раз меньше периода времени изучения объекта.

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