ГЛАВА 6. МОДЕЛИ СИНТЕЗА СТРУКТУРЫ АСОИУ

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

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

Основными проблемами, возникающими при разработке структуры АС, являются:

1) определение необходимого числа уровней иерархии;

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

3) распределение ответственности;

4) выбор конкретных схем обработки информации и создание контуров принятия решений;

5) организация информационных потоков;

6) выбор соответствующих технических средств.

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

- множество возможных принципов построения системы или ее элементов. Возможные принципы бывают обычно заданы и выбираются при синтезе системы;

- выбранные принципы построения системы или ее элементов. Очевидно, что ;

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

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

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

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

; (1)

 

;    (2)

 

;                                                         (3)

 

 

                               (4)

 

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

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

 

6.2. Частные задачи синтеза оптимальной структуры АСОИУ

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

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

Выясним вначале возможные критерии оптимизации.

А) Минимизация затрат на реализацию задач в АС.

,                                                                     (1)

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

Б) минимизация общего времени решения всех задач АС.

                                                                  (2)

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

В) Минимизация максимального времени решения задач АС.

 .                                        (3)

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

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

а) на связи между задачами, т.е. задан граф задач в виде матрицы

.                                                                                       (4)

б) на связи между узлами, т.е. задана матрица вида

                                                                                         (5)

в) на общие затраты на реализацию задач в АС

                                                             (6)

г) на затраты на реализацию задач в узлах

,                                             (7)

д) на загрузку каждого узла

,                                                (8)    

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

 

е) на общее время решения всех задач

                                                                       (9)

ж) на время решения отдельных задач

                                                                (10)

Рассмотрим теперь некоторые частные задачи синтеза оптимальной структуры АС.

6.2.2. Первая частная задача синтеза

 

Необходимо так распределить задачи  между узлами , чтобы обеспечить минимум общих затрат (1) или минимум общего времени решения (2) при исполнении ограничений на загрузку каждого из узлов (8), или затраты в каждом узле , то есть ограничение (7).

Математическая модель этой задачи может быть записана следующим образом:

                                                               (11)

при следующих ограничениях:

,                                                (12)

                                      (13)

В этих соотношениях приняты следующие обозначения:

 - затраты (время решения) задачи с номером  в узле с номером ;

- допустимые затраты (загрузка) в узле с номером ;

- переменная, равная 1, если задача с номером  решается в узле с номером , и равная 0 – в противном случае.

Условие (13) означает, что каждая задача должна решаться только в одном узле.

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

Вершины первого уровня получают, поочередно закрепляя первую задачу за первым узлом, вторым и т. д., т.е. фиксируя  для узлов  при

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

 

,                                                                                            (14)

где - число рассмотренных уровней ветвления; .

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

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

- исключены все элементы , тогда решение отсутствует;

- остался лишь один элемент , он обязательно входит в оптимальное решение, если оно существует. Значение  заменяется величиной , и этот элемент в дальнейшем поиске не участвует;

- осталось несколько элементов, они участвуют в дальнейшем поиске оптимального решения.

 

6.2.2. Вторая частная задача синтеза

 

Необходимо так распределить задачи  между узлами , чтобы обеспечить минимум общих затрат ( критерий 1) или минимум общего времени решения (критерий 2) при выполнении ограничений на общее время решения (9) или общие затраты (6) соответственно.

Математическая модель этой задачи может быть записана следующим образом:

                                                                                          (15)

при следующих ограничениях:

                                                                                                   (16)

                                                     (17)

В соотношениях (15) - (17) приняты следующие обозначения:

 - затраты (время решения) задачи , расположенной в узле ,

 - время решения (затраты) на задачу , расположенную в узле ,

- общее время решения (затраты) всех задач.

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

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

                                                             (18)

где  - минимальный элемент в соответствующей строке;

- рассматриваемый элемент, .

Другими словами, каждая задача последовательно закрепляется за каждым из узлов и проверяется выполнение условия (16) в лучшем случае.

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

Из условия (17) следует, что в каждой строке может быть только один элемент. Поэтому  без учета выражения (14) равен . Отсюда следует, что если для элементов одновременно выполняются условия  и , , то эти элементы могут быть исключены из рассмотрения.

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

Далее используется метод «ветвей и границ». В отличие от предыдущей задачи, ветвление осуществляется с учетом ограничения (16), что существенно сокращает число рассматриваемых вариантов. Оценка для каждой вершины находится по элементам матрицы (15) аналогично предыдущей задаче (14). Ограничение при этом имеет следующий вид:

,                                                                                            (19)

где - уровень ветвления;

.

6.2.4. Третья частная задача синтеза

 

Необходимо так распределить задачи  между узлами , чтобы обеспечить минимум общих затрат ( критерий 1) или минимум общего времени решения (критерий 2) при выполнении ограничений на общее время решения (критерий 9) и загрузку узлов (критерий 8), либо на общие затраты (критерий 6) и загрузку узлов (критерий 8) соответственно.

Математическая модель этой задачи может быть записана в следующем виде:

                                                                             (20)

при следующих ограничениях:

                                                                                   (21)

                                                                   (22)

                                                                       (23)

