Задачи синтеза структуры АСУ

МЕТОДЫ ФОРМАЛИЗАЦИИ И АЛГОРИТМИЗАЦИИ ЗАДАЧ СИНТЕЗА СТРУКТУРЫ АСУ

Задачи синтеза структуры АСУ

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

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

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

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

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

В общем случае задача синтеза структуры АСУ включает в себя: 1) выбор принципов построения системы управления; 2) распределении функций управления и обработки информации по узлам и уровням иерархии АСУ; 3) рациональное размещение задач принятия решений и обработки информации по конкретным элементам с одновременным выбором методов их решения и согласованием целей отдельных элементов, уровней и подсистем с общими для всей системы; 4) распределение функций и задач между техническими средствами и коллективами специалистов по управлению; 5) определение наиболее эффективных взаимосвязей между всеми составляющими структуры системы; 6) выбор и назначение технических средств для решения задач и осуществления связи в АСУ.

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

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

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

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

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

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

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

Обозначим множество возможных принципов построения системы и ее элементов через P (к ним можно отнести, например, принцип централизованного или децентрализованного управления). Каждому набору принципов я построения системы соответствует некоторое множество возможных функций , из которого при проектировании системы необходимо выбрать подмножество , необходимое и достаточное для реализации выбранных принципов управления . В АСУ обычно различают функции принятия решений и обработки информации. Через т обозначим множество взаимосвязанных физических элементов структуры АСУ. Подобными элементами могут быть узлы системы, технические средства, пункты обслуживания, отдельные исполнители, коллективы и т. д. Через А обозначим операцию отображения на т. Оптимальное отображение должно обеспечивать экстремум некоторой целевой функции при выполнении заданных ограничений [3-2].

С учетом введенных обозначений можно выделить следующие задачи синтеза структуры АСУ.

Задача 1. В общем случае задача синтеза оптимальной структуры состоит в определении

(3-1)

(3-2)

(3-3)

(3-4)

Задача 2. Если принципы построения системы заданы, то задача синтеза оптимальной структуры состоит в определении (3-1) и (3-3).

Задача 3. Если заданы принципы построения системы и.выполняемые ее функции, то задача синтеза оптимальной структуры состоит в определении (3-1) и (3-4).

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

Задача 5. Задача анализа состоит в определении характеристик системы при заданных условиях (3-1) - (3-4).

В зависимости от цели исследования в понятие «разработка структуры системы» включаются различные вопросы из числа рассмотренных выше.

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

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

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

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

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

Функции, выполняемые системой, обычно могут быть представлены в виде совокупности взаимосвязанных задач. Задачи в свою очередь могут быть разбиты на совокупность операций. Последовательно выполняемые операции задачи (или группы операций) обычно называются ее этапами. Заметим, что деление задач на этапы обычно бывает условным и в ряде случаев этапы могут выступать в качестве самостоятельных задач. В процессе обработки информации обычно выделяются следующие этапы: подготовка информации - преобразование – хранение - преобразование - потребление (получение информации).

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

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

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

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

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

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

При формализации задач встречается два типа отображений:

тип А. Объем задачи, этапа, операции выполняется лишь в одном из нескольких возможных элементов;

Таблица 3-1

Условие	Формализация условия
Весь объем этапа выполняется в одном узле (отображение типа А)	Пусть - этапы i-й задачи, - узлы системы, тогда
Объем этапа распределяется между узлами (отображение типа Б)	Пусть - часть объема m-го этапа i-й задачи, решаемого в j-м узле, тогда
Выбирается вариант решения задачи и вариант решения каждого этапа
Выбирается способ реализации узла

тип Б. Объем задачи, этапа, операции распределяется между несколькими элементами.

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

Формализация задач типа А приводит к задачам целочисленного программирования, а типа Б - смешанного программирования.

Задача синтеза структуры в общем случае формулируется следующим образом:

(3-5)

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

(3-6)

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

Рассмотрим основные типы ограничений (условий), которые учитываются при решении задач (3-5), (3-6).

Условие 1. Каждая задача i решается лишь в одном варианте из числа возможных:

Аналогично условие 1 записывается для этапов и узлов:

Условие 2. Число задач, выполняемых системой, ограничено сверху (снизу):

Либо число узлов, входящих в систему, должно быть больше (меньше) заданного.

Условие 3. В каждом узле j решается не более чем (не менее, столько же) nij этапов i-й задачи:

(3-7)

