Проблемы автоматизированной обработки информации

§ 1 Литература

§ 1−1. Понятие БСУ

§ 1−2. Системный подход

§ 2 Функциональное описание

§ 3 Морфологическое описание

§ 4 Информационное описание

§ 5 Цели и задачи структурного анализа

§ 6 Задача структурного анализа

6.1 Формализация описания структуры на основе теории графов

§ 7 Описание и анализ потоков в БСУ

§ 8 Информационное взаимодействие элементов системы

§ 9 Топологическая декомпозиция структур

§ 10 Алгоритм декомпозиции

§ 11 Структурно-топологические характеристики систем и их применение

Глава 2. Модель структурного сопряжения элементов в БСУ

Глава 3. Агрегативные модели функционирования БСУ

§ 1 Общая модель функционирования

§ 2 Основные классы структур систем с под (???) управления

Глава 4

§ 1 Параграф

1.2 Организация многоуровневой структуры управления

§ 2 Глобальная задача оптимизации.

2.1 Уровень САР

2.2 Уровень САУ

2.3 Уровень координации

2.4 Уровень оперативного управления и принятия решений

§ 3 Оптимальное управление

3.1 Постановка задачи управления

§ 4 Целочисленность переменных

Глава 5. Элементы линейного программирования

§ 1 Общая задача линейного программирования

§ 2 Транспортная задача

§ 3 Постановка задачи оптимального управления

§ 4 Задача оптимального управления

§ 5 Основные принципы вариационного исчисления

§ 6 Каноническая форма уравнений Эйлера

§ 7 Вариационные задачи при наличии ограничений

§ 8 Метод неопределённых множителей Лагранжа

§ 9 Принцип максимума Понтрягина (1956;61 гг.)

Глава 6. Элементы динамического программирования

§ 1 Оптимизация непрерывных систем

§ 2 Оптимизация дискретных систем

Глава 7. Методы решения экстремальных задач при отсутствии ограничений

§ 1 Градиентные методы

§ 2 Методы, использующие случайный поиск (Нелокальный метод)

§ 3 Метод оврагов (нелокальный метод)

Глава 8. Структурный синтез

§ 1 Постановка задачи структурного синтеза

§ 2 Классические задачи принятия решений

§ 3 Граф процесса поиска допустимого решения

§ 4 Алгоритмическая теория сложности

§ 5 Теория информационной сложности

§ 6 Теория вычислительной сложности

§ 7 Теория сложности

Глава 9. Задачи принятия решений на расширенных множествах по скалярному критерию

§ 1 Постановка задач

1.1 Задача. Идентификация типов внешних воздействий

1.2 Задача. Идентификация неопределённостей

1.3 Задача. Выбор критериев

1.4 Задача. Выработка технического задания

1.5 Задача. Выработка технического задания совместно с критерием его оценки

1.6 Задача. Выбор области управления

1.7 Задача. Выбор модели объекта

§ 2 Общие процедуры принятия решений на расширенных множествах и графы структур решений

§ 3 Математическая постановка задачи принятия оперативных решений

3.1 Задача 2.9. Выбор алгоритма принятия оперативных решений

§ 4 Концепция доминантных условий в проблеме принятия решений

Глава 10. Методы и алгоритмы решения задачи выбора (назначения) в классической постановке на расширенных множествах альтернатив.

§ 1 Постановка задач

§ 2 Точные методы решения классической задачи выбора

2.1 Методы линейного программирования.

2.2 Метод динамического программирования

2.3 Методы кратчайшего увеличивающего пути

§ 3 Приближённые методы решения классической задачи выбора

3.1 Методы локальных вариаций «текущей величины» и их вариации.

3.2 Методы, основанные на доминантных условиях первого типа.

§ 4 Алгоритмы решения классической задачи выбора на расширенных множествах альтернатив.

Сокращения и аббревиатуры

ИСУ — иерархическая система управления.

БСУ — большая система управления;

АСУ — автоматическая система управления.

Шейнкман Г. Б. Ярочкин В.И.

Технические средства телеобработки информации в АеНТИ

(метод. пособие) М 1988.

Экубайтис Эдуард Александрович Информация и средства ее обработки.

