Software & Systems

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

Рассмотрим технологический процесс, состоящий из p-связанных подсистем. Пусть i-тая подсистема характеризуется вектором входных переменных xi=(xi1,. . .,xik), вектором выходных переменных yi =(yi1 . . .,yik), и вектором управлений ui=(ui1,. . .,uim). Векторы xi и ui удовлетворяют локальным ограничениям xiÎXi и uiÎUi. Интересы i-той подсистемы задаются критерием Fi. Состояние центра характеризуется значением глобального критерия F=.

Задача определения оптимального числа подсистем

G(p)                                                           (1)

для двухуровневой системы была рассмотрена в работе [1]. Вид зависимости G(p) зависит от технологической схемы объекта, выбранного метода декомпозиции и применяемых алгоритмов оптимизации. Примем, что для решения задачи оптимального управления используется метод явной декомпозиции [2]. Поиск оптимума в локальных задачах и задаче координации осуществляется методом прямого сканирования. При этом общее время поиска оптимума складывается из времени условной оптимизации подсистем и времени их координации. Определим множество Xi входных сигналов и множество Ui управлений i-той подсистемы в виде k- и m-мерных параллелепипедов и зададим точность по каждой координате векторов xi и ui значением L числа уровней квантования. Количество вычислений локального критерия Fi составит Lm+k, а количество вычислений критерия F на стадии координации Lk-p. Положим для простоты и без потери общности k=1. Тогда, учитывая, что m=n/p, где n – общая размерность вектора управления (сумма векторов управления всех подсистем), и без учета некоторых, не влияющих на результат деталей, выражение для G будет иметь вид:

G=L[n / p]+1 + L p,                                              (2)

где [ ] – операция взятия целой части числа. Задача (2) может быть решена прямым перебором по p при различных значениях n.

Оказалось, что оптимальное число подсистем, минимизирующее (1), пропорционально квадратному корню из общей размерности задачи n, то есть существует следующая зависимость:

p=[].                                                               (3)

Зависимость (3) справедлива не только для метода прямого сканирования, но и для любых методов, трудоемкость которых экспоненциально растет с увеличением размерности. Кроме того, эта закономерность имеет место как при последовательном решении локальных задач в одном вычислительном устройстве, так и при их параллельном решении в различных ЭВМ. Все это вытекает из следующих двух теорем.

Представим критерий G в виде суммы двух функций G=G1(n/p)+G2(p). Функции G1 и G2 являются функциями дискретного аргумента. Аппроксимируем дискретную зависимость от p непрерывной. Кроме того, пусть выполняются следующие допущения:

¨ функции G1(p) и G2(p) непрерывные и имеют непрерывные первые производные;

¨ функция G1(p) монотонно убывающая выпуклая вниз функция, а G2(p) монотонно возрастающая выпуклая вниз функция;

¨ справедливы условия: G1(1)=M1, G1(n)=m1, G2(1)=m2, G2(n)=m2, M1>>m1,m2, M2 >> m1,m2, то есть функции G1(p) и G2(p) имеют вид, показанный на рисунке 1.

Сначала проанализируем случай, когда функции G1(n/p) и G2(p) имеют одинаковый вид.

Теорема 1. Точка p0 =является точкой минимума функции G = G1(n/p)+G2(p).

Доказательство.

По условию теоремы G=G1(n/p)+G2(p). Вычислим производную функции G в точке p0= и приравняем ее к нулю:

=G1’ (n/p0)(-n/p02)+G2’ (p0)=0.

Подставим вместо n значение p02

G1’(p02/p0)(-p02/p02)+G2’(p0)=-G1’(p0)+G2’(p0)=0.

Так как вид функций G1(n/p) и G2(p) одинаковый, последнее равенство справедливо. Согласно допущению функции G1(p) и G2(p) являются выпуклыми вниз. Значит G=G1(p)+G2(p) также выпуклая вниз функция. Следовательно, точка p0= является точкой минимума функции G.

Теперь рассмотрим случай, когда функции G1(n/p) и G2(p) не имеют одинакового вида. Найдем производную функции G по p и приравняем ее к нулю

=G1’(n/p)(-n/p2)+G2’(p)=0 .                  (4)

Преобразуем (4) к виду

 n/p2=G2’(p)/G1(n/p).                                            (5)

Теорема 2. Если G1’(n/p) и G2’(p) монотонные функции от p или постоянные и если при p=1 справедливо условие G2’(p)/G1’(n/p).

Доказательство.

Сначала рассмотрим случай, когда G1’(n/p) монотонно убывающая функция, а G2’(p) монотонно возрастающая. Следовательно, дробь G2’(p)/G1’(p) при изменении p от 1 до n монотонно возрастающая функция. Левая часть выражения (5) при изменении p от 1 до n монотонно убывает. Тогда существует единственное решение n/p02=G2’(p0)/G1’(n/p0). Отсюда

.

Случай, когда одна из функций G1’(n/p) или G2’(p) постоянна, доказывается аналогично.

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

В своей работе по теории иерархических систем М.Месарович [3] выдвинул постулат, согласно которому любая многоуровневая иерархическая система может рассматриваться как совокупность двухуровневых. Поскольку определение оптимальной структуры двухуровневой системы намного проще, чем многоуровневой, указанный постулат получил широкое использование при выборе структуры. Однако вопрос о применимости данного утверждения для многоуровневых систем с числом уровней большим двух остается открытым, поскольку он противоречит диалектическому понятию целостности системы, согласно которому система не представляет собой простой набор независимых элементов. Система означает взаимодействие частей, такое, что вся совокупность частей представляет характеристики и свойства, не являющиеся результатом простой суммы или сопоставления. Поэтому представляет интерес задача определения оптимального числа подсистем на каждом уровне иерархической системы при числе уровней большим двух.

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

