Формализация разбиения проектируемой АС на модули

3.6.1 Общая постановка задачи

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

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

Модульное проектирование АСУ обладает рядом преимуществ:

— упрощается процесс разработки и отладки программного и информационного обеспечения АСУ;

— упрощается последующая модификация системы, так как модульные программы могут быть улучшены путем простой замены отдельных модулей, которые функционально эквивалентны, но имеют лучшие системные характеристики;

— улучшается организация управляющих программ;

— появляются возможности внедрения передовых методов разработки и автоматизации проектирования АСУ.

Реализация модульного принципа проектирования АСУ предполагает, что каждый модуль обладает следующими качествами:

– функциональность, т.е. модуль должен представлять собой функционально законченную максимально независимую совокупность операций по обработке данных; обращение к модулю осуществляется как к единому целому, и значения вызываемых параметров обычно отражает специфику функций модуля;

– связность, т.е. модуль реализует совокупность взаимосвязанных функций, требующих одних и тех же данных; часть этих данных обычно скрыта для системы в целом;

– алгоритмичность, т.е. функции модуля группируются на алгоритмической основе;

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

– однородность, т.е. в модуле объединяются однородные по своему функциональному назначению процедуры.

Основой для формализованной постановки и решения задач анализа и синтеза модульных АСУ является определение модулей системы и межмодульного интерфейса.

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

Перейдем к формализации.

Пусть А={a₁, a₂, …, a_m} – множество задач, выявленных на предпроектной стадии. Каждое a_i в общем случае характеризуется n – мерным вектором показателей x_i, которыми являются время выполнения, число входных и выходных переменных, требуемый объем памяти и т.д.

Все задачи информационно взаимосвязаны. Это можно задать орграфом Г=(A,D), у которого вершины А={a₁, a₂, …, a_m} – это задачи, а ребра D – информационные связи между задачами (процедурами).

Пусть граф Г задан матрицей смежности ║d_ij║, причем d_ij=1, если существует информационная дуга из задачи a_i в задачу a_j, и d_ij=0 в противном случае. Каждая дуга между элементами a_i и a_j характеризуется некоторым параметром ρ_ij, который может быть и вектором. Будем считать, что ρ_ij=0, если d_ij=0.

Обозначим через Е={θ} – множество всех возможных разбиений множества А на отдельные подмножества, т.е. каждое θ таково, что

Θ=(А₁^θ, …, А_ℓ^θ, …, А_L(θ)^θ), , , i,j=1,..,L(θ), i≠j.

Рассмотрим некоторое разбиение θ. Подмножество А_ℓ^θєθ будем в дальнейшем называть модулем.

Для данного разбиения θ множество дуг исходного графа Г распадается на L(θ)+1 попарно не пересекающихся подмножеств: а) подмножество внутреннее G_ℓ^θ дуг, соединяющих вершины из А_ℓ^θ; б) подмножество внешнее D^θ дуг, концы которых лежат в разных модулях. Внешние дуги, входящие в какой-либо элемент модуля А_ℓ^θ называют его входом, а выходящие из какого-либо элемента – выходом.

Разбиению θ можно сопоставить агрегированный граф Г^θ, получающийся из исходного графа Г в результате объединения всех вершин подмножества А_ℓ^θ в одну для каждого ℓ=1,..,L(θ). Из вершины А_r^θ в вершину А_k^θ идет дуга тогда и только тогда, когда в графе Г имеется дуга, направленная от некоторой вершины a_iє А_r^θ в вершину a_jє А_k^θ. Дугам графа Г^θ сопоставим параметры r≠k,

где C_rk^θ={(i, j): a_iєA_r^θ, a_jєA_k^θ, d_ij=1}.

Агрегированный граф Г^θ описывает разбиение исходной системы на модули.

В зависимости от интерпретации дуг и вершин рассмотренной модели, используемых критериев оптимизации и ограничений могут быть рассмотрены различные способы разбиения графа Г.

Мы рассмотрим несколько таких постановок и соответствующих им математических моделей.

3.6.2. Постановка и модель решения задачи разбиения ИЛМ АСУ на функциональные модули с минимальным числом информационных связей

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

Исходными данными для задачи являются:

1) множество различных типов входных, промежуточных и выходных данных,

2) множество необходимых процедур преобразования данных.