Рига, ИЭВТ, 1987

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

Параллельная обработка информации.

Высокопроизводительные системы обработки информации.

(ред. Грицык В. В. — Киев, Наукова думка, 1988)

Эф — не системы параллельной обработки информации.

[Информационно-вычислительные сети. Настоящее и будущее]

Network technology — Current and future. London, 1988.

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

В качестве отдельной перспективы развития ИВС рассматривается единая сеть цифровой связи (ISDN) и концепция взаимосвязи открытых систем (OSI). Концепция OSI предполагает создание серии стандартов под эгидой МОС, которая охватывает все уровни передачи информации от физического до человеко-машинного интерфейса, что позволяет любым ВС взаимодействовать друг с другом.

ISDN (скорость передачи данных 144 кбит/с) решит проблему высококачественной телефонной, фиксированной, телеи видеотексной связи, передачи данных и изображений, а также проведения телеконференций.

Учитываемые ограничения

Бусленко Н.П., Калашников В. В., Коваленко И. А. Лекции по теории сложных систем. — М.: Сов.рад., 1973.

Денисов А.А., Колесников Д. Н. Теория больших систем управления. Ленин, 1982.

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

Цвиркун А. Д. Структура сложных систем, М., Сов.р., 1975.

Расин Л. Г. Анализ сложных систем и элементы теории оптимального управления, М., Сов.р., 1976.

Игнатушенко В. В. Организация структур управляемых многопроцессорных вычислительных систем. — М.: Энергоатомиздат, 1984.

Барский А. Б. Параллельные процессы в вычислительных системах. Планирование и организация. — М.: Радио и связь, 1990.

Понятие БСУ перекликается с понятием сложной системы.

Необходимо найти четкие формальные признаки либо параметры, по которым можно было бы отличить большую систему от небольшой, сложную — от простой.

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

число взаимосвязанных элементов; отсутствие формальной математической модели функционирования;

способ описания.

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

С появлением АСУ: БСУ отождествляют с АСУ и т. д.

Лекция 1

§ 1−1. Понятие БСУ

Некоторые общие свойства и отличительные особенности БСУ:

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

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

Взаимодействие элементов в системе может происходить по каналам обмена информацией, энергией, материалами и др.

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

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

Взаимодействие элементов в системе и с внешней средой в большинстве случаев носит стохастический характер.

Система является эргономической.

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

Для включения в класс БСУ необязательно наличие полного перечня признаков, перечисленных выше.

Рассмотренные выше особенности БСУ, несмотря на отсутствие единого их определения, привели к необходимости разработки новых подходов к изучению подобных систем, объединенных общим названием — системный подход.

§ 1−2. Системный подход

Введем определения и понятия, принятые в общей теории систем:

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

Для любых систем характерно наличие интегративных качеств (свойств).

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

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

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

Можно выделить систему в виде целостного объекта из окружающей среды.

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

Модель — описание системы, отображающее определенную группу ее свойств; углубление описания — детализация модели.

Описание системы можно рассматривать с 3 точек зрения:

функциональной

морфологической

информационной

§ 1 Функциональное описание

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

Для построения общего функционального описания системы вводятся следующие понятия.

Состояние — множество существенных свойств, которыми система обладает в данный момент времени.

Внешняя среда — множество элементов, которые не входят в систему, но изменение их состояния вызывает изменение состояния системы.

Модель функционирования (поведения) системы — модель, предсказывающая изменение состояния системы во времени.

§ 2 Морфологическое описание

Морфологическое описание должно дать представление о строении системы.

Оно не может быть исчерпывающим. Изучение морфологии начинается с элементного состава. В результате возникает понятие структуры.

Структура — совокупность элементов и связей между ними.

§ 3 Информационное описание

Информационное описание системы должно давать представление об организации системы.

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

Необходимость конструирования современных БСУ привела к активному использованию системного подхода в технике, в результате чего появилась дисциплина «системотехника», охватывающая вопросы проектирования сложных систем.

Лекция 2 Структурный анализ БСУ

§ 4 Цели и задачи структурного анализа

Одной из важнейших характеристик всякой системы является ее структура.

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

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

Рис. 1

