Всё для Учёбы — студенческий файлообменник
1 монета
docx

Лекции по Автоматизации технологических процессов (Нечитайло С. А.)

1.1. Определение и состав автоматизированной системы.

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

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

Элемент системы – часть системы, не подлежащая расчленению на данном уровне рассмотрения. Нас не интересует на данном уровне внутреннее содержание элемента, а интересуют лишь его связи с другими элементами.

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

§ 1.1.1. Функциональная часть АС.

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

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

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

Рис.1.1.1. Общее представление функциональной подсистемы.

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

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

Применительно к АСУПу традиционно выделяют следующие функциональные подсистемы (п/с):

– п/с технической подготовки производства;

– п/с технико-экономического планирования;

– п/с оперативного управления производством;

– п/с материально-технического снабжения;

– п/с управления кадрами;

– п/с управления качеством продукции;

– финансовая п/с и т.п.

Цели этих подсистем следуют из их названия.

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

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

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

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

– задачи регулирования, т.е. сопоставления собранного круга данных с некоторыми запланированными (или нормативными) величинами;

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

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

– экономические (выдача заработной платы, премий, начисление штрафов),

– технологические (введение нового оборудования, изменение существующей технологии),

– административные (объявления благодарностей, административных взысканий и т.д.).

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

§ 1.1.2. Обеспечивающая часть АС.

Она включает в себя информационное, математическое, лингвистическое, программное и техническое обеспечения.

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

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

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

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

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

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

§ 1.2. Классификация АС.

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

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

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

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

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

Системы автоматизированного проектирования (САПР) – в них объектом управления является процесс проектирования изделий любой природы (станка, самолета, ЭВМ, АСУ и т.п.).

Следующий класс систем – АС научных исследований и комплексных испытаний (АСНИ). Здесь объектом управления является процесс исследования объекта любой работы (исследования процесса работы двигателя, полета самолета, работы реактора и т.п.).

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

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

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

§ 1.3. Основные принципы построения АС.

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

1. Принцип системного подхода.

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

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

2. Принцип новых задач.

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

3. Принцип первого руководителя.

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

Функциями заказчика являются:

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

– определение приоритетов и очередности ввода различных задач управления (совместно с разработчиками системы),

– участие в разработке информационной базы системы,

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

Функции разработчика (помимо перечисленных выше):

– разработка технического задания на проектируемую систему (совместно с руководством организации заказчика),

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

– разработка рабочего проекта (разработка форм документов, разработка рабочих программ, разработка инструкций по эксплуатации),

– внедрение разработанной системы в эксплуатацию (совместно с персоналом, эксплуатирующим систему).

4. Принцип непрерывного развития системы.

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

5. Принцип разумной типизации проекта.

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

6. Принцип автоматизации документооборота.

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

7. Принцип единой информационной базы.

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

8. Принцип однократности ввода и многократности использования информации.

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

9. Принцип комплексности задач и рабочих программ.

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

10. Принцип согласованности пропускных способностей различных элементов системы.

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

§ 1.4. Этапы разработки АС.

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

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

Рис.1.4.1. Укрупненный сетевой график разработки АС.

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

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

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

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

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

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

Операция – обоснование и выбор комплекса технических средств.

Операция – предварительный расчет экономической эффективности.

Событие – работа всех групп сводится в выпуск технического проекта, его корректировка, согласование, утверждение.

Операция – разработка и отладка рабочих программ.

Операция – связная отладка комплексов программ по задачам.

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

Операция – разработка и выпуск рабочих инструкций персоналу автоматизированной системы.

Операция – уточненный расчет экономической эффективности.

Событие – выпуск рабочего проекта.

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

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

Операция – передача в промышленную эксплуатацию.

Операция – возможна частичная модернизация и доработка системы.

Если рассматривать процесс создания системы еще более укрупненно, то можно выделить четыре ГОСТированных этапа (стадии):

1 стадия – предпроектная, (ее еще называют стадией ТЗ), здесь два крупных направления работ – это обследование и выпуск ТЗ.

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

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

4 стадия – внедрение. Здесь: опытная эксплуатация системы совместно с разработчиками этой системы. Затем промышленная эксплуатация, выполняемая силами работников объекта автоматизации.

§ 1.5. Задачи, решаемые на стадиях проектирования АС.

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

В таблице 1.5.1. приведены основные направления работ, выполняемых на стадии технического задания.

Таблица 1.5.2. посвящена перечислению задач стадии технического проектирования.

В таблице 1.5.3. приведены основные направления работ, выполняемых на стадии рабочего проектирования.

Таблица 1.5.1.

Стадия технического задания

Этапы Основные направления работ

Системный анализ проблемной области 1. Изучение целей проектируемой системы

2. Изучение организационной структуры

3. Изучение источников и потребителей информации

4. Изучение входной, промежуточной и выходкой информации

5. Изучение методов обработки данных, решения задач и принятия решений

6. Документирование

Разработка технического задания 1. Формулировка цели и назначения разработки

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

3. Формулировка специальных требований

4. Документирование

Таблица 1.5.2.

Стадия технического проектирования

Этапы Основные направления работ

1 2 Проработка общесистемных решений 1. Разработка общей структурной схемы

2. Разработка способов сопряжения с внешними абонентами и другими системами

3. Разработка общего алгоритма функционирования)

4. Документирование

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

2. Разработка функциональной схемы

3. Разработка информационной базы

4. Разработка математической модели

5. Алгоритмизация

6. Документирование

Разработка информационно-го обеспечения 1. Разработка состава и структуры информа-ционной базы

2. Распределение информации на машинных носителях

3. Организация обмена данными

4. Организация сбора, передачи и обработки информации

5. Разработка системы классификации и кодирования информации

6. Разработка форм документов

7. Документирование

Разработка программного обеспечения 1. Разработка структуры общего программного обеспечения

2. Разработка структуры операционной систе-мы и методов организации вычислительного процесса

3. Разработка алгоритмов обмена информацией с внешними абонентами по каналам связи

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

5. Разработка алгоритмов разграничения до-ступа к информации

6. Разработка состава и структуры специаль-ного программного обеспечения

7. Разработка пакета прикладных программ

8. Документирование

Проектирование комплекса технических средств 1. Обоснование и выбор состава и структуры комплекса технических средств

2. Разработка вычислительной системы

3. Разработка системы сбора и телеобработки

4. Разработка системы отображения информации

5. Оценка надежности комплекса технических средств

6. Документирование

Таблица 1.5.3.

Стадия рабочего проектирования

Этапы Основные направления работ

Разработка программного обеспечения 1. Разработка текстов программ

2. Разработка контрольного примера

3. Разработка программной документации: руководства программиста, руководства оператора, эксплуатационной программы и др.

4. Документирование

Разработка техпроцесса функционирования объекта проектирования 1 Разработка технологических процессов: сбора и передачи информации, обработки данных, оценки загрузки комплекса технических средств

2. Документирование

Разработка комплекса технических средств 1. Проектирование общего вида технических устройств

2. Изготовление сборочных чертежей

3. Изготовление принципиальных схем

4. Разработка технической документации: технического описания, инструкции по эксплуатации

5. Документирование

РАЗДЕЛ II. ЧЕЛОВЕК В КОНТУРЕ ОРГАНИЗАЦИОННОГО УПРАВЛЕНИЯ.

§ 2.1. Проблема принятия решений.

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

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

Ситуации, в которых осуществляется выбор, характеризуют следующие основные черты:

1) Наличие цели (целей).