При этом задачи относятся к одному и тому же уровню (см. л. 8).

Отношение, т.е. оператор отображения множества процедур к множеству информационных элементов можно представить в виде двудольного графа, дуги которого соединяют процедуры с соответствующими информационными данными (см. рис. 3.13).

 

 

Рис. 3.13. Двудольный граф связи процедур и информационных элементов

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

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

Пусть граф задачи содержит пять процедур и шесть информационных элементов (см. рис. 3.14). Матричная форма соотношений между процедурами и информационными элементами приведена в таблице 3.4.

 

 

Рис. 3.14 Граф взаимосвязи процедур с информационными элементами

 

Таблица 3.4. Матричная форма соотношений

Ar	dℓ
	+	+	+		+	+
		+			+
	+	+			+	+
	+		+	+
		+	+	+

Необходимо разбить множество процедур обработки данных на два модуля, имеющих минимальное число общих информационных элементов, причем разбиение необходимо провести таким образом, чтобы модули включали только соседние процедуры.

Рассмотрим решение задачи при следующих ограничениях:

1) общее число модулей V=2;

2) общее число информационных элементов в каждом из модулей L_v≤6, v=1,2;

3) общее число процедур в каждом модуле M_v≤4, v=1,2.

Находим матрицу взаимосвязи процедур обработки с информационными элементами:

║d_jℓ║=

При заданных условиях возможно четыре варианта разбиения процедур на модули

I [ a₁ ], [ a₂, a₃, a₄, a₅ ]

II [ a₁, a₂ ], [ a₃, a₄, a₅ ]

III [ a₁, a₂, a₃ ], [ a₄, a₅ ]

IV [ a₁, a₂, a₃, a₄ ], [ a₅ ]

 

Для каждого варианта разбиения определяем матрицы X_ji и Y_ℓi и значение критерия S:

I.

; ; S_I=5

II.

; ; S_II=5

III.

; ; S_III=3

IV.

; ; S_IV=3

По критерию оптимальным является IV вариант разбиения.

Наиболее наглядно формализованная постановка задачи иллюстрируется с использованием графа, вершинами которого являются процедуры и информационные элементы, а связывающие их дуги соответствуют имеющимся информационным элементам.

Для формализации задачи введем следующие обозначения:

А={a₁, a₂, …, a_j, …, a_m} – множество задач, далее процедур системы обработки данных

R={r₁, r₂,…, r_ℓ,…, r_L} – множество информационных элементов

1, если информационный элемент r_ℓ используется для выполнения

процедуры а_j

0, в противном случае

 

Введем в рассмотрение следующие переменные:

1, если процедура а_j входит в модуль А_i, j=1,..,m; i=1,..,M=2^m-1

0, в противном случае

 

и связанные с ней переменные:

 

 

1, если ; i=1,..,M; ℓ=1,..,L

y_ℓi=

0, если

т.е. y_ℓi=1, если r_ℓ - й информационный элемент используется процедурой a_j, которая размещается в модуле А_i.

При этих обозначения суммарное число различных информационных элементов, являющихся общими для различных модулей А_i, i=1,..,M равно

(1)

При ограничениях:

1. На число выделяемых модулей M₀≤M (2)
Каждая процедура хотя бы в одном модуле должна находиться:

j=1,..,m (3)
3. Число процедур в одном модуле может быть ограничено некоторой величиной N: i=1,..,M₀ (4)
4. Некоторые процедуры j и j` должны быть разнесены по разным модулям, т.е.

x_ij+x_ij`≤1 , i=1,..,M₀ (5)

5. Число информационных элементов, с которыми связан модуль, может быть ограничено, т.е. i=1,..,M₀ (6)

6. Ограничения на сложность взаимодействия информационных элементов и процедур внутри модулей, т.е. i=1,..,M₀ (7)

7. Ограничения на количество сложных связей между информационными элементами и некоторой парой i и i` модулей, т.е.

(8)

Задача (1)-(8) является задачей квадратичного целочисленного программирования.

Для удобства решения она может быть сведена к линейной форме путем линеаризации выражений (1) и (8).

Введем переменную

1, если ℓ-й информационный элемент необходим для модулей А_i и A_i`