При анализе организационной структуры предприятия как объекта управления решаются следующие задачи:

Описание состава организации и построение ее структурной схемы.

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

Описание материальных, вещественных и информационных связей.

Построение обобщенной структурной информационной модели предприятия.

При анализе функциональной структуры:

Изучаются функцией управления в структурных подразделениях существующей системы.

Выбирается состав автоматизируемых функций.

Определяются их взаимосвязи.

Составляется обобщенная функциональная структура задач управления АСУП.

При анализе технической структуры:

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

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

§ 5 Задача структурного анализа

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

Существует 3 уровня описания связей между элементами.

Наличие связи Направление связи Вид и направление сигналов, определяющих взаимодействие элементов.

На 1-м уровне:

Система — неориентированный граф. Вершины — элементы системы. Ребра — связи между элементами.

Основные задачи:

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

Выделение циклов.

Определение min и max — ых последовательностей элементов (цепей), разделяющих элементы друг от друга.

На втором уровне: система — ориентированный граф, дуги — направление связей

Задачи структурного анализа

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

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

Основы подобной формализации описания структур заложены в теории графов

5.1 Формализация описания структуры на основе теории графов

5.1.1 Понятие связности графа

Для неориентированных графов вводится понятие слабой связности, или просто связности, если для всех вершин графа i и j существует цепь из вершины i в вершину j.

Граф G (V) — сильно связан (ориентированный граф), если для всех вершин графа i, j существует путь из вершины i в вершину j.

5.1.2 Порядковая функция на графе. Понятие уровня

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

Полученные непересекающиеся подмножества — уровни.

Алгоритм упорядочения

В подмножество нулевого уровня N₀ — все вершины i, у которых G^-1(i) = 0 (нулевой (пустой) столбец)

Проводится последовательная нумерация вершин: 1, 2, …, l. Строка — куда выходят связи, столбец — что входит в вершину.

В подмножество первого уровня N₁ — все вершины i, у которых (те вершины, в которые входят духи только из вершин N₀ уровня).

Проводится последовательная нумерация вершин: l + 1, l + 2, …, l + r.

Второй уровень N₂: .

Нумерация: l + r +1, l + r + 2, …, l + r + p.

Данный процесс повторяется до тех пор, пока не будут пронумерованы все вершины графа. Изложенная процедура нумерации приводит к тому, что в матрице смежности вершин графа a_ij = 0 при i > j.

Рис. 2 Неупорядоченный граф

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

5.1.3 Числовая функция на графе

Числовая функция на вершинах графа считается заданной, если каждой i-той вершине a_i графа G (V), ставится в соответствие некоторое число l_i = l (a_i) из некоторого множества L.

Числовая функция на дугах (ребрах) считается заданной, если каждой дуге (a_ia_j) ставится в соответствие число q_i = q (a_ia_j) из некоторого множества Q.

Значение функции на пути S через вершины a₁, a₂, …, a_i () при задании числовой функции на вершинах графа определяется

(1)

или

(2)

Аналогично значения функции на пути через вершины при задании числовой функции на дугах (ребрах) графа

(3)

или

(4)

Определение максимального (минимального) путей на графе чаще всего формулируется в виде задачи динамического программирования:

так в соответствии с (2−3)

где — максимальное значение функции на путях S из вершины a₁ в вершину a_j.

— множество левых инциденций для a_j.

q (a_ia_j) — значение функции на дуге (a_ia_j).

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

Пример2. Определение максимального пути на графе

Рис. 4

Множество определяет все вершины, из которых можно непосредственно попасть в вершину i, называется обратным соответствием (столбец) — множество левых инциденций.

Для вершины a₁:

Для вершин a₂, a₃, a₄:

Для вершины a₅:

Для вершины a₆:

Для вершины a₇:

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

§ 6 Описание и анализ потоков в БСУ

БСУ отличаются информационной сложностью, т. е. для принятия решений требуются сбор, обработка и анализ больших объёмов информации.

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

На примере ЛСУП.

Источником информации в системе является документ.

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

Все документы могут быть классифицированы на:

Исходные — поступающие в систему

Временные — результаты переработки исходных

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

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

Между документами, входящими в поток существует отношения вхождения и порядка.