Необходимость принятия решения диктуется только наличием цели, которую необходимо достичь. Если цель отсутствует, то и нет никакой необходимости принимать решение.

2) Наличие альтернативных линий поведения.

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

3) Наличие ограничивающих факторов.

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

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

– технические факторы (габариты, вес, энергопотребление, надежность, точность и т.п.),

– социальные факторы, которые учитывают требования человеческой этики и морали, а также, экологические требования.

Проблему принятия решений проиллюстрируем на примере выбора оптимального варианта проекта.

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

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

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

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

каким-то образом зависит от внутренних параметров

т.е. (2.1.1)

Таким образом, каждому варианту проекта или (что тоже самое) вектору внутренних параметров

(2.1.2)

соответствует вектор внешних параметров

(2.1.3) Будем называть допустимым вариантом проекта такой набор значений внутренних параметров:

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

Основными ограничениями, как следует из выше изложенного материала, являются:

1. Ограничения, вытекающие из ограниченности ресурсов:

(2.1.5)

Особо следует отметить ограничение на стоимость.

2. Ограничение, связанное со сроком разработки:

(2.1.6) 3. Ограничения, вытекающие из необходимости поддержания внешних параметров в заданном диапазоне:

(2.1.7)

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

(2.1.8) Теперь сформулируем задачу оптимального проектирования: ищется вариант проекта (набор внутренних параметров), который принадлежал бы множеству допустимых проектов (2.1.4) и обращал бы в оптимум вектор внешних параметров (2.1.3).

Иначе говоря, требуется найти

(2.1.9)

(2.1.10) где opt – оператор оптимизации. Он определяет выбранный принцип оптимизации.

§ 2.2. Процесс принятия решения.

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

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

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

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

Процесс принятия решения является сложной итерационной процедурой. Основные этапы этого процесса и их последовательность представлены на рисунке 2.2.1.

Рис. 2.2.1. Процесс принятия решений.

Комментарий к рисунку.

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

§ 2.3. Общая постановка задачи принятия решений.

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

– контролируемые (управляемые) факторы, выбор которых определяется лицом, принимающим решения. Обозначим их через X1, X2, …, Xl.

– неконтролируемые (неуправляемые) факторы. Они характеризуют условия, в которых осуществляется выбор; и лицо, принимающее решение, не может повлиять на их величину. В состав неконтролируемых факторов включают и время t. Неконтролируемые факторы, в зависимости от информированности о них лица, принимающего решения, можно разделить на три подгруппы:

– детерминированные неконтролируемые факторы – это неслучайные фиксированные величины, значение которых в точности известно. Обозначим их через A1, A2, …, Ap.

– стахостические неконтролируемые факторы – случайные величины с известными законами распределения. Обозначим их через Y1, Y2, …, Yq.

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

В соответствии с выделенными факторами, критерий оптимальности можно представить в следующем виде:

(2.3.1)

Величины X,A,Y,Z в самом общем случае могут быть скалярами, векторами, матрицами.

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

(2.3.2) причем это выражение может быть меньше или равно, равно, больше или равно

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

(2.3.3)

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

Таким образом, общая постановка задачи принятия решений может быть сформулирована следующим образом: при заданных значениях фиксированных и неконтролируемых факторов A1, A2, …, Ap стохастических неконтролируемых факторов Y1, Y2, …, Yq с учетом неопределенных факторов Z1, Z2, …, Zr найти ( оптимальное), принадлежащее областям их допустимых значений Wx1, Wx2, …, Wxl которые по возможности обращали бы в максимум (минимум) критерий оптимальности F.

§ 2.4. Классификация задачи принятия решений.

Воспользуемся классификацией, в основу которой положены три важных классификационных признака (рис. 2.4.1):

1. количество целей управления и соответствующих им критериев оптимальности;

2. наличие или отсутствие зависимости критерия оптимальности и ограничений от времени;

3. наличие случайных и неопределенных факторов, этот признак, называют признаком «определенность — риск — неопределенность».

По первому классификационному признаку ЗПР делятся на одноцелевые или однокритериальные (скалярные) и многоцелевые или многокритериальные (векторные) ЗПР.

По второму классификационному признаку ЗПР делится на статические (не зависящие от времени) и динамические (зависящие от времени) ЗПР. Динамическим ЗПР присущи две особенности:

1) в качестве критерия оптимальности в динамических ЗПР выступает не функция, как в статических ЗПР, а функционал, завися-

Рис. 2.4.1. Классификация ЗПР и методов их решения

щий от функций времени;

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

По признаку «определенность — риск — неопределенность» ЗПР подразделяют на три больших подкласса:

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

2) принятие решений при риске, или стохастические ЗПР.

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

3) принятие решений в условиях неопределенности. Любое принятое решение может привести к одному из множества возможных исходов, вероятности появления которых неизвестны.

§ 2.5. Общая постановка однокритериальной статической детерминированной ЗПР.

Пусть исход управляемого мероприятия зависит от выбранного решения (стратегии управления) и некоторых неслучайных, фиксированных факторов, полностью известных лицу, принимающему решение. Стратегии управления могут быть представлены в виде значений n-мерного вектора X = (x1, x2, …, xn) на компоненты которого наложены ограничения, обусловленные рядом естественных причин и имеющие вид

(2.5.1)

где Аi — некоторый массив фиксированных неслучайных параметров.

Условия (2.5.1) определяют область WX допустимых значений стратегий X.

Эффективность управления характеризуется некоторым численным критерием оптимальности F:

(2.5.2)

где С — массив фиксированных, неслучайных параметров.

Массивы, Ai и С характеризуют свойства объектов, участвующих в управлении, и условия протекания управления.

Перед лицом, принимающим решение, стоит задача выбора такого значениях вектора управления X = (x1, x2, …, xn) из области WX его допустимых значений, которое максимизирует значение критерия оптимальности F, а также значение этого максимума

(2.5.3)

где область WX представляется условием (2.5.1).

В (2.5.3) символы и обозначают максимально до-стижимое в условиях (2.5.1) значение критерия оптимальности F и соответствующее ему оптимальное значение вектора управления X.

Совокупность соотношений (2.5.1), (2.5.2) и (2.5.3) представляет собой общий вид математической модели однокритериальной статической детерминированной ЗПР.

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

Рассмотрим пример однокритериальной статической детерминированной ЗПР.

Пусть необходимо отображать некоторое количество информационных моделей (например, картографическую информацию). Для отображения любой из моделей всегда требуется решать n различных задач З1, З2, ..., 3n (отображение символов, отображение векторов, поворот и перемещение изображения, масштабирование и т.п.). Все задачи взаимно независимы. Для решения этих задач могут быть использованы m различных микропроцессоров М1, М2, ..., Мn. В течение времени T микропроцессор Mj, может решить aij, задач типа 3i, ( ; ), т. е. решить задачу 3i, несколько раз по одному и тому же алгоритму, но для различных исходных данных.

Информационную модель можно отображать только в том случае, если она содержит полный набор результатов решения всех задач 31, 32, ..., 3n.

Требуется распределить задачи по микропроцессорам так, чтобы число информационных моделей, синтезированных за время Т, было максимально. Иначе говоря, необходимо указать, какую часть времени Т микропроцессор Мj, должен занимать решением задачи 3i.

Обозначим эту величину через xij (если эта задача не будет решаться на данном микропроцессоре, то xij = 0).

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

Общее количество решений Ni задачи Зi полученных всеми микропроцессорами вместе.

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

Итак, имеем следующую математическую модель: требуется найти такиеxij, чтобы обращалась в максимум функция F

