Примеры сетевых топологий


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


Проблемы с большим числом состояний и, в частности, проблемы PERT, всегда были первейшими кандидатами для методов Монте-Карло. Как в случае детерминистских схем многие схемы Монте-Карло, представленные в разделе 5, могут быть адаптированы для задач с большим числом состояний. Ради краткости мы коснемся только главных схем моделирования по методу Монте-Карло.

Схемы Монте-Карло для проблем с большим числом состояний имеют дело почти исключительно с проблемой PERT. В частности, предположим, что нужна оценка для, скажем, среднего значения выборки Е[Ф]. Пусть Fe(a)=Pr[XeЈa] для каждого ребра е является cdf для переменной Хе. Значение выборки

для этой случайной переменной получено с помощью выборки
от однородного генератора случайных чисел и установки
(или хе = min{x|Fe(x)іUe} для дискретных распределений). После того как сформирован весь вектор состояния
, с помощью определенного детерминистского алгоритма вычисляется
. Среднее по всем системным значениям выборки равно несмещенной оценке Е[Ф].

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

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


Начало  Назад  Вперед



Книжный магазин