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

         

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


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


Кроме того, каждый граф всегда содержит, по крайней мере, один однородно ориентированный (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 и кратчайшего пути так, как это предложено выше.


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