при

§ 2.6. Общая постановка однокритериальной статической задачи принятия решений в условиях риска.

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

При оптимизации решения в подобной ситуации стохастическую ЗПР сводят к детерминированной. Широко используют при этом следующие два принципа: искусственное сведение к детерминированной схеме и оптимизации в среднем.

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

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

Прием «оптимизация в среднем» заключается в переходе от исходного показателя эффективности Q, являющегося случайной величиной:

где X — вектор управления; A — массив детерминированных факторов; y1, y2, ..., yq — конкретные реализации случайных фиксированных факторов Y1, Y2, ..., Yq к его осредненной, статической характеристике, например к его математическому ожиданию M[Q]:

(2.6.1)

Здесь B — массив известных статистических характеристик случайных величин Y1, Y2, …, Yq; f (y1, y2, …, yq) — закон распределения вероятностей случайных величин Y1, Y2, ..., Уq.

При оптимизации в среднем по критерию (2.6.1) в качестве оптимальной стратегии будет выбрана такая, стратегия, которая, удовлетворяя ограничениям на область Qx допустимых значений вектора X, максимизирует значение математического ожидания F = М[Q] исходного показателя эффективности Q, т. е.

(2.6.2) В том случае, если число возможных стратегий i конечно и число возможных исходов j конечно , то выражение (2.6.2) переписывается в виде

(2.6.3)

где Qij — значение показателя эффективности управления в случае появления j-го исхода при выборе i стратегии управления; Pij — вероятность появления j-го исхода при реализации i-й стратегии.

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

Сравнение двух рассмотренных принципов оптимизации в стохастических ЗПР показывает, что они представляют собой детерминизацию исходной задачи на разных уровнях влияния стохастических факторов. «Искусственное сведение к детерминированной схеме» представляет собой детерминизацию на уровне факторов, «оптимизация в среднем» — на уровне показателя эффективности.

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

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

Для создания картографической базы данных необходимо кодировать картографическую информацию. Использование поэлементного кодирования приводит к необходимости использования чрезвычайно больших объемов памяти. Известен ряд методов кодирования, позволяющих существенно сократить требуемый объем памяти [например, линейная интерполяция, интерполяция классическими многочленами, кубические сплайны и т.п.]. Основным показателем эффективности метода кодирования является коэффициент сжатия информации. Однако значение этого коэффициента зависит от вида кодируемой картографической информации (гидрография, границы вида графической кодируемой информации и т.п.). Обозначим через значение коэффициента сжатия i-го метода кодирования для j-го вида информации. Конкретный район подлежащий кодированию, заранее известен. Однако предварительный анализ кар-тографической информации всего региона и опыт предыдущих разработок позволяет вычислить вероятность появления каждого из видов информации. Обозначим через Pi вероятность появления j-го вида.

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

§ 2.7. Принятие решений в условиях неопределенности.

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

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

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

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

В терминах «игр с природой» задача принятия решений может быть сформулирована следующим образом. Пусть лицо, принимающее решение, может выбрать один из m возможных вариантов своих решений: x1, x2, …, xm и пусть относительно условий, в которых будут реализованы возможные варианты, можно сделать n предположений: y1, y2, …, yn. Оценки каждою варианта решения в каждых условиях (xi, yi) известны и заданы в виде матрицы выигрышей лица, принимающего решения: A = |aij|.

Предположим вначале, что априорная информация о вероятностях возникновения той или иной ситуации yj отсутствует.

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

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

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

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

Критерий Сэвиджа. В каждом столбце матрицы находится максимальная оценка и составляется новая матрица, элементы которой определяются соотношением

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

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

Критерий Гурвнца. Вводится некоторый коэффициент α, называемый «коэффициентом оптимизма», 0< α <1. В каждой строке матрицы выигрышей находится самая большая оценка и самая маленькая .

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

При α = 0 критерий Гурвица трансформируется в критерий Вальда. Это случай крайнего «пессимизма». При α = 1 (случай крайнего «оптимизма») человек, принимающий решение, рассчитывает на то, что ему будет сопутствовать самая благоприятная ситуации. «Коэффициент оптимизма» α назначается субъективно, исходя из опыта, интуиции и т.п. Чем более опасна ситуация, тем более осторожным должен быть подход к выбору решения и тем меньшее значение присваивается коэффициенту α.

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

§ 2.8. Многокритериальные задачи принятия решений.

В примере, рассмотренном в предыдущем параграфе, имелся всего один критерий – F, но значительно чаще принимаемое решение описывается совокупностью критериев f1, f2, …, fk. Кроме того, каждый из этих критериев, назовем их локальными критериями, – характеризуется своим коэффициентом относительной важности. Обозначим эти коэффициенты через λ1, λ2, …, λk. Итак, совокупность локальных, или частных, критериев fq где , образует интегральный, или векторный, критерий оптимальности принимаемого решения. Обозначим это так: F = {fq}где F – интегральный критерий.

В свою очередь, коэффициенты относительной важности λq, λ = 1, …, k образуют вектор важности: .

Как и прежде, задача заключается в том, чтобы найти оптимальное значение X из области допустимых значений WX. Каждый локальный критерий характеризует одно какое-либо качество принимаемого решения. Например, в задаче выбора ЭВМ локальными критериями могут быть: стоимость, быстродействие, объем оперативной памяти, качество разработанного программного обеспечения и т.п. Совокупность этих локальных критериев образует интегральный критерий, различный для каждого типа машины, и с помощью интегрального критерия можно производить сравнение различных типов машин, или сравнение качества принимаемого решения. Формально оптимальное решение может быть условно записано следующим образом:

(2.8.1)

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

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

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

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

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

Случай 1 – пусть ЭВМ-1 лучше и по стоимости и по быстродействию, чем ЭВМ-2, и тогда, при переходе от ЭВМ-2 к ЭВМ-1 оба критерия «согласны» улучшить свои значения. Тогда говорят, что оба эти варианта лежат в области согласия, и очевидно, что выбирать следует первый вариант, а второй просто отбрасывается.

Случай 2 – Пусть у ЭВМ-1 лучше (меньше) стоимость, но худшее быстродействие, чем у ЭВМ-2. Выбирая ЭВМ-1, мы улучшаем решение по стоимости, но ухудшаем его по быстродействию, выбирая ЭВМ-2, мы ухудшаем решение по стоимости, но улучшаем по быстродействию.

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

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

Далее необходимо задаться некоторой «схемой компромисса», или, говоря иначе, раскрыть смысл оператора оптимизации – opt – выражения (2.8.1).

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

(2.8.2)

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

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

§ 2.8.1. Принцип равномерности.

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

Используются следующие реализации принципа равномерности: это принцип равенства, принцип квазиравенства и принцип максимина (maxmin).

Принцип равенства.

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

Таблица 2.8.1

1, 2, 3 – номера трех вариантов, один из которых надо выбрать;

f1, f2, f3 – некоторые локальные критерии (к примеру, f1 – быстродействие,f2 – объем оперативной памяти и т.д.). f13 – значение локального критерия f3 для первого варианта и т.п.

Пусть, например, f21 = f22 = f23, а остальные значения локальных критериев для первого и второго вариантов не равны между собой. Тогда вариант 2 признается лучшим.

В общем виде эта модель расписывается следующим образом:

Принцип квазиравенства.

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

Принцип максимина – maxmin.

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

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

§ 2.8.2. Принцип справедливой уступки.

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

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

Принцип абсолютной уступки.

Формально он может быть выражен с помощью следующего выражения:

