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


Методики ограничений - часть 3


Рассмотрим любую фиксированную цепочку потоков h1,…,hr, которая корректна для нормального набора пропускных способностей (се: eОE). В стохастической модели конкретная цепочка Гk может, следовательно, дать запрошенную долю потока hk, если и только если все ее ребра находятся в рабочем состоянии, в противном случае выдается нуль. Крайняя вероятность реализации этого равна, следовательно,
. Во-первых, заметим, что значение Е[ФFLOW] очевидно, по крайней мере, также велико, как ожидаемое значение случайного потока, полученного путем допущения потока вдоль каждой цепочки Гk, равного hk, несмотря на рабочие условия других цепочек, использующих те же ребра, что и Гk. Это ожидание в свою очередь равно сумме ожидаемых значений потоков для каждой из цепочек Г1,…,Гr, рассматриваемых как независимые случайные переменные.

Метод группировки ребер и непересекающихся разрезов, обсужденные в разделах 4.2.1 и 4.2.2, предоставляют также эффективный способ расчета ограничений для проблем сетей с большим числом состояний. В частности, пусть Р1,…,Рq и Г1,…,Гr являются наборами разъединенных (s,t)-маршрутов и (s,t)-разрезов, соответственно. Эти два набора дают естественные верхние и нижние границы функций ФL и ФU для действительной функции Ф, зависящей от проблемы:

Кратчайший путь:

Максимальный поток:

Работоспособность сети PERT:

Эти функциональные ограничения в свою очередь дают естественные границы как для cdf, так и для действительной функции Ф, в частности,

и

Далее, каждая функция, описанная выше, состоит из одного min/max и одной свертки, поэтому cdf и ожидания для всех этих функций могут быть вычислены за полиномиальное время.

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




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



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