Z_ℓii`=

0, в противном случае

Тогда критерий (1) может быть записан так:

(9)
Ограничение (8) при этом будет иметь вид:

для заданных i и i` (10)
Задача разбиения, представленная выражениями (9), (2)-(7), (10) имеет линейный вид и может быть решена с использованием стандартных методов.

3.6.3. Постановка и модель решения задачи разбиения ИЛМ АСУ на функциональные модули с минимальным временем обмена с внешней памятью ЭВМ (базой данных)

Исходными данными для постановки и решения этой задачи являются:

А={а_j; j=1,..,m} – множество последовательно выполняемых процедур в системе обработки данных;

R={r_ℓ; ℓ=1,..,L} – множество информационных элементов, обрабатываемых процедурами множества А;

W^с(з)=– 2-е матрицы взаимосвязей информационных элементов с процедурами обработки данных соответственно при считывании и записи, где w_jℓ^c(з)=1, если ℓ-й элемент считывается (записывается) j-й процедурой, и w_jℓ^c(з)=0, в противном случае;

τ_i – среднее время считывания i-го модуля из внешней памяти в оперативную память ЭВМ;

t_f^с – среднее время считывания f-го массива из внешней памяти в оперативную память ЭВМ;

t_f^з – среднее время записи результатов в f-й массив.

Переменные:

1, если j-я по порядку выполнения процедура включается в состав i-го модуля

x_ij=

0, в противном случае;

 

i=1,..,V; V≤M; V- возможное число модулей;

1, если ℓ-й информационный элемент включается в f-й массив

z_ℓf=

0, в противном случае;

 

f=1,..,F; F≤L;

1, если

y_iℓ^с(з)=

0, если

Условие обработки информации всеми процедурами модуля, причем одновременно 2 модуля не обрабатываются.

Другими словами, y_iℓ=1, если при выполнении i-го модуля, т.е. входящих в него процедур, требуется информационный элемент с номером ℓ.

1, если

z_if^с(з)=

0, если

Другими словами, z_if=1, если массив с номером f содержит хотя бы один информационный элемент, необходимый для выполнения хотя бы одной процедуры из модуля с номером i.

Таким образом, переменные y_iℓ^с(з) и z_if^с(з) служат для формализации взаимосвязи системы разрабатываемых модулей с отдельными информационными элементами и массивами при считывании и записи в процессе обмена с внешней памятью ЭВМ.

Общая задача синтеза оптимальной модульной АСУ, обеспечивающая минимальное общее время обмена с внешней памятью, формулируется следующим образом:

где 1-е слагаемое – учет времени считывания модулей, причем процедура выполняется последовательно;

2-е слагаемой – учет времени считывания (записи) информационных массивов;

при ограничениях:

- на общее число процедур в составе каждого модуля:

где - допустимое число процедур в i-ом модуле;

- на число информационных элементов, обрабатываемых процедурами каждого модуля:

где - максимальное допустимое число информационных элементов обрабатываемых i-ым модулем;

- на сложность интерфейса между всеми модулями системы обработки данных:

где - максимально допустимый межмодульный интерфейс между модулями СОД, т.е. допустимое число переменных, информационных элементов, являющихся общими для выделенных модулей;

- на сложность интерфейса между отдельными модулями системы обработки данных:

для заданных i и i′, где - максимальное число общих переменных (информационных элементов), обрабатываемых модулями i и i′;

- на однократность включения процедур в программные модули:

- на включение отдельных процедур в состав одного модуля:

x_ij+x_ij′≤1, для заданных j и j′, i=1,..,V;

- на передачу управления из модуля до завершения обработки информации всеми процедурами модуля:

_- на дублирование информационных элементов в массивах:

где k - допустимая степень дублирования информационных элементов в массивах системы;

- на размер записи каждого массива:

где - максимально допустимое число информационных элементов в f-ом массиве.

3.6.4. Синтез технической структуры АСУТП на основе конденсации графовой функциональной модели системы

В.Я. Войтенко, А.В. Кузнецов «Приборы и системы управления», №4, 1991г.

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

Постановка задачи и ее математическая модель

Техническую структуру локального уровня АСУТП, на которую возлагается решение некоторого множества L предназначенных для автоматизированного выполнения задач (функций), определим отображением d множества L={ℓ_j}, j=1,..,k на множество M={m_i}, i=1,..,n технических документов (процессоров) АСУ, которые необходимо использовать для построения технической структуры (ТС) локального уровня АСУТП, т.е.