Для решения этой задачи, прежде всего из матриц коэффициентов  исключаются элементы, которые заведомо не могут войти в оптимальное решение. Исключение элементов  и  из матриц систем (21) и (22) осуществляется аналогично тому, как это делалось рассмотренному выше, т.е. исключаются все элементы, для которых не выполняется условие (18). Оценка для матрицы коэффициентов (20) находится аналогично оценке системы (14) в первой задаче.

Лекция 3

 

6.2.5.Примеры решения рассмотренных задач

 

Пример 1. Этот пример рассматривается для того, чтобы показать, как осуществляется процедура ветвления. Итак, пусть необходимо решить следующую задачу:

                                                                        (24)

при следующих ограничениях:

                                                                                        (25)

                                                                                        (26)

                                                                                             (27)

.                                                                  (28)

Условие (25) означает, что каждый узел может решать только одну задачу. Условие (26) означает, что каждая задача может решаться только в одном узле.

Будем изображать множество вариантов кружками, в верхней части которых проставлен номер множества, а в нижней – значение нижней границы (см. рис. 6.3.1).

Для вычисления нижней границы используется следующее соотношение:

,                                                                               (29)

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

Для исходного множества (обозначим его через «0») соотношение (29) имеет вид , т.е. из матрицы  (28) выбираются минимальные числа по строкам и эти числа складываются. При этом условие (25) может нарушаться.

 

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

 

Рис. 6.3.1. Процедура ветвления

Таблица 6.3.1

 

1	8	+2+3+3	16
2	5	+2+1+2	10
3	6	+2+1+2	11
4	4	+2+1+2	9

 

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

Таблица 6.3.2

 

1	4+5	+3+3	15
2	4+3	+1+2	10
3	4+2	+1+2	9

 

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

 

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

Таблица 6.3.3

 

1	4+2+1	+3	10
2	4+2+7	+2	15

 

Из таблицы 6.3.3 следует, что третья задача должна быть закреплена за узлом номер один. Тогда четвертая задача однозначно закрепляется за узлом номер два.

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

Значение целевой функции равно 10.

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

 

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

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

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

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

Таким образом, . Поэтому имеем:

Выбираем минимальные элементы в каждой строке. Загрузка не превышает заданную величину. Окончательно имеем:

 или

Значение целевой функции в первом случае , а во втором случае . Варианты равнозначны.

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

                                                                                                 (30)

при следующих ограничениях:

                                                                                              (31)

                                                                                                            (32)

                                                                                                          (33)

Пусть

Сначала находим минимальные элементы в каждой строке матрицы  и проверяем, удовлетворяется ли условие (31) по одноименным элементам матрицы

.

Условие (31) не выполняется, и задачу «в лоб» решить не удается. Приступим к упрощению матриц коэффициентов  и . Для матрицы  последовательно для всех элементов проверяется условие (18), т.е. условие

                                                             (34)

где  - минимальный элемент в соответствующей строке;

- рассматриваемый элемент, .

Для

Элемент  не удовлетворяет условию (34), он исключается из матрицы , и одноименный элемент  исключается из матрицы . Аналогично для  имеем:

Для

 

Для

 

Для :

Легко видно, что для  все элементы удовлетворяют условию (34).

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

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

- (3 и 7) и (1, 5 и 3) – условие  выполняется и, следовательно, можно убрать элементы и ;

- (2 и 4) и (2 и 9) - условие  снова выполняется и, следовательно, можно убрать элементы и .

      Таким образом, первая строка матрицы  запишется как ( 3 – 2 - ), а последняя строка как ( 7 - - 1).

После соответствующих упрощений матрицы  и  принимают следующий вид:

Из матрицы в каждой строке выбираем минимальные элементы и получаем следующее решение:

 

Подсчитываем время решения: 2+5+3+4+5=19< 20. Оно не превышает допустимой величины. Задача решена.

Если бы это не удалось, пришлось бы вести ветвление, и каждый минимальный вариант проверять на условие (31).

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

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

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

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

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

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

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

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

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

Пусть Е – это множество задач управления. Каждой задаче припишем номер (индекс) . Обозначим через множество алгоритмов решения -ой задачи в АСOИУ, включая решение задачи без применения технических средств, .

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

Пусть  – множество номеров узлов (уровней) АСОИУ, , а Ɣ = ║ ║ - матрица удельных затрат на передачу информации из -го узла вузел Для не связных узлов полагаем , а =0).

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

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

Пусть, также – потребность в ресурсах технических средств -й задачи, решаемой k-м способом (например, в машинном времени, памяти и т.п.);  – затраты на эксплуатацию ℓ -го технического средства в j-м узле,  - капитальные затраты на технические средства,  – затраты на разработку и внедрение i-й задачи в k-м вариантеее реализации.

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

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

 

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

 

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

=

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

 

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

=

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

 

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

 

,                                                   (1)

 

где                                                              (2)

 

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

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

 

1) ,                                                                                                         (3)

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

 

  2)                                                             (4)

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

3)                                                                                         (5)

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

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

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

                                                                                                          (6)

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

                                                                                       (7)

                                                (8)

                                                     (9)

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

 

, где .

 

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

                                                             (10)

                                                          (11)

                                                                        (12)

                                                  (13)

 

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

 

                           (14)

⇐ Предыдущая15161718192021222324Следующая ⇒

Поделиться: