19.Топологическая декомпозиция структур асу. Алгоритм декомпозиции структуры

Топологическая декомпозиция структур АСУ, проводится с целью выделения в структуре сильносвязанных подсистем. Ориентированный граф G(V) называется сильно связным, если для любых вершин i, j существует путь из вершины i в вершину j.

Опр. Множество вершин, достижимых из вершины i, называется достижимым множеством R(i).

где — множество вершин, достижимых из вершины i с помощью путей длиною λ, n- число ребер

Контрдостижимым множеством Q(i) графа G(V) называется множество таких вершин, когда из любой вершины этого множества можно достигнуть вершину i.

где — множество вершин, из которых можно достигнутьi-тую вершину за λ шагов.

R(i)Q(j) является множеством таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему отi-той вершины кj-той, Эти вершины называются существенными или неотъемлемыми относительно двух кольцевых вершин (i) и (j)

R(i)Q(i) определяет сильно связный подграф графа G(V), содержащий i-тую вершину, поскольку все существенные вершины, принадлежащие множеству , достижимы из i-той вершины и, кроме того, из каждой такой вершины достижима вершина i

Aлгоритм декомпозиции:

1. В исходном графе G(V) производим нумерацию вершин.

2. Для i-той вершины (i= 1) определяем множествоR(l) и множествоQ(l).

3. Находим сильно связный подграф G1 включающий множество вершинV1 =R(l)nQ(l).

4. Все вершины, принадлежащие G1 (V1) удаляются из исходного графаG(V).

5. пункты 2, 3, 4 повторяются для i= 2, 3, 4,... до тех пор, пока все вершины исходного графа не будут сгруппированы в соответствующие сильно связные подграфы.

Пример топологической декомпозиции.Пусть в распределенной АСУ пункты обработки информацией обмениваются данными так, как это изображенонаграфе. Возникла необходимость в сокращении числа этих пунктов, исходя только из структурных свойств анализируемой системы.

Используя соотношение , находим сильно связный подграф, содержащий вершину 1:

После удаления сильно связного подграфа G1 (V1) исходный граф G(V) имеет вид

Полагаем i = 2, но вершина 2 входит в выделенный подграф V1 следовательно, i = 3.

R(3) = (3, 4, 7, 9), Q(3) = (3), V2 = (3). Затем удаляем сильно связный подграф G2(V2)

Полагаем i = 4, тогда R(4) = (4, 7, 9), Q(4) = (4, 7, 8, 9, 10), V3 = (4, 7, 9). Удаляем сильно связный подграф G3(V3)

Полагаем i= 8, тогда R(8) = (8, 10), G(8) = (8, 10), V4 = (8, 10).Итак, окончательно имеем:

Объединяем полученные сильно связанные подграфы в соответствии с исходным графом:

Или окончательно:

22.Модели синтеза структуры асу. Частные задачи синтеза.

При разработке структуры АСУ определяется множество элементов и связи м/у ними,распределяются задачи возлагаемые на них,также выбор технических средств,обеспечивающих своевременное решение задач АСУ.

Определение числа уровней иерархии. Устанавливаются связи м/у уровнями,распред-ся ответственности,выбираются технические средства,организуются информац-ые потоки.

Формализация задачи синтезаструктуры АСУ.

Р-это множ-во возможных принципов организации АСУ

π-множ-во выбранных принципов

F-функции,исполняемые системой(для чего системы строим)

F(π)<Fэто некоторое подмножество функцииF

А-множ-во возможных элементов системы

a<Aмнож-во выбранных элементов

W-оптимальное отображение,которое обеспечивает экстремум некоторой целевой функции

F:f-aвыбрать элементы системы,взаимосвязи м/у ними,так чтобы все функцииfвыполнялись и оптимально.(например с min затратами,за min время)

Частные задачи синтеза

1)min затрат АСУ на релизацию задач(1)

Где i=1,I-решаемые в АСУ задачи

j=1,J-узлы АСУ на которых реш-ся задачи

aij-расходы для решения i задачи на j узле

xij-индикатор

2)min общего времени решения задачи в АСУ(2)

tij-время решения i задачи на j узле

3)min максимального времени решения задач в АСУ

Min(max)

Ограничения:

1)на связи м/у задачами. Задается граф

2)на связи м/у узлами граф

3)на общие затраты ≤B

4)ограничение реализации в узлах где j=

5)ограничение времени ∑ ∑

6)на нагрузку в узлах где-коэф-т загрузки j узла при решении задачи

7)на время решения каждой задачи гдеi=