Отношение вхождения.

т. е. документ образуется непосредственно из документов .

Отношение порядка.

следует за. Это означает, что может быть образован только после .

Информационный граф:

Документы — вершины графа, отношения порядка и вхождения — дуги.

§ 7 Информационное взаимодействие элементов системы

Структура информационного графа задана матрицей смежности А.

Формальный анализ свойств последовательности матриц позволяет выявлять следующие свойства и параметры построенного информационного графа (n — число вершин):

Порядком элемента j называется длина наибольшего пути, связывающего j-й элемент с i-м (i=1, 2, …, n;). Порядок определяется по условиям:, , где — сумма элементов j-го столбца. Физический смысл — номер такта, к которому «готовы» все документы, формирующие j-й документ.

Число N =max () называется порядком информационного графа. Если для N справедливо:, то соответствующий граф называется n-тактным.

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

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

Аналогично, равенство 0 суммы элементов i-й строки A, служит признаком для выделения функциональных (конечных) результатов, а определяет число элементов, в которые входит i-й элемент.

Если при некотором i=j одновременно и, то к рассматриваемой схеме потока информации этот элемент не имеет отношения.

Число путей длиной k от элемента i к элементу j определяется элементом матрицы .

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

Максимальное значение порядка элементов i-й строки A, отличное от 0 определяет номер такта, после которого элемент i уже не используется.

Число тактов, в течение которых элемент i должен храниться в памяти, равно: .

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

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

§ 8 Топологическая декомпозиция структур

Проведение топологической декомпозиции структуры БСУ на основе представления её в виде ориентированного графа G (V) связано с выделением в ней отдельных сильно связанных подсистем.

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

R (i) = i G (i) G²(i) … G^p(i) …; (2−1)

G (i) — мн-во вершин, достижимых из вершины i с использованием путей длиной =1

G^p(i) — мн-во вершин, достижимых из вершины i с использованием путей длиной p.

При этом предполагается, что сама вершина i достижима с использованием пути длиной = 0 и включена в множество R (i).

Объединения в (2−1) прекращаются как только R (i) перестанет увеличиваться по размеру при очередной операции объединения.

С этого момента последующие операции не будут давать новых элементов множеству. Образовано достижимое R (i).

Число объединений зависит от графа, но число p не может быть больше числа вершин в графе.

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

Q (i) = (i) G^-1(i) G^-2(i) … G^-p(i) .; (2−2)

Где G^-2 (i) = G^-1 [G^-1 (i)] - множество вершин, из которых можно достигнуть i-й вершины, при этом длина пути = 2.

Объединение выполняется до тех пор, пока очередная операция не перестанет изменять текущее мн-во Q (i).

Мн-во R (i) Q (j) — мн-во таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от i-й вершины к j-й

Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин i и j

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

§ 9 Алгоритм декомпозиции.

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

Для первой вершины определяем R (1) и Q (1)

Находим сильно связанный подграф G1, включающий мн-во вершин V1 = R (1) Q (1)

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

Повторяем п 2−4 для новой вершины из оставшихся с наименьшим номером.

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

Рис. 5

Из (2−1) и (2−2) =>

R (1) = (1, 2, 4, 5, 6, 7, 8, 9, 10)

Q (1) = (1, 2, 3, 5, 6)

Отсюда находим мн-во вершин для сильно связного подграфа, содержащего вершину 1.

V₁ = (1,2,5,6)

Аналогично

R (3) = (3,4,7,9);

Q (3) = (3); => V₂ = (3);

R (4) = (4,7,9);

Q (4) = (4,7,9); => V₃ = (4,7,9);

R (8) = (8,10);

Q (8) = (8,10); => V₄ = (8, 10)

§ 10 Структурно-топологические характеристики систем и их применение

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

Рассмотрим некоторые структурные характеристики:

Связность структуры: данная характеристика позволяет выявить наличие обрывов в структуре, висящие вершины и др.

Связность элементов ориентированного графа определяется матрией связности С = |Cij| - выч-ся на основе

С_ij = 1, если a_ij >= 1; C_ij = 0, если a_ij = 0;

Для неориентированных графов связность всех элементов:

(5) — минимально необходимое число связей,

где n — кол-во вершин

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

(6)

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

Структурная компактность. Близость двух элементов i и j между собой будем определять через минимальную длину пути для ориентированного графа (цепи — для неориентированного) dij

(7) ,

Структурная компактность может быть охарактеризована диаметром структуры d

(8)

Степень централизации в структуре — вводится понятие индекса центральности.

(9)

Z_max — max величины ==>

(10), i =1,2…n; i ≠ j

= 1 (рисунок в) — максимальная степень централизованности

= 0 (рисунки б, д) — равномерное распределение связей

(куча рисунков)

5. Ранг элемента используется при представлении структуры системы в виде ориентированного графа. Хар-ка позволяет распределить элементы системы в порядке их значимости, которая определяется только числом связей данного элемента с другими.

(11) ,

где a_ij^(k) — элементы матрицы A^k (k = 3.4)

Чем выше ранг элемента, темболее сильно он связан с другими элементами.

Рассчитаем количественные характеристики для основных видов структур (число элементов = 5).

Таблица 1

Из таблицы видно, что:

Для несвязных структур R<0; (е) Для последовательной, радиальной, древовидной (а, в, г) => R = 0 (без избыточности) Для кольцевой и полного графа (б, д) R>0 — с избыточностью.

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

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

Глава 2 Модель структурного сопряжения элементов в БСУ

Для построения модели делается ряд допущений.

Входной сигнал x (t), поступающий к элементу в момент t рассматривается как совокупность элементарных сигналов x1(t), x2(t),…, xn (t), одновременно возникающих на входах элемента. Аналогично для выходного сигнала.

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

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

Итак, пусть система S состоит из N элементов. Для i-го элемента C_i имеем X⁽ⁱ⁾ — множество входных сигналов x⁽ⁱ⁾, (x⁽ⁱ⁾ X⁽ⁱ⁾), Y⁽ⁱ⁾ — множество входных сигналов y⁽ⁱ⁾, (y⁽ⁱ⁾ Y⁽ⁱ⁾)

Внешнюю среду можно представить в виде фиктивного элемента системы C₀, причем сигнал, выдаваемый системой во внешнюю среду, принимается внешней средой как входной сигнал x⁽⁰⁾(t) = [x₁⁽⁰⁾(t), x₂⁽⁰⁾(t),…, x_n⁽⁰⁾(t)], а сигнал, поступающий в систему из внешней среды => выходной сигнал элемента C₀ y⁽⁰⁾(t) = [y₁⁽⁰⁾(t), y₂⁽⁰⁾(t),…, y_n⁽⁰⁾(t)]

Для любого элемента, включая и внешнюю среду, имеем множество входных контактов и множество выходных контактов

Введем некоторый оператор, где ;

Определение 1. R — называется оператором сопряжения Он задается в виде таблицы, в которой на пересечении строк с номерами элементов системы (i) и столбцов с номерами контактов (j) располагаются пары чисел (k, l), указывающие номер элемента (k) и номер контакта (l), с которым соединение контакт X_j⁽ⁱ⁾.

Пример 1. Одноуровневая схема сопряжения (i-ый столбей — входы элементов, а содержимое таблицы — выходы)

Пусть дана система и оператор сопряжения R в таблице.

Рис. 12 Одноуровневая схема сопряжения

Определение 2. Сопряжение: входы рассматриваемого элемента в с выходами элементов из таблицы.

Таблица 1.

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

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

Подсистема Sм как самостоятельная система должна иметь контакты X_j^(0)м и Y_l^(0)м, характеризующие источники и потребители внешней среды, а как элемент системы S, подсистема Sм должна содержать входы X_j^м и выходы Y_l^м контакты для связи с другими подсистемами.

Контакты при j = l объединяются в «двойные» контакты на границах подсистемы Sм.

Пусть .

(12) —как самостоятельная система — как элемент системы

Аналогично и для подсистемы S₂.

(13) — как самостоятельная система

— как элемент системы

A. Введем оператор, м = 1;2 с областью определения

(14), принимающей значения из множества