G = ,

где p1 – число подсистем на втором уровне; p – число подсистем на третьем уровне. Решая задачу методом прямого перебора при L=10 и n=100, получим оптимальные значения числа подсистем на втором и третьем уровнях p1=5, p=25. Отношения числа подсистем на соседних уровнях =4, =5, =5. Среднее значение отношения равно 4.67. Заметим, что , а это при округлении до ближайшего целого значения дает 5. Следовательно, отсюда можно сделать вывод, что оптимальное значение числа подсистем на втором уровне равно корню третьей степени из общей размерности задачи и, кроме того, корню третьей степени из n равно отношение числа подсистем между соседними уровнями или модуль системы M [4]. Значит, иерархическая система, обладающая оптимальной структурой, является модульной, а это один из признаков высокой организации системы [4]. Так как 4.64 не целое число, модуль может принимать значения 4 или 5.

Оптимальные значения числа подсистем для трехуровневой системы при других значениях n, а также значения , средний модуль и возможные значения модуля приведены в таблице 1. Из таблицы видно, что при увеличении n указанная зависимость полностью сохраняется, что дает право говорить об устойчивой закономерности.

Таблица 1

Для четырехуровневой системы критерий оптимальности будет G= , где p2 – число подсистем на втором уровне, p1 – число подсистем на третьем уровне и p – на четвертом уровне. При тех же значениях L и n получим p2=3, p1=9, p=34. Отношения числа подсистем на соседних уровнях =2.9, =3.8, =3, =3. Среднее значение равно 3.17, = 3.16. Следовательно, для четырехуровневой системы значение модуля можно определить как корень четвертой степени из общей размерности системы. В таблице 2 приведены оптимальные значения числа подсистем для четырехуровневой системы при других значениях n, значения , Mcp и M.

Таблица 2

Продолжим эксперимент для пятиуровневой системы с критерием оптимальности G=, где p3 – число подсистем на втором уровне; p2 – число подсистем на третьем уровне; p1 – на четвертом уровне и p – на пятом. Минимуму критерия G соответствуют значения p3=2, p2=6, p1=17, p=50. Отношения , , , , . Среднее равно 2.5, . Следовательно, для пятиуровневой системы значение модуля опять может быть определено как корень пятой степени из n.

Для произвольного числа уровней l критерий оптимальности будет иметь вид G=, или, в общем случае:

G=G(n/p)+G(p/p1)+...+G(pi /pi+1)+...+G(pk), (6)

где k=l+2. Если допустить, что функция G является непрерывной выпуклой вниз и имеет непрерывные частные производные по p, p1,..., pk, то можно доказать следующую теорему.

Теорема 3. Если l-уровневая иерархическая система является модульной и трудоемкость решения задачи оптимального управления определяется выражением (6), то для модуля M= значения p, p1,..., pk являются решением задачи G.

Доказательство.

По условию теоремы, так как система является модульной

, , , ..., ,..., . Отсюда , ..., . Оптимальное решение должно удовлетворять условиям:

.

Выразив p, p1,..., pk через  и выполнив преобразования, получим:

,

то есть при M= существует . Так как по предположению функция G выпуклая вниз, то полученное решение является единственным.

Таблица 3

Таким образом, на основании изложенного можно сделать вывод, что для многоуровневых иерархических систем оптимальных по критерию оперативности модуль структуры определяется из выражения M=, где l – число уровней системы. Кроме того, заметна тенденция, согласно которой с возрастанием l модуль M стремится к значению два, а из анализа таблицы 3 видно, что величина критерия G для оптимального варианта структуры при фиксированном значении n=100 с ростом l монотонно убывает.

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

В заключение следует отметить, что полученные выше результаты можно безусловно использовать только применительно к безытеративным методам координации [5]. Для итеративных методов общее время T на решение задачи оптимального управления может быть вычислено по формуле:

T=hK × (J × TL+TK),                                           (7)

где hK = hK(p) – число шагов координации; J =J(p) – количество вычислений локальных задач на каждом шаге координации; TL=TL(n/p) – время решения локальных задач; TK=TK(p) – время вычислений на каждом шаге координации. Выражение (7) можно представить следующим образом: T=hK(p)×J(p)×TL(n/p)+ hK(p)×TK(p)=T1(p,n/p)+T2(p). Следовательно, если первый член T1(p,n/p) представляет собой монотонно убывающую функцию от p, то рассмотренные в данной статье результаты относительно определения оптимальной структуры иерархических систем могут быть распространены и на системы, в которых для решения задачи оптимального управления используются итеративные методы координации.

Список литературы

1. Марьясин О.Ю. Выбор структуры распределенных автоматизированных систем управления сложными технологическими процессами: Автореф. на соиск. уч. степ. к. т. н. - М.: МИХМ, 1992. - 16 с.

2. Артамонов А. Г., Володин В. М., Авдеев В. Г. Математическое моделирование и оптимизация плазмохимических процессов. - М.: Химия, 1989. - 224 с.

3. Месарович М., Мако Д., Тахакара И. Теория иерархических многоуровневых систем. - М.: Мир, 1973. - 332 с.

4. Каянелло Э. и др. Структура и модулярность в самоорганизующихся сложных системах. В сб.: Исследования по теории структур. - М.: Наука, 1988. - С.144-177.

5. Алиев Р.А., Либерзон М.И. Методы и алгоритмы координации в промышленных системах управления. - М.: Радио и связь, 1987. - 208 с.