d: L → M → {ℓ_j} → {m_i} (1)

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

1. однородность элементов ТС АСУТП и равнозначности связей между задачами одного уровня;

2. согласованности величин информационной емкости I_j задач ℓ_j локального уровня управления с допустимыми объемами памяти V_j^* устройств ЭВТ, реализующих технические элементы АСУТП; при этом из-за предыдущего ограничения справедливо равенство V₁^*=V₂^*=^…=V_n^*=V^*;

3. не превышения времени t_j решения (обработки) задач ℓ_j некоторых пороговых (допустимых) значений T_i^*, определяемых динамикой технологического процесса (ТП);

4. замкнутости (разомкнутости) межэлементного шинного интерфейса ТС АСУТП одного уровня.

С учетом сделанных ограничений синтез оптимальной ТС АСУТП сводится к определению требуемого оптимального числа n однородных технических элементов АСУТП, необходимых для решения задач локального уровня АСУТП, и распределению связей между этими элементами. Другими словами, нужно определить минимальное число, а также состав и взаимосвязи подмножеств сильно связанных задач, каждое из которых решается своим техническим элементом m_i; при этом число задач, входящих в состав таких подмножеств, может принимать значения от 1 (тогда число подмножеств равно k) до k (число подмножеств равно 1), а значит, и число n требуемых для их решения технических элементов согласно выражению (1) может варьироваться от k до 1.

Сильно связными будем полагать взаимно связные, а слабо связными – односторонне связные задачи рассматриваемого уровня иерархии ТС АСУТП.

Формализацию поставленной задачи проведем на базе математического аппарата теории графов.

В этом случае она может быть сформулирована следующим образом:

найти минимальное значение величины n, равное минимальному числу сильно связных компонент графа G_i; i=1,..n, информационного графа G:

G=(‹L, V, T›, ‹F, W›), где

L={ℓ_j}, j=1,..,k – множество автоматизируемых задач АСУТП локального уровня, соответствующих вершинам графа G;

V={v_j}, j=1,..,k – множество, каждый элемент которого определяет требуемый в процессе решения j-й задачи объем памяти, непосредственно зависящий от значения информационной емкости I_j задачи ℓ_j, т.е. v_j=f(I_j);

T={t_j}, j=1,..k – множество, каждый элемент которого определяет время, требуемое для решения j-й задачи;

F={f_js}, j=1,..,k; s=1,..,k – множество связей (дуг графа G) между задачами, причем равенство индексов j=s допустимо, что соответствует связи каждой вершины графа G с самой собой посредством дуги, называемой петлей, изображение которой на графе, как правило, опускается с целью упростить его схему;

W={w_js}, j=1,..k; s=1,..,k – множество весов соответствующих дуг графа G, соединяющих его вершины; вследствие ограничения, сформулированного в п. 1) каждый элемент w_js множества W положим равным 1 (w_js=1),

причем таких сильных компонент, что

: G_i≠0, G_i∩G_u=0, i,u=1,..,n; u≠i =G

и обеспечивается условие:

Q_опт → max

при ограничениях

(объем памяти процессора) (2)

(время решения всех задач i-ым процессором) (3)

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

Пусть в результате функционального анализа объекта управления (ТП) установлено множество L={ℓ_j}, j=1,..,k задач, решение которых подлежит автоматизации. Описаны также все условные и безусловные, непосредственные и косвенные, прямые, обратные и взаимные, а также другие связи между ними, на основе чего выстраивается информационный граф G, вершинами которого являются сами задачи ℓ_j и их атрибуты (v_j, t_j), а ориентированными дугами – связи f_js между задачами. На рис. 3.15 дан пример такого графа G.

Рис. 3.15. Информационный граф G задач локального уровня АСУТП

Алгоритм решения задачи

Поставленная задача решается на основе реализации процедуры конденсации G^* графа G путем отыскания его сильных компонент, число которых априорно неизвестно.

Граф G^* называемый конденсацией графа G, определяется следующим образом: каждая его вершина m_i соответствует множеству вершин некоторой сильной компоненты G_i графа G, т.е. m_i~G_i=(разным сильным компонентам из графа G отвечают разные вершины в конденсации G^*); дуга f_iu^* существует в конденсации G^* тогда, когда в графе G имеется такая дуга f_js, что вершина ℓ_j принадлежит сильной компоненте графа G_i, соответствующей вершине m_i в конденсации G^*, а вершина ℓ_s – сильной компоненте графа G_u, отвечающей вершине m_u в конденсации G^*, т.е.

