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

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

Кроме того, каждый граф всегда содержит, по крайней мере, один однородно ориентированный (s,t)-разрез.

Большинство методик Монте-Карло, представленных выше, используется также для проблем наикратчайшего пути и, в общем, не требуют того, чтобы базовый граф не имел циклических структур, как это имеет место во многих методиках ограничения для проблем PERT. Как было показано выше, пусть для еОЕ параметр ребра Xe имеет cdf Fe(x). Предположим, что вы имеете функциональные ограничения ФL и ФU для мультивариантной меры Ф, удовлетворяющей условиям

· ФL(x) Ј Ф(х) Ј ФU(x) для каждого вектора состояния х

· Для любого присвоения

величинам первой компоненты х при k=0,…,m, условная cdf имеет вид

может быть вычислено за полиномиальное время. Пространство Х важности в мультивариантной версии проблемы равно теперь

X={xО{0,1}E:ФL(x)Ј a, Ф>U(x)>a}

а модификация метода розыгрыша, базирующегося на ограничениях, представленная в разделе 5.1 приобретает вид

1. Разыгрывается событие

из пространства Х путем последовательного розыгрыша для k=1,…,m компонент состояния

из cdf

2. Вычисляется доля

тех выборок, для которых Ф(х) Ј a. Число

равно теперь несмещенной оценке R.

Функциональные ограничения на основе группирования ребер или непересекающихся разрезов, описанные в разделе 6.4, также дают хорошие функции ограничения для этого метода, так как условные cdf для этих функций могут быть легко вычислены. Хотя в работах Фишмана и др. эти ограничения используются только для задач максимального потока, как это описано в разделе 6.4, они могут применяться также к проблемам PERT и кратчайшего пути так, как это предложено выше.

Содержание раздела