Модели требований типа МТ

Качественные модели.

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

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

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

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

Если считать, что информацией является ошибка регулирования

е = х – у,

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

П-закона регулирования (пропорциональный), для которого управляющее воздействие определяется как

U = K₁^.e,

где K₁ – коэффициент усиления регулятора;

И-закона (интегральный), для которого

;

Д-закона (дифференциальный), для которого

. ¨

Обычно используются сочетания перечисленных законов регулирования: ПИ- и ПИД-законы.

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

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

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

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

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

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

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

.

Оба показателя имеют одинаковые шкалы полезности: чем меньше, тем лучше. Если для какого-либо показателя направление шкалы не совпадает с установленным, то для изменения направления шкалы полезности вводится показатель вида I’_I = 1 / I_i или I’₁ = - I₁ (I’_I – уровень «плохости»).

Рассмотрим задачу покупки товара наилучшего качества за наименьшие деньги (см. рис. 4.6.). Ресурсом оптимизации (варьируемым параметром или параметрами q), от которых зависят значения показателей I₁ (q),I₂(q) будут варианты товара у разных продавцов.

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

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

Рис. 4.6.

Точка 3, принадлежит множеству решений

М ={q^* | arg{J ® opt}}

– множеству Парето (множество компромиссов, переговорное множество). Это множество не улучшаемых в смысле векторного критерия решений, (в рассматриваемом случае opt = min). Существенно, что решение задачи оптимизации по векторному критерию носит принципиально множественный характер и для выбора наилучшего варианта нужен суперкритерий, который устанавливает приоритеты между показателями. Приоритеты, в конечном счете, устанавливает человек – лицо, принимающее решение (ЛПР).

Существует несколько методов получения решений из множества Парето:

1) метод сворачивания векторного критерия в глобальный скалярный,

2) метод последовательных уступок,

3) метод минимизации по частному критерию или показателю.

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

Сворачивание может производится по одной из следующих форм:

1) аддитивный критерий

,

где α_i – веса (весовые коэффициенты) показателей.

Если показатели имеют разные шкалы или размерности, то для облегчения выбора весов иногда эти показатели нормируют:

,

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

Веса также нормированы, т.е. .

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

2) линейно-квадратичный критерий

.

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

3) Минимаксный (Чебышёвский) критерий

.

Физический смысл – минимизация самой большой потери.

4) Модель справедливого компромисса.

.

Для случая n = 2 имеем α = α₁ = α₂ = 0,5 и решение

.

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

Метод последовательных уступок.

Метод требует большой определенности по приоритетам показателей (по важности). Последовательность применения метода:

1 шаг. Все показатели должны быть расположены в порядке убывания приоритетов.

2 шаг. Отыскивается минимум старшего (наиболее важного) показателя и назначается уступка

I₁ £ I₁^* + DI₁.

3 шаг. В рамках назначенной уступки проводится минимизация:

…

.

Метод минимизации по частному критерию или показателю.

Рассмотрим задачу оптимизации по двум показателям (частным критериям) I₁ и I₂. Допустим, что

, (4.19)

где х – переменная (ресурс оптимизации).

Свойства решений задач оптимизации по частным критериям.

Задача 1. I₁ ® min.

Область определения х Î(-¥, +¥).

Результат:, то есть абсолютный минимум I₁ достигает при х = 0.

Задача 2. I₂ ® min.

Область определения х Î(-¥, -1) и х Î(-1, +¥).

при e ® 0. При этом I₂ ® -¥.

На плоскости критериев {I₁, I₂} = I₁´I₂ частным решениям задач 1 и 2 соответствуют точки а(1,1) и с(¥, -¥).

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

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

Предположим, что по критерию I₁ делается уступка (вводится ограничение) d₁:

I₁ £ I₁^* + d₁,

где I₁^* = min I₁.

Тогда, как можно видеть из анализа задачи (4.19), существуют два важных случая:

1) При d₁ < 1 аргумент может изменяться в пределах х Î(-1, 1). Решение задачи: x = arg{x ® max}, то есть при решение будет

и .

Случаю х Î(-1, 1) соответствует отрезок кривой между точками А и В (см. рис. 4.7).

2) при d₁ ³ 1 решение задачи 2 дает значение х = -1 и I₂ = I₂^*, то есть в точке В решение «срывается» в -¥. Другими словами, при всех d₁ ³ 1 существует единственное решение х = -1.

II. Метод сворачивания векторного критерия в глобальный скалярный.

Выберем аддитивную форму сворачивания:

(4.20)

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

Приходим к кубическому уравнению

2^.с^.х^.(х + 1)² = 1 – с, х ¹ -1 - из (4.20).

Если представить это уравнение в виде

,

то легко убедиться, что при с = 1 (абсолютный приоритет критерия I₁) получается решение х = 0. При с = 0 (приоритет I₂) решения не существует.

Рассмотрим качественно минимизацию (4.20).

При некотором с ¹ 0 и с ¹ 1 получается качественно график функции J(x) (см. рис. 4.8). Как видно, при неограниченном диапазоне изменения х решение задачи (4.20) и, соответственно, задачи (4.19) будет х = -1.

