Этап 1. Декомпозиция проблемы и заполнение матриц суждений 2 страница

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

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

Таким образом, граф достижимости представляется как

GD = (V, E),

где V – массив вершин (маркировок, соответствующих вершинам):

V = {М₁, М₂ … М_q},

М_i – i-я маркировка, q – количество маркировок;

Е = {e₁, e₂ … e_p} – массив дуг, связывающих вершины (р – количество дуг).

Каждая дуга представляется как совокупность e_i = {a₁, a₂, Т}, где a₁ и a₂ – номера начальной и конечной вершин графа; Т = {t₁, t₂, … t_k} – массив переходов, соответствующий дуге; k – количество одновременно срабатывающих переходов при переходе от одной маркировки к другой.

Алгоритм построения графа по исходной СП:

1. За исходную берется маркировка М₀ и ей присваивается метка «новая».

2. Для каждой «новой» маркировки выполнять следующие операции:

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

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

2.2.1. Определяется маркировка М’, которая образуется при срабатывании данного перехода (комбинации переходов).

2.2.2. Просматриваются все маркировки на пути от М’ к начальной М₀. Если на пути находится маркировка М”, элементы которой больше либо равны соответствующим элементам новой и которая не равна М’, то вместо элементов m’_i, которые больше, чем элементы m_i маркировки М₀, записывается символ «w» (бесконечность). В массив Е записывается дуга с соответствующими a₁, a₂ и Т.

2.2.3. Просматриваются все маркировки графа. Если находится маркировка, равная новой, то в массив Е записывается новая дуга, у которой a₁ = a₂ и равны номеру найденной маркировки.

М₁

М₂

М₃

М₄

М₅

М₆

М₇

t₁

t₂

t₄

t₆

t₈

t₉

t₃

t₅

t₇

Рис. 4.14

Таблица 4.3

	(Р1 Р2 Р3 Р4 Р5 Р6 Р7 Р8)
М1	(11000000)
М2	(00100000)
М3	(00010000)
М4	(00000100)
М5	(00000001)
М6	(00001000)
М7	(00000010)

2.2.4. Если в п.п. 2.2 и 2.3 маркировки не найдены, то создается новая вершина графа, в которую записывается новая маркировка, в массив Е записывается дуга, у которой a₁ равна номеру исходной маркировки, a₂ - номеру новой маркировки, Т – набор переходов, срабатывание которых привело к переходу от одной маркировки к другой. Далее определяется массив всех разрешенных переходов и расчет продолжается, начиная с п. 2.2.

Для рассмотренного выше примера СП граф ГД имеет вид (см. рис. 4.14), список маркировок приведен в табл. 4.3.С помощью ГД могут быть определены свойства СП и, в конечном счете, моделируемой системы. К ним относятся:

- живость (отсутствие тупиковых состояний);

- ограниченность (сеть ограниченна, если символ «w» не входит ни в одну вершину графа);

- безопасность (сеть безопасна, если в метки вершин входят только «0» и «1») – физически безопасность означает отсутствие зацикливаний;

- правильность (если сеть безопасная и живая, то она правильная);

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

- пассивность переходов (переход t_i пассивен, если он не соответствует ни одной дуге графа);

- число возможных состояний N_сост.

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

Любая система должна представляться правильной сетью.

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

Практическое значение и наиболее ясную интерпретацию имеют два вида СП:

1) Маркированные графы – каждая позиция такой СП должна иметь не более одного входного и одного выходного перехода;

2) А-сети (автоматные сети) – каждый переход такой СП должен иметь не более одной входной и одной выходной позиции.

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

Методология SADT

Примером реализации семантической сети (см. раздел 5.4) является методология SADT (Structure Analysis and Design Technique), которая реализуется в различных автоматизированных программных пакетах анализа и конструирования для целей структуризации и формализации процессов принятия решений в организационных системах. В частности, широко известна так называемая IDEF-методология построения моделей систем, согласно которой модель системы представляется в виде совокупности трех моделей:

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

- IDEF1X – информационная модель, показывающая структуру информации;

- IDEF/CPN – динамическая модель, базирующаяся на так называемых раскрашенных СП (Colored Petri Net) и позволяющая просматривать и анализировать систему с точки зрения динамики.

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

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

Рис. 4.15

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

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

Методология IDEF1X - один из подходов к семантическому моделированию данных, основанный на концепции "Сущность - Отношение" (Entity-Relationship), это инструмент для анализа информационной структуры систем различной природы. Информационная модель, построенная с помощью IDEF1X-методологии, представляет логическую структуру информации об объектах системы. Эта информация является необходимым дополнением функциональной IDEF0-модели, детализирует объекты, которыми манипулируют функции системы.

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

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

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

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

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

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

Пример независимой сущности приведен на рис. 4.16, зависимой - на рис. 4.17.

Рис. 4.16

Рис. 4.17

Динамическая модель (IDEF/CPN) осуществляет проверку функциональной модели системы путем преобразования ее в СП. При этом функциональным блокам ставятся в соответствие переходы СП, а дугам – позиции.

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

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

и методы системного анализа

5.1. Основные понятия

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

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

1) декомпозиция исследования (задачи) на этапы (подзадачи);

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

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

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

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

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

Введем еще несколько, используемых в теории систем терминов.

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

1) цель и средства ее достижения,

2) критерии эффективности путей (альтернатив) достижения целей,

3) модель, описывающая зависимости между альтернативами,

5) модель принятия решений.

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

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

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

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

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

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

5.2. Методология системного анализа

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

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

1) элемент объекта описывается в той мере, в которой он важен для понимания объекта; могут рассматриваться структурные и функциональные аспекты и методы;

2) неотделимость свойств системы от условий ее существования, т.е. учет эффектов взаимодействия со средой;

3) связи и взаимообусловленность свойств целого и элементов (в том числе интегративное качество, эмержентность);

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

Системный анализ (СА) конкретизирует СсП путем разработки моделей систем (Мс) и моделей требований (Мт), то есть является инструментом СсП. Методы СА различаются уровнем определенности Мс и Мт.

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

5.3. Общая схема принятия решений

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

В дальнейшем рассматриваются более сложные системы.

Будем различать следующие ситуации:

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

2) когда известна цель и возможные методы ее достижения, хотя четкого алгоритма решения может и не быть - это задача.

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

Общая схема принятия решений приведена на рис. 5.1.

€

10-исследование вариантов

9-определение задач

11-база знаний

вариант 1

результат 1

вариант 2

результат 2

вариант n

результат n

7-критерии

8-цели

6-потребности

1- модель принятия решений

2-выбор

3-результаты

4-уровень удовлетворения потребностей

5-результат

обучение

Рис. 5.1. Общая схема принятия решений

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

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

принятие решения

I

II

III

IV

Рис. 5.2

Контур I (1-2-3-4-5-1): на старых знаниях (с известными вариантами-альтернативами) с фиксированными целями и критериями производится выбор варианта.

Контур II (5-6-8-7-1-2-3-4-5-6): старые знания, известные альтернативы, корректируются цели, критерии, модель принятия решений.

Контур III (9-10-2-3-4-5-6-9): старые знания, новые альтернативы (новые пути, варианты), возможно, изменение целей, критериев и т.д.

Контур IV (11-9-…..-4-5-11): коренное отличие от предыдущих случаев в том, что используется возможность изменения базы знаний, а с ним и возможное изменение остальных элементов схемы. Принципиальной является также необходимость тесного взаимодействия со средой.

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

5.4. Основные этапы приятия решений

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

Таблица 5.1

Оптнер	Янг	Федоренко	Никаноров
1) идентификация симптомов 2) определение актуальности проблемы 3) определение целей 4) определение структуры системы 5) определение возможностей 6) определение альтернатив 7) оценка альтернатив 8) выработка решений 9) принятие решений 10) запуск процесса решения 11) управление процессом реализации решения 12) оценка реализации и ее последствий	1) определение цели организации 2) выработка проблемы 3) диагноз 4) поиск решения 5) выработка альтернатив 6) согласование решений (координация) 7) утверждение решений 8) подготовка к вводу в действие 9) управление решением 10) проверка эффективности	1) формулирование проблемы 2) определение целей 3) сбор информации 4) разработка альтернатив 5) построение модели 7) оценка затрат 8) испытание чувствительности решения	1) обнаружение проблемы 2) оценка актуальности проблемы 3) анализ ограничений 4) определение критериев 5) анализ системы 6) поиск альтернатив 7) выбор альтернатив 8) принятие решения 9) реализация решения 10) оценка результатов

Общими для всех методик являются этапы:

1) постановка проблемы,

2) анализ ограничений,

3) разработка альтернатив,

4) выбор альтернативы,

5) разработка методов реализации,

6) реализация,

7) оценка эффективности.

Перечисленные этапы и будем считать элементами методологии СА.

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

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

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

3 группа – семиотические методы, в которых широко используется эвристики и логика: математическая и (или) неформальная (нечеткая);

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

5 группа – эвристическое программирование – группа методов экспертного оценивания и принятия решений.

5.5. Аналитические методы системного анализа

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

Формализованно описываются такие этапы, как:

а) процедура генерирования альтернатив (например, перебором);

б) оценка альтернатив по системе показателей на основе моделей системы;

в) выбор решения (модель компромисса).

По виду моделей Мс и Мт различают такие, например, задачи:

- анализ свойств (характеристик);

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

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

- проектирование систем и ряд других.

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

Заметим, что требование полного детерминизма не накладывается. Модель системы может быть описана как:

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

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

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

Модель принятия решений может включать такие процедуры как:

- вычисление показателей на основе моделей,

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

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

- линейное программирование (модель является системой линейных уравнений и ограничений),

- нелинейное программирование,

- динамическое программирование,

- вариационные методы и т.д.

5.6. Математические методы

Рассмотрим некоторые методы СА в качестве типичных примеров методов этой группы.

Метод логического ранжирования

Метод используется для задач составления расписаний.

Назначение метода: упорядочивание этапов выполнения некоторых работ.

Предположим, что имеется набор работ (этапов выполнения работ), причем некоторые виды работ не могут быть начаты до того, как будут окончены другие работы. Например, определены причинно-следственные отношения между отдельными работами (см. рис. 5.3): работа Р₀ является завершающей, ей должны предшествовать работы Р₁, Р₂ и Р₃, работе Р₁ должны предшествовать работы Р₄, Р₅ и Р₉ и т.д. Продолжительность каждой работы примем за единицу.

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

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

Р₁₁, Р₁₄ ® Р₁₂, Р₁₃ ® Р₇, Р₁₀ ® Р₅, Р₆, Р₈ ® Р₄, Р₉ ® Р₁, Р₂, Р₃.

То есть, сначала выполняются работы Р₁₁ и Р₁₄, после них Р₁₂ и Р₁₃ и т.д. Может быть учтена неравнозначность видов работ, выполняющихся одновременно.

Р₀

Р₁

Р₂

Р₃

Р₄

Р₈

Р₁₀

Р₁₃

Р₉

Р₁₂

Р₅

Р₆

Р₇

Р₁₁

Р₁₄

Дата добавления: 2014-12-16