, который данному входному контакту X_j⁽ⁱ⁾ `элемента C_i подсистемы Sм ставит в соответствие выходной контакт Y_l^(k) той же подсистемы, соединенной с X_j⁽ⁱ⁾ элементарным каналом (если такие <�кривой скан — ничего не разобрать> существуют)

R_м⁽¹⁾ — внутренний оператор сопряжения Sм (м = 1,2)

Операторы сопряжения R₁⁽¹⁾ и R₂⁽¹⁾ предоставлены в таблицах 2 и 3. В паре: (№ элемента; № контакта). Содержимое таблицы есть выходные контакты.

Рис. 13 Схема с операторами сопряжения

B. Рассмотрим теперь Sм как элемент системы S. Она характеризуется множеством входных и выходных контактов. и. Внешняя среда — подсистема S₀ с входными контактами и выходными контактами. Введем оператор, реализующий отображения множества всех входных контактов подсистемы S₀, S₁, …, S_м системы S в множество всех выходных контактов, который данному контакту ставит в соответствие контакт, соединенный с элементарным каналом, если такое соединение в с существует.

Определение 3. R^(k) — оператор сопряжения подсистем в системе с или оператор 2-го уровня.

Таблица 2.

Определение 4. Совокупность внутренних одноуровневых схем сопряжения всех подсистем с_м (м=1,2) вместе со схемой сопряжения 2-го уровня называется двухуровневой схемой сопряжения системы с.

Определение 5. Канал С_jC_k — последовательность элементов С_j, С_j+1, …, С_k, когда каждый предыдущий элемент является источником сигналов для последующего.

Определение 6. Сквозной канал — если последовательность начинается вход и заканчивается выходным .

Определение 7. Канал управления — если С_k элементы в последовательности обмениваются входными или выходными управляющими сигналами, причем С_k-1 управляет элементом С_k, иначе каналом следования

Контур — канал в случае, когда — источник для .

Контур следования — если выходные сигналы любого элемента воспринимаются только как входные, но не управляющие для следующего элемента.

Контур управления — если выходные сигналы хотя бы одного из элементов, входящих в контур воспринимаются следующим в качестве управляющих.

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

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

Элементы, принимающие входящие или управляющие сигналы от внешней среды (вх. полюса).

Элементы, выдающие выходные сигналы полностью или частично во внешнюю среду (вых. полюса).

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

Глава 3. Агрегативные модели функционирования БСУ.

§ 11 Общая модель функционирования

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

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

Функционирование системы во времени рассматривается как процесс перехода системы из состояния в состояние. Прежде необходимо определить множество состояний Z. Возможны различные способы определения состояний:

A. Состояние системы определяется как совокупность состояний элементов системы. Если элементы системы могут находиться в 2-х состояниях, то система из n элементов может находиться в одном из состояний. Так определяется состояние дискретных автоматов в ВТ, сложных систем при анализе надёжностных характеристик, кодирующих и декодирующих преобразователей в технике передачи данных и др. Таким образом,, где z-дискоетно.

B. Состояние системы характеризуется некоторым целым неотрицательным числом z (z =0, 1, 2, 3, …). Так определяется состояние при анализе сложных информационных систем с одной фазой обслуживания.

— число задач, запросов, находящихся в системе (на обслуживании либо в очереди).

Состояние системы описывается набором целых неотрицательных чисел:

где — число требований вй фазе; — число фаз.

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

Состояние системы определяется набором действительных чисел.

Например, положение самолета можно в данный момент времени описать вектором фазовых координат, где — наклонная дальность, — азимут, — угол места.

Состояние рассматриваемой БСУ описывается некоторым набором характеристик, где — заданные множества, а множество возможных состояний БСУ определяется как прямое произведение множеств :

— пространство состояний системы.

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

На вход любой сложной системы могут поступать входные сигналы, где — множество входных сигналов. Входной сигнал, поступающий в систему в момент, обозначим .

— входной сигнал,

— дискретное или непрерывное множество.

— пространство входных сигналов,

входной сигнал — точка пространства с координатами .

Множество входных сигналов; при этом — означает отсутствие сигнала в момент .

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

Система способна выдавать выходные сигналы, где — множество сигналов.

Выходной сигнал в момент обозначим .

Если описывается набором таких, что , — заданные множества, то — пространство выходных сигналов .

Аналогично — выходной процесс.

Мы будем рассматривать динамику только для классических БСУ, называемых системами без последействия.

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

Различают 2 класса БСУ без последействия:

Детерминистические

Стохастические

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

Оператор переходов определяет динамику переходов системы из состояния в состояние:

где

— начальное состояние, ;

— множество всевозможных участков входного процесса, соответствующих интервалу .

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

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

Траектория системы является проекцией фазовой траектории на пространство. Оператор переходов должен удовлетворять следующим двум основным условиям:

;

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

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

Оператор выходов системы определяет динамику выходных сигналов:

.

Оператор из ставит в соответствие определенный элемент (пространства состояний).

Однако, на выходе может быть (отсутствие выходного сигнала в момент).

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

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

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

;

где — элементарные случайные события, которые независимо выбираются из в соответствии с вероятностными мерами, , .

При этом, если и фиксированы, то стохастическая система называется системой со случайными начальными состояниями;

Если и фиксированы, то стохастическая система называется системой со случайными переходами;

Если и фиксированы, то стохастическая система называется системой со случайными выходами;

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

Основной метод построения моделей функционирования БСУ состоит в функциональной декомпозиции системы, которая требует раскрытия структуры системы (состав элементов, их функций и их взаимодействия). Модель функционирования часто носит иерархический характер.

Такой подход во построении моделей функционирования систем разработан А. П. Бусленко (агрегативный подход).

Лекция 1. Управление в больших системах

§ 12 Основные классы структур систем с под (???) управления

Децентрализованная структура

Объекты управления по материальным, энергетическим, информационным ресурсам — независимы.

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

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

Централизованная структура

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

Достоинства:

Простота реализации процессов информационного взаимодействия.

Глобально-оптимальное управление системой в целом.

Нет пересылки промежуточных результатов.

Легко корректируются оперативно-изменяемые данные.

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

Недостатки:

Высокий объем запоминающих устройств.

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

Высокая суммарная протяженность каналов связи при наличии территориально рассредоточенных объектов управления.

Рис. 14

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

Понижение требований к объему используемой памяти, производительности и надежности каждого центра обработки и управления;

Уменьшение суммарной протяженности и стоимости каналов связи.

Недостатки:

Усложеннность информационных процессов в системе вследствие обмена данными между центрами обработки и управления и корректности хранимой информации;

Избыточность технических средств.

Рис. 15

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

Рис. 16

Главной причиной иерархического управления является несоответствие между сложностью управляемого объекта и способностью любого управляющего объекта получать и перерабатывать информацию. Многие объекты управления имеют собственную иерархию. Одновременно управляемая система имеют свою собственную иерархическую структуру, которая зачастую не совпадает с иерархией управляющего объекта. Управляемые процессы требуют своевременного формирования правильных решений, которые требуют постановки соответствующих задач управления. Их совокупность образует иерархию задач управления, которая часто сложнее иерархии объектов управления. Решение этой иерархии — главная функция объектов управления. Любой отдельный объект может решать разный, но ограниченный набор задач. И каждый объект имеет разную пропускную способность. Поэтому иерархия задач (?) следовательно иерархия органов управления, которая может быть сложнее иерархии задач.

Рис. 17

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

Последовательное вертикальное расположение подсистем, составляющих подсистему.

Приоритет действий или право вмешательства подсистем верхнего уровня действие нижних.

Зависимость действия подсистем верхнего уровня от фактического исполнения подсистем нижних уровней своих функций.

Лекция 4

Глава 2.

§ 1 Параграф

1.2 Организация многоуровневой структуры управления

Имеем следующие общие функциональные особенности:

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

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

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

В многоуровневой иерархии принятия решения по формированию управления в БСУ выделяют обычно 3 уровня:

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

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

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

Определение 8. Распространенной является иерархическая структура с двумя уровнями управления, которую называю централизованной структурой с автономным управлением.

Особенность: сочетание централизованного управления системой с локальным управлением отдельными объектами (либо группами).

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

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

максимальная автономность локальных центров в процессе управления с возможностью оптимального управления системой в целом;

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

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