Если ограничить x > -1, то решение существует с opt, зависящим от с. Причем, при уменьшении с (при с ® 0) точка х = arg{min J} смещается в сторону увеличения.

Для с << 1 примерное решение: . Например, при с = 0,001 имеем х = 10.

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

Рассмотрим некоторые виды моделей типа Мт, к числу которых относятся логические модели четкой (конечно-автоматные (КАМ) модели) и нечеткой логики (НЛМ), семантические сети (СС), продукционные системы (ПС), предикатные системы (ПрС), большая группа экспертных методов и др.

Логические модели.

Конечные автоматы. Логические модели этого типа базируются на алгебре логики. В булевой алгебре используются два элемента «0» и «1» (или {0, 1}).

Примечание: кроме булевой логики имеются также многозначные логики, например, {-1, 0, 1}, а также нечеткие логики, в которых переменные принадлежат значениям 0 и 1 с различной степенью уверенности.

Если используются две переменные Х и Y, принимающие по два значения: 0 = «ложь» и 1 = «правда», то для булевой алгебры определены логические операции (см. табл. 4.1):

Таблица 4.1.

Х					Название логической операции	Обозначение
Y						в выражениях
					- конъюнкция (лог. умножение)	И, AND, &, *, V
					- дизъюнкция (лог. сложение)	ИЛИ, OR, +, L
					- тождественность	=, ~

а также функция одного операнда:

- отрицание (функция «НЕ», NOT, «¬»), например, если Х = 0, то ¬Х = 1.

Существуют и другие функции: стрелка Пирса, штрих Шеффера, импликация и др.

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

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

и .

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

Таблица 4.2.

X	Y	Z	F

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

1) совершенная дизъюнктивная нормальная форма (СДНФ), представляющая собой дизъюнкцию конъюнкций логических переменных; иными словами, логическая сумма слагаемых, каждое из которых является логическим произведением переменных и называется «термом»:

,

где D_i – дизъюнкт (терм), n – число дизъюнктов в выражении;

2) совершенная конъюнктивная нормальная форма (СКНФ), представляющая собой конъюнкцию дизъюнкций, иначе называемую записью по нулю:

,

где K_i – конъюнкт, n – число конъюнктов.

Правило записи выражения в СДНФ: если в строке, где значение функции равно F = «1» какая-либо переменная принимает значение «1», то эта переменная записывается в дизъюнкт в чистом виде, если принимает значение «0», то с отрицанием.

Правило записи выражения в СКНФ: если в строке, где значение функции равно F = «0» какая-либо переменная принимает значение «0», то эта переменная записывается в конъюнкт в чистом виде, если принимает значение «1», то с отрицанием.

Так, для функции F по табл. Х имеем СДНФ:

или то же самое в более простой записи:

.

Для упрощения записи логических функций используются:

- логические преобразования,

- карты Карно,

- диаграммы Вейтча,

- методы целенаправленного перебора (алгоритм Мак-Класки).

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

Карта Карно представляет собой особый вид таблиц состояний, имеющих прямоугольный вид и состоящих из 2ⁿ квадратов, где n – число входных переменных. Стороны карты помечаются именами переменных таким образом, чтобы половина карты соответствовала «1»-му значению переменной, а другая – «0»-му, причем в карте должны быть учтены все возможные сочетания значений переменных (состояния входов). В результате, каждая ячейка карты будет соответствовать определенному набору значений входных переменных. В ячейки заносятся соответствующие значения минимизируемой функции. Так, для рассматриваемого примера карта представлена на рис. 4.9.

Рис. 4.9.

Далее для записи выражения в СДНФ производятся объединения ячеек карты, содержащих «1» так, чтобы данные ячейки образовывали прямоугольники или квадраты размером 1, 2, 4, 8, 16 и т.д. ячеек. Каждый такой прямоугольник будет соответствовать своему терму, причем, чем он больше, тем проще будет терм. Прямоугольники могут пересекаться.

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

.

Запись выражений в СКНФ производится аналогично, но объединяются ячейки с нулями. Термы записываются в виде дизъюнкции переменных по принципу: если прямоугольнику соответствует «1»-ое значение какой-либо переменной, то данная переменная входит в конъюнкт в инверсном виде; если «0»-ое значение, то в чистом; если соответствует как «1»-ое, так и «0»-ое, то в конъюнкт переменная не входит. После конъюнкты объединяются функциями конъюнкции. Для рассматриваемого примера:

.

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

Основы теории нечетких множеств и нечеткой логики.

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

В частности, расширение языков программирования промышленных контроллеров на базе нечетких систем (Fuzzy Logic Programming) предложено для стандарта IEC 1131.

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

[0, 1]. Она была введена доктором Lotfi Zadeh в 1960-ых годах как способ моделирования неопределенностей естественного языка.
Основная идея Заде состояла в том, что человеческий способ рассуждений в большинстве случаев не может быть описан традиционными математическими формализмами. Основная цель нечеткой логики - моделирование человеческих рассуждений и объяснение человеческих приемов принятия решений в ходе решения различных задач.

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

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