Причем, если требуется выполнение равенства в (3-7) и nij=mi, то задача i целеком выполняется в узле j.

Условие 4 (на загрузку узла). В j-м узле решается не более nj этапов различных задач:

Условие 5. При задании отображения типа А требуется, чтобы каждый этап i-й задачи выполнялся лишь в одном узле:

При задании отображения типа Б решение каждого этапа i-й задачи может распределяться между узлами. При этом ximj равно части объема m-го этапа i-й задачи, выполняемой в j-м узле, и необходимо, чтобы

Условие 6 (логические условия типа И и ИЛИ). Для каждого узла j либо задачи i (этап m) задается множеством узлов (задач, этапов) Njp(Njk, Nimj), связанных с j(i,m) следующим условием (типа И) (если Xjp=1, то и =1 для всех j’p’ Njp):

Если требуется, чтобы при Xjp=1 равенство =1 выполнилось лишь для одного j’p’ из заданного множества Mjp, то получаем логические условия типа ИЛИ:

Аналогично могут быть формализованы более сложные условия, например условие, не допускающее решения взаимосвязанных этапов m и m’ в узлах, не связанных каналом связи. Пусть djj’=1, если узлы j и j’ связанны между собой, и 0 в противном случае, тогда требуется чтобы

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

1. Затраты на разработку системы

где Rimnj – затраты на разработку m-го этапа i-й задачи, решаемого в n-м варианте в j-м узле.

2. Затраты на создание системы. Пусть lirmn – тип набора технических устройств, используемых для решения m-го этапа i-й задачи, решаемой в k-м варианте, и c_l – стоимость набора l, тогда затраты на оснащение системы необходимыми техническими средствами составят:

где,

3. Затраты на эксплуатацию системы. Пусть

где - затраты на решение m-го этапа i-й задачи в j-м узле; - средний поток информации, циркулирующий между m-ным этапом i-й задачи и m’-ным этапом i’-й задачи в процессе функционирования системы, а - затраты на передачу единицы информации из узла j в узел j’. Тогда ограничение на затраты имеет вид:

4. Аналогично записываются ограничения на эффективность и оперативность выполнения функций (задач) в узлах системы. Пусть - время выполнения m-го этапа i-й задачи, решаемого n-м способом в j-м узле, - время передачи единицы информации между узлами j и j’, тогда время выполнения задачи (оперативность), которое складывается из времени последовательно выполняемых этапов и времени на передачу информации между этапами, выразится следующим образом:

5. Загрузка узлов системы. Каждый узел системы располагает ограниченным набором ресурсов , необходимым для выполнения заданных функций, здесь γ – тип ресурса, а t – период функционирования системы.

Пусть - количество ресурсов γ-го типа в период t, необходимое для выполнения
m-го этапа i-й задачи. Естественно считать, что известно лишь для задач планового типа. Тогда ограничение на загрузку записывается следующим образом:

где - ресурсы, необходимые для выполнения оперативных задач.

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

В зависимости от специфики синтезируемой системы в качестве оптимизируемого показателя качества могут выступать объединения различных характеристик. Так, для синтеза АСУ отраслевого типа характерны экономические характеристики типа общей эффективности функционирования системы (3-4).

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

3-2. Методология решения задач синтеза структуры

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

Рассмотрим основные методы решения задач синтеза структуры. Эти методы могут быть классифицированы следующим образом:

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

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

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

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

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

Пусть в целевой функции или ограничениях встречается выражение вида

где - переменные, принимающие два значения: 0 или 1.

Введением переменной принимающей значения 0 или 1 исходные условия можно заменить на:

2) задача с разрывными целевыми функциями сводится к задачам с линейными ограничениями (метод М. Балинского [3-4]). Возможность сведения задач с разрывными целевыми функциями к частично целочисленным задачам основывается на наличии верхних границ для переменных.

Пусть

и

3) при формализации параллельно выполняемых операций часто возникают выражения типа W=max(L₁, …, L_m), где L_i – выражения от некоторых переменных. Подобное выражение можно представить в линейной форме путем введения переменной принимающей значения 0 или 1, и следующих условий:

Если - выражения линейные или с произведением булевых переменных, то при использовании рассмотренного выше приема выражения могут быть приведены к линейному виду.

2. Задачи синтеза структуры часто допускают простую и наглядную интерпретацию в виде графовой модели. Эта модель часто может быть использована для построения эффективных алгоритмов их решения [3-5].