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


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


Улучшения выше описанной схемы для проблемы PERT заключается в вычислении для каждой вершины v в графе распределения для промежуточных случайных переменных

Фv= наидлиннейший маршрут до вершины v.

Во всех случаях вычисления производятся в топологическом порядке v1= s,v2,…,vn, т.е. все ребра, указывающие на vi исходят из вершин vj с j<i. Данная схема служит для вычисления нижней границы

для E[Фvi], используя достаточно простую рекурсивную формулу

j = 2,…,n

суммирование производится по всем векторам b= ( bji: j<I) значений параметра, которые могут быть приняты для ребер, указывающих на вершину vi (члены, где (vj,vi) не существуют, игнорируются). Улучшения этой методики первоначально включали в себя оценки cdf значений Fi(a) для Фvi, в частности, вычисление верхней и нижней границы

и
, соответственно. Заметим, что эти величины могут использоваться по очереди, чтобы вычислить нижнюю и верхнюю границы, соответственно для значений E(Фvi), используя элементарную формулу

Все они используют одну и ту же формулу с

для всех неотрицательных a (и нуль в противном случае).

Соответствующие ограничения для Е[Фvi] могут быть также упорядочены и их нижние ограничения лучше, чем полученные Фулкерсоном, нижние ограничения Фулкерсона и Кляйндорфера не могут быть единообразно сравнены. Ограничения Фулкерсона, Кляйндорфера и Шогана могут быть также модифицированы при использовании для проблемы кратчайшего пути (если исходный граф не содержит циклов) и для случая непрерывных параметров ребра. Ограничения Кляйндорфера априори вычисляемы за полиномиальное время.

Здесь мы предполагаем, что случайное значение пропускной способности Се является двоичным с ”рабочим” состоянием, представляющим нормальную пропускную способность се с вероятностью ре, и состоянием отказа, представляющим пропускную способность нуль с вероятностью 1-ре. Пусть Г1,…,Гr является набором всех цепочек (s,t) в G и пусть h1,…,hr равны потоку для каждого r цепочки (s,t). Этот значение потока верно, если для каждого ребра е в G, сумма потоков цепочки последовательных ребер, проходящих через е, меньше чем или равна пропускной способности е, а величина потока равна

.


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



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