~~

Сильными компонентами графа G_i будем считать максимальные подграфы графа G, обладающие заданным свойством. Поскольку в данном случае в качестве такого свойства выступает сильная связность вершин графа G, его сильные компоненты будут представлять собой подмножества (порожденные подграфы) взаимно связных вершин.

Требуется найти его сильные компоненты и построить конденсацию G^*.

Эта процедура реализуется при использовании матриц достижимости R_G и контрдостижимости Q_G графа G.

Матрица достижимости R_G=||r_js|| определяется следующим образом:

 

1, если вершина ℓ_s достижима из вершины ℓ_j (т.е. ℓ_j→ℓ_s)

r_js=

0, в противном случае, т.е. ℓ_j → ℓ_s.

Вершина ℓ_s считается достижимой из вершины ℓ_j, если существует путь от вершины ℓ_j к вершине ℓ_s.

Все диагональные элементы матрицы R_G равны 1, т.к. каждая вершина достижима из самой себя путем длиной 0. В качестве алгоритма построения матрицы достижимости R_G можно предложить следующий:

Вход: Матрица A_G смежности графа G, состоящая из строк A₁, A₂,…, A_j,…, A_k; A_j=(a_j1,…, a_js,…, a_jk)

Выход: Матрица достижимости R_G, состоящая из строк R₁, R₂,..., R_j,…, R_k, где R_j=(r_j1,…, r_js,…, r_jk)

Алгоритм запишем в виде, использующем псевдоалгол:

Начало

1. для j от 1 до k шаг 1 цикл А

2. сформировать множество S индексов s таких, что a_js=1;

3. R_j := A_j ; k:=0;

4. пока S≠0 цикл В

5. выбрать sєS;

6. R_j:=R_jA_s;

7. S:=S\{s};

8. K:=K{s};

9. Сформировать множество S_s индексов r таких, что a_sr=1;

10. S:=S(S_s\K);

11. конец цикла В;

12. возврат R_j;

13. конец цикла А;

Конец

Для примера матрица смежности A_G имеет вид:

 

		ℓ1	ℓ2	ℓ3	ℓ4	ℓ5	ℓ6
	ℓ1
	ℓ2
AG= ℓ3
	ℓ4
	ℓ5
	ℓ6

Применяя описанный выше алгоритм, получаем следующую матрицу достижимости R_G:

 

		ℓ1	ℓ2	ℓ3	ℓ4	ℓ5	ℓ6
	ℓ1
	ℓ2
RG= ℓ3
	ℓ4
	ℓ5
	ℓ6

 

Матрица контрдостижимости Q_G=║q_js║ определяется следующим образом:

1, если из вершины ℓ_s графа G достижима вершина ℓ_j (т.е. ℓ_j←ℓ_s)

q_js=

0, в противном случае, т.е. ℓ_j ← ℓ_s.

При этом q_js=1, если j=s.

Очевидно, что матрица Q_G есть транспонированная матрица R_G.

Для нашего примера имеем:

 

		ℓ1	ℓ2	ℓ3	ℓ4	ℓ5	ℓ6
	ℓ1
	ℓ2
QG= ℓ3
	ℓ4
	ℓ5
	ℓ6

 

На следующем этапе алгоритма выполняется поэлементарное умножение матриц R_G и Q_G графа G, в результате чего получаем R_G Q_G:

		ℓ1	ℓ2	ℓ3	ℓ4	ℓ5	ℓ6
	ℓ1
	ℓ2
RG QG= ℓ3
	ℓ4
	ℓ5
	ℓ6

 

При этом строка ℓ_j матрицы R_G Q_G содержит единицы только в тех столбцах ℓ_s, для которых выполняется условие: вершины ℓ_j и ℓ_s взаимно достижимы. В других местах строки стоят нули. Таким образом, две вершины графа G находятся в одной и той же сильной компоненте тогда, когда соответствующие им строки (или столбцы) в матрице R_G Q_G идентичны.

Следующий шаг алгоритма – преобразование матрицы R_G Q_G путем транспонирования ее строк и столбцов в блочно-диагональную матрицу (R_G Q_G)^′, каждая из диагональных подматриц (блоков) которой соответствует сильной компоненте графа G и содержит только единичные элементы, поскольку вершины, которым отвечают строки, имеющие единицу в столбце ℓ_s, образуют множество вершин сильной компоненты, содержащей вершину ℓ_s. Все остальные блоки данной матрицы имеют нули. Для нашего примера имеем:

 

		ℓ1	ℓ5	ℓ2	ℓ3	ℓ4	ℓ6
	ℓ1
	ℓ5
(RG QG)′= ℓ2
	ℓ3
	ℓ4
	ℓ6

 

Анализ матрицы (R_G Q_G)^′ позволяет получить число n и состав подмножеств сильно связных задач локального уровня АСУТП, решаемых каждое своим m_i-м техническим элементом i=1,..,n. В данном примере в состав G входит три сильные компоненты, следовательно, число однородных технических элементов, которые могут быть использованы для построения оптимальной ТС локального уровня АСУТП, равно 3, т.е. имеем:

 

=G

l

~

 

~

 

~

 

На основе блочно-диагональной матрицы (R_G Q_G)^′, а также структуры самого информационного графа G (см. рис. 3.12) строится его конденсация – граф G^*, определяющий связи между m_i-ми техническими элементами ТС АСУТП на локальном уровне, i=1,2,3 (см. рис. 3.16).

Рис. 3.16. Конденсация G^* графа G

В соответствии с определением конденсации графа и его сильных компонент, а также с учетом принятых ограничений (2) и (8) для элементов графа G^* справедливы соотношения:

где i=1,2,3 для рассмотренного примера.

Кроме того, имеют место соответствия:

f₂₁^*~f₂₁; f₂₃^*~f₂₄; f₃₁^*~f₃₁

Таким образом, для построения оптимальной по числу элементов n ТС АСУТП определены все ее составные части: число n технических элементов, состав подмножеств сильно связных задач, решаемых каждым из них, а также взаимосвязи между элементами ТС локального уровня АСУТП.

Если в ограничении, сформулированном в п. 4, задана замкнутость межэлементного шинного интерфейса данного уровня ТС АСУТП, то на основании результатов анализа блочно-диагональной матрицы (R_G Q_G)^′, а также полученных в конденсации G^* (см. рис. 2) связей f_iu^* (ориентированных дугах графа G^*)

Выстраивается искомая децентрализованная ТС АСУТП в целом с единственным (локальным, первым, нижним) уровнем иерархии (см. рис. 3.17).

Рис. 3.17. Децентрализованная одноуровневая оптимальная ТС АСУТП

В случае, когда в ограничении на ТС АСУТП определена разомкнутость соответствующего интерфейса или требуется построение многоуровневой иерархической ТС АСУТП, с учетом связей f_iu^* составляется информационный граф G⁽²⁾ задач второго уровня ТС, выстраиваемый по результатам функционального анализа множества задач (функций) этого уровня, лежащих в плоскости среза локального уровня, но решаемых соответственно на втором уровне иерархии ТС АСУТП. После этого относительно данного уровня ТС повторяется вся ранее описанная процедура синтеза. Аналогично выстраивается и все последующие уровни иерархической АСУТП.

Физический эффект оптимизации обусловлен, во-первых, сокращением числа связей между задачами каждого уровня ТС (на основе их внутреннего представления в соответствующих технических элементах), требующих взаимодействия различных элементов одного уровня, что увеличивает оперативность обмена информацией при соблюдении ограничений, определяемых выражениями (2) и (3), и, во-вторых, распараллеливанием решения только слабо связных задач фиксированного уровня ТС АСУТП; при этом сильно связные задачи, образующие свою сильную компоненту в информационном графе задач соответствующего уровня, предлагается решать последовательно на одном своем техническом элементе, т.е. задачи разных сильных компонент решаются параллельно, а в составе одной сильной компоненты – последовательно.

При этом следует иметь в виду следующее:

- Если каждая задача решается своим техническим элементом, то это дает возможность параллельной обработки всех задач одного уровня ТС, что приводит к увеличению оперативности обработки. Однако при этом возможна задержка при организации обмена между элементами, т.е. имеют место их простаивания в ожидании исходной информации. Кроме того, усложняются протоколы обмена, системные алгоритмы, модели и программы управления системой, заметно поднимается и стоимость такой системы.

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

