Теория систем

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЯНОЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ А.П. Верёвкин, О.В. Кирюшин теория систем Учебное пособие х1 y1 у2 S F1 х2 х3 х4 Уфа 2003 F2 2 УДК 007.5 ББК Утверждено Редакционно-издательским советом УГНТУ в качестве учебного пособия Рецензенты: Зав. кафедрой «Техническая кибернетика» УГНТУ, проф., д-р техн. наук Б.Г. Чудаев Кафедра «Техническая кибернетика» Уфимского государственного авиационного технического университета (зав. кафедрой, д-р техн. наук, профессор Б. Г. Ильясов) Директор департамента стратегических исследований МОАО «Нефтеавтоматика», канд. техн. наук В.Я. Соловьев Веревкин А.П., Кирюшин О.В. В 31 Теория систем: Учеб. пособие. – Уфа: Изд-во УГНТУ, 2003. –100 с. ISBN 5-7831-0444-2 В книге рассмотрены основные понятия общей теории систем и системного анализа. Приводятся сведения по проблеме моделирования, классификации моделей, методам и моделям систем принятия решений. Рассматриваются некоторые проблемы, которые в равной степени могут быть отнесены как к общей теории систем, так и к исследованию операций. Книга предназначена для студентов, аспирантов, а также читателей, желающих получить начальные сведения по общей теории систем и системному анализу. УДК 007.5 ББК ISBN 5-7831-0444-2  Уфимский государственный нефтяной технический университет, 2003  Веревкин А.П., 2003  Кирюшин О.В., 2003 3 СОДЕРЖАНИЕ Введение 1. Системы и задачи их анализа 1.1. Свойства систем 1.2. Количество информации 1.3. Классификация систем 2. Элементы теории множеств 2.1. Основные понятия и термины 2.2. Операции над множествами 2.3. Свойства операций над множествами 2.4. Алгебры 3. Элементы теории графов 4. Модели систем 4.1. Цели моделирования систем 4.2. Уровни моделирования 4.2.1. Классификация уровней моделирования 4.2.2. Задачи анализа свойств систем, решаемые на концептуальном уровне 4.2.3. Задачи, решаемые на топологическом уровне 4.2.4. Модели структурного уровня 4.2.5. Модели параметрического уровня 4.3. Классификация моделей систем 4.4. Модели систем типа Мс 4.5. Модели требований типа Мт 5. Современная методология научных исследований и методы системного анализа 5.1. Основные понятия 5.2. Методология системного анализа 5.3. Общая схема принятия решений 5.4. Основные этапы принятия решений 5.5. Аналитические методы системного анализа 5.6. Математические методы 5.7. Семиотические методы 5.8. Группа экспертных методов 5.9. Игровые методы принятия решений 5.10. Имитационное моделирование Список использованной литературы С. 4 5 5 10 11 12 12 14 15 16 16 20 20 20 20 21 21 26 26 27 28 32 52 52 53 54 55 57 58 64 64 66 69 71 4 Введение Учебное пособие подготовлено на основе курсов лекций, читаемых в Уфимском государственном нефтяном техническом университете для ряда специальностей факультетов автоматизации производственных процессов, экономики и менеджмента. Содержание пособия соответствует рабочим программам курсов «Теория систем» и «Системный анализ», которые читаются на втором – третьем курсах до начала циклов общепрофессиональных и специальных дисциплин. В процессе изучения дисциплин специальностей 21.02.00 - «Автоматизация технологических процессов и производств», 06.04.00 – «Финансы и денежное обращение», 06.18.00 – «Математические методы в экономике» и ряда других, связанных с проблемами управления, возникает необходимость использования основных понятий и элементов общей теории систем и системного анализа. Несмотря на достаточно большой перечень литературы по данной тематике, практически вся эта литература либо устарела, либо в ней рассматриваются отдельные аспекты теории, либо она мало доступна для студентов. Помимо изложения общепринятых и устоявшихся разделов общей теории систем и системного анализа, в данном пособии значительное внимание уделено методическим вопросам моделирования систем в соответствии с современным уровнем понимания роли этой проблемы. При подготовке пособия использовались работы Дж. Ван Гига, Николаева В.И., Брука В.М., Холла А.Д., Прангишвили И.В., Вавилова А.А., Имаева Д.Х., Моисеева Н.Н., Перегудова Ф.И., Тарасенко Ф.П., Саати Т. и многих других авторов, а также материалы, подготовленные преподавателями кафедры автоматизации химико-технологических процессов УГНТУ. Значительная часть пособия посвящена изложению разделов математики, которые не входят в перечень тем, регламентируемых Государственным образовательным стандартом для специальностей 21.02.00, 06.18.00, 06.04.00. При изложении материалов по теории графов, классификации систем и моделей систем, моделированию процессов принятия решений и некоторых других разделов использовались работы и результаты исследований авторов. 5 1. Системы и задачи их анализа 1.1. Свойства систем Понятие «система» не имеет, а по мнению некоторых авторов, и не может иметь исчерпывающего и однозначного определения. Это связано с первичностью, аксиоматическим характером понятия, поскольку понятие «системность» очень часто носит субъективный характер и оценивается через другие понятия, которые также являются первичными. Блез Паскаль писал: «Я считаю, что познать части без знания целого так же невозможно, как познать целое без знания его частей». Теория систем изучает общие проблемы связи целого и его частей. В более узком понимании это вопросы, связанные с решением следующих проблем: - определение содержания проблем; - назначение и (или) определение целей при принятии решений; - поиск путей решения проблем; - проектирование и (или) построение систем для достижения целей и т.д. Так что же будет пониматься под термином «система»? Достаточно устоявшейся является мысль, что «система» («S») обладает минимум четырьмя свойствами: 1) Целостность и членимость Целостность означает, что система воспринимается окружающей средой как единый элемент этой среды. Членимость означает, что в системе можно выделить некоторые элементы, совокупность которых вместе с их взаимодействием и образует систему. При этом совокупность элементов обладает качественно новыми свойствами, которые позволяют рассматривать их как элемент более сложной системы. Новое качество, эмерджентность, - это то, что определяет «лицо» системы, идентифицирует ее целостность, и поэтому оно первично для системы. 2) Интегративные качества Свойства, обеспечивающие целостность, которые есть у системы, но нет у элементов, составляющих систему, называются интегративным качеством (ИК), они определяют эмерджентность. Существенно, что ИК не может быть выявлено сколь угодно глубоким изучением свойств элементов. Например, команда (бригада) может выполнить задачи, которые члены команды (бригады) по отдельности выполнить не в состоянии. 3) Связи (отношения) Система, как правило, взаимодействует с другими системами (Fi, i=1,2,…), которые для нее являются внешней средой, связь осуществляется между некоторыми (или всеми) элементами, принадлежащими данной системе, и элементами других систем (см. рис. 1.1). Другие системы – это внешняя среда для системы S. Если взаимодействие системы S с внешней средой не рассматривается (в теоретических исследованиях, например), тогда система называется закрытой или автономной. Множество переменных (координат), через которые система S 6 взаимодействует с внешней средой, часто разделяют на подмножества входных X={xi, i=1,2…} и выходных Y={yj; j=1,2…} координат системы. В реальном мире один и тот же элемент может входить в разные системы. Взаимодействие систем носит разноплановый характер, поэтому существенным вопросом является определение границ системы и выделение переменных Х,Y. Причем значение имеют только связи, определяющие интегративное качество, т.е. «имидж» системы. Связь подсистем количественно задается множеством характеристик связей В={bi, i=1,2,…}, к числу которых относится физическое наполнение (энергетическая, информационная, вещественная, механическая связь и т.д.), а также мощностью, направленностью и т.д. границы системы S х1 у1 S F2 F1 у2 х2 границы системы F1 х3 х4 границы системы F2 Рис. 1.1 - Графическое представление системы и среды Формально связь может быть представлена отображением β:Х→ Х при условии, что метрики множеств Х и Х связаны функцией f(b): ρ X = f (b)ρ X . Метрика (мера, расстояние)– это способ измерения расстояния между элементами множеств а,b,с∈Х. Метрика должна удовлетворять некоторым определяющим свойствам: а) ρ ≥ 0 при любых а,b,c; б) ρ(a,b) = 0 тогда и только тогда, когда a = b (аксиома идентичности); в) ρ(a,b) = ρ(b,a) (аксиома симметричности); г) ρ(a,b) ≤ ρ(а,с) + ρ(с,b) (аксиома треугольника). Пара (Х,ρХ) называется метрическим пространством. Примеры метрик: а) ρ(а,b) = |a - b|; 7 1 n 2 2  б) ρ2(a,b) = ∑ a i − b i  - евклидова метрика в евклидовом пространстве  i =1  n R, max в) ρ∞(а,b) = 1 ≤ i ≤ n ai − bi - чебышевская метрика; 1 n K K г) ρК(a,b) = ∑ a i − b i  - метрика Гельдера, К – целое.  i =1  В общем случае – отношения бывают: унарные (самого с собой); бинарные (между двумя элементами); тернарные (между тремя элементами); вообще, - n-арные. 4) Организация Введем в рассмотрение понятие «состояние» элемента или системы. Количество состояний (мощность множества состояний) может быть конечно, счетно (количество состояний измеряется дискретно, но их число бесконечно); мощности континуум (состояния изменяются непрерывно и число их бесконечно и несчетно). Состояния можно описать через переменные состояния. Если переменные – дискретные, то количество состояний может быть либо конечным, либо счетным. Если переменные – аналоговые (непрерывные), тогда - мощности континуум. Минимальное количество переменных, через которые может быть задано состояние, называется фазовым пространством. Изменение состояния системы отображается в фазовом пространстве фазовой траекторией. Уравнение состояния системы: Y = F(X, Z), (1.1) где Z – переменные состояния (вектор аналоговых или дискретных величин), Х – входные переменные, Y – выходные переменные системы. Одной из наиболее часто используемых характеристик организации является энтропия (поворот, превращение – греч.). Энтропия систем Степень организации элементов в системе связывается с изменением (снижением) энтропии системы по сравнению с суммарной энтропией элементов. Понятие энтропии введено Больцманом для термодинамических систем: Н (S ) = − m ∑ P j log 2 P j , j = 1 (1.2) где P j ( j = 1, m ) - вероятность j-го состояния (в теории информации – события); m - возможное число состояний (событий). 8 Например, два элемента А и В могут каждый принимать два равновероятных состояния: «0»и «1». Вероятность каждого состояния: Р1(А) = Р2(А) = Р1(В) = Р2(В) = 0,5. Для одного элемента энтропия составит Н(А) = Н(В) = -0,5 log20,5 - 0,5log20,5 = 1. Энтропия двух элементов: Н(А) + Н(В) = 1 + 1 = 2. ♦ Допустим, что система S элементов А и В может принимать три состояния: «-1», «0», «1» с вероятностями Р1(S) = Р3(S) = 0,2; Р2 = 0,6. Тогда Н(S) = -2.0,2.log20,2 - 0,6.log20,6 = -0,4⋅(-2,32) - 0,6⋅(-0,737) = 1,37. Энтропия системы S меньше суммы энтропий элементов А и В на ∆Н = Н(А) + Н(В) - Н(S) = 2 - 1,37 = 0,63. ♦ Для расчета изменения энтропии системы через вероятности состояний очень часто используется метод Колмогорова. Допустим, дана структурная схема (граф) состояний подсистемы S (см. рис. 1.2). Исходным состоянием системы с равной степенью вероятности может быть одно из четырех состояний, т.е. 2 P10 = P20 = P30 = P40 = 0,25 . λ21 λ32 Будем считать, что интенсивности 1 3 переходов λ21, λ32, λ43, λ14, λ24 заданы. Тоλ24 гда можно показать, что скорости измеλ43 λ14 нения вероятности нахождения системы в i-м состоянии определяются как 4 r m Рис. 1.2 dP i = dt i ∑ i µ j ⋅ Pj − j =1 ∑ λ k ⋅ Pi k =1 , (1.3) где i = 1, n ; n – число узлов графа (количество состояний); µj j = 1 , r i - интенсивности переходов по дугам, входящим в i-й узел; ri – число дуг, входящих в i-й узел; λk k = 1, m i - интенсивности переходов по дугам, исходящим из i-го узла; mi – число дуг, выходящих из i-го узла; Pi и Pj – вероятности нахождения системы в i-м и j-м состояниях соответственно. Заметим, что 9 n ∑ P i i=1 = 1 . Установившееся значение вероятности нахождения системы в i-м состоянии определяется из условия dP i = 0 . dt Тогда для системы с n состояниями имеем систему из (n + 1) уравнений с n неизвестными: mi dPi ri = ∑ µj ⋅ Pj − ∑ λk ⋅ Pi ; dt j=1 k=1 i = 1, n . (1.4) n ∑ Pi = 1 i=1 Одно из уравнений (1.4) можно отбросить, так как оно может быть получено из (n - 1) оставшихся. Пример. Примем λ21 = 0,1, λ32 = 0,2, λ43 = 0,3, λ14 = 0,4, λ24 = 0,5. Тогда получаем: λ14.Р4 - λ21.Р1 = 0 λ21.Р1 + λ24.Р4 - λ32.Р2 = 0 λ32.Р2 - λ43.Р3 = 0 λ43.Р3 – (λ14 + λ24).Р4 = 0 Р1 + Р2 + Р3 + Р4 = 1. Из системы отбросим второе уравнение и получим: - 0,1.Р1 + 0.Р2 + 0.Р3 + 0.Р4 = 0 0.Р1 + 0,2.Р2 – 0,3.Р3 + 0.Р4 = 0 0.Р1 + 0.Р2 + 0,3.Р3 – 0,9.Р4 = 0 1.Р1 + 1.Р2 + 1.Р3 + 1.Р4 = 1. Решение полученной системы: Р1 = 0,32, Р2 = 0,36, Р3 = 0,24, Р4 = 0,08. Расчет энтропий ведется по формуле n Э=− ∑ P log i i =1 2 Pi . Для исходного состояния Э0 = -4 . 0,25 . log20,25 = 2, для конечного состояния Эк = -(0,32 . log20,32 + 0,36 . log20,36 + 0,24 . log20,24 + 0,08 . log20,08) = 1,835. 10 То есть, изменение энтропии составляет ∆Э = Э0 – Эк = 2 – 1,835 = 0,165. ♦ Существуют два основных подхода к расчету энтропий систем и ценности информации. Первый подход основан на декомпозиции исходной задачи на этапы вычисления вероятностей апостериорной и априорной вероятности элементарных событий. Методика расчета включает: - декомпозицию исходной задачи на последовательность таких элементарных событий, априорная вероятность которых известна, а апостериорная может быть легко рассчитана; - расчет энтропий (или ценности информации) каждого элементарного события; - вычисление изменения энтропии исходного состояния по отношению к конечному (или ценности информации) путем суммирования изменений энтропий элементарных этапов (переходов, событий). Данный подход позволяет избежать вычисление вероятности сложных событий. Второй подход основывается на использовании условных вероятностей событий. Последние иногда рассчитать довольно сложно. Таким образом, энтропия выступает в качестве меры хаоса, беспорядка и ее снижение означает увеличение организации. Для информационных систем степень организации очень часто зависит от количества информации, которая может быть использована для управления. 1.2. Количество информации В теории информации количество информации часто измеряют в битах (binary digital), где бит определяется как ценность I информации об исходе двух равновероятных событий. Например, эта информация о том, что сейчас день, а не ночь. Вероятность каждого из событий Р(Д) = 0,5; Р(Н) = 0,5; I = log2 Р1 (х ) Р 2 (х ) , где Р1(х) – апостериорная вероятность; Р2(х) – априорная вероятность. Для примера: I = log 2 1 = 1, бит . 0 ,5 Кроме битов (термин ввел Тьюки) используются (1.5) 11 «нат» I = ln Р1 (х) Р 2 (х) и «дит» I = lg Р1(х ) Р 2 (х ) . 1.3. Классификация систем Существует достаточно большое число классификационных признаков (свойств) систем, в частности: - открытость – замкнутость (отсутствие связи с внешней средой); - детерминированность (определенность) – стохастичность (случайность); - простота – сложность; -наличие цели – отсутствие цели; - субстанциональные признаки (по этим признакам выделяют: естественные, концептуальные, искусственные системы); - наличие направленности связей и характер связей: не направленные, обратные, линейные, нелинейные; - наличие или отсутствие иерархии элементов в системе; - эволюционирующие – не эволюционирующие (жесткие, не адаптируемые) системы; - непрерывные – дискретные; - по физическому наполнению: вещественные, энергетические, информационные и т.д.; - по мощности связей: коэффициенты связи, интенсивности, чувствительности, коэффициенты корреляции и т.д.; - по роли связи: ограничивающая, координирующая, положительная, отрицательная. Для характеристики свойств систем выделяют факторы: - системосоздающие; - системоразрущающие; - системозначимые (свойства, характеризующие интегративное качество, в том числе вне системы); - системоопределяющие (свойства определяют интегративное качество системы) и др. По признаку «сложность» выделяются два типа систем (простые - сложные). Существует несколько аспектов, по которым система может классифицироваться как простая или сложная. Достаточно общее с практической точки зрения определение сложной системы: это такая система, анализ и прогноз изменения состояния которой невозможен с заданной точностью за заданное время. 12 Для искусственных систем, к которым относится подавляющее большинство систем, создаваемых человеком, выделяют три основных уровня формулирования цели: 1) цель не очень ясна (целенаправленные системы); 2) цель ясна и намечены пути ее достижения (целеустремленные системы); 3) цель определена и формализована на уровне математической постановки, есть алгоритм достижения цели (алгоритмические системы). Реальные постановки проблем могут представлять собой промежуточные варианты перечисленных случаев. 2. Элементы теории множеств Наиболее общие формальные описания элементов и систем опираются на язык теории множеств. Рассмотрим некоторые элементы этой теории. 2.1. Основные понятия и термины Множество – совокупность элементов, объединенных по какому-либо признаку. Через «∈ » обозначается отношение принадлежности, то есть «х∈ А» означает, что х принадлежит множеству А. Если х не является элементом А, то пишется «х∉ А». Множества А и В считаются равными, если они состоят из одних и тех же элементов: А = В. В противном случае А ≠ В. Элементами множества могут быть любые объективные и субъективные понятия, объединяемые в соответствии с некоторым законом, правилом, признаком и т.д. Множества могут содержать подмножества, например, если В - подмножество А, то оно записывается через отношение включения «В ⊆ А», то есть каждый элемент А является элементом В (но не наоборот, см. рис. 2.1). множество А множество В Рис. 2.1 Если В ⊆ А и А ≠ В, то В является собственным подмножеством А, т.е. В ⊂ А. Множество, не содержащее элементов, называется пустым, например, В = ∅. Семейство всех подмножеств множества А обозначается как Р(А). 13 Множества, элементами которого являются множества, обычно называют классом. Задание множества можно осуществлять следующим образом: 1) перечислением А := {a1, a2, … , an}; 2) характеристическим предикатом (правилом): А := {x | P(x)} , например, элементами А являются все значения х такие, что sin(x) ≥ 0. 3) порождающей процедурой: А := {x | x := f}, например, А := {n | for n = 1 to 9 do yield}. Мощность множества А обозначается как A . Мощностью множества А называется класс всех множеств, эквивалентных А. Эквивалентность (~), в отличие от равенства – это возможность установить взаимно однозначное соответствие между элементами множеств А и В: А ~ В. Используются следующие основные градации мощности: а) n–конечные множества - это мощность множеств из набора любых n элементов; множество конечно; б) если элементов бесконечное количество, но их можно перечислить (например, множество чисел), мощность такого количества обозначают через χ0. Оно называется счетным. в) если множество эквивалентно множеству всех натуральных чисел, его мощность обозначается через С и оно называется континуальным (мощность континуума). Множество не счетно. Мощности произвольных множеств называются кардинальными числами. Очевидно, что С «больше» χ0, а χ0 «больше» n. Возникает ряд вопросов: может ли мощность быть больше С? Например, какова мощность множества комплексных чисел? Как оценить эту мощность? Введем в рассмотрение так называемое прямое (декартово) произведение множеств А и В: М = А × В := {(a, b) | a ∈ A, b ∈ B}. Это множество упорядоченных пар элементов множеств А и В. Если множество действительных чисел R имеет мощность С, множество мнимых чисел I также имеет мощность С. Тогда кажется, что M = C 2 . Однако можно показать, что M = C . Для ответа на подобные вопросы приведем свойства мощности: n 1 + n 2 = n 1 + n 2, χ0 + C = C, χ0 ⋅χ0 = χ0, n + χ0 = χ0, C + C = C, χ0⋅C = C, χ0 + χ0 = χ0, n1⋅n2 = n1⋅n2, C⋅C = C. 14 Бинарным отношением между множествами А и В называется любое подмножество R ∈ A × В. Например, если А = В – множества четных действительных чисел от 0 до 8, тогда А × В – это множество пар четных чисел: 00, 02, 04, … 88. 2.2. Операции над множествами 1) Объединение (сумма, дизъюнкция) Х = А ∪ В := {x | x ∈ A v x ∈ B} «v» = «или» (см. рис. 2.2, а) Х Х В А В А б) а) Х Х В А в) А В г) Рис. 2.2 2) Пересечение (произведение, конъюнкция) Х = А ∩ В := {x | x ∈ A & x ∈ B} «&» = «и» (см. рис. 2.2, б). 3) Разность (см. рис. 2.2, в) Х = А \ В := {x | x ∈ A & x ∉ B}. 4) Симметрическая разность (см. рис. 2.2, г) Х = (А \ В) ∪ (В \ А) = А ∆ В := {x | x ∈ A & x ∉ B, x ∈ В & x ∉ А }. 15 5) Дополнение A := {x | x ∉ A} . Элементы всех множеств можно считать элементами некоторого универсального множества U – универсума, который играет роль единицы. Тогда разность U \ A называется дополнением множества А и часто обозначается (-А) или (¬А). 2.3. Свойства операций над множествами 1) Идемпотентность: А ∪ А = А, А ∩ А = А. 2) Коммутативность: А ∪ В = В ∪ А, А ∩ В = В ∩ А. 3) Ассоциативность: А ∪ (В ∪ С) = (А ∪ В) ∪ С, А ∩ (В ∩ С) = (А ∩ В) ∩ С. 4) Дистрибутивность: А ∪ (В ∩ С) = (А ∪ В) ∩ (А ∪ С), А ∩ (В ∪ С) = (А ∩ В) ∪ (А ∩ С). 5) Поглощение: (А ∩ В) ∪ А = А, (А ∪ В) ∩ А = А. 6) Свойства нуля: А ∩ ∅ = ∅, А ∪ ∅ = А. А ∪ U = U. 7) Свойства единицы: А ∩ U = A, 8) Инволютивность: − (− A ) = (A ) = ¬ (¬ A ) = A . 9) Законы де Моргана: A∩B = A∪B , 10) A∪A = U A∪B = A∩B . A ∩A = ∅ . A \ B = A∩B . 11) 12) Рефлексивность: А ⊆ А. 13) Транзитивность: если А ⊆ В и В ⊆ С, то А ⊆ С. Алгебраическая операция определена на А, если можно указать закон, по которому любой паре (a, b) из А×А ставится в соответствие третий элемент, принадлежащий этому же множеству. c = a + b – сложение, с = a⋅b – умножение, c = a°b – в общем случае. Основные свойства операций: коммутативность и ассоциативность. Операция – это всегда отношение, но не наоборот. Множество К называется кольцом, если в нем определены операции сложения и умножения, обе ассоциативны и дистрибутивны, причем сложение коммутативно и обладает обратной операцией. Множество К называется линейным или векторным пространством, если для элементов (векторов) из К определены операции сложения и умножения на число Р и выполняются аксиомы: 1) Каждой паре векторов (х, у) отвечает вектор (х + у) и называется суммой, причем х + у = у + х (коммутативность) и х + (у + z) = (х + у) + z (ассоциативность). Существует единственный нулевой вектор О такой, что х + О = х, ∀х. Существует вектор (-х) такой, что х + (-х) = О. 16 2) Каждой паре (α, х), где α - число, а х – вектор, отвечает вектор αх, причем: α (β х) = (α β) х, 1⋅х = х. 3) α⋅(х + у) = α⋅х + α⋅у, (α + β)⋅х = α⋅х + β⋅х. 2.4. Алгебры Множества и функции на них – это два типа объектов, на которых в конечном счете строится любая математическая теория. Если аргументы функции f пробегают множество М и она принимает значения из того же множества, то f – это алгебраическая операция на М. Итак, алгебра – это множество М вместе с набором операций на нем. Обозначается алгебра как двойка (М, Σ), где Σ:={ϕ1, ϕ2, …, ϕn} – набор (множество) операций, сигнатура алгебры, а М – носитель алгебры. Группой называется множество, если: 1) выполняется условие наличия одной ассоциативной операции; 2) в группе есть элемент «е», удовлетворяющий условию a.e = e.a = a, он называется «единицей»; 3) для каждого элемента а существует единственный элемент (а-1) такой, что a.a-1 = e, (a-1).a = e. Если, кроме того, для ∀a, b ∈G имеет место коммутативность a.b = b.a, то группа называется коммутативной или абелевой. 3. Элементы теории графов При изложении предыдущего материала уже были использованы модели в виде графов. Наряду с теоретико-множественным описанием моделей систем представление в виде графов является одним из наиболее распространенных. Граф Г – геометрическая фигура, построенная на множестве вершин V = {v1, v2, … vm} и ребер R = {r1, r2, … rn}: Г = (V, R). (3.1) Если ребра ориентированы, то их называют дугами, а граф - ориентированным (орграфом). При этом вершины называются узлами. v1 r1 А B r2 r3 r4 v3 r1 v2 C r2 v1 D r4 r3 v4 v3 а) б) Рис. 3.1 v2 17 Примеры использования графов для моделирования: 1. Неориентированные графы описывают (моделируют) дороги между населенными пунктами А, B, C и D (см. рис. 3.1, а). 2. Орграф описывает однонаправленные каналы передачи информации (см. рис. 3.1, б). Дуга ri, связанная с злом vj, называется инцидентной этому узлу, причем, если заходит – положительно инцидентная, если выходит – отрицательно инцидентная. Два узла vk и vi смежны, если им инцидентна одна дуга. Аналогично, две дуги смежны, если они инцидентны одному узлу, причем, если одна выходит, а другая заходит – последовательно смежны, в противном случае - параллельно смежны. Дуга, выходящая из узла и в нее же заходящая, называется петлей. Узел, из которого дуги только выходят, называется истоком, а в который только заходят – стоком. Узлы сток и исток – висячие узлы. Две системы S1 и S2 с заданными на них отношениями R1 и R2 изоморфны, если: 1) их структурные элементы попарно взаимно однозначно соответствуют друг другу; 2) подмножество элементов А1 системы S1 связано отношением R1, тогда соответствующее подмножество (см. п. 1) А2 системы S2 связано отношением R2. Существует гомоморфизм – упрощенная модель исходной системы, т.е. не выполняются какие-либо из вышеуказанных условий. Связи в системе можно изображать двояко: 1) элементы – это вершины, а связи – дуги (вершинный граф), 2) элементы – дуги, а связи – узлы (реберный или сигнальный граф). Структуры графов можно представить как графически, так и структурными матрицами. Известны три вида структурных матриц, изоморфных графической модели графа: матрицы смежности, инцидентности (инциденций) и структуры связей. Матрица смежности – квадратная матрица А = {aij}, i, j =1, m, где m – число узлов, т.е. Аmxm, для которой а= 1, если есть дуга из узла vi в узел vj 0, если дуги нет. Число единиц в матрице А равно числу дуг n. Эта матрица обладает интересным свойством: если возвести матрицу А в k-ю степень, то каждый элемент матрицы Аk будет равен числу путей из узла vi в узел vj длиной в k дуг. Путь в графе – это последовательность последовательно смежных дуг, ориентированных в одном направлении. 18 Пример 3.1. 1 W1 W4 2 W5 W 3 4 3 W2 0 0 A=  1  1 0 0 1 0 0  0 0 1 2 1 0 , A= 0 1 0 0 0   0 1 0 1 1 0 1 1 0 . 0 0  0 0 Рис. 3.2 Как видно (см. рис. 3.2), через две (k = 2) смежные дуги можно попасть: из вершины 1 в вершину 4, из 2 в 1, из 2 в 3, из 3 в 4, из 4 в 1 и из 4 в 2. ♦ Таким образом, можно алгоритмически определить, существует ли путь из vi в vj длиной в k дуг. Очевидно, что если число узлов m, максимальная степень k, в которую нужно возвести А для определения самого длинного пути, равна (m – 1). Матрица инцидентности – в общем случае прямоугольная матрица В = {bij}, i = 1, m , j = 1, n , где m – число вершин, n – число ребер. Для орграфов: bij = 1, если i – начальная вершина -1, если i – конечная вершина 0, если нет связи. Для неориентированных: 1, если есть связь i-й вершины с j-м 0, если нет связи. Для примера 3.1 матрица инцидентности имеет вид: №№ вершин 1 0 + 1 − 1 1   1 0 0  2 − 1 0 B= 0 −1 0 1 0  3 ♦   1 − 1 0 1  4.  0  Матрица структуры связей С = {cij} устанавливает отношения между дугами: bij = С = ВТ⋅В, С – симметрическая матрица размером n x n, т.е. Сnxn, для которой cij = 2, если i = j или дуга ri кратна дуге -r2, если дуга ri симметрична дуге rj 1, если дуга ri параллельно смежна -1, если дуге r дуга ri последовательно смежна дуге rj 0, если дуга ri не смежна дуге rj. 19 ri ri ri ri rj rj rj rj кратные дуги симметричные дуги параллельно смежные дуги ri rj последовательно смежные дуги Рис. 3.3 Таким образом, матрица структуры связей содержит информацию о взаимной ориентации пар дуг графа. Кроме этого, могут использоваться структурные матрицы, кодирующие отдельные свойства графов: - наличие контуров (контур = замкнутый путь), - наличие путей, - отношения касания. Касающимися называются пути, контуры или пути с контурами, если они содержат хотя бы один общий узел. Сильносвязанным называется граф, в котором любой узел достижим из любого другого узла. Достижимость – это существование пути из узла vi в узел vj. Например, на рис. 3.3 путь из узла 1 в узел 4 имеет вид: узел 1 → W1 → узел 2 → W2 → узел 3 → W4 → узел 4. Может оказаться, что не все узлы достижимы из остальных узлов. В этом случае может быть W1 выделен подграф Г1, т.е. совокупность, подмноже1 2 ство узлов, для которого условие сильной связноW2 W3 сти выполняется. Например, граф Г (см. рис. 3.4) не сильносвязный, т.к. в узел 1 из узлов 2, 3 и 4 W4 нет путей. Сильносвязной компонентой Г1 для 4 3 графа Г состоит из узлов 2, 3 и 4 с соответствующими дугами W2 – W5. W5 Физический смысл сильной связности – наличие обратных связей (ОС) между всеми узлами Рис. 3.4 или, другими словами, взаимозависимость (взаимовлияние) всех переменных в графе. Важность понятия «сильная связность» вытекает из того, что практически все целенаправленные системы строятся на основе принципа обратной связи, когда информация о выходных величинах (координатах) некоторого объекта используется для формирования управляющего сигнала U этим объектом. Структура простейшей системы управления описывается графом (см. рис. 3.5), где W1 можно интерпретировать как модель объекта управления, а W2 20 – модель управляющего устройства. Узлы 1 – управление U, 2 и 4 можно интерпретировать как выходную величину объекта у, 3 (ε) –ошибка регулирования, узел 5 – задание х (желаемое значение величины у). W1 U 1 1 2 W2 3 ε 4 у х 5 Рис. 3.5 4. Модели систем 4.1. Цели моделирования систем Основными задачами моделирования является адекватное представление информации для достижения двух основных целей: во-первых, для анализа характеристик (свойств) систем и, во-вторых, для синтеза (разработки) систем, отвечающих заданным условиям. Имея в виду, что искусственные системы являются, в конечном счете, системами управления, можно сказать, что целью моделирования при анализе является оценка характеристик систем при различных уровнях представления информации об объекте, а при синтезе – разработка модели управляющей части системы (системы принятия решений). Кроме основных целей моделирование может использоваться также для проверки работоспособности управляющего устройства в разных режимах работы (данный процесс моделирования называется тестированием ), для улучшения качества процессов управления (системы управления с моделью), проверки решений параллельно с их генерированием (имитационное моделирование) и т.д. 4.2. Уровни моделирования 4.2.1. Классификация уровней моделирования Существует достаточно большое количество классификационных признаков для моделей элементов и систем, однако, наиболее общим является объем информации, который несет в себе модель. Уровень определенности информации определяет границы, при которых модель и объект или модели разного вида сохраняют гомоморфизм (иногда говорят «гоморфизм»), т.е. могут рассматриваться как адекватные в смысле определенных критериев близости. С указанной точки зрения выделим следующие уровни моделирования: 1) Концептуальный уровень, когда определяются границы системы (элемента), т.е. указываются векторы входных и выходных координат системы (элемента). 2) Топологический уровень, когда определены связи входных, выходных и внутренних переменных системы. Моделями данного уровня являются графы. Если, кроме того, указаны (хотя бы в общем виде, без задания 21 структуры операторов) интенсивности связей, то моделями этого уровня являются сети. 3) Структурный уровень, когда определена структура операторов, описывающих взаимосвязь входных, выходных и внутренних переменных. Например, взаимосвязь может задаваться функциональными статическими соотношениями, операторами описания динамики (дифференциальные, интегральные уравнения, передаточные функции и т.д.), матричными преобразованиями и т.д. 4) Параметрический уровень, когда заданы параметры операторов связей, т.е. модель данного уровня полностью определена (в той степени, в которой определены параметры) и над ней могут проводится наиболее информативные эксперименты и делаться расчеты. При использовании моделей различных уровней возникают вопросы: 1) Какие задачи позволяет решать модель того или иного уровня? 2) Для каких задач модель каждого уровня является информационно не избыточной? Ответы на эти вопросы позволяют определить минимально допустимый уровень информации для решения тех или иных задач, что, в свою очередь, позволяет минимизировать затраты ресурсов на формирование баз данных и разработку методов анализа моделей. 4.2.2. Задачи анализа свойств систем, решаемые на концептуальном уровне На концептуальном уровне могут решаться задачи декомпозиции (разбиения) на подсистемы и агрегации (объединения) подсистем в систему. Эти процедуры являются неотъемлемыми элементами анализа и синтеза сложных систем, в том числе, на основе системного подхода. Основа методов декомпозиции и агрегации – мнение экспертов, специалистов предметной области. 4.2.3. Задачи, решаемые на топологическом уровне На моделях топологического уровня могут решаться следующие основные задачи: 1) определение общих характеристик и структурных свойств системы, 2) определение эквивалентных передач на графе (сети), 3) выделение подсистем в системе. Рассмотрим пути решения некоторых задач. I. Определение структурных свойств системы Определяются следующие характеристики: Степень централизации, которая оценивает тип структуры, к которому тяготеет данный граф. Известны несколько основных типов структур (см. рис. 4.1). 22 б) скелетная Рис. 4.1 а) сетевая в) централистская Структуры сложных систем управления тяготеют к структурам иерархического типа (см. рис. 4.2), рыночных хозяйственных структур – к скелетному типу. Рис. 4.2 Количественно неравномерность загрузки элементов графа характеризуют индексами центральности. Для ненаправленного графа: β= (n − 1)(2 ⋅ Z max − n ) , Z max (n − 2) (4.1) где ( ) −1 n 1 n n  Zmax = max  ∑ ∑ d ij ∑ d ik  , i  2 i =1 j =1 k =1  (4.2) n – число вершин графа, dij – длина минимального пути (при i = j длина dij = 0). Для графа на рис. 4.1, а, когда все вершины инцидентны одному и тому же количеству ребер, β ≈ 0. Для графа на рис. 4.1, в β ≈ 1. Для ориентированного графа индекс центральности γ= n 1 ∑ (V (k ) − V(i)) , (n − 1)(V(k ) − 1) ii =≠1k (4.3) где V(i) = vi + vi – суммарное число входящих и исходящих ребер i-й вершины, а V(i) = max V(i) . i Диаметр структуры оценивается максимальным числом связей, разделяющих входные и выходные элементы графа: d = max d ij , i ∈ I, j ∈ J , i, j (4.4) 23 где I – множество вершин-истоков, J – множество вершин-стоков, dij - минимальный путь от i к j. Связность – наименьшее число вершин, удаление которых приводит к несвязному графу. Реберная связность – наименьшее число ребер, которое приводит к несвязному графу. Известны и другие характеристики: сложность, наличие контуров, петель, сильносвязных компонент, отношения касания и т.д. II. Определение эквивалентных передач Требуется установить эквивалентный оператор, описывающий связь от iго узла к j-му узлу с учетом всех связей графа. Для сигнальных графов Мезоном получено следующее соотношение: (i ) = Ф ij = ( j) ∑P k ⋅ ∆k k ∆ , (4.5) где ∆ – определитель графа: ∆ = 1 − ∑ W∞ , r + ∑ W∞ , r ⋅ W∞ , p − ∑ W∞ , r ⋅ W∞ , p ⋅ W∞ , q + ... r r,p (4.6) r , p, q W∞,r (r = 1,2,…) - передаточный коэффициент r-го разомкнутого контура (определяется как произведение передач входящих в контур дуг), W∞,r. W∞,p (p,r = 1, 2, …, r ≠ p) – произведение «пар» передаточных коэффициентов некасающихся контуров, далее аналогично для «троек», «четверок» и т.д. некасающихся контуров; Pk – передача k-го прямого пути, определяемая как произведение передаточных коэффициентов дуг, образующих путь; ∆k – минор k-го прямого пути (составляется аналогично определителю, но для подграфа, полученного из исходного графа при удалении узлов, принадлежащих k-му прямому пути). III. Выделение подсистем в системе Задача может решаться: - формальными методами, - концептуально (в этом случае концептуальное выделение должно подтверждаться на основе формальных процедур). Формальные методы обычно базируются на анализе топологии (структуры системы), концептуальные – на функциональных характеристиках в тех или иных аспектах. Рассмотрим формальные методы выделения подсистем, базирующиеся на двух основных подходах: а) подсистемами считаются несвязные сильные компоненты графа. Порядок выделения следующий: - определяется множество всех сильносвязных компонентов; 24 - на полученном множестве выделяется подмножество пар, троек и т.д. сильносвязных компонентов, которые являются некасающимися. б) подсистемами считаются сильносвязные компоненты, получающиеся при удалении дуг-мостов. Анализ графа обычно проводится в предположении, что число удаляемых дуг должно быть минимально. Вначале отыскиваются единичные дуги, удаление которых нарушает сильную связность графа, но сохраняет не менее двух сильных компонент. Если таких друг нет, ищутся пары дуг, удаление которых вызывает описанный эффект и т.д. Концептуальные методы выделения подсистем базируются на неформальных признаках выделения подсистем. Например, для графа на рис. 4.3,а можно насчитать пять сильносвязных компонент (кроме самого графа), но концептуально подсистемами можно считать, например, подграфы, изображенные на рис. 4.3, б и в. -R11 W11 W31 W24 -R22 W22 W33 -R33 -R22 W22 -R11 W11 W33 -R33 W54 W54 б) подсистема S1 а) граф S в) подсистема S2 Рис. 4.3 Проверку силы связности компонент можно осуществлять различными методами, в частности: - с помощью матрицы Бристоля [17 ], - метода Розенброка (метод проверки диагональной доминантности) [18 ], - метода Вавилова-Имаева [19 ]. Рассмотрим последний метод подробнее на примере графа, изображенного на рис. 4.4. Предположим, что системы S1 и S2 не связаны, то есть организованы в систему S ошибочно. Определитель такой несвязной системы будет равен n ∆∞ = ∏ ∆ i , (4.7) i =1 где n – число подсистем (в примере n = 2), ∆i – определитель i-й подсистемы. В примере ∆1 = 1 + W11.R11, ∆2 = 1 + W22.R22, (4.8) 25 ∆∞ = 1 + W11.R11 + W22.R22 + W11.R11.W22.R22. (4.9) S1 -R11 1 W11 W23 2 S W41 3 W22 S2 4 -R22 Рис. 4.4 Определитель системы с учетом существующих связей: ∆ = 1 + W11.R11 + W22.R22 + W11.R11.W22.R22 – W23.R11.W41.R22. (4.10) Можно видеть, что разность определителей δ∆ = ∆ - ∆∞ = – W23.R11.W41.R22. (4.11) Очевидно, что если δ∆ << 1 , ∆∞ (4.12) «добавкой» δ∆ можно пренебречь и подсистемы S1 и S2 рассматривать как независимые. Модуль в (4.12) берется потому, что, во-первых, «добавка» δ∆ может быть как со знаком «+», так и со знаком «-», во-вторых, значения δ∆, ∆ и ∆∞ это не обязательно действительные числа. Операторы передач Wij, Kkp (i, j, k, p – целые числа) могут быть произвольными объектами, в том числе комплексными числами и матрицами. Поэтому модуль может пониматься, по крайней мере, в трех смыслах: - для действительных чисел – число без знака (со знаком «+»); - для комплексных чисел p = α + j.ω, где j = − 1 - мнимая единица: p = α 2 + ω2 ; - для матриц – определитель матрицы. (4.13) 26 4.2.4. Модели структурного уровня Различают модели элементов в статике и в динамике. Моделями статики являются функции вида y = f(x), где х и у соответственно входные и выходные координаты системы, которые не зависят от времени или их значения рассматриваются как установившиеся (t→∞). f – функция, которая может задаваться аналитически, графически или алгоритмически. Динамические модели и характеристики описываются линейными и нелинейными дифференциальными уравнениями, разностными уравнениями. уравнениями в частных производных, операторными уравнениями, передаточными функциями и др. 4.2.5. Модели параметрического уровня Прежде, чем говорить о задании параметров, необходимо сказать, что параметры могут быть измерены в разных шкалах. Существует четыре уровня измерений: 1) шкала наименований (примеры: Иванов, Эверест,…); 2) шкала порядка – имеется признак, по которому производится сравнение, но не обязательно в виде числа (пример: холодно – тепло – горячо); 3) шкала интервалов – используются числа, характеризующие разности границ интервалов (пример: температура в гр. Цельсия или Фаренгейта); 4) шкала отношений. Для шкал 3-го и 4-го уровней справедливы группы аксиом: 1) аксиомы тождественности А = В (или А ≠ В), если А = В, то В = А, если А = В и В = С, то А = С; 2) аксиомы рангового порядка (для их выполнения требуется, чтобы выполнялось условие сравнимости и транзитивности; например, нельзя сравнивать бифштекс с книгой) если А > B, то B < A, если А > В и В > С, то А > С (то же для нестрогого порядка); 3) аксиомы аддитивности если А = Р и В > 0, то А + В > Р, А + В = В + А, если А = Р и В = Q, то А + В = P + Q, (А + В) + С = А + (В + С). Кроме переменных, измеряемых действительными числами, существуют комплексные числа, задаваемые парой (а,в) действительных чисел, одно из которых (а) условно измеряет действительную, а второе (в) - мнимую составляющую. 27 Кроме того, существуют также переменные, измеряемые нечеткими, лингвистическими «числами», характеризуемые парой (х, µх), где х нечеткая переменная, µх - функция принадлежности к какому-либо множеству. С помощью таких переменных измеряют (оценивают) человеческие ощущения. Данные числа сложно отнести к какому-либо из вышеперечисленных типов и следует согласиться, что это особый тип чисел. 4.3. Классификация моделей систем Одна из возможных классификаций моделей, используемых в процессе анализа и синтеза (создания) систем, представлена на рис. 4.5. Среди моделей различного вида и назначения выделяются два принципиально различных типа: -первый тип предназначен для описания характеристик (свойств) систем, т.е. для целей анализа; -второй тип предназначен для принятия каких-либо решений с целью достижения целей. В дальнейшем эти типы моделей будем условно обозначать как Мс – модели систем и Мт – модели требований. Рассмотренные выше примеры моделей, в основном, могут быть отнесены к типу Мс. Модели Качественные СС ПС Математические НЛМ ПФ Статистические Аппроксиматоры Вероятностные Механистические модели Корреляционные ЛМ ДУ АМ Рис. 4.5 Основными элементами моделей типа Мт являются: - -цели и критерии, по которым осуществляется выбор решения; - модели принятия решений: законы регулирования и управления, алгоритмы формирования управлений, схемы и процедуры принятия решений и т.д. 28 Все возможные варианты постановки задач построения целенаправленных систем являются бинарными отношениями (декартовым произведением) этих двух типов моделей S = Мс × Мт. Далее в п.п. 4.4 и 4.5 будут рассмотрены некоторые виды моделей типов Мс и Мт. 4.4. Модели систем типа Мс Рассмотрим несколько видов классификационных признаков и соответствующие классы моделей, не претендуя на попытку обоснования их выбора. Заметим только, что сочетания различных классификационных признаков могут образовывать достаточно большое разнообразие практически выделяемых классов моделей. Аппроксиматоры, называемые также в литературе «черными ящиками» (black box), «формальными моделями», являются разновидностью математических моделей, описывают функциональные связи между входами и выходами моделируемой системы без учета (при отсутствии) каких-либо знаний о топологии системы. Коэффициенты таких моделей могут не иметь какого-либо физического смысла, не соотносятся, например, с технологическими параметрами процессов. В этом заключается недостаток таких моделей. Однако, эти модели эффективны в случае невозможности или трудности построения строгих математических описаний поведения систем. Распространенными примерами таких моделей являются нейронные сети (НС). Механистические модели. Если знания о функционировании модели формализованы, то для описания таких моделей могут быть использованы механистические модели (ММ), к числу которых относят: - алгебраические модели (АМ), представляющие собой системы алгебраических и трансцендентных уравнений, - дифференциальные уравнения (ДУ) и системы ДУ, - передаточные функции (ПФ), - логические модели (ЛМ) и др. Такие модели обычно получают путем анализа физических и химических основ моделируемых процессов. Результатом анализа является прямая или обратная модель процесса. Прямая модель отражает влияние входных координат процесса на выходные и может быть представлена в виде функции Y = F(X), где Х и Y - множества входных (в том числе управляющих) и выходных координат соответственно. В ряде случаев необходимым является получение обратной модели вида X = Q(Yн), 29 где Yн - множество наблюдаемых или измеряемых значений выходных координат процесса. В большинстве случаев построение обратных моделей является некорректной задачей, т.е. имеющей более одного решения или вообще его не имеющей. Статистические модели являются технологией построения моделей путем описания свойств процесса через статистические переменные и соответствующие статистические оценки этих переменных. По своей сути эти модели содержат элемент неопределенности. Модели, согласно этой технологии, строятся с использованием методов статистического анализа, теории игр, теории информации и т.п. Разновидностями данных моделей являются вероятностные и корреляционные модели. Вероятностные модели используют плотности вероятности переменных процесса. При этом наиболее часто используются нормальный и экспоненциальный законы распределения. Использование таких моделей ограничено тем, что при числе переменных более двух требуется большое число экспериментов, возникают трудности, связанные с коррелируемостью параметров. Динамические модели и характеристики описывают поведение систем в динамике, т.е. во времени. Наиболее часто динамические модели представляются линейными и нелинейными дифференциальными уравнениями, разностными уравнениями в частных производных, операторными уравнениями, передаточными функциями и др. Линейными называются элементы, для которых справедлив принцип суперпозиции: Λ(х1 + х2) = Λ(х1) + Λ(х2), где Λ - некоторый оператор. Таким свойством обладают операторы суммирования, интегрирования, дифференцирования. При исследовании динамических свойств систем может быть использованы прикладные математические методы операционного исчисления. Например, функционирование некоторой системы описывается ДУ вида d2y dy dx a 2 2 + a1 + a 0 y = b1 + b0 x , dt dt dt (4.14) где х и у - входная и выходная величины. Если в данное уравнение вместо x(t) и y(t) подставить функции X(s) и Y(s) комплексного переменного s такие, что ∞ X(s) = ∫ x ( t )e − st dt ∞ и Y(s) = ∫ y( t )e − st dt , (4.15) то ДУ (4.14) при нулевых начальных условиях равносильно линейному алгебраическому уравнению a2 s2 Y(s) + a1 s Y(s) + a0 Y(s) = b1 X(s) + b0 X(s). 30 Такой переход от ДУ к алгебраическому уравнению называется преобразованием Лапласа, формулы (2.2) соответственно формулами преобразования Лапласа, а полученное уравнение - операторным уравнением. Новые функции X(s) и Y(s) называются изображениями для x(t) и y(t) по Лапласу, тогда как x(t) и y(t) являются оригиналами по отношению к X(s) и Y(s). Переход от одной модели к другой заключается в замене знаков диффеdn 1 ренциалов n на операторы sn, знаков интегралов ∫ ...dt на множители , а саs dt мих x(t) и y(t) - изображениями X(s) и Y(s). Для обратного перехода от операторного уравнения к функциям от времени используется метод обратного преобразования Лапласа. Общая формула обратного преобразования Лапласа: f (t ) = 1 +∞ jωt ∫ F( jω)e dω , 2π − ∞ где f(t) - оригинал, F(jω) - изображение при s = jω, j - мнимая единица, ω - частота. Преобразование ДУ по Лапласу дает возможность ввести понятие передаточной функции, характеризующей динамические свойства системы. Например, операторное уравнение 3s2Y(s) + 4sY(s) + Y(s) = 2sX(s) + 4X(s) можно преобразовать, вынеся X(s) и Y(s) за скобки и поделив друг на друга: Y(s)*(3s2 + 4s + 1) = X(s)*(2s + 4), W (s) = Y (s) 2s + 4 = 2 . X (s) 3s + 4s + 1 Полученное выражение называется передаточной функцией. Передаточная функция - это отношение изображения выходного воздействия Y(s) к изображению входного X(s) при нулевых начальных условиях: W (s) = Y (s) . X (s) Передаточная функция для линейных элементов часто является дробнорациональной функцией комплексной переменной: B(s) b 0 + b1s + b 2s 2 + ... + b m s m , = W (s) = A (s) a 0 + a 1s + a 2s 2 + ... + a n s n где B(s) = b0 + b1s + b2 s2 + … + bm sm - полином числителя, А(s) = a0 + a1s + a2 s2 + … + an sn - полином знаменателя. 31 Если вместо s подставить выражение s = j.ω, получаем преобразование Фурье, которое характеризует связь между частотными характеристиками входных и выходных сигналов элемента. Частотные характеристики дают возможность анализировать описание системы с учетом динамики. В последнее время более широко используется описание динамики систем методом пространства состояний. Для описания динамики элементов систем используется в данном методе матричная запись ДУ: • X = A ⋅ X + B ⋅ U, (4.16) где А – матрица коэффициентов, U – матрица входов или управлений, Х – матрица пространства состояний: Х = (х1, х2, … хn)Т. В данном случае хi называется переменной состояния или фазовой переменной («Т» – символ транспонирования). Предположим, что динамические свойства объекта описываются ДУ вида an dn y d2y dy dmu d 2u du + ... + a + a + a y = b + ... + b + b + b0u , 2 1 m 2 1 dt n dt 2 dt dt m dt 2 dt (4.17) где ai и bi – коэффициенты, у – выходной сигнал, u – входной сигнал объекта. Если ввести переменные состояния: x 1 = y, d 2 y dx 2 x3 = 2 = , и т.д., dt dt dy dx 1 x2 = = , dt dt то левая часть ДУ (4.17) примет вид (после деления на (-аn ): − a0 a a dx x 1 − 1 x 2 − ... − n −1 x n − n . an an an dt Можно записать уравнение в матричном виде:  x• 1   0 •   0 x 2   •  = 0  x 3   ...  ...   a  •  − 0  x n   a n 1 1 ... a − 1 an ... a − 2 an 1 ... a − 3 an 0  x  1   0  x   0    2   ... 0  ⋅ x  +  0  ⋅ U . 3    ... ...   ...   ...    a b ... − n −1   x   0  a n   n   a n  ... ... Решением полученного матричного уравнения является матрица Х. Для определения выходных параметров yi уравнение (4.16) дополняется уравнением Y = C.X + D.U, 32 где С (p×n) – матрица связей, D (p×q) – матрица обхода, p – число выходных параметров уi, q – число входных параметров ui. Решение матричных уравнений для некоторых случаев может быть произведено аналитически, в частности, для однородного ДУ вида • X = A ⋅ X. (4.18) Прямое преобразование Лапласа для данного уравнения дает s.X(s) – X0 = A.X(s), где Х0 – матрица начальных условий, т.е. начальные условия по переменной у, по скорости ее изменения, ускорению и т.д. Отсюда получено Х(s) = X0.[s.E – A]-1 = Ф(s).X0, где Е – единичная матрица, Ф(s) – изображение фундаментальной матрицы Ф(s) = [s.E – A]-1. Оригиналом фундаментальной матрицы является матричный экспоненциал Ф( t ) = e A⋅ t (A ⋅ t ) 2 (A ⋅ t ) 3 ≈E+A⋅t + + + ... . 2! 3! Тогда решение ДУ (4.18) можно получить в виде ряда с шагом ∆t по времени: Х0 – начальные условия, Х(∆t) = Ф(∆t).Х0, Х(2. ∆t) = Ф(2.∆t).Х(∆t) и т.д. Качественные модели Существует множество примеров, когда природа процессов принятия решений или функционирования объекта не может быть описана в виде математических соотношений в виду наличия нечетких определений и лингвистических операций или ограничений на технологические параметры и т.д. Решением этой проблемы является использование качественных моделей, которые наиболее часто представляются в терминах нечетких множеств. 4.5. Модели требований типа МТ Спектр моделей требований весьма широк, т.к. отражает уровень формализованности как целей и критериев, так и моделей принятия решений. На одном конце этого спектра лежат модели требований для наиболее простых систем принятия решений – регуляторов или простейших видов управляющих устройств, используемых для формирования управлений в автоматических системах регулирования (АСР), а на другом – схемы экспертного, субъективного, характера. 33 4.5.1. По своей сути модели регуляторов являются моделями типа Мс механистического класса. Если считать, что информацией является ошибка регулирования е = х – у, где х – желаемое значение регулируемого параметра, у – его текущее значение, то управляющее воздействие может формироваться, например, с использованием трех наиболее часто используемых законов: П-закона регулирования (пропорциональный), для которого управляющее воздействие определяется как U = K1.e, где K1 – коэффициент усиления регулятора; И-закона (интегральный), для которого 1 U= Tè t t ∫ e( t )dt = K 0 ∫ e( t )dt ; Д-закона (дифференциальный), для которого U = Tä de dt . ♦ Обычно используются сочетания перечисленных законов регулирования: ПИ- и ПИД-законы. 4.5.2. В более сложных случаях, когда требуется описывать процессы принятия решений с участием человека на тех или иных этапах, эти модели оказываются мало пригодными. Некоторые особенности моделей принятия решений с участием человека рассмотрим на примере оптимизационной задачи, когда решение принимается на основе процедуры оптимизации по множеству показателей или критериев - векторному критерию. Заметим, что задача формирования управляющих переменных на основе процедуры оптимизации по одному (скалярному) критерию, также как и на основе стандартных законов регулирования, является полностью формализованной и относится к алгоритмическим методам принятия решений. Векторный критерий состоит из набора (множества показателей), в числе которых могут быть показатели с разными направлениями шкалы полезности. Направление шкалы полезности связывает категории «больше»-«меньше» с категориями «лучше»-«хуже». Например, чем выше цена, тем хуже для покупателя, но чем выше качество товара, тем лучше для того же покупателя. При оптимизации по скалярному критерию решение получается как наилучшее (с учетом ограничений), соответствующее минимуму или максимуму 34 критерия в зависимости от направления шкалы полезности. Иное дело, если показателей несколько. Рассмотрим задачу выбора решения для случая, когда имеется векторный критерий состоит из двух показателей: I  J=  1. I 2  Оба показателя имеют одинаковые шкалы полезности: чем меньше, тем лучше. Если для какого-либо показателя направление шкалы не совпадает с установленным, то для изменения направления шкалы полезности вводится показатель вида I’I = 1 / Ii или I’1 = - I1 (I’I – уровень «плохости»). Рассмотрим задачу покупки товара наилучшего качества за наименьшие деньги (см. рис. 4.6). Ресурсом оптимизации (варьируемым параметром или параметрами q), от которых зависят значения показателей I1 (q),I2(q) будут варианты товара у разных продавцов. Движение начнем с произвольного выбора товара, точка 0. Далее будем выбирать товар либо более дешевый и не худшего качества, либо более качественный, но не более дорогой товар. При этом каждая последующая точка пути соответствует лучшему соотношению цены и качества. В конце концов, наступит момент (точка 3), когда описанную процедуру выполнить не удастся, т.е. одновременное улучшение по двум показателям будет невозможно. I2 M 3 1 O 2 I20 I1 I10 Рис. 4.6 Точка 3 принадлежит множеству решений М ={q* | arg{J → opt}} – множеству Парето (множество компромиссов, переговорное множество). Это множество не улучшаемых в смысле векторного критерия решений, (в рассматриваемом случае opt = min). Существенно, что решение задачи оптимизации по векторному критерию носит принципиально множественный характер и для выбора наилучшего варианта нужен суперкритерий, который устанавлива- 35 ет приоритеты между показателями. Приоритеты, в конечном счете, устанавливает человек – лицо, принимающее решение (ЛПР). Существует несколько методов получения решений из множества Парето: 1) метод сворачивания векторного критерия в глобальный скалярный, 2) метод последовательных уступок, 3) метод минимизации по частному критерию или показателю и ряд других. Метод сворачивания векторного критерия Сворачивание может производится по одной из следующих форм: 1) Аддитивный критерий n J = ∑ α i ⋅ Ii , i =1 где αi – веса (весовые коэффициенты) показателей. Если показатели имеют разные шкалы или размерности, то для облегчения выбора весов иногда эти показатели нормируют: Îi = I1 , I1o где I1o - минимально (максимально) возможное значение показателя. n Веса также нормированы, т.е. ∑ α i = 1 . i =1 Физический смысл минимизации такого критерия – это минимизация общих потерь (применений, когда все показатели имеют одинаковый смысл). 2) Линейно-квадратичный критерий n J = ∑ α i (⋅I i ) 2 . i =1 Минимизация по такому критерию эквивалентна нахождению точки, ближайшей к началу координат (с учетом весов). Физический смысл - минимизация среднеквадратичных (статистических) потерь. 3) Минимаксный (Чебышёвский) критерий J = max (α i ⋅ I i ) . 1≤ i ≤ n Физический смысл – минимизация самой большой потери. 4) Модель справедливого компромисса n n J = ∏ Iiα ⇔ J = ∑ α i ⋅ ln Ii . i i =1 i =1 Для случая n = 2 имеем α = α1 = α2 = 0,5 и решение ∆I1 ∆I 2 = . I1 I2 36 То есть относительные потери по одному критерию приводят к относительному выигрышу другого и наоборот. Метод последовательных уступок Метод требует большой определенности информации о приоритетах показателей (об их важности). Последовательность применения метода: 1 шаг. Все показатели должны быть расположены в порядке убывания приоритетов. 2 шаг. Отыскивается минимум старшего (наиболее важного) показателя и назначается уступка I1 ≤ I1* + ∆I1. 3 шаг. В рамках назначенной уступки проводится минимизация очередного критерия и т.д.: min I1 → I1* → I1 ≤ I1* + ∆ I1 min I2 → I*2 → I2 ≤ I*2 + ∆ I2 … min In → I*n → In ≤ I*n + ∆ In . Метод минимизации по частному критерию или показателю Метод можно рассматривать как вариант предыдущего, если уступки по всем критериям, кроме наименее важного, известны. Пример Рассмотрим задачу оптимизации по двум показателям (частным критериям) I1 и I2. Допустим, что I1 = 1 + x 2   , 1  → min x I2 = x + 1  (4.19) где х – переменная (ресурс оптимизации). Свойства решений задач оптимизации по частным критериям. Задача 1. I1 → min. Область определения х ∈(-∞, +∞). Результат: arg min I1 = 0 , то есть абсолютный минимум I1 достигает при х = 0. x { } Задача 2. I2 → min. Область определения х ∈(-∞, -1) и х ∈(-1, +∞). 37 { } arg min I 2 → −(1 + ε) при ε → 0. При этом I2 → -∞. x На плоскости критериев {I1, I2} = I1×I2 частным решениям задач 1 и 2 соответствуют точки а(1,1) и с(∞, -∞). Возможные методы получения точек из множества Парето. I. Метод минимизации одного частного критерия (для данной размерности задачи совпадает с методом последовательных уступок) Предположим, что по критерию I1 делается уступка (вводится ограничение) δ1: I 2 1 -1 I1 ≤ I1* + δ1, А В 1 2 3 I1 -1 Рис. 4.7 где I1* = min I1. Тогда, как можно видеть из анализа задачи (4.19), существуют два важных случая: 1) При δ1 < 1 аргумент может изменяться в пределах х ∈(-1, 1). Решение задачи: x = arg{x → max}, то есть при x ∈ (− δ1 , δ1 ) решение будет x = δ1 и I 2 = 1 δ1 + 1 . Случаю х ∈(-1, 1) соответствует отрезок кривой между точками А и В (см. рис. 4.7). 2) При δ1 ≥ 1 решение задачи 2 дает значение х = -1 и I2 = I2*, то есть в точке В решение «срывается» в -∞. Другими словами, при всех δ1 ≥ 1 существует единственное решение х = -1. II. Метод сворачивания векторного критерия в глобальный скалярный Выберем аддитивную форму сворачивания: J = c ⋅ I1 + (1 − c) ⋅ I 2 = c ⋅ (1 + x 2 ) + 1− c , c ∈ [0; 1] x +1 и попытаемся найти экстремум функции классическим методом: dJ 1− c = 2⋅c⋅x − = 0. dx ( x + 1) 2 Приходим к кубическому уравнению 2.с.х.(х + 1)2 = 1 – с, х ≠ -1 - из (4.20). Если представить это уравнение в виде 1− c = ( x + 1) 2 , 2⋅c⋅x (4.20) 38 то легко убедиться, что при с = 1 (абсолютный приоритет критерия I1) получается решение х = 0. При с = 0 (приоритет I2) решения не существует. Рассмотрим качественно минимизацию (4.20). J При некотором с ≠ 0 и с ≠ 1 получается качественно график функции J(x) (см. рис. 4.8). Как видно, при неограни1 ченном диапазоне изменения х решение задачи (4.20) и, соответственно, задачи x -1 δ (4.19) будет х = -1. Если ограничить x > -1, то решение существует с opt, зависящим от с. Причем при уменьшении с (при с → 0) точРис. 4.8 ка х = arg{min J} смещается в сторону увеличения. 1− c . Например, при с = 0,001 имеДля с << 1 примерное решение: x = 3 c ем х = 10. Принятие решения на основе оптимизационной процедуры при известных показателях принципиальных трудностей не вызывает. Неопределенными могут оказаться только приоритеты ЛПР. К сожалению, так бывает очень редко. Обычно имеется неопределенность как в моделях объекта типа Мс, так и в моделях принятия решений (критериях и способах получения решения). Рассмотрим некоторые виды моделей типа Мт, используемые для принятия решений в более сложных случаях. К числу таких моделей относится большая группа моделей семиотического типа и группа экспертных методов. 4.5.3. Семиотика – общая теория, исследующая свойства систем знаков, каждому из которых сопоставляется значение. Для семиотического подхода характерны три уровня исследования знаковых систем: 1) синтактика – изучает синтаксис, правила построения и связи в знаковых системах; 2) семантика – изучает интерпретацию, смысл знаковых систем; 3) прагматика – изучает отношения между знаковыми системами и теми, кто их использует. Теоретическая семиотика изучает совокупность семантики и синтактики, является основой металогики, математических исчислений. Является, в конечном счете, моделью фрагментов мира людей. В эту группу моделей входят: - логические модели четкой (конечно-автоматные (КАМ) модели) и нечеткой логики (НЛМ); - семантические сети (СС); - продукционные системы (ПС); 39 - предикатные системы (ПрС) и ряд других. Рассмотрим некоторые из моделей этой группы. Логические модели Конечные автоматы. Логические модели этого типа базируются на алгебре логики. В булевой алгебре используются два элемента «0» и «1» (или {0, 1}). Примечание: кроме булевой логики имеются также многозначные логики, например, {-1, 0, 1}, а также нечеткие логики, в которых переменные принадлежат значениям 0 и 1 с различной степенью уверенности. Если используются две переменные Х и Y, принимающие по два значения: 0 = «ложь» и 1 = «правда», то для булевой алгебры определены логические операции (см. табл. 4.1): Х Y 1 1 1 1 1 1 Название логической операции 1 1 - конъюнкция (лог. умножение) 1 - дизъюнкция (лог. сложение) 1 - тождественность Таблица 4.1 Обозначение в выражениях И, AND, &, *, V ИЛИ, OR, +, Λ =, ~ А также функция одного операнда - отрицание (функция «НЕ», NOT, «¬»), например, если Х = 0, то ¬Х = 1. Существуют и другие функции: стрелка Пирса, штрих Шеффера, импликация и др. Из булевых переменных и логических операций могут быть построены логические выражения. Для формирования любой логической формулы достаточно только двух логических операций, одна из которых – отрицание. Для этого применяются законы де Моргана-Шеннона: AΛB = AV B AVB = AΛ B . и Для получения логической функции используют таблицу состояния, которая может иметь произвольный вид. Например, см. табл. 4.2. Таблица 4.2 X Y Z F 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 40 Для синтеза логической функции существуют две основные формы записи логических выражений: 1) совершенная дизъюнктивная нормальная форма (СДНФ), представляющая собой дизъюнкцию конъюнкций логических переменных; иными словами, логическая сумма слагаемых, каждое из которых является логическим произведением переменных и называется «термом»: n F = (XΛYΛZ)V (...)V (...)... = V D i , i =1 где Di – дизъюнкт (терм), n – число дизъюнктов в выражении; 2) совершенная конъюнктивная нормальная форма (СКНФ), представляющая собой конъюнкцию дизъюнкций, иначе называемую записью по нулю: n F = (XVYVZ)Λ (...)Λ (...)... = V K i , i =1 где Ki – конъюнкт, n – число конъюнктов. Правило записи выражения в СДНФ: если в строке, где значение функции равно F = «1», какая-либо переменная принимает значение «1», то эта переменная записывается в дизъюнкт в чистом виде, если принимает значение «0», то с отрицанием. 2 терм 1 терм Y Х 1 1 Х=0 1 1 1 Х=1 Z 3 терм Рис. 4.9 Правило записи выражения в СКНФ: если в строке, где значение функции равно F = «0», какая-либо переменная принимает значение «0», то эта переменная записывается в конъюнкт в чистом виде, если принимает значение «1», то с отрицанием. Так, для функции F по табл. Х имеем СДНФ: F = (XΛ YΛ Z)V(XΛYΛZ)V(XΛ YΛ Z)V(XΛYΛ Z)V(XΛYΛZ) или то же самое в более простой записи: F = X Y Z + XYZ + X Y Z + XY Z + XYZ . Для упрощения записи логических функций используются: - логические преобразования, - карты Карно, 41 - диаграммы Вейтча, - методы целенаправленного перебора (алгоритм Мак-Класки). Рассмотрим метод упрощения полученного логического выражения с помощью карты Карно. Карта Карно представляет собой особый вид таблиц состояний, имеющих прямоугольный вид и состоящих из 2n квадратов, где n – число входных переменных. Стороны карты помечаются именами переменных таким образом, чтобы половина карты соответствовала «1»-му значению переменной, а другая – «0»-му, причем в карте должны быть учтены все возможные сочетания значений переменных (состояния входов). В результате каждая ячейка карты будет соответствовать определенному набору значений входных переменных. В ячейки заносятся соответствующие значения минимизируемой функции. Так, для рассматриваемого примера карта представлена на рис. 4.9. Далее для записи выражения в СДНФ производятся объединения ячеек карты, содержащих «1» так, чтобы данные ячейки образовывали прямоугольники или квадраты размером 1, 2, 4, 8, 16 и т.д. ячеек. Каждый такой прямоугольник будет соответствовать своему терму, причем, чем он больше, тем проще будет терм. Прямоугольники могут пересекаться. После этого записываются термы по принципу: если данному прямоугольнику соответствует «1»-е значение какой-либо переменной, то данная переменная входит в терм в чистом виде; если «0»-е значение, то в инверсном; если соответствует как «1»-е, так и «0»-е, то в терм переменная не входит. Наконец, термы объединяются в логическое выражение с помощью функций дизъюнкции. Для рассматриваемого примера получено выражение, состоящее из трех термов: F = YZ + Y Z + XY Z . Запись выражений в СКНФ производится аналогично, но объединяются ячейки с нулями. Термы записываются в виде дизъюнкции переменных по принципу: если прямоугольнику соответствует «1»-е значение какой-либо переменной, то данная переменная входит в конъюнкт в инверсном виде; если «0»-е значение, то в чистом; если соответствует как «1»-е, так и «0»-е, то в конъюнкт переменная не входит. После конъюнкты объединяются функциями конъюнкции. Для рассматриваемого примера: F = (Z + Y)(X + Y + Z) . Из логических выражений подобного вида могут быть образованы логические последовательности, моделирующие процессы принятия решений. Элементы теории нечетких множеств и нечеткой логики Нечеткие множества и логические операции на нечетких множествах (далее НС - нечеткие системы) в последнее время стали завоевывать ведущее положение в системах управления, использующих слабоструктурированную, например, лингвистическую информацию. Они позволяют использовать эври- 42 стический опыт управления процессами в тех случаях, когда моделирование процессов принятия решений формальными методами не дает удовлетворительного эффекта. В результате появились технические и программные продукты, выпускаемые ведущими мировыми производителями как бытового, так и технологического оборудования. В частности, расширение языков программирования промышленных контроллеров на базе нечетких систем (Fuzzy Logic Programming) предложено для стандарта IEC 1131. Нечеткая логика появилась как расширение Булевой логики путем использования логических (нечетких) переменных, принимающих любые значения в интервале [0, 1]. Она была введена доктором Л. Заде (Lotfi Zadeh) в 1960-х годах как способ моделирования неопределенностей естественного языка. Основная идея Заде состояла в том, что человеческий способ рассуждений в большинстве случаев не может быть описан традиционными математическими формализмами. Основная цель нечеткой логики - моделирование человеческих рассуждений и объяснение человеческих приемов принятия решений в ходе решения различных задач. µх 0,5 1,0 1,5 2,0 Рис. 4.10 2,5 рост, м Основным понятием НС является нечеткая логическая переменная х, которой поставлена в соответствие некоторая функция принадлежности µ(х), характеризующая уверенность в принадлежности элемента какому-либо множеству. µ 1 1,0 µ(х1) µ(х2) 1,5 µ(х3) µ(х4) 2,0 Рис. 4.11 µ(х5) 2,5 рост, м 43 Существует несколько типовых видов функций принадлежности (см. рис. 4.12): µ 1 1) µ(х) = а а) х (четкая логика); µ(х) = exp(-k.x2), k > 0; х б) 3) µ 1 µ(х) = а1 в) а2 х µ(х) = а1 а2 г) х 1, х ≤ a1 x − a1 , х ∈ [a1, a2] a 2 − a1 0, x ≥ a2; 4) µ 1 0, х > a 2) µ 1 1, х ∈ [0, a] 0, х ≤ a1 x − a1 , х ∈ [a1, a2] a 2 − a1 1, x ≥ a2. Рис. 4.12 Пример. Введем переменную х, характеризующую рост человека. Допустим, что это лингвистическая переменная означает свойство «высокий». Поскольку представления людей о том, какой рост человека считать высоким четко не определены, данная переменная будет являться нечеткой. Интуитивно полученная зависимость ее значения от роста в метрах может иметь, например, вид (рис. 4.10): для характеристики человеческого роста может быть введено множество переменных Х = {х1, х2, х3, х4, х5}, соответствующих значениям: х1 - «очень низкий», х2 - «низкий», х3 – «средний», х4 – «высокий», х5 – «очень высокий». Соответственно переменным определяются функции µ(хi), которые могут иметь вид, показанный на рис. 4.11. Операции над нечеткими множествами: 1) сравнение: А = В, если µА(х) = µВ(х); 2) дополнение (отрицание): B = A , если µВ(х) = 1 - µА(х); 3) пересечение А∩В: µА∩В(х) = min(µА(х), µB(х)); 44 4) объединение А∪В: µА∪В(х) = max(µА(х), µB(х)); 5) разность: A − B = A ∩ B; 6) сумма: µА+В(х) = µА(х) + µB(х) – µА(х)*µB(х); µА×В(х) = µА(х)*µB(х); 7) произведение: 8) концентрация («очень»): µcon(A)(х) = µ2А(х); 9) растяжение («довольно»): µ dil ( A ) ( x ) = µ ( A ) ( x ) . Системами НЛ называются системы, которые оперируют с нечеткими понятиями и используют при этом нечеткую логику. Системы НЛ могут быть классифицированы на три основных типа: 1) простые (pure), 2) системы Токаги и Суджено, 3) системы с фаззификатором и дефаззификатором (fuzzy). В простых системах используется механизм нечеткого вывода R X→Y , где R – композиционные правила. Недостаток простых систем в том, что входные и выходные переменные являются нечеткими. Системы Токаги и Суджено. Предлагается выходные переменные взвешивать пропорционально значениям входных. Системы с фаззификатором и дефаззификатором получаются из простых систем, если перед применением нечетких операций входные переменные фаззифицировать (перевести в нечеткий вид), а после - дефаззифицировать выходные (преобразовать из нечеткого вида в четкий или аналоговый). Продукционные системы Наиболее простым с точки зрения построения и широко используемым типом моделей принятия решений являются продукционные системы. Они представляют собой структурированные наборы продукционных правил (ПП) вида PR = , где S - сфера применения данного правила; N - номер или имя правила; F - предусловие применения (условие активизации), содержащее информацию об истинности и приоритетности данного правила; A ⇒ C - ядро ПП; W - постусловие. Сфера применения S обозначает принадлежность ПП какому-либо определенному этапу функционирования ПС или состоянию процесса принятия решения. В состав правил могут входить условия активизации F, которые представляют собой либо переменную, либо логическое выражение (предикат). Когда F принимает значение «истина», ядро продукции может быть активизировано. Если F «ложно», то ядро не активизируется. 45 Постусловие W описывает, какие изменения следует внести в ПС, и актуализируется только после того, как ядро продукции реализовалось. Интерпретация ядра может быть различной в зависимости от вида А и С, находящихся по разные стороны знака секвенции «⇒». Прежде всего, все ядра делятся на два типа: детерминированные и недетерминированные. В детерминированных ядрах при актуализации ядра и при выполнимости А правая часть ядра выполняется обязательно; в недетерминированных ядрах В может выполняться с определенной вероятностью. Таким образом, секвенция «⇒» в детерминированных ядрах реализуется с необходимостью, а в недетерминированных - с возможностью. Наиболее часто в ПС используют детерминированные ПП вида «если А то С», где А и С - логические выражения, которые могут включать в себя другие выражения; А называется антецедентом, С - консеквентом. ПП могут быть доопределены логическими выражениями, определяющими инициируемые процедуры, которые имеют место в случае отсутствия ее активности: «если А то С1 иначе С2». Продукционные правила, используемые в СУ, учитывают накладываемые ограничения, а также показатели эффективности, по которым определяются управляющие воздействия и которые часто являются неизмеряемыми лингвистическими переменными. Достоинствами продукционных систем являются: - удобство описания процесса принятия решения экспертом (формализация его интуиции и опыта); - простота редактирования модели; - прозрачность структуры. ПС в качестве моделей применимы в следующих случаях: - не могут быть построены строгие алгоритмы или процедуры принятия решений, но существуют эвристические методы решения; - существует, по крайней мере, один эксперт, который способен явно сформулировать свои знания и объяснить свои методы применения этих знаний при принятии решения; - пространство возможных решений относительно невелико (число решений счетно); - задачи решаются методом формальных рассуждений; - данные и знания надежны и не изменяются со временем. Сети Петри Сети Петри (СП) являются примером семантических сетей, представленных разновидностью ориентированных двудольных графов. Двудольный граф включает вершины двух типов: позиции (обозначаются кружками) и переходы 46 (обозначаются планками). Сеть Петри может быть формально представлена как совокупность множеств: N = (P, T, G, Ω), где P = {p1, p2… pn} – множество всех позиций (n – количество позиций), Т = {t1, t2… tm} – множество переходов (m – количество переходов), G = (Gp-t, Gt-p) – множество дуг сети: Gp-t = (p×t), Gt-p = (t×p) – множества дуг, ведущих соответственно от переходов к позициям и от позиций к переходам (дуг, соединяющих однородные вершины, не существует), Ω = {ω1, ω2… ωk} – множество весов дуг (k – количество дуг). Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции pi, как mi, то маркировка всей сети: M = {m1, m2… mn}. Тогда полное определение сети Петри, включая данные о начальной маркировке, можно записать в виде PN = (N, M0), где М0 – начальная маркировка сети. При моделировании процессов принятия решений с помощью СП ее позиции интерпретируют собой некоторые условия, состояния, значения переменных и т.д. Переходы интерпретируют собой логические предложения (принятие решений), соответствующие выполнению действий, при этом входные позиции – условия выполнения действий, выходные позиции – результат выполнения действий. Действие (переход) связано с принятием какого-либо решения, которое инициировано определенными условиями и результатом которого является новое состояние (условие). Пример. Схема принятия решений при попытке получить деньги из банкомата (см. рис.4.13). ● Р6 t4 Р1 t1 Р3 t2 t6 Р4 Р7 Р2 ● t5 t9 t3 t7 Р5 t8 Р8 Рис. 4.13 Смысл позиций: Р1 – карта (ее наличие); Р2 – исправность банкомата; Р3 – введенный код; Р4 – код набран правильно, запрашивается сумма; Р5 – код на- 47 бран неправильно; Р6 – сумма доступна; Р7 – сумма недоступна (нет такого количества денег на карте); Р8 – деньги (получены). Смысл переходов: t1 – банкомат принимает карту и делает запрос в банк, ввод кода; t2 – запрос суммы; t3 – повторный ввод кода; t5 – выдача сообщения о недоступности суммы; t6 – выдача денег; t7 – повторный набор суммы; t8 – забрать карту из банкомата (другой исход: имеется другая карта, с которой также нужно снять деньги – см. дуги, обозначенные пунктиром); t9 – выдача сообщения, что код неверный. ♦ Роль указателей мощности потоков выполняют фишки или метки (●). Формально метка – это знак выполнения соответствующего условия. Переход срабатывает только в том случае, если во всех входных позициях имеется достаточное количество меток (по меньшей мере, по одной). При срабатывании перехода из входных позиций изымаются метки (в случае взвешенной СП изымается количество меток, соответствующее весам дуг, связывающих входные позиции с данным переходом), а во входные – добавляются (для взвешенной СП – также соответственно весам дуг). Начальная маркировка СП есть начальное состояние системы. Таким образом, если осуществить начальную маркировку СП, то использованием формальных правил можно описать логику работы системы и произвести анализ ее работоспособности. Переходы меток описываются графом достижимости (ГД), у которого каждой вершине соответствует определенная маркировка, а каждой дуге – переход, который срабатывает при данной маркировке. Таким образом, граф достижимости представляется как GD = (V, E), где V – массив вершин (маркировок, соответствующих вершинам): V = {М1, М2 … Мq}, Мi – i-я маркировка, q – количество маркировок; Е = {e1, e2 … ep} – массив дуг, связывающих вершины (р – количество дуг). Каждая дуга представляется как совокупность ei = {α1, α2, Т}, где α1 и α2 – номера начальной и конечной вершин графа; Т = {t1, t2, … tk} – массив переходов, соответствующий дуге; k – количество одновременно срабатывающих переходов при переходе от одной маркировки к другой. Алгоритм построения графа по исходной СП: 1. За исходную берется маркировка М0 и ей присваивается метка «новая». 2. Для каждой «новой» маркировки выполнять следующие операции: 2.1. Для «новой» маркировки Мнов определяются все переходы, которые могут быть запущены, а также все возможные комбинации этих переходов. 2.2. Для каждого разрешенного перехода или комбинации переходов производятся следующие действия: 2.2.1. Определяется маркировка М’, которая образуется при срабатывании данного перехода (комбинации переходов). 48 2.2.2. Просматриваются все маркировки на пути от М’ к начальной М0. Если на пути находится маркировка М”, элементы которой больше либо равны соответствующим элементам новой и которая не равна М’, то вместо элементов m’i, которые больше, чем элементы mi маркировки М0, записывается символ «ω» (бесконечность). В массив Е записывается дуга с соответствующими α1, α2 и Т. 2.2.3. Просматриваются все маркировки графа. Если находится маркировка, равная новой, то в массив Е записывается новая дуга, у которой α1 = α2 и равны номеру найденной маркировки. М1 t1 t9 М2 t2 t3 М6 М3 t5 t7 М7 t4 М4 М1 М2 М3 М4 М5 М6 М7 Таблица 4.3 (Р1 Р2 Р3 Р4 Р5 Р6 Р7 Р8) (11000000) (00100000) (00010000) (00000100) (00000001) (00001000) (00000010) t6 М5 t8 Рис. 4.14 2.2.4. Если в п.п. 2.2 и 2.3 маркировки не найдены, то создается новая вершина графа, в которую записывается новая маркировка, в массив Е записывается дуга, у которой α1 равна номеру исходной маркировки, α2 - номеру новой маркировки, Т – набор переходов, срабатывание которых привело к переходу от одной маркировки к другой. Далее определяется массив всех разрешенных переходов и расчет продолжается, начиная с п. 2.2. Для рассмотренного выше примера СП граф ГД имеет вид (см. рис. 4.14), список маркировок приведен в табл. 4.3.С помощью ГД могут быть определены свойства СП и, в конечном счете, моделируемой системы. К ним относятся: - живость (отсутствие тупиковых состояний); - ограниченность (сеть ограниченна, если символ «ω» не входит ни в одну вершину графа); - безопасность (сеть безопасна, если в метки вершин входят только «0» и «1») – физически безопасность означает отсутствие зацикливаний; - правильность (если сеть безопасная и живая, то она правильная); - обратимость (сеть обратима, если в графе имеется хотя бы одна дуга, направленная к начальной маркировке М0); 49 - пассивность переходов (переход ti пассивен, если он не соответствует ни одной дуге графа); - число возможных состояний Nсост. Сеть Петри называется k-ограниченной, если в любом состоянии в любой позиции скапливается не более k фишек. Любая система должна представляться правильной сетью. Для рассмотренного примера можно сделать вывод, что сеть правильная, обратимая и без пассивных переходов. Практическое значение и наиболее ясную интерпретацию имеют два вида СП: 1) Маркированные графы – каждая позиция такой СП должна иметь не более одного входного и одного выходного перехода; 2) А-сети (автоматные сети) – каждый переход такой СП должен иметь не более одной входной и одной выходной позиции. СП моделируют очень широкий класс логических задач. Существует много разновидностей сетей. Главное их достоинство – возможность анализировать логический процесс по неизбыточным моделям. Кроме того, формализованные методы анализа СП в сочетании с возможностью декомпозиции дают возможность решать очень сложные задачи принятия решений. Методология SADT Примером реализации семантической сети (см. раздел 5.4) является методология SADT (Structure Analysis and Design Technique), которая реализуется в различных автоматизированных программных пакетах анализа и конструирования для целей структуризации и формализации процессов принятия решений в организационных системах. В частности, широко известна так называемая IDEF-методология построения моделей систем, согласно которой модель системы представляется в виде совокупности трех моделей: - IDEF0 – функциональной модели, отображающей причинно-следственные связи между функциями и подфункциями в системе; - IDEF1X – информационная модель, показывающая структуру информации; - IDEF/CPN – динамическая модель, базирующаяся на так называемых раскрашенных СП (Colored Petri Net) и позволяющая просматривать и анализировать систему с точки зрения динамики. В терминах IDEF0 модель системы представляется в виде комбинации блоков и дуг. Блоки используются для представления функций системы и сопровождаются текстами на естественном языке. Дуги представляют множества объектов(как физических, так и информационных) или действия, которые образуют связи между функциональными блоками. Место соединения дуги с блоком определяет тип интерфейса. Управляющие выполнением функции данные входят в блок сверху, в то время как информация, которая подвергается воздействию функции, показана с левой стороны блока; результаты выхода показаны с правой стороны. 50 Механизм (человек или автоматизированная система), который осуществляет функцию, представляется дугой, входящей в блок снизу (рис. 4.15). Рис. 4.15 Важнейшая цель информационной модели заключается в выработке непротиворчивой интерпретации данных и взаимодействий между ними с тем, что необходимо для интеграции, совместного использования и управления целостностью данных. Появление понятий концептуальной схемы данных привело к методологии семантического моделирования данных, т.е. к определению значений данных в контексте их взаимосвязей с другими данными. Методология IDEF1X - один из подходов к семантическому моделированию данных, основанный на концепции "Сущность - Отношение" (EntityRelationship ), это инструмент для анализа информационной структуры систем различной природы. Информационная модель, построенная с помощью IDEF1X-методологии, представляет логическую структуру информации об объектах системы. Эта информация является необходимым дополнением функциональной IDEF0-модели, детализирует объекты, которыми манипулируют функции системы. Концептуально IDEF1X-модель можно рассматривать как проект логической схемы базы данных для проектируемой системы. Основными объектами информационной модели являются сущности и отношения. Сущность представляет множество реальных или абстрактных предметов (людей, объектов, мест, событий, состояний, идей, пар предметов и т.д.), обладающих общими атрибутами или характеристиками. Отдельный элемент этого множества называется "экземпляром сущности". Каждая сущность может обладать любым количеством отношений с другими сущностями. Сущность является "независимой", если каждый экземпляр сущности может быть однозначно идентифицирован без определения его отношений с другими сущностями. 51 Сущность называется "зависимой", если однозначная идентификация экземпляра сущности зависит от его отношения к другой сущности. Сущность обладает одним или несколькими атрибутами, которые либо принадлежат сущности, либо наследуются через отношение, обладает одним или несколькими атрибутами, которые однозначно идентифицируют каждый образец сущности и может обладать любым количеством отношений с другими сущностями модели. Если внешний ключ целиком используется в качестве первичного ключа сущности или его части, то сущность является зависимой от идентификатора. И наоборот, если используется только часть внешнего ключа или вообще не используются внешние ключи, то сущность является независимой от идентификатора. Пример независимой сущности приведен на рис. 4.16, зависимой - на рис. 4.17. Рис. 4.16 Рис. 4.17 Динамическая модель (IDEF/CPN) осуществляет проверку функциональной модели системы путем преобразования ее в СП. При этом функциональным блокам ставятся в соответствие переходы СП, а дугам – позиции. 4.5.4. Группа экспертных моделей представляет собой, по существу, схемы организации опроса экспертов и принятия решений. Конкретные методы из группы экспертных моделей рассматриваются в разделе 5.5. 52 5. Современная методология научных исследований и методы системного анализа 5.1. Основные понятия На сегодняшний день основным является так называемый системный подход (СсП) к научному познанию и исследованиям. Как расширение этого подхода можно рассматривать также синергетический (СгП) и информационный подходы (ИфП). Системный подход базируется на целостном видении исследуемых объектов с точки зрения целей исследования. В отличие от «бытового» подхода (от простого к сложному, от элемента к системе), при решении задач он исходит из того, что исследование (или решение задачи) начинается с целей исследования, которые на основе анализа объекта исследования редуцируются до задач анализа и формирования моделей элементов (до решения подзадач) с учетом взаимосвязи элементов. При этом организуются два взаимодействующих по принципу обратной связи процесса: 1) декомпозиция исследования (задачи) на этапы (подзадачи); 2) разработка, выполнение этапов (решение подзадач) и интегрирование результатов, полученных на этапах, для достижения цели исследования (решения задачи). Синергетический подход – метод учета и использования случайного фактора (хаоса) для организации систем и управления ими. Хаос выступает при этом не как дезорганизующий фактор, а как необходимое условие появления более сложной и организованной системы. Развитие и построение сложных самоорганизующихся систем, в том числе систем с искусственным интеллектом, связывается с синергетикой. В качестве примитивного примера СгП может служить решение задачи укладки множества гвоздей разного размера в банку. Обычный, детерминированный, подход сводится к тому, что гвозди надо отсортировать, рассчитать оптимальный способ укладки и произвести укладку. Синергетический подход надо потрясти банку (внести фактор случайности) и они улягутся (самоорганизуются). Информационный подход– развитие СсП на информационные системные процессы, характерной особенностью которых является отсутствие закона сохранения энергии. Применение СсП к разрешению проблемы гармонии и дисгармонии приводит к принципам функционирования гомеостатических систем. Изучается управление, обеспечивающее существование систем в условиях антагонизма двух и более подсистем. Введем еще несколько, используемых в теории систем терминов. Концепция – совокупность основных понятий с их связями (система понятий), выражающая суть некоторой идеи. В число основных понятий входят, как правило: 1) цель и средства ее достижения, 2) критерии эффективности путей (альтернатив) достижения целей, 53 3) модель, описывающая зависимости между альтернативами, 5) модель принятия решений. Системная парадигма – основные элементы той или иной концепции, модель постановки проблем и их решения. Катастрофа – скачкообразное изменение состояния при малых изменениях входных и фазовых координат системы. Зона бифуркации – кризисное состояние с непредсказуемым исходом; район, ситуация, область значений переменных, где возможна катастрофа. Одним из важнейших принципов при организации сложных систем является принцип компенсации энтропии: энтропия системы может быть уменьшена только за счет увеличения энтропии другой системы. В целенаправленных системах это осуществляется за счет увеличения энтропии внешней среды. Когнитивная структуризация – метод формирования гипотезы (топологической модели) о функционировании объектов на основе опыта и представлений человека. Когнитивная карта – это знаковый (взвешенный) орграф, отражающий причинно-следственные связи между элементами системы, как их понимает человек. 5.2. Методология системного анализа Это конкретизация системного подхода в отношении проблем управления и проектирования систем путем использования математических и эвристических процедур. СсП – это методология, которая указывает направление поиска и разработки методов анализа для решения проблем. СсП характеризуется принципами: 1) элемент объекта описывается в той мере, в которой он важен для понимания объекта; могут рассматриваться структурные и функциональные аспекты и методы; 2) неотделимость свойств системы от условий ее существования, т.е. учет эффектов взаимодействия со средой; 3) связи и взаимообусловленность свойств целого и элементов (в том числе интегративное качество, эмержентность); 4) источник преобразования системы и ее функций лежит обычно в самой системе; поэтому основное направление преобразований – самоорганизация, базирующаяся на широко понимаемом принципе обратной связи. Системный анализ (СА) конкретизирует СсП путем разработки моделей систем (Мс) и моделей требований (Мт), то есть является инструментом СсП. Методы СА различаются уровнем определенности Мс и Мт. Случай, когда эти модели формализованы (выражены в виде математических соотношений), относится обычно к области науки, называемой исследованием операций. Если же в Мс и Мт в качестве элемента содержится субъективный фактор (человек), то этот случай относится к СА. 54 5.3. Общая схема принятия решений Простые целенаправленные и целеустремленные системы могут быть представлены не менее, чем двумя элементами: объектом и управляющим устройством (УУ). На рис. 3.4 изображена простейшая схема системы управления, где в качестве элемента принятия решений выступает УУ. В дальнейшем рассматриваются более сложные системы. Будем различать следующие ситуации: 1) когда цели и методы их достижения не формализованы (Мс и Мт не определены до моделей параметрического уровня определенности), т.е. имеется неопределенность, требующая при принятии решения элементов творчества – это проблема; 2) когда известна цель и возможные методы ее достижения, хотя четкого алгоритма решения может и не быть - это задача. Системный анализ необходим в первую очередь для разрешения проблем. Общая схема принятия решений приведена на рис. 5.1. 10исследование вариантов вариант 1 результат 1 вариант 2 результат 2 вариант n результат n 2выбор 9-определение задач 11-база знаний
3-результаты 7-критерии 8-цели 1- модель принятия решений 6-потребности 4-уровень удовлетворения потребностей 5-результат обучение Рис. 5.1. Общая схема принятия решений Во всех случаях, когда что-то не определено, возникает задача разработки модели принятия решений, включающих элементы, которые устанавливают пути устранения неопределенности. Как правило, это требует пополнения знаний (базы знаний) и в том или ином виде связано с необходимостью проведения экспериментов. 55 Анализ схемы принятия решений позволяет выделить несколько вложенных циклов (контуров обратной связи), которым соответствуют типовые варианты принятия решений, рис. 5.2. IV III II I принятие решения Рис. 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). 56 Оптнер 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) испытание чувствительности решения Таблица 5.1 Никаноров 1) обнаружение проблемы 2) оценка актуальности проблемы 3) анализ ограничений 4) определение критериев 5) анализ системы 6) поиск альтернатив 7) выбор альтернатив 8) принятие решения 9) реализация решения 10) оценка результатов Общими для всех методик являются этапы: 1) постановка проблемы, 2) анализ ограничений, 3) разработка альтернатив, 4) выбор альтернативы, 5) разработка методов реализации, 6) реализация, 7) оценка эффективности. Перечисленные этапы и будем считать элементами методологии СА. По степени уменьшения уровня формализованности процедур, реализующих перечисленные этапы методологии СА можно выделить следующие группы методов СА: 1 группа – аналитические методы – полная формализация схемы; эта группа в большей мере может быть отнесена к области Исследования операций; 2 группа –математические методы, когда в значительной степени используются формальные приемы анализа и эпизодически – возможности человека; 57 3 группа – семиотические методы, в которых широко используется эвристики и логика: математическая и (или) неформальная (нечеткая); 4 группа – имитационное моделирование, когда процесс выполнения этапов неотделим от процессов разработки моделей и получения информации по модели на основе формальных и эвристических процедур; 5 группа – эвристическое программирование – группа методов экспертного оценивания и принятия решений. 5.5. Аналитические методы системного анализа Это, в основном, формализованные методы, использующие математизированного вида модели систем и модели принятия решений при ограничениях, наложенных различного рода допущениями при моделировании. Формализованно описываются такие этапы, как: а) процедура генерирования альтернатив (например, перебором); б) оценка альтернатив по системе показателей на основе моделей системы; в) выбор решения (модель компромисса). По виду моделей Мс и Мт различают такие, например, задачи: - анализ свойств (характеристик); - синтез систем (синтез топологии, структуры, параметров) при детерминированных условиях среды и системы; - то же при случайных характеристиках среды и системы (задачи массового обслуживания); - проектирование систем и ряд других. Перечисленные задачи идут в порядке возрастания сложности и, как правило, нижележащие задачи включают как этап решения вышележащих. Заметим, что требование полного детерминизма не накладывается. Модель системы может быть описана как: - детерминированная (дифференциальные уравнения, передаточные функции, структурные схемы, сети и т.д.); - стохастическая – топология, структура, параметры могут содержать неопределенности, вызванные случайными факторами, характеристики которых известны (мат. ожидание, дисперсия, вид закона распределения случайной величины др.); - нечеткая (топология, структура, параметры могут содержать неопределенности, вызванные незнанием). Модель принятия решений может включать такие процедуры как: - вычисление показателей на основе моделей, - способ получения единственного решения на основе оптимизации по критерию или выбора по прецеденту или ситуации. В свою очередь, могут использоваться различные схемы оптимизации: - линейное программирование (модель является системой линейных уравнений и ограничений), - нелинейное программирование, - динамическое программирование, 58 - вариационные методы и т.д. 5.6. Математические методы Рассмотрим некоторые методы СА в качестве типичных примеров методов этой группы. Метод логического ранжирования Метод используется для задач составления расписаний. Назначение метода: упорядочивание этапов выполнения некоторых работ. Предположим, что имеется набор работ (этапов выполнения работ), причем некоторые виды работ не могут быть начаты до того, как будут окончены другие работы. Например, определены причинно-следственные отношения между отдельными работами (см. рис. 5.3): работа Р0 является завершающей, ей должны предшествовать работы Р1, Р2 и Р3, работе Р1 должны предшествовать работы Р4, Р5 и Р9 и т.д. Продолжительность каждой работы примем за единицу. Для принятия решений нужно выработать критерий, по которому будет происходить оптимизация. В качестве критерия возьмем вес работы. Он чем больше, тем раньше работу необходимо выполнить. Для решения задачи составляется матрица весов (см. табл. 5.2). В последней колонке таблицы отмечены веса каждой работы, равные сумме чисел в соответствующей строке. Отсюда можно определить последовательность выполнения работ: Р11, Р14 → Р12, Р13 → Р7, Р10 → Р5, Р6, Р8 → Р4, Р9 → Р1, Р2, Р3. То есть, сначала выполняются работы Р11 и Р14, после них Р12 и Р13 и т.д. Может быть учтена неравнозначность видов работ, выполняющихся одновременно. Р0 Р1 1 Р4 2 Р8 1 Р9 2 Р2 Р5 3 Р3 1 Р6 3 Р11 7 Р12 6 3 Р10 4 Р7 4 Р13 6 Рис. 5.3 7 Р14 59 Р0 Р1 Р2 Р3 Р4 Р5 Р6 Р7 Р8 Р9 Р10 Р11 Р12 Р13 Р14 Р0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Р1 1 1 1 1 1 1 1 1 1 Р2 Р3 1 1 1 1 1 Р4 Р5 Р6 Р7 Р8 Р9 Р10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Р11 Р12 Таблица 5.2 Р13 Р14 Σ 1 1 1 2 3 3 4 3 2 4 7 6 6 7 Метод анализа иерархий Это один из достаточно формализованных и классических методов СА, используемый для разрешения проблемы принятия решений в условиях многокритериальности. Назначение и идея метода: проводится иерархическая декомпозиция проблемы на задачи таким образом, чтобы облегчить человеку принятие решений для отдельных задач на основе парных, а не многокритериальных сравнений. После этого синтез приоритетов проводится математическими методами. Название метода связано с тем, что сначала для проблемы строится иерархия задач, а затем эти задачи решаются, начиная с нижнего уровня, при этом результат решения задач нижнего уровня используется при решении задач более высоких уровней. Этап 1. Декомпозиция проблемы и заполнение матриц суждений Используются три принципа: Принцип 1. Декомпозиция, при которой производится как структурная, так и функциональная дифференциация. Пример. Имеется цель: купить дом. Есть варианты покупки, различающиеся по эффективности в смысле некоторых плохо структурированных критериев. Проблема представляется иерархически: Первый уровень (верхний) – основная цель; Второй уровень – критерии: 1 - размеры, 2 - удобство транспорта, 3 - место расположения дома, окружающая среда, 4 - стоимость, 60 5 - возраст дома, состояние, 6 - наличие гаража и приусадебного участка и т.д.; Третий уровень – претенденты (альтернативы) на покупку. Принцип 2. Элементы нижнего (i-го) уровня должны быть попарно сравнимы по отношению к элементам более высокого ((i-1) –о) уровня. Принцип 3. Сопоставление вариантов производится на основе принципа дискриминации суждений, то есть элементы сравниваются попарно с точки зрения их воздействия на результат (на элемент более высокого уровня иерархии) и представляются в виде квадратной матрицы (для второго уровня в примере размер матрицы равен 6х6). Каждый элемент имеет свой вес, определяемый, например, экспертом. Заполнение матрицы идет в произвольном порядке по правилу: если элемент строки важнее элемента столбца, то в соответствующую ячейку ставится число r ∈ [1; 9] (значение определяет степень важности одного элемента относительно другого), в противном случае ставится число r-1. Для каждого критерия строится аналогичная матрица сравнительной оценки вариантов, например, домов А, В, С и D. Таблица 5.3. Цель Кр1 Кр2 Кр3 Кр4 Кр5 Кр5 Кр1 1 2 3 4 ¼ 1/3 Таблица целей Кр2 Кр3 Кр4 ½ 1/3 ¼ 1 ½ 1/3 2 1 1/3 3 3 1 4 1 1 4 2 2 Кр5 4 1/4 1 1 1 1 Кр6 3 ¼ ½ ½ 1 1 Таблица 5.4. Кр1 A B C D А 1 2 3 1 В ½ 1 2 1 Таблицы для каждого критерия С D … Kp6 A 1/3 2 … A 1 ½ 1 … B ½ 1 1 … C 3 1 1 … D 4 B 2 1 ½ 3 C 1/3 2 1 2 D ¼ 1/3 ½ 1 Приблизительная связь приоритета (веса) и лингвистической оценки: 1/1 – равный вес; 3/1 –слабое предпочтение; 5/1 - довольно сильное предпочтение; 7/1 – сильное предпочтение; 9/1 – очень сильное предпочтение. Сравнение критериев ведется обычно по трем критериям: 61 - что важнее (обычно для критериев), - что более вероятно (для сценариев), -что более предпочтительно (для альтернатив). Этап 2. Синтез приоритетов Это один из способов решения проблемы многокритериальности. Синтез приоритетов (СП) – это вычисление собственных векторов, которые после нормализации и являются векторами приоритетов. Собственные векторы искать сравнительно трудоемко, поэтому достаточно близкие оценки можно получить с помощью геометрического среднего, для чего элементы каждой строки перемножаются и из результата извлекается корень n-й степени. Например, для Кр1 в матрице целей: Кр1: 1*1/2*1/3*1/4*4*3 = ½ ⇒ 6 1 / 2 = 0,917 , Кр2: 2*1*1/2*1/3*1/4*1/4 = 0,0417 ⇒ 6 0,0417 = 0,616 , Кр3: 3*2*1*1/3*1*1/2 = 1 ⇒ 6 1 = 1, Кр4: 4*3*3*1*1*1/2 = 18 ⇒ 6 18 = 1,435 , Кр5: ¼*4*1*1*1*1 = 1 ⇒ 6 1 = 1, Кр6: 1/3*4*2*2*1*1 = 16/3 ⇒ 6 16 / 3 = 1,23 . 6 Далее оценки нормируются путем деления на сумму ∑ = 6,193 ; i =1 α1 = 0,917 / 6,193 = 0,148; α4 = 1,435 / 6,193 = 0,23; α2 = 0,616 / 6,193 = 0,1; α5 = 1 / 6,193 = 0,16; α3 = 1 / 6,193 = 0,16; α6 = 1,23 / 6,193 = 0,198. Полученные оценки – это матрица – строка приоритетов критериев α(1х6) . Далее для каждого из домов (альтернатив) рассчитываются приоритеты в смысле каждого из критериев: Для критерия Кр1 получим: для А: 4 2 * 1 / 2 * 1 / 3 * 2 = 0,76 , для В: 4 2 *1 *1/ 2 *1 = 1, для С: для D: 4 4 3 * 2 * 1 * 1 = 1,56 , 1 * 1 * 1 * 1 = 1. 62 Сумма равна 0,76 + 1 + 1,56 + 1 = 4,32, поэтому нормированные значения приоритетов: β11 = 0,175, β12 = 0,23, β13 = 0,36, β14 = 0,23 . Аналогично для остальных критериев получим β21,… ,β24; β3,… ,β34; β41,… ,β44; β51,… ,β54; β61,… ,β64. Данные приоритеты образуют матрицу В(6х4). Приоритеты альтернатив с учетом двух уровней, т.е. матриц α и В, получаются путем перемножения Ц = α х В, где Ц – матрица-строка глобальных приоритетов, т.е. оценки с точки зрения цели. Этап 3. Оценка согласованности приоритетов Оценивается согласованность локальных приоритетов, т.е. правильности заполнения матриц парных сравнений. Заметим, что данный этап может выполняться сразу после заполнения матриц. В качестве оценки используются индекс согласованности (ИС) и отношение согласованности (ОС): ИС = λ max − n , n −1 где n – число сравниваемых элементов, λmax - максимальное собственное значение матрицы суждений (Ц, Кр1, Кр2…), λmax ≥ n: Wi αj . j =1 i =1 W j n n λ max = ∑ ∑ ОС = ИС / СС, где СС – случайная согласованность, определяемая по табл. 5.5. Должно быть ОС ≤ 0,1…0,2, иначе следует пересмотреть матрицу суждений. n СС 3 0,58 4 0,9 5 1,12 6 1,24 7 1,32 8 1,41 Таблица 5.5 9 10 1,41 1,49 63 1,6 1,4 1,2 1 0,8 0,6 0,4 0,2 1 2 3 4 5 6 7 8 9 10 Рис. 5.4 Группа математических методов решения сложных экспертиз Как было видно в методе анализа иерархий, синтез приоритетов более высокого уровня в отношении вариантов самого низкого уровня проводится по соотношению Ц(1×m) = α(1×n)хВ(n×m), где В – матрица приоритетов нижнего уровня по отношению к приоритетам верхнего уровня; α – приоритеты высшего уровня (критериев); m – число вариантов нижнего уровня; n – количество критериев. Эта идея реализуется в методе решающих матриц. n Если начать с задания матрицы γ предпочтений для альтернатив (нижний), (n -й уровень) по отношению к элементам (n-1) -о уровня, матрица Аn-1, то получим матрицу-строку An-2, учитывающую приоритеты двух нижних уровней. Продолжая процедуру формирования матриц приоритетов более высоких уровней n An-2 = γ An-1 и умножения их на матрицы нижних уровней, получим для матрицы цели Ц0 =.γn Аh-1.Аn-2….А1. В отличие от метода анализа иерархий назначение приоритетов на каждом уровне проводится многокритериальным, а не парным сравнением, что требует большей информированности эксперта. Метод дерева целей еще менее формализован и ограничен, чем предыдущий. Существует несколько типовых схем координации целей подсистем по уровням для сложных систем принятия решений. Методы АИ и РМ по виду взаимодействия элементов соседних уровней относятся к так называемым ромбовидным иерархическим структурам. Для ромбовидной структуры характерно наличие зависимостей целей (i + 1) уровня от одних и тех же элементов i-го уровня (см. рис. 5.5). 64 Ц0 Ц1 Ц2 Рис. 5.5 Метод дерева целей, как следует из его названия, не может использоваться для задач подобного вида, что является большим ограничением метода. В то же время очень большая выразительность и простота метода, являющегося методом когнитивной структуризации для большого круга практических задач, сделали его достаточно употребительным (рис. 5.6). Ц0 Ц1 Ц2 Рис. 5.6 Идея расчета глобальных приоритетов в методе дерева целей реализуется в несколько этапов: 1) строится граф (когнитивная карта), отражающий взаимодействие целевых функций между элементами различных уровней. 2) для каждой связи назначаются и нормируются веса элементов нижнего уровня для целей верхнего уровня. 3) вес (приоритет) альтернатив рассчитывается как произведение весов от альтернативы к вершине. 5.7. Семиотические методы Семиотические методы базируются на моделях семиотического типа и относятся к области интересов Теории и методов искусственного интеллекта. Помимо перечисленных моделей семиотического типа, используются такие виды моделей, как нейронные сети, фреймы, предикатные системы и т.д. Рассмотрение этих методов выходит за рамки возможностей данного пособия. 5.8. Группа экспертных методов Отличие экспертных методов от всех предыдущих заключается в том, что помимо формирования процедуры принятия решений при известных предпоч- 65 тениях эксперта ставится задача формирования и оценки правильности экспертных весов. Известны следующие экспертные методы: - метод анкетирования, - метод дискуссии, - метод интервьюирования, в частности, метод Дельфы (наиболее формализованный), - метод сценариев, - метод «мозгового штурма» и т.д. Метод дискуссии заключается в обмене мнениями, но решение принимает ЛПР. Метод «мозгового штурма»: собирается группа лиц из разных областей и каждый предлагает варианты решения данной проблемы, при этом критика запрещена. Может оказаться, что какое-нибудь «абсурдное» мнение окажется правильным. Синетика – генерирование решений (альтернатив) на основе ассоциативного мышления. Метод аналогичен «мозговому штурму», но подбираются специалисты с ассоциативным характером мышления и обладающие психологической совместимостью. Обсуждение ведется в режиме свободной дискуссии. Метод сценариев заключается в составлении некоторых деревьев, отражающих причинно-следственные связи между посылами и результатами. Обычно составляются три сценария: пессимистический (для наихудших условий), оптимистический и наиболее вероятный. Анкетирование и интервьюирование относятся к наиболее субъективным методам принятия решений. Рассмотрим идею метода Дельфы. В основу метода Дельфы положены следующие положения: 1) ставящиеся вопросы допускают возможность численного оценивания вариантов; 2) ответ на вопрос обосновывается экспертом; 3) ответы должны базироваться на достаточном объеме информации, которая может быть слабо формализованной. Обработка анкет состоит в том, что оценки экспертов разбиваются на квартили, т.е. на интервалы ответов, примерно равные четверти мнений от числа экспертов. Квартиль – одна из числовых характеристик распределения вероятностей. Если взять некоторую случайную величину Х, мнения экспертов от 0 до 1 с функцией распределения F(Х) – вероятность соответствующего Х, то квартилью порядка Р называется число К такое, что F(Кр) < Р, F(Кр + ε) ≥ Р, ε → 0. То есть квартиль – это диапазон изменения переменной, соответствующий мнению каждой четверти экспертов. Медиана характеризует «среднее» мнение экспертов, крайние квартили – разброс мнений. Например, мнение каждого эксперта Х ∈ [0, 1], тогда выделяется примерно четверть экспертов, которые утверждают, что величина Х ∈ [Х1, Х1+]. В результате опроса формируется плотность распределения мнений в виде ступен- 66 чатого графика или в идеале, при большом числе экспертов, непрерывной кривой. 1 этап. Формирование группы координаторов (штаба). 2 этап. Выбор группы экспертов, т.е. лиц, принимающих решения (ЛПР). Выбор проводится на основе анкет для экспертов: вопросы анкеты формируются, исходя из целей координаторов. Например: 1) практический опыт решения аналогичных задач, 2) уровень образования, 3) возраст и т.д. 3 этап. Составляется вопросник (анкеты) по существу проблемы с указанием числовых критериев ответов. Это начало первого тура. 4 этап. Обработка ответов. Каждый эксперт отвечает на вопросы и обосновывает свое решение. Работа ведется анонимно. Мнения экспертов упорядочиваются по оси Х, и эксперты разбиваются на четыре группы. Мнения крайних групп экспертов озвучиваются (доводятся до всех экспертов) с обоснованиями. 5 этап. Выделение группы решений-претендентов на выход в следующий тур. Составление (коррекция) вопросников 2-го тура. 6 этап. Проводится 2-й тур аналогично первому. Далее 3-й тур и т.д. Обычно необходимы 3-4 тура. Критерий окончания процедуры – отсутствие изменений в мнениях экспертов. Существует два варианта: 1) найдено общее мнение, решение принято; 2) эксперты к единому мнению не пришли, требуются дополнительные исследования. Близким к методу Дельфы является Дельфийское совещание. Отличие данного метода: обработка анкет не проводится анонимно, а мнение экспертов просто озвучивается. 5.9. Игровые методы принятия решений Игровые методы принятия решений рассматривают вопросы принятия решений в условиях: 1) конфликтного взаимодействия элементов системы, 2) неопределенности, 3) сложности задачи принятия решений, вызванной многообъектностью системы. Существует пять принципов конфликтного взаимодействия: 1) антагонизм, 2) бескоалиционное взаимодействие, 3) коалиционное взаимодействие, 4) кооперативное взаимодействие, 5) иерархическое взаимодействие с правом первого хода сверху. Теория игр – математическая теория конфликтных ситуаций. Ее цель – дать инструмент для выработки разумного поведения участников конфликта. Наиболее простой случай ситуаций, для которых имеется неопределенность – это случай конфликтных ситуаций, когда сталкиваются противополож- 67 ные интересы двух или более групп. Выигрыш каждой стороны зависит от поведения соперника, а оно неизвестно. Игра ведется по правилам, т.е. должны быть указаны права и обязанности участников. Игра может быть парной и множественной. Каждый участник делает ходы, которые могут быть личные и случайные. Некоторые игры (часто азартные) не являются предметом теории игр. Если ходы число случайные, то это предмет для теории вероятности. Если существуют правила вида «если ситуация А, то я поступлю В», значит принята стратегия игры. В зависимости от числа стратегий могут быть конечные и бесконечные игры. Оптимальной называется стратегия, которая обеспечивает максимальный выигрыш. Если есть случайные ходы, то говорят о максимизации выигрыша в среднем. Игра называется игрой с нулевой суммой, если алгебраическая сумма выигрыша всех участников равна нулю. Самая простая игра с нулевой суммой называется антагонистической (игра со строгим соперником). Теория таких игр наиболее развита и строга. Рассмотрим игру G с игроками А и В. Будем считать, что «мы» - это А, а противник – В. Пусть у нас имеются m возможных стратегий Аi, а у противника – n стратегий Bj, то есть игра будет (m×n). Обозначим выигрыш А через aij, где i - стратегия А, j – стратегия В. Предполагается, что для всех пар стратегий Аi и Вj выигрыш aij известен (а значит, проигрыш В также известен aij = - bij). Представим информацию в виде таблицы 5.6. А1 А2 … Аm В1 a11 a21 … am1 В2 a12 a22 … am2 Таблица 5.6 … Вn … a1n … a2n … … … amn Игра приведена к матричной форме. Обозначим эту матрицу как Λ = {aij}. Если цифры в строках одинаковые – стратегии называются дублирующими. Можно упростить матрицу, если в ней имеются дублирующие и доминирующие стратегии как по строкам, так и по столбцам путем отбрасывания таких стратегий. Рассмотрим пример G(4×5) (см. табл. 5.7). Если мы выберем максимально выигрышную стратегию А3 (до 10), то противник выберет В3 и выигрыш будет всего 1. Отсюда типичный принцип игры: минимальный выигрыш должен быть максимальным (принцип минимакса). Добавим к табл. 5.7 столбец αi и строку βj, в которые выпишем минимальные выигрыши для столбца и максимальные для строки. 68 А1 А2 А3 А4 βj В1 3 1 10 4 10 В2 В3 4 5 8 4 3 1 5 3 8 5 Таблица 5.7 В4 В5 α i 2 3 2 3 4 1 7 6 1 4 8 3 7 8 Противник выбирает стратегию, где его проигрыш минимален. Таким образом, исходя из принципа осторожности мы будем выбирать А4, а противник В3 . Теперь предположим, что мы узнали о том, что противник выбрал В3, тогда мы выбираем А1 и получаем выигрыш 5. Но если противник узнал, что у нас А1, он выберет В4 и наш выигрыш будет 2. Мы и противник начали метаться. Это очень важно: минимаксные стратегии неустойчивы по отношению к информации о поведении другой стороны. Иногда минимаксные стратегии дают устойчивое решение, когда α = β. В этом случае говорят, что совпадают верхняя и нижняя цена игры. Стратегии Аi и Вj, дающие на пересечении α = β, называются чистыми, а квадрат матрицы, соответствующий таким стратегиям – седловой точкой матрицы. Можно показать, что решение игры сводится к задаче линейного программирования: LA = x1 + x2 + … + xm → min при ограничениях вида a11.x1 + a21.x2 + … + am1.xm ≥ 1, a12.x1 + a22.x2 + … + am2.xm ≥ 1, a1n.x1 + a2n.x2 + … + amn.xm ≥ 1 при выборе стратегии А*. Выбор стратегии В аналогичен, но LB → max при выборе стратегии В*. Пара задач линейного программирования, по которой находится решение * (А , В*), называется двойственной. Показано, что минимум одной линейной функции соответствует максимуму другой. Стабильно зависимое решение в зависимости от постановки задачи бывает: 1) скалярным Нэш-равновесием, 2) векторными равновесиями, 3) угрозы – контругрозы (УКУ), 4) векторно-оптимальное решение, 69 5) дележ по Шекли. Для решения всех этих задач имеются соответствующие алгоритмы. 5.10. Имитационное моделирование Имитационное моделирование (ИМ) имеет целью не только проверку решений, но и их генерирование на основе дуальной процедуры моделирования и разработки модели. Характерной особенностью ИМ является итеративный характер формирования модели объекта и модели принятия решений. ИМ позволяет решать следующие задачи: 1) проверку принимаемых решений, 2) формирование адекватных моделей объектов, 3) оптимизацию решений на управление, 4) техническую и психологическую подготовку операторов к решению сложных задач (задача разработки тренажеров-имитаторов). Структура имитационной системы (ИС) состоит из модели объекта, модели вычисления показателей качества и эффективности (ПКиЭ), блока инициализации управления (ИУ), блока формирования интенсивности управления (ФИУ), блока интерфейса (MMI – Man-Machine Interface, человеко-машинный интерфейс). Х модель объекта блок ИУ MMI Y модель вычисления ПКиЭ блок ФИУ Рис. 5.7 На рис. 5.7 обозначены параметры: Х – возмущение (воздействие окружающей среды, может быть, модель внешней среды), Y – некоторое управляющее воздействие на объект управления. Общая идеология использования и создания ИС состоит в том, что построение системы, выбор моделей, проведение экспериментов – это итерационный процесс. Модели элементов усложняются и уточняются на основе анализа чувствительности свойств (характеристик) системы к изменению характеристик (моделей) элементов. Как правило, модели формируются в терминах «вход-выход» и изображаются на топологическом уровне в виде функциональных блоков, имеющих 70 наборы входных и выходных координат. Такой подход используется в ряде программных пакетов имитационного моделирования: VisSim, СИАМ, DinSim, Simulink (MatLab) и др. Отличительной чертой этих пакетов является возможность для большинства задач избежать необходимости программирования стандартных для моделирования функций и процедур. 71 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Дж. Ван Гиг. Прикладная общая теория систем.-М.: Мир. 1981. Кн.1 - 336с. Кн.2 - с.336-733. 2. Николаев В.И., Брук В.М. Системотехника: методы и приложения.Л.:Машиностроение, 1985. -199с. 3. Диалектика и системный анализ.-М.:Наука, 1986. -336с. 4. Холл А.Д. Опыт методологии для системотехники.-М.:Сов. радио.1975.-448с. 5. Прангишвили И.В. Системный подход и общесистемные закономерности. – М.: СИНЕГ, 2000. -520 с. 6. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ: Учеб. пособие для вузов. - М.: Высшая школа, 1989. 7. Захаренко Н.Н., Минеева Н.В. Основы системного анализа. -М., 1992 - Ч. I. 8. Черняк Ю.И. Системный анализ в управлении экономикой. - М.: Экономика, 1975. 9. Варенник В.В., Шишкин А.В. Основы научных исследований. - М., 1990. 10. Моисеев Н.Н. Математические задачи системного анализа. - М.: Наука, 1981. 11. Черняк Ю.И. Анализ и синтез в экономике. - М.: Экономика, 1970. 12. Клиланд Д., Кинг В. Системный анализ и целевое управление. - М.: Сов. радио, 1974. 13. Оптнер С. Системный анализ для решения деловых и промышленных проблем. - М.: Сов. радио, 1969. 14. Саати Т., Кернс К. Принятие решений. Метод анализа иерархий.-М.: Радио и связь. 1993.-224 с. 15. Кусимов С.Т., Ильясов Б.Г., Исмагилова Л.А., Валеева Р.Г. Интеллектуальное управление производственными системами. –М.: Машиностроение, 2001. – 327 с. 16. Построение системного проекта с использованием IDEF-технологии: Учеб.метод. пособие / Сост. О.В. Кирюшин. -Уфа: Изд-во УГНТУ, 2000. -32 с. 17. Рей У. Методы управления технологическими процессами.-М.:Мир, 1983.368 с. 18. Васильев В.И. и др. Многоуровневое управление динамическими объектами. -М.: Наука, -309 с. 19. Вавилов А.А., Имаев Д.Х. Эволюционный синтез систем управления: Учеб. пособие.-Л.: ЛЭТИ, 1983.-80 с. 20. Веревкин А.П., Дадаян Л.Г. Анализ и синтез автоматических систем регулирования сложных объектов нефтепереработки и нефтехимии: Учеб. пособие.-Уфа: УНИ, 1989. -94 с. 21. Веревкин А.П., Динкель В.Г. Технические средства автоматизации химикотехнологических процессов. Синтез логических устройств: Учеб. пособие.Уфа: УНИ, 1989. -87 с.