Рис. 4.10.

Для характеристики человеческого роста может быть введено множество переменных Х = {х₁, х₂, х₃, х₄, х₅}, соответствующих значениям: х₁ - «очень низкий», х₂ - «низкий», х₃ – «средний», х₄ – «высокий», х₅ – «очень высокий». Соответственно переменным определяются функции m(х_i), которые могут иметь вид, показанный на рис. 4.11.

Рис. 4.11.

Существует несколько типовых видов функций принадлежности (см. рис. 4.12):

Операции над нечеткими множествами:

1) сравнение: А = В, если m_А(х) = m_В(х);

2) дополнение (отрицание): , если m_В(х) = 1 - m_А(х);

3) пересечение АÇВ: m_АÇВ(х) = min(m_А(х), m_B(х));

4) объединение АÈВ: m_АÈВ(х) = max(m_А(х), m_B(х));

5) разность: ;

6) сумма: m_А+В(х) = m_А(х) + m_B(х) – m_А(х)*m_B(х);

7) произведение: m_А´В(х) = m_А(х)*m_B(х);

8) концентрация («очень»): m_con(A)(х) = m²_А(х);

9) растяжение («довольно»): .

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

1) простые (pure),

2) системы Токаги и Суджено,

3) системы с фаззификатором и дефаззификатором (fuzzy).

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

,

где R – композиционные правила.

Недостаток простых систем в том, что входные и выходные переменные являются нечеткими.

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

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

Продукционные системы.

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

PR = <S, N, F, A Þ C, W>,

где S - сфера применения данного правила; N - номер или имя правила; F - предусловие применения (условие активизации), содержащее информацию об истинности и приоритетности данного правила; A Þ C - ядро ПП; W - постусловие.

Сфера применения S обозначает принадлежность ПП какому-либо определенному этапу функционирования ПС или состоянию процесса принятия решения.

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

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

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

Наиболее часто в ПС используют детерминированные ПП вида

«если А то С»,

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

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

«если А то С₁ иначе С₂».

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

Достоинствами продукционных систем являются:

- удобство описания процесса принятия решения экспертом (формализация его интуиции и опыта);

- простота редактирования модели;

- прозрачность структуры.

ПС в качестве моделей применимы в случаях, когда:

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

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

- пространство возможных решений относительно невелико (число решений счетно);

- задачи решаются методом формальных рассуждений;

- данные и знания надежны и не изменяются со временем.

Сети Петри.

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

N = (P, T, G, W),

где P = {p₁, p₂… p_n} – множество всех позиций (n – количество позиций),

Т = {t₁, t₂… t_m} – множество переходов (m – количество переходов),

G = (G_p-t, G_t-p) – множество дуг сети:

G_p-t = (p´t), G_t-p = (t´p) – множества дуг, ведущих соответственно от переходов к позициям и от позиций к переходам (дуг, соединяющих однородные вершины, не существует),

W = {w₁, w₂… w_k} – множество весов дуг (k – количество дуг).

Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции p_i, как m_i, то маркировка всей сети: M = {m₁, m₂… m_n}. Тогда полное определение сети Петри, включая данные о начальной маркировке, можно записать в виде:

PN = (N, M₀),

где М₀ – начальная маркировка сети.

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

Пример. Схема принятия решений при попытке получить деньги из банкомата (см. рис.4.13).

Рис. 4.13.

Смысл позиций: Р₁ – карта (ее наличие), Р₂ – исправность банкомата, Р₃ – введенный код, Р₄ – код набран правильно, запрашивается сумма, Р₅ – код набран неправильно, Р₆ – сумма доступна, Р₇ – сумма недоступна (нет такого количества денег на карте), Р₈ – деньги (получены). Смысл переходов: t₁ – банкомат принимает карту и делает запрос в банк, ввод кода, t₂ – запрос суммы, t₃ – повторный ввод кода, t₅ – выдача сообщения о недоступности суммы, t₆ – выдача денег, t₇ – повторный набор суммы, t₈ – забрать карту из банкомата (другой исход: имеется другая карта, с которой также нужно снять деньги – см. дуги, обозначенные пунктиром), t₉ – выдача сообщения, что код неверный. ¨

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

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

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

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₂ и равны номеру найденной маркировки.

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

Для рассмотренного выше примера СП граф ГД имеет вид (см. рис. 4.14), список маркировок приведен в табл. 4.3.

Таблица 4.3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 4.15.

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 4.16.

Рис. 4.17.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 5.2.

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

Анализ схемы принятия решений позволяет выделить несколько вложенных циклов (контуров обратной связи), которым соответствуют типовые варианты принятия решений, рис. 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.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) оценка результатов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 5.3.

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

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

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

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

Таблица 5.3

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

Р8

Р9

Р10

Р11

Р12

Р13

Р14

Σ

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

Р8

Р9

Р10

Р11

Р12

Р13

Р14

5.7. Метод анализа иерархий.

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

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

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

Этап 1. Используются три принципа:

Принцип 1. Декомпозиция, при которой производится как структурная, так и функциональная дифференциация.

Пример. Имеется цель: «купить дом». Есть вариа

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