Приведенные доводы свидетельствуют в пользу предлагаемого метода синтеза оптимальной ТС АСУТП, свободного от перечисленных недостатков.

3.5.5. Обобщенная математическая модель определения рациональной структуры распределенной АСУ

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

Под определением структуры АСУ будем понимать следующие операции:

1. Выбор задач управления, возлагаемых на технические средства АСУ.

2. Выбор алгоритмов их реализации в АСУ.

3. Распределение выбранных задач по узлам (уровням) системы.

4. Определение КТС в узлах АСУ.

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

Для формализации задачи введем ряд обозначений.

Пусть Е – это множество задач управления. Каждой задаче припишем номер (индекс) i=1,..,I. Обозначим через M_i множество алгоритмов решения i-ой задачи в АСУ, включая решение задачи без применения технических средств, M_i={k/k=1,..,k_i}.

Через ║║ обозначим матрицу связи между задачами. Задачи i и i^′ считаются связанными, если для решения i^′-й задачи используется информация, являющаяся входной для i-й задачи, при этом имеет смысл среднего потока информации от i-й задачи к i^′-й. Если задачи не связаны, то =0.

Пусть Q – множество номеров узлов (уровней) АСУ, причем Q={j/j=1,..,J}; ║║ - матрица удельных затрат на передачу информации из j-го узла в j^′ (для не связных узлов =∞, а =0).

Обозначим через F множество номеров технических средств, т.е. F={ℓ/ℓ=1,..,L}, m_ℓ - величина, характеризующая ресурсы ℓ-го технического средства. Кроме того, а_ikj – эффективность решения i-й задачи k-м способом в j-м узле, m_ik – потребность в ресурсах технических средств i-й задачи, решаемой k-м способом (например, в машинном времени, памяти и т.п.); C_ℓj – затраты на эксплуатацию ℓ-го технического средства в j-м узле, K_ℓ - капитальные затраты на технические средства, K_ik – затраты на разработку и внедрение i-й задачи в k-м варианте.

Напомню, что под термином «задача» понимается комплекс взаимосвязанных операций по обработке информации и принятию решений. Выбор этих задач может осуществляться, например, экспертным методом, о чем уже говорилось ранее. Также экспертным методом может быть определена эффективность решения задач а_ikj и другие необходимые для анализа данные.

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

Введем следующие переменные:

1, если i-я задача решается в j-м узле k-м способом

x_ikj=

0 в противном случае

1, если j-й узел оборудуется ℓ-м техническим средством

x_ℓj=

0 в противном случае.

 

Задача может быть теперь записана в следующем виде:

(1)

а_ikj , если ikj=i′k′j′

где b_{ikji′k′j′}= (2)

-α_{ikji′k′j′}*γ_jj′ , если ikj≠i′k′j′.

 

Величина b_{ikji′k′j′} равна эффективности решения k-го варианта i-й задачи в j-м узле, т.е. а_ikj, если ikj=i′k′j′ и равна затратам на передачу информации из j-го узла в j^′-й в противном случае.

В качестве ограничений здесь выступают следующие:

(3) , т.е. каждая задача должна быть решена, причем только в одном каком-либо узле и только одним каким-либо способом;

(4)

1, если j-й узел оборудуется ℓ-м техническим средством

x_ℓj=

0 в противном случае.

т.е. общие затраты на разработку АСУ, состоящие из стоимости на капитальные затраты на технические средства и на разработку и внедрение задач не должны превышать заданной величины K;

(5)

 

т.е. используемые технические средства имеют определенные ресурсные ограничения.

Рассмотренная задача является нелинейной задачей математического программирования.

Если заранее произведен выбор технических средств и известно, что задачи независимы, то выражение (1) примет вид:

(6) при ограничениях:

(7)

(8)

(9)

Задачу (6) - (9) можно свести к двухиндексной, если ввести переменную x_fj. Взаимно однозначное соответствие между множествами индексов {f} и {ik} устанавливается следующим соотношением:

f=k+b_i,

В этом случае задача будет иметь вид:

(10)

(11)

(12)

(13)

Если задачи зависимы, то вместо (10) следует записать

(14)