4.1. Постановка задачи

                Заданы узлы связи сети X={x_j}_j=1..n, места размещения узлов связи (УС) распределённой вычислительной сети (РВС) -{d_j,w_j} ; матрица требований в информационном обмене между всеми узлами H=|| h_ij ||_i,j=1..n, набор ПС каналов связи D={d₁,d₂,..,d_k} и их удельных стоимостей С={c₁,c₂,..,c_k} ; надёжностные характеристики каналов связи: g_rs=g₀Vl_rs и h_rs, где g_rs интенсивность отказов в КС (r,s) ; h_rs- интенсивность восстановления.

Необходимо: определить структуру сети E⁰={(r,s)}, и найти ПС всех КС {d_rs⁰}, и распределение потоков в КС {f_rs⁰}, соответствующее матрице требований таким образом, чтобы обеспечить

          min C_S({d_rs})=min _S   C_rs^пер(d_rs, l_rs)         (4.1)

                                  (r,s) Î(E⁰)

при ограничениях на вероятность своевременной доставки

        P_СД=P{T_ср <= t_зад} >= P_зад                       (4.2)

и следующих ограничениях на живучесть сети при отказах:

        P{H_S^Ф =100%H_зад}>=P_0зад          (4.3a)

        P{H_S ^Ф >=90%H_зад}>=P_1зад          (4.3б)

        P{H_S ^Ф >=80%H_зад}>=P_2зад          (4.3в)

        P{H_S ^Ф >=70%H_зад}>=P_3зад           (4.3г)

        P{H_S ^Ф >=50%H_зад}>=P_4зад           (4.3д)

при ограничении на среднее время доставки T_ср <= t_зад.

Кроме того, коэффициент связности структуры сети k_св  должен удовлетворять условию  k_св>=k_зад (k_зад=2).

Основой для предложенного ниже алгоритма являются доказанные раньше свойства максимального потока через сеть и соответствующий алгоритм нахождения максимального потока [20].

При этом

 T_ср= 1/h_SS  f_rs/(d_rs-f_rs)                           (4.4)

                      (r,s) ÎE

а вероятность своевременной доставки (ВСД) определяется соотношением [93]

P_СД=P{T_ср<=t_зад}= _П (d_rsk_гrs-f_rs)/(d_rsk_гrs-f_rs+n_yfrs/h_S )     (4.5)

                              (r,s) Î E

Данная задача синтеза относится к классу NP-полных задач нелинейного дискретного программирования.

Для её решения предлагается декомпозиционный подход (алгоритм), разбивающий исходную задачу на ряд взаимосвязанных этапов.