В этом выражении J(+) – подмножество мажорируемых, т.е. увеличиваемых критериев;

I( ) – подмножество минорируемых, т.е. уменьшаемых критериев. Причем, как следует из определения, – абсолютное значение величин приращения, / – символ «такой, при котором».

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

Пример: пусть, как и прежде, значения локальных критериев заданы таблицей (2.8.1):

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

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

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

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

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

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

т.е. ищется сумма по строкам всех локальных критериев:

и та из этих сумм, которая окажется максимальной, соответствует лучшему варианту.

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

Принцип относительной уступки.

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

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

В каждом столбце находится максимальное значение локального критерия.

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

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

Или, для случая трех критериев: для каждой строчки вычисляется произведение:

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

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

§ 2.8.3. Принцип выделения одного оптимизируемого критерия.

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

Формально этот принцип может быть записан следующим образом:

§ 2.8.4. Принцип последовательной уступки.

Пусть теперь локальные критерии имеют различную важность и пусть, также, самым важным является критерий f1, вторым по важности является критерий f2 , третьим – f3 и т.д.

Сначала отыскивается вариант, обращающий критерий f1 в максимум. После этого, исходя из некоторых соображений (например, из точности, с которой мы знаем значение f1), на критерий f1 накладывается некоторая «уступка» и при ограничении выбирается вариант, обращающий в максимум второй по важности критерий f2. Совершенно аналогично, на критерий может быть наложена «уступка» и при соблюдении условий:

, выбирается вариант, обращающий в максимум следующий по важности критерий f3 и т.д.

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

Пример. Пусть имеется таблица 2.8.2:

Таблица 2.8.2

. Допустим, что мы согласны допустить «уступку» . Тогда, при условии , просматриваем варианты по первому критерию. В столбце «оставшиеся варианты» знаком «–» отмечен отбрасываемый вариант. Среди оставшихся вариантов находится лучший вариант по второму критерию, стало быть, выбираем первый вариант.

§ 2.8.5. Свертка локальных критериев.

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

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

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

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

(2.8.3)

(2.8.4) В этих соотношениях fq, q = 1, …, l – локальные критерии, которые необходимо максимизировать fq, q = l + 1, …, k – локальные критерии, которые необходимо минимизировать.

Соотношение (2.8.3) соответствует принципу абсолютной уступки, соотношение (2.8.4) – принципу относительной уступки.

§ 2.8.6 Способы нормализации локальных критериев.

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

В нормализованном пространстве критериев вместо действительного значения локального критерия рассматривается безразмерная величина

– действительная величина поделенная на идеальную величину.

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

1 способ. Идеальный вектор определяется некоторыми заданными значениями локальных критериев. Эти заданные значения может определить, например, заказчик разработки. Формальная запись:

Недостаток этого способа – полнейший субъективизм выбора.

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

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

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

§ 2.8.7. Способы задания и учета приоритета локальных критериев.

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

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

В том случае, если имеются равноприоритетные критерии, они выделяются скобками , т.е. критерии 3, 4, 5 – равноприоритетны и занимают третье место по важности. Это чисто качественный способ задания приоритетов. При таком способе обычно используется принцип «жесткого приоритета», т.е. не допускается ни малейшего снижения критерия, стоящего левее в ряду приоритета.

Вектор приоритета – это способ количественного задания приоритетов. Компоненты этого вектора определяют степень относительного превосходства двух соседних критериев из ряда приоритета, т.е. определяет, во сколько раз критерий fq важнее критерия fq+1, в том случае, если fq и fq+1,равны по важности, то, стало быть, и . Для удобства, всегда равно единице

Задание приоритета с помощью весового вектора. Весовой вектор представляет собой k-мерный вектор, компоненты которого связаны соотношениями:

Компонента показывает степень относительного превосходства критерия fq над всеми оставшимися критериями. Обычно, если необходимо количественно задавать приоритет критериев, то его задают в виде ряда приоритета, поскольку там сравнение идет только между двумя соседними критериями; затем с помощью соотношения:

(2.8.5)

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

Для случая 3-х локальных критериев соотношения (2.8.5) переписывается в виде

где

Раздел III. МОДЕЛИ СИНТЕЗА СТРУКТУРЫ АС

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

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

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

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

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

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

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

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

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

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

Все эти вопросы взаимосвязаны и образуют сложную проблему.

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

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

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

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

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

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

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

(3.1.1)

(3.1.2) (3.1.3)

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

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

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

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

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

§ 3.2.1 Частные критерии оптимизации.

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

(3.2.1) где множество задач, реализуемых в АСУ,

- множество обслуживающих узлов системы управления,

Wij затраты на реализацию i-й задачи в j-м узлe,

Кроме того, пусть ; xi j = 1, если i-я задача выполняется в j-м узле и xi j = 0 в противном случае.

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

(3.2.2) где tij - время решения i-й задачи в j -м узле.

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

(3.2.3)

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

§ 3.2.2. Ограничения в частных задачах синтеза.

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

(3.2.4)

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

(3.2.5) в) На общие затраты на реализацию задач в AС

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

(3.2.7)

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

(3.2.8) где λi - интенсивность поступления i-й задачи на решение. Возможны дополнительные требования к равномерности загрузки узлов.

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

(3.2.9)

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

(3.2.10) § 3.2.3. Первая частная задача синтеза оптимальной структуры АС.

Необходимо так распределить i задач между j узлами , чтобы обеспечить минимум общих затрат (3.2.1) или минимум общего времени решения (3.2.2) при исполнении огра-ничений на загрузку каждого из узлов (3.2.8), или на затраты в каждом j -м узле (3.2.7).

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

(3.2.11)

при (3.2.12)

(3.2.13) В этих соотношениях:

aij - затраты (время решения) i-й задачи в j-м узле;

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

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

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

Наиболее удобным для решения данного класса задач является метод "ветвей и границ". Применительно к данной задаче он за-ключается в направленном движении по вершинам дерева, полученного путем фиксирования части переменных xij, (xij = {0, 1}).

Вершины первого уровня получают, поочередно закрепляя пер-вую задача за первым узлом, вторым и т.д., т.е. фиксируя для j = 1, 2, 3, … при i = 1.

Вершины второго уровня получают, фиксируя для j = 1, 2, 3, … при i = 2 и т.д. Для каждой вершины находят оценку

(3.2.14)

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

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

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

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

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

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

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

Необходимо так распределить i задач между j узлами , чтобы обеспечить минимум общих затрат (3.2.1) или минимум общего времени решения (3.2.2) при выполнении ограничений на общее время решения (3.2.9) или общие затраты (3.2.6) соответственно.

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

(3.2.15)

при (3.2.16)

(3.2.17) В этих соотношениях:

аij затраты (время решения) i-й задачи в j-м узле;

bij время решения (затраты) i-й задачи в j-м узле;

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

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

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

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

(3.2.18)

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

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

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

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

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

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

Далее используется метод "ветвей и границ". В отличие от предыдущей задачи, ветвление осуществляется с учетом ограниче-ния (3.2.16), что существенно сокращает число рассматриваемых ва-риантов. Оценка для каждой вершины находится по элементам матрицы (3.2.15) аналогично предыдущей задаче (3.2.14). Ограничение при этом имеет вид

(3.2.19)

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

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

Необходимо так распределить i задач между j узлами , чтобы обеспечить минимум общих затрат (3.2.1) или минимум общего времени решения (3.2.2) при выполнении ограничений на общее время решения (3.2.9) и загрузку узлов (3.2.8), либо на общие затраты (3.2.6) и загрузку узлов (3.2.8) соответственно.

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

(3.2.20)

при (3.2.21)

(3.2.22) (3.2.23)

Для решения этой задачи прежде всего из матриц коэффициентов , , исключаются элементы, которые заведомо не могут войти в оптимальное решение. Исключение элементов bij и сij из матриц систем (3.2.21) и (3.2.22) осуществляется аналогично рассмотренной выше, т.е. исключаются все элементы, для которых не выполняется условие (3.2.18). Оценке для матрицы коэффициентов (3.2.20) находится аналогично оценка системы (3.2.14) в первой задаче.

§ 3.3 Примеры частных задач синтеза оптимальной структуры АС

Пример 1. [1] . Сначала решим методом "ветвей и границ" следующую задачу: найти минимум

(3.3.1)

при , (3.3.2)

, (3.3.3) , (3.3.4)

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

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

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

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

(3.3.6) где

i* число рассмотренных уровней ветвления.

Для исходного множества (обозначим его через "0") соотношение (3.3.6) имеет вид , т.е. из матрицы (3.3.5) выбираются минимальные числа, причем условие (3.3.2) мо-жет нарушаться. Итак,

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

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

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

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

Таблица 3.3.1 Таблица 3.3.2 Таблица 3.3.3

Из табл. 3.3.3 следует, что задача 3 должна быть закреплена за узлом один. Четвертая задача однозначно закрепляется за узлом 2.

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

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

Пример 2.

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

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

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

Пусть bj = |3 6 5 2|. Тогда после исключения имеет вид

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

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

Итак, x12 = 1. Имеем

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

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

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

(3.3.7)

При (3.3.8)

(3.3.9) (3.3.10)

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

Условие (3.3.8) не выполняется и задачу "в лоб" решить не удается. Приступим к упрощению матрицы. Для матрицы по-следовательно для всех элементов проверяется условие

(3.3.11)

где - рассматриваемый элемент;

blj - минимальные элементы строк;

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

Из матрицы выбираем минимальные элементы и подсчи-тываем время решения: 2 + 5 + 3 + 4 + 5 = 19 < 20. Задача решена. Если бы это не удалось, пришлось бы вести ветвление и каждый минимальный вариант проверять на условие (3.3.8). Итак, ответ:

[1] Пример имеет цель продемонстрировать процедуру ветвления.

Раздел IV. СТРУКТУРНЫЙ АНАЛИЗ АС.

§ 4.1. Цели и задачи структурного анализа АС.

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

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

– организационная структура и ее модель;

– функциональная структура и ее модель;

– алгоритмическая структура и ее модель;

– техническая структура и ее модель и т.п.

§ 4.1.1. Организационная структура.

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

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

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

– сокращение излишних подразделений или операторов;

– минимизация связей между этими элементами системы (подразделения и операторы);

– повышение пропускной способности этих связей;

– упорядочивание документооборота;

– ликвидация циклов в движении документов и т.п.

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

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

– определение функций отдельных подразделений и операторов;

– описание материальных и информационных связей;

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

§ 4.1.2. Функциональная структура.

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

Основные направления совершенствования функциональной структуры:

– устранение параллелизма в выполнении функций управления;

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

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

– создание максимально четких контуров ответственности.

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

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

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

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

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

§ 4.1.3. Алгоритмическая структура.

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

Основные направления совершенствования алгоритмической структуры:

– использование стандартных (типовых) алгоритмов обработки информации;

– повышение точности, скорости и надежности вычислений;

– сокращение требуемых объемов памяти;

– совершенствование отдельных алгоритмов.

При анализе алгоритмической структуры решаются следующие задачи:

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

– определение их информационно-логической взаимосвязи;

– определение последовательности их реализации.

§ 4.1.4. Техническая структура.

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

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

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

§ 4.2. Три уровня описания систем.

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

– наличие связей;

– наличие и направление связей;

– наличие и направление связей и вид и направление движения сигналов, которые определяются взаимодействием элементов.

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

Основные задачи, решаемые на этом уровне:

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

– выделение циклов;

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

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

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

– определение связности (целостности) системы;

– топологическая декомпозиция системы с выделением сильно связанных подсистем;

– нахождение входных и выходных полюсов системы и в соответствии с этим выделение пунктов приема и выдачи информации;

– выделение уровней в системе и определение их взаимосвязей;

– определение максимальных и минимальных путей;

– определение характеристик топологической значимости элементов;

– получение информации о слабых местах в структуре.

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

Основные задачи на этом уровне:

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

– построение моделей функционирования элементов системы и самой системы.

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

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

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

§ 4.3.1. Способы формализованного задания графа.

А. Графическое представление.

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

Б. Матричное представление.

Матрица смежности вершин для неориентированного графа имеет вид:

где n – число вершин графа,

Для ориентированного графа матрица смежности

задается следующим образом:

Матрица инциденций

где n – число вершин, m – число ребер, определяется следующим образом:

– для неориентированного графа

– для ориентированного графа:

Рис. 4.3.1 иллюстрирует это определение.

Рис. 4.3.1. Правило построения bij.

В. Множественное представление.

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

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

Таким образом, ориентированный граф задается перечислением (списком) множеств вида G(i), либо множеств вида G-1(i)для всех вершин графа. Такой способ оказывается наиболее компактным и эффективным при задании исходной информации о структуре для решения задач синтеза, особенно для иерархических структур.

Пример. Пусть структура системы представлена на рис. 4.3.2. Необходимо представить ее рассмотренными способами.

Рис. 4.3.2. Структура системы Рис. 4.3.3. Граф системы

Матрица смежности Матрица инцидентности

Множественное задание структуры: G(1) = (2,3), G(2) = 0, G(3) = (5,4), G(4) = (2), G(5) = (1,2).

Или G-1(1) = (5), G-1(2) = (1, 5, 4), G-1(3) = (1), G-1(4) = (3), G-1(5) = (3)

§ 4.3.2. Определение цепи, пути, цикла, контура.

Цепью называется такая последовательность ребер E0, E1, …, Ek-1, Ek, когда каждое ребро Ek-1 соприкасается одним из концов с ребром Ek. Цепь можно обозначить последовательностью вершин, которые она содержит. Например, для графа, представленного на рис. 4.3.4, цепью будет (1, 4, 3, 5) или (1, 3, 5) (рис. 4.3.5).

Рис. 4.3.4. Граф Рис. 4.3.5. Цепи

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

Путем называется такая последовательность дуг, когда конец каждой предыдущей дуги совпадает с началом последующей. Например, для графа (п. 4.3.1, рис. 4.3.2) последовательность дуг (1, 3), (3, 4), (4, 2) является путем (рис. 4.3.6). Понятие пути обычно используется для ориентированных графов.

Циклом называется такая конечная цепь, которая начинается и заканчивается в одной вершине. Например, на рис. 4.3.7, цепь (1, 4, 3) является циклом. Понятие цикла имеет смысл только для неориентированных графов.

Контуром называется такой конечный путь, у которого начальная вершина первой дуги совпадает с конечной вершиной последней дуги. Для графа (п. 4.3.1,рис. 4.3.2) последовательность дуг (1, 3), (3, 5), (5, 1) есть контур (рис. 4.3.8).

Рис. 4.3.6. Путь Рис. 4.3.7. Цикл Рис. 4.3.8. Контур

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

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

Элемент матрицы определяет число путей длиной l от вершины i к вершине j.

Например.

Рис. 4.3.9. Пример элементов матрицы Аl.

§ 4.3.3. Степень вершины.

Число ребер, инцидентных вершине i неориентированного графа, называют степенью вершины i и обозначают r(i).

Для графа, представленного на рис. 4.3.10,

Или в общем виде , где n – число вершин графа, m – число дуг графа.

Число дуг ориентированного графа, которые имеют начальной вершиной вершину i, называют полустепенью исхода вершины i и обозначают через ρ+i(i). Аналогично, число дуг, которые имеют своей конечной вершиной вершину j, называют полустепенью захода вершины j и обозначают через ρ-j(i). Для графа, представленного на рис. 4.3.3 в §4.3:

где m – число дуг графа, n – число вершин графа.

§ 4.3.4. Понятие связности графа.

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

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

Граф на рис. 4.3.10 является слабо связным. На рис. 4.3.11 представлен сильно связный граф, на рис. 4.3.12 – несвязный, распадающийся на два сильно связных подграфа.

Рис. 4.3.11. Сильно связанный граф Рис. 4.3.12. Несвязный граф, распадающийся на два сильно связанных подграфа

§ 4.3.5. Порядковая функция на графе. Понятие уровня. Триангуляция.

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

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

– В подмножество нулевого уровня N0 включаются все вершины i, для которых G-1(i) = 0 (иначе говоря, для которых не существует множества левых инциденций, или, еще проще – вершины, в которые ни откуда нельзя попасть). Проводится последовательная нумерация этих вершин: 1, 2, …,l.

– В подмножество первого уровня N1 включаются все вершины i, для которых , т.е. для которых вершины уровня N0 являются множеством левых инциденций. Проводится последовательная нумерация этих вершин: i + 1, i + 2, …, i + r.

– В подмножество второго уровня N2 включаются все вершины i, для которых . Проводится последовательная нумерация вершин: i + r + 1, i + r + 2, …, l + r + p.

– В подмножество третьего уровня N3 включаются все вершины i, для которых . Проводится последовательная нумерация вершин и т.д.

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

Рассмотренный алгоритм нумерации приводит к тому, что в матрице смежности вершин графа aij = 0 при i > j т.е. матрица становится треугольной.

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

Пример.

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

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

Составляем матрицу смежности анализируемого графа.

В соответствии с рассмотренным алгоритмом переходим к множественному представлению графа. (Напомним, что множество левых инциденций G-1(i) определяет все вершины, из которых можно непосредственно попасть в вершину i). Из исходного множествен-

Матрица смежности

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

Результаты преобразований сведены в таблице 4.3.1.

Таблица 4.3.1

Уровень Условия включения Включаемые вершины Новая нумерация

(1, 10) (1. 2)

(5, 8, 9) (3, 4, 5)

(6, 7) (6, 7)

(2) (8) (3, 4) (9, 10)

На основании таблицы строим преобразованный граф. Его вершины в новом обозначении размещаем по найденным уровням (внутри кружков помещаем новые обозначения, рядом – старые). Соединяем старые обозначения вершин дугами в соответствии с ранее найденной матрицей смежности (рис. 4.3.14).

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

Рис. 4.3.14. Упорядоченный граф.

Матрица смежности

*** главная диагональ матрицы смежности.

Если рассматривать уровни как такты движения информации, то рис. 4.3.14 непосредственно дает ответы на вопросы, сформулированные в начале примера.

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

1. Составляется матрица инциденций по правилам, изложенным выше.

2. Из матрицы вычеркиваются строчки, состоящие только из 0 и +1, и столбцы, соответствующие +1.

3. Отмечается порядок вычеркивания. Уровни соответствуют порядку вычеркивания.

4. На последнем этапе на соответствующем уровне размещаются оставшиеся вершины.

5. Уровень будет равен порядку вычеркивания минус единица.

В качестве примера рассмотрим граф, представленный на рис. 4.3.15.

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

Исходная матрица инциденций .

(Проверять равенство нулю суммы элементов по всем таблицам).

* – обозначение пустой клетки.

Первое вычеркивание. Вычеркнуты вершины 1 и 10.

Второе вычеркивание. Вычеркнуты вершины 5, 8 и 9.

Третье вычеркивание. Вычеркнуты вершины 6 и 7.

Результат четвертого вычеркивания.

Вычеркнута вершина 2.

Оставшиеся вершины 3 и 4 размещаются на следующем уровне.

Результат сводим в таблицу 4.3.2:

Таблица 4.3.2

Порядок вычеркивания 1 2 3 4 5

Вершины 1, 10 5, 8, 9 6, 7 2 3, 4

Уровни 0 1 2 3 4

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

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

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

Множество вершин, достижимых из вершины i, называется достижимым множеством R(i). Достижимое множество определяется следующим образом:

(4.4.1)

где G(i) – множество вершин, достижимых из вершины i с использованием пути длинной, равной единице;

– множество вершин, достижимых из вершины i с по мощью путей длинною l.

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

В соответствии с выражением (4.4.1) множество R(i) может быть получено последовательным слева направо объединением множеств до тех пор, пока текущее множество R(i) не перестанет увеличиваться по размеру при выполнении очередной операции объединения. Число объединений, естественно, зависит от вида графа, но, очевидно, всегда , где n число вершин графа.

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

Aналогично построению R(i) можно построить Q(i), используя следующее выражение:

(4.4.2)

где G 1(i) – множество вершин, из которых можно достигнуть i-ую вершину с помощью путей, длина которых равна единице, G 2(i) – то же самое, но с помощью путей, длина которых равна двум и т.д.

Рис. 4.4.1. Достижимые и контрдостижимые множества.

Так как R(i) является множеством вершин, достижимых из i-ой вершины, а Q(i) – множеством вершин, из которых можно достичь вершину j, то множество является множеством таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от i-ой вершины к j-ой, что иллюстрируется рис. 4.4.2. Эти вершины называются существенными или неотъемлемыми относительно двух кольцевых вершин i и j.

В свою очередь множество

(4.4.3) определяет сильно связный подграф графа G(V), содержащий i-ую вершину, поскольку все существенные вершины, принадлежащие множеству (3), достижимы из i-ой і вершины и, кроме того, из каждой такой вершины достижима вершина i, т.е. все эти вершины взаимодостижимы (рис. 4.4.3).

Рис. 4.4.2. Существенные вершины Рис. 4.4.3. Сильно связанный подграф

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

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

1. В исходном графе G(V) производим нумерацию вершин;

2. Для i-ой вершины (i = 1) определяем множество R(1) и множество Q(1);

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

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

Далее пункты 2, 3, 4 повторяются для i = 2, 3, 4, … до тех пор, пока все вершины исходного графа не будут сгруппированы в соответствующие сильно связные подграфы.

Пример.

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

Рис. 4.4.4. Исходный граф

В соответствии с рассмотренным алгоритмом определяем множества R(1) и G(1).

Полагаем i=1 и находим, используя формулы (4.4.1) и (4.4.2), достижимое R(1) и контрдостижимое Q(1) множества:

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

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

Используя соотношение (3), находим сильносвязный подграф, содержащий вершину 1:

V1 = (1, 2, 5, 6).

После удаления сильносвязного подграфа G1(V1) исходный граф G(V) имеет вид, представленный на рис. 4.4.5.

Рис. 4.4.5. Граф после удаления G1(V1).

Полагаем i = 2, но вершина 2 входит в выделенный подграф V1, cледовательно, i = 3.

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

Q(3) = (3), V2 = (3). Удаляем сильносвязный подграф G2(V2) (рис. 4.4.6).

