3. 5. Анализ вероятностно-временных характеристик РВС.
Использование вероятности своевременной доставки вместо ограничения на время доставки, позволяет по новому сформулировать задачи анализа распределённой вычислительной сети. В работах рассматриваются и исследуются три типа наиболее важных задач анализа вероятностно-временных характеристик распределённой вычислительной сети:
1.задача выбора пропускных способностей каналов связи (ВПС);
2.задача выбора маршрутов и распределения потоков в сети (РП);
3.задача ВПС РП, которая является комбинацией вышеуказанных.
Рассмотрим их по порядку.
3.5.1. Задача ВПС для распределённой вычислительной сети
Задана структура сети 
, матрица требований 
и распределение потоков в каналах 
.
Имеем набор каналов связи с различной пропускной способностью 
и известна стоимость единицы длины канала типа 
. Нужно найти такие пропускные способности всех линий связи 
, при которых
(3.7)
при условии:
(3.8)
и очевидном условии
(3.9)
Исследование свойств функции ограничений
Вначале исследуем функцию из (3.7).
1. Доказательство вогнутости функции 
.
Имеем
(3.10)
где 
.
Обозначим 
(3.11)
Тогда 
.
Справедлива следующая теорема.
Если все функции 
-вогнуты по переменным 
, то и функция-произведение 
вогнута по переменным 
.
Докажем сначала вогнутость отдельной функции 
, для этого необходимо вычислить 
.
Обозначим для удобства 
, 
.
Тогда
.
Итак функция 
- вогнута по переменной 
.
Теперь докажем, что произведение вогнутых функций- вогнутая функция. Действительно, вспомним определение вогнутой функции.
Функция 
- вогнута на некотором выпуклом множестве 
, если для произвольной пары точек 
и любого 
выполняется условие
(3.12)
Так как функции f(x)- мультипликативная, то 
. Каждая 
вогнута, т.е. для неё выполняется соотношение типа(3.12), т.е.
(3.13)
так как это соотношение справедливо для всех i, то получаем:
что и требовалось доказать.
Аналогично доказывается, что произведение выпуклых функций выпуклая функция.
Исследуем характер функции 
и докажем, что она также вогнута по переменным 
.
(3.14)
Для этого необходимо и достаточно, чтобы функции 
были вогнуты по переменным 
.
Найдём
Находим вторую производную
и так как 
, то 
поэтому функция 
вогнута по переменной 
и т.д.
3.5.2. Существующие решения задачи ВПС.
Впервые эта задача в постановке
была рассмотрена Клейнроком [33], где предложены методы её решения для некоторых классов функций 
. В частности, если функция 
, то необходимое решение 
можно найти аналитическим методом множителей Лагранжа. используя метод множителей Лагранжа, получаем следующее выражение относительно необходимых пропускных способностей каналов:
(3.15)
При этом минимальная стоимость, которая удовлетворяет ограничению на максимальную задержку
(3.16)
Если функции Crs(mrs) вогнуты, то для отыскания необходимых значений 
можно снова применить метод множителей Лагранжа. Но в этом случае необходимо решить систему нелинейных уравнений, а найти аналитическое решение для величин 
невозможно. Для нахождения оптимального решения задач ВПС, когда 
- дискретные величины, вышеуказанные методы не могут быть использованы и необходима разработка специальных методов дискретной оптимизации.
В данной роботе для решения этой задачи предлагается алгоритм, который использует идеи последовательного анализа вариантов и находит оптимальные пропускные способности для дискретных переменных [93].
3.5.3.Описание алгоритма ВПС
Алгоритм А1 состоит из последовательного применения процедуры отсева по ограничению 
и отсева по значениям целевой функции (процедура 
)
Начальный этап.
Сначала находим диапазон изменения по каждой из переменных:
1. Вместо 
выбираем такое значение, для которого выполняется следующее условие:
(3.17)
Дальше округляем это значение к ближайшему большему целому из ряда 
или расширенного ряда 
, где 
целое, 
.
2. Вместо 
выбираем 
, которое определяется из условия:
(3.18)
Вместо начального верхнего значения пропускной способности канала(r,s) 
можно взять максимально возможное значение ПС из заданного набора dk с учётом максимальной пропускной способности каналов в одной ЛС: 
в случае, если условие (3.18) не выполняется.
Учитывая мультипликативный вид функции 
, необходимым условием выполнения (3.17) является условие:
(3.19)
так как понятно, что
(3.20)
Поэтому, если окажется, что условие (3.19) не выполняется для 
, то необходимо увеличить значение 
.
Потом переходим к 1-ой итерации.
1-я итерация.
Процедура 
.
1. Находим
та 
Приравниваем
2. Выполняем отсев существующих значений 
по условию 
.
Тогда условие отсева значений для переменной имеет вид:
(3.21)
при этом будут отсеяны все значения 
,где 
- это то минимальное значение 
, при котором начнёт выполняться (3.21).
3. Повторяем эту процедуру для всех (r,s), при этом получаем новые верхние границы переменных 
. Если хотя бы для одного множества Mrs mrs(в)(1)<mrs max (т.е. изменилось), переходим к процедуре 
. Иначе на шаг 1 процедуры 
,при этом надо сузить множество вариантов 
путём введения нового ограничения
(3.22)
где 
.
Процедура 
.
Выполняем отсев по ограничению. Отсев происходит в соответствии с условием:
(3.23)
По нему отсеиваются все те значения 
, для которых 
, где 
максимальное значение 
, при котором начинает не выполняться условие (3.23).
Отсев согласно (3.23) проводим для всех каналов связи (r,s). В результате получаем новые множества вариантов Mrs=[mrsmin(1),mrsmax(1)].
Если окажется, что Mrs(1)=Æ, хотя бы для одного (r,s), то переход к 2-ой итерации, при этом расширяем множество вариантов, для этого приравниваем
Последовательность итераций повторяем до тех пор, пока не получим настолько небольшие подмножества Mrs(k) для каждого (r,s) принадлежащего E, что из них можно будет найти оптимальные решения простым перебором, т.е. путём проверки по ограничению и приравнивая значения целевой функции.
Замечания.
Если в процессе итераций необходимо расширить множество после его сужения или наоборот сузить множество вариантов после расширения, то приравниваем