Рис. 4.4.6. Граф после удаления G1(V1) и G2(V2).

Полагаем i = 4, тогда

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

Q(4) = (4, 7, 8, 9, 10),

V3 = (4, 7, 9).

Удаляем сильносвязный подграф G3(V3) (рис. 4.4.7).

R(8) = (8, 10)

G(8) = (8, 10) V4 = (8, 10).

Рис. 4.4.7. Граф после удаления

G1(V1), G2(V2) и G3(V3).

Итак, окончательно имеем:

1. G1(V1) = G1(1, 2, 5, 6).

Рис. 4.4.8. Подграф G1.

2. G2(V2) = G2(3).

Рис. 4.4.9. Подграф G2.

3. G3(V3) = G3(4, 7, 9).

Рис. 4.4.10. Подграф G3.

4. G4(V4) = G4(8, 10).

Рис. 4.4.11. Подграф G4.

Объединяем полученные сильносвязные подграфы в соответствии с исходным графом:

Рис. 4.4.12. Сильно связанные подграфы

Или окончательно:

Рис. 4.4.13. Результат декомпозиции

§ 4.5. Описание и анализ потоков информации в АС.

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

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

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

означает, что документ Xj каким-то образом формируется из документов .

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

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

Если элементом потока информации X1, X2, …, Xn поставить в соответствие вершины графа X1, X2, …, Xn и каждую пару вершин и соединить дугой, идущей от Xi к Xj, в том и только том случае, если Xi является входом для Xj, то полученный граф называют информационным графом.

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

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

либо n раз, N < n где n – число вершин.

Для возведения матрицы А в степень удобно воспользоваться рекуррентным соотношением

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

Рассмотрим эти свойства.

1. Порядком πj элемента Xj (для краткости в дальнейшем просто j) называется длина наибольшего пути, связывающего j-тый элемент с i-тым .

Формально πj определяется с помощью следующего соотношения:

(*)

В этом соотношении σj (λ) – есть сумма элементов j-того столбца матрицы А, т.е.

Например, пусть мы хотим найти элементы первого порядка, стало быть полагаем πj = 1. Обращаемся к 1-ой строке соотношения (*), то есть λ = 1 и мы должны обратиться к матрице A1. Пусть матрица A1 имеет следующий вид (рис. 4.5.1):

Рис. 4.5.1. Фрагмент матрицы А.

В соответствии с первой строкой выражения (*) выписываем те j, для которых σj > 0. Это j=3,4,5.

Теперь обращаемся ко 2-ой строке соотношения (*). Добавляем 1, следовательно, λ = 2 и нам следует обратиться к матрице A2.

Пусть матрица A(2) имеет вид (рис. 4.5.2):

Рис. 4.5.2. Фрагмент матрица A2.

В соответствии со 2-ой строчкой соотношения (*) выписываем такие j, для которых si = 0. Это j = 1, 2, 3. Совместно соотношение (*) выполняется только для j = 3. Стало быть, в данном примере элемент x[3] есть элемент первого порядка. Для того, чтобы найти элементы второго порядка, надо положить πj = 2 и, обратившись к матрицам A2 и A3, проделать те же самые процедуры.

Физический смысл pj – это номер такта, к которому "готовы" все составляющие элемента xj.

2. Число называют порядком информационного графа. Если для N справедливо соотношение

, (**)

то соответствующая схема называется N-тактной.

Записанное условие возможно только в случае отсутствия контуров.

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

4. Равенство нулю суммы элементов j-того столбца матрицы смежности, т.е. σj (λ = 1) = 0 является формальным признаком для выделения входных элементов потока. Значение k = σj (λ = 1) > 0 равняется числу элементов, участвующих в формировании элемента Xj.

Пусть матрица А имеет вид, представленный на рис. 4.5.3.

Рис. 4.5.3. Фрагмент матрица А.

Из матрицы следует, что элементы 1, 2, 3 – входные элементы и, например, для формирования X5 требуется 4 других элемента.

5. Аналогично свойству 4, равенство нулю суммы элементов i-той строки матрицы смежности информационного графа σj (λ = 1) = 0 служит формальным признаком для выделения выходных элементов потока, а число L = σj (λ = 1) > 0 равно числу элементов, в которые входит элемент . Например, судя по предыдущей матрице, X1 используется дважды.

6. Если при некотором i = j одновременно

то к анализируемой схеме этот элемент не имеет отношения (ошибка обследования).

7. Число путей длиною l от элемента Xi к элементу Xj определяется элементом aij (l) матрицы Aλ.

8. Число всевозможных путей от элемента Xi к элементу Xj определяется элементом aij (å) матрицы A(å) где

Матрица A(å) есть сумма всех одноименных элементов всех матриц Aλ.

9. По аналогии со свойствами 4 и 5 отличные от нуля элементы j-того столбца матрицы достижимости A(å) указывают все элементы потока, которые участвуют в формировании Xj, а отличные от нуля элементы i-той строки этой матрицы указывают, все элементы при формировании которых используется элемент Xi.

10. Максимальное значение порядка элементов i-той строки матрицы смежности A, которые не равны нулю, определяет номер такта , после которого элемент Xi уже не используется и он может быть "погашен" в памяти системы.

Например.

Рис. 4.5.4.Фрагмент матрицы А.

Пусть мы нашли, что πj 0,0321. Тогда для элемента Х1 : τ1 = 3.

11. Число тактов, в течение которых элемент Хi должен храниться в памяти системы определяется соотношением ti = τi – πi.

Для нашего примера τi = 3 – 0.

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

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

Рис. 4.5.5. Исходный граф.

Прежде всего необходимо составить матрицу смежности исходного графа А.

Будем формально возводить матрицу А в степень до тех пор, пока Определяем матрицу достижимости А(å) как сумму одноименных элементов всех предыдущих матриц.

Рис. 4.5.6. Матрица смежности исходного графа.

Последовательность матриц A(λ) и позволяет выяснить свойства анализируемого потока.

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

Для определения i-той строчки матрицы A(λ) ai(λ):

1. Выписывается известная нам i-тая строчка матрицы A(λ 1) ai(λ 1);

2. В этой выписанной строчке отмечаются ненулевые элементы;

3. Из матрицы А выписываются строчки, соответствующими этим ненулевым элементам;

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

Определяем матрицу А2:

и т.д. Окончательно имеем:

Рис. 4.5.7. Матрица А2.

Определим матрицу А3:

и т.д.

Окончательно имеем:

Рис. 4.5.8. Матрица А3.

Матрица A4 = 0

Определяем матрицу достижимости

Рис. 4.5.9. Матрица достижимости А( ).

Определяем матрицу – достижимости.

Находим

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

Рассмотрим эти свойства в той же последовательности, в которой они излагалось в теории.

1. Определение порядка элементов.

Для этого используется система

Определяем элементы нулевого порядка, для чего полагаем

σj (λ = 0) > 0 для j = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, так как любое число в степени 0 матрицы A дает 1.

σj (λ = 0) = 0 для j = 1, 2, 3, 4 – это следует из матрицы A. Совместно указанное соотношение выполняется для j = 1, 2, 3, 4.

Следовательно элементы x1, x2, x3, x4, есть элементы нулевого порядка. Определяем элементы 1-го порядка, полагая πj = 1.

Совместно задание условия выполняется для j = 5, 6. Следовательно, x5, x6 – элементы первого порядка.

Полагаем πj = 2.

Совместно задание условия выполняется для j = 7, 10. Следовательно, x7, x10 – элементы второго порядка.

Полагаем πj = 3.

Совместно задание условия выполняется для j = 8, 9. Следовательно, x8, x9 – элементы третьего порядка.

2. Определение “тактности” системы.

Данная схема является трехтактной.

3. Отсутствие ненулевых элементов на главной диагонали свидетельтвует о том, что в анализируемом документообороте контуров нет.

4. Определение входных элементов потока.

σj (λ = 1) = 0 для j = 1, 2, 3, 4. Следовательно элементы x1, x2, x3, x4 входные элементы.

Например, σ6(λ = 1) = 2. Это означает, что в x6 входят два элемента и т. д.

5. Определяем выходные элементы потока.

σi (λ = 1) = 0 для j = 8, 9, 10. Следовательно элементы x8, x9, x10, – выходные элементы.

Например, σ5(λ = 1) = 3. Это означает, что x5 используются для формирования 3-х других элементов.

6. Определение висящих вершин.

Ситуация σj (λ = 1) = σi (λ = 1) = 0 отсутствует, т.е. висящих вершин нет.

7. Определение числа путей длиной l.

Например, σ28(λ = 2) = 2. Это означает, что от x2 к x8 имеют два различных пути длиною 2.

8 Определение всевозможных путей между двумя элементами

Например, σ18( ) = 3. Это означает, что от x1 к x8 имеют два различных пути длиною l.

9. Определение всех элементов, участвующих в формировании данного.

Например, отличные от нуля элементы 8-го столбца матрицы указывают все элементы потока, участвующие в формировании x5, т.е. x1, x2, x3, x4, x5, x7, причем, например, x5 – дважды, а, например ненулевые элементы 5-ой строки матрицы и указывают все элементы, при формировании которых используется x5, т.е. x7, x8, x9, x10, причем для формирования x5x8 используется дважды.

10. Определение номера такта, после которого данный элемент может быть погашен.

, например, уже не используется, τ1 = 3, т.к. судя по А для формирования x1 используется x5 с π5 = 1 и x8 с π8 = 3. Максимум равен 3.

11. Определение числа тактов хранения.

Например, : t1 = τ1 – π1 = 3 – 0 = 3.

12. Рассмотрим столбцы матрицы A( ), соответствующие выходным элементам.

Например столбец, соответствующий x8. Как указывалось, эта матрица задает число всех связей между элементами. В формировании x8 участвуют элементы x1, x2, , x4, x5, и x7, причем x1, и x2 – трижды, а x5 – дважды.

Наличие большого числа ненулевых и неединичных элементов в столбце j = 8 свидетельствуют о необходимости проведения содержательного анализа фрагмента общей схемы потока, связанной с формированием x8 (рис. 4.5.10). Быть может удастся упростить фрагмент за счет исключения излишних связей или промежуточных элементов.

Рис. 4.5.10. Фрагмент графа, связанный с формированием x8.

§ 4.6. Структурно – топологические характеристики систем и их применение.

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

§ 4.6.1. Виды топологических структур (на примере 5 элементов).

1) Последовательная структура.

2) Кольцевая структура. 3) Радиальная структура.

4) Древовидная структура.

5) Полный граф.

6) Несвязная структура.

Рис. 4.6.1. Виды топологических структур.

§ 4.6.2. Связность структуры.

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

(4.6.1.)

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

Соотношение (4.6.1.) можно переписать в виде

т.е. это не что иное, как число ребер в неориентированном графе.

Определим m как функцию от n для основных типов структур в общем виде.

– Последовательная структура. Очевидно m = n-1

– Кольцевая структура. Очевидно m = n

– Радиальная структура. Очевидно m = n-1

– "Дерево". Трудно сказать в общем виде, т.к. определяется видом дерева.

– Cтруктура "полный граф". Для 1-го элемента число связей n-1, т.к. он связан со всеми элементами, кроме себя. У 2-го элемента n-2 связей, т.к. нет связи с самим собой и связь с 1-ым мы уже учли. Аналогично у 3-го – n-3 и т.д. У n-го – 0, т.к. все связи учтены. Итак, имеем

Окончательно

– Для несвязной структуры эта характеристика не имеет смысла.

§ 4.6.3. Структурная избыточность.

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

(4.6.1.) все члены на n-1 и разность обозначим через R. Тогда будем иметь

(4.6.2)

(4.6.3) R-структурная избыточность.

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

1.Последовательная структура.

2.Кольцевая структура.

3.Радиальная структура.

4.Структура "полный граф".

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

Для систем с избыточностью –

Для систем с минимальной избыточностью –

Для несвязных систем –

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

Рис. 4.6.2. Граф

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

Вспомним понятие "степень вершины" ρi, т.е. число ребер, инцидентных вершине i. Было показано, что

Если связи распределены равномерно, то, очевидно, все ρi одинаковы. Тогда

где – средняя степень вершины.

Теперь можно определить квадратичные отклонения распределения степеней вершин от равномерного.

Среднеквадратичное отклонение

Так как , то

И, окончательно,

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

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

1. Последовательная структура.

2.Кольцевая структура.

3.Радиальная структура.

4.Структура "полный граф".

Раздел V. УПРАВЛЕНИЕ НА СТРУКТУРАХ В АС.

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

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

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

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

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

Такая структура (рис.5.2.1.) предполагает реализацию всех процессов управления объектами в едином центральном органе управления. Этот орган собирает информацию о состоянии всех объектов управления, осуществляет ее обработку и каждому объекту управления выдает свою собственную управляющую команду. Достоинства такой структуры:

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

– Достаточно просто реализуются процессы информационного взаимодействия.

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

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

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

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

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

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

– В соответствии с этим необходимость наличия запоминающих устройств очень большого объема.

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

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

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

§ 5.3. Централизованная рассредоточенная структура.

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

Рис. 5.3.1. Централизованная рассредоточенная структура

Алгоритмы управления в этом случае состоят из совокупности взаимосвязанных алгоритмов управления объектами.

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

Достоинствами такой структуры являются:

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

– Суммарная протяженность и стоимость каналов связи в такой системе может быть снижена.

К недостаткам следует отнести:

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

– Сложность корректировки хранимой в памяти системы информации.

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

– Сложность синхронизации процессов обмена.

§ 5.4. Иерархическая структура.

Идея иерархической структуры представлена на рис.5.4.1.

Рис. 5.4.1. Иерархическая структура.

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

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

Рис. 5.4.2. Суть иерархического управления.

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

Рис. 5.4.3. Иерархия управляемой части

Такими тенденциями являются:

– рост сложности выпускаемых изделий;

– рост сложности технологии производства;

– рост скорости смены номенклатуры выпускаемых изделий;

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

Это объективные системообразующие факторы, определяющие иерархию производственных объектов в АС.

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

Таким образом, в организационных иерархических системах имеет место:

– иерархия объектов управления;

– иерархия управляющей части, которая, в свою очередь, содержит:

а) иерархию органов управления,

б) иерархию задач управления.

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

– Последовательное вертикальное расположение подсистем, или, иначе говоря, вертикальная соподчиненность.

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

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

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

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

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

§ 5.5. Типовые организационные структуры управления производством.

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

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

§ 5.5.1. Линейная структура.

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

Рис. 5.5.1. Линейная структура.

§ 5.5.2. Функциональная структура.

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

Рис. 5.5.2. Функциональная структура управления

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

§ 5.5.3. Линейно – штабная структура.

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

Рис. 5.5.3. Линейно – штабная структура

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

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

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

Показать полностью…
Похожие документы в приложении