Аксиоматические методы. 2 страница

Компьютерный эксперимент

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

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

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

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

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

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

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

Виды компьютерных экспериментов

Во-первых, различают детерминированный и стохастический эксперимент.

Детерминированный эксперимент («what if», «что, если») должен отвечать на вопросы:

«Как работает система при заданных значениях параметров?»

«К каким последствиям могут привести изменения структуры системы и значений её параметров?»

«Что будет, если принять некие решения или реализовать управление?»

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

Во-вторых, по назначению различают три вида компьютерных экспериментов (и детерминированных и стохастических)

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

Схема простого эксперимента:

или:

,

где: - входные факторы, - выходные значения.

2. Проверка (анализ) чувствительности модели. Её цель – оценка области применения модели и оценки влияния изменений факторов на поведение системы

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

Схема оптимизационного эксперимента

- целевая функция, в общем случае - векторная.

Существуют два основных подхода к оптимизации системы на основе использования её имитационной модели.

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

2. Используется встроенный в программное средство универсальный оптимизатор. Как правило, в нем применяется поисковые методы оптимизации: случайный поиск, генетические алгоритмы, «рассеянный поиск» и т.п. Например, такой оптимизатор OptQuest встроен в программное средство AnyLogic. А универсальный математический пакет Maple содержит оптимизатор GOT for Maple (global optimization tool for Maple).

Этапы разработки модели сложной системы

1. Анализ требований (и к проектируемой системе и к модели); уточнение объекта моделирования; оценка необходимых ресурсов.

2. Определение структуры модели (архитектуры).

3. Выбор методов моделирования для частных моделей и выбор программных средств (предварительный).

4. Планирование разработки и распределение работ.

5. Уточнение методов и программных средств, программирование и тестирование частных задач.

6. Синтез частных моделей (задач) и тестирование модели в целом.

7. Идентификация параметров модели.

8. Проверка чувствительности.

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

Контрольные вопросы

1) Научное и практическое значение моделирования.

2) Моделирование и основные задачи системного анализа.

3) Понятия «модель» и «моделирование».

4) Основные виды моделей; примеры.

5) Математическое моделирование, основные виды моделей.

6) Оптимизационные модели, основные задачи и методы.

7) Специфические модели и методы системного анализа.

8) Структурные модели и графы; основные виды графов.

9) Представление графами основных структур в системном анализе.

10) Основные требования к моделям, область применимости.

11) Адекватность и эффективность моделей.

12) Роль компьютеров, информационных технологий в СА.

13) Дайте определение понятию «граф»; графы как модели систем.

14) Какой граф называют деревом, какую структуру системы он моделирует?

15) Методы и инструменты изучения систем.

16) Значение моделирования в системном анализе и проектировании сложных систем.

2.2. Методы анализа систем и проблем

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

Введение: многокритериальный анализ

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

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

- многокритериальность (см. ниже);

- разнородность критериев (количественные, качественные);

- часто они имеют неопределённости нестатистического характера;

- наличие «человеческого фактора»: целей, предпочтений…

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

Уточним определения. Цель – это (главная) цель решения проблемы; целей может быть и несколько (многоцелевые поблемы).

Критерий – количественная или качественная характеристика, существенная для суждения об объекте.

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

Альтернативы – это сами сравниваемые объекты; причём под объектами в МКА понимаются как существующие системы, так и проекты. Набор показателей называется профилем альтернативы.

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

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

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

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

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

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

2. Достаточная универсальность – можно сравнивать и ранжировать любые объекты, для которых можно построить общую систему критериев.

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

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

Методы МКА программно реализованы в системах поддержки принятия решений (СППР), которые рассматриваются в п. 2.4.

Рассматриваемые ниже методы и ряд других содержатся в СППР NooTron (http://nootron.net.ua), разработанной на кафедре «Информационные технологии и системы» Национальной металлургической академии Украины, г. Днепропетровск. Эту СППР рекомендуется использовать при выполнении контрольных заданий. Тем более, что в ней имеется раздел «Справка» с описанием алгоритмов методов и примерами решения задач.

Применение многокритериальных методов

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

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

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

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

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

Методов многокритериального анализа довольно много, существуют две «ветви» методов – количественный (кардинальный) анализ решений (КАР) и порядковый (ординальный) анализ решений.Частной «ветвью» последнего является вербальный анализ решений (ВАР).

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

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

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

Краткий обзор количественных методов

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

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

I. Прямые методы. Здесь форма зависимости результирующей полезности альтернативы постулируется либо выбирается из базового набора СППР. Параметры этой зависимости задаются так:

a) нормативно («закон есть закон»);

b) непосредственно устанавливаются лицом принимающим решение («начальник всегда прав») или этим лицом и консультантами («система коллективной ответственности»);

c) определяются из статистики, если она есть в достаточном объёме и надёжна («статистика знает всё»).

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

2. Метод компенсации. Здесь эксперты пытаются уравновесить (скомпенсировать) оценки одной альтернативы оценками другой.

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

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

К методам данной группы относятся следующие: метод комитетов, методы ЭЛЕКТРА («исключение и выбор в условиях реальности»).

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

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

5. Метод анализа иерархий (МАИ) и его производныеприменяются сейчас очень широко и для самых разных практических задач. Аналитический иерархический процесс (другое название метода) обладает рядом достоинств по сравнению с другими методами количественного анализа решений. Именно в этом методе полностью реализована схема системного анализа проблем, а именно: представление проблемы как системы.

Контрольные вопросы

1) Понятия «проблема», «выбор», «рациональное решение», «оптимальное решение».

2) Условия принятия решения, пояснить.

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

4) Основная проблема многокритериального сравнительного анализа.

5) Понятия «цель», «критерий», «показатель», «альтернатива», примеры.

6) Основные требования к методике многокритериального сравнительного анализа.

7) Достоинства многокритериальных методов.

8) Основные проблемы многокритериальных методов.

9) Количественный анализ решений: основные идеи, общая схема.

10) Основные группы методов количественного анализа решений.

11) Аксиоматические методы количественного анализа решений: теоретическая основа, достоинства и недостатки.

12) Прямые методы количественного анализа решений: теоретическая основа, достоинства и недостатки.

13) Основные группы прямых методов количественного анализа решений.

14) Основные системные задачи, где применяются методы анализа решений.

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

Характеристика метода анализа иерархий

В 70-80-е годы американский учёный Т.Л. Саати разработал и развил «иерархический аналитический процесс» (analytic hierarchy process, AHP). В литературе этот метод называют также методом анализа иерархий (МАИ). Метод применяется для многих задач. Вот основные:

1. Сравнительный анализ (многокритериальное ранжирование)

2. Многокритериальный выбор лучшей альтернативы

3. Принятие проектных решений

4. Распределение ресурсов между проектами

5. Оценка эффективности проектов

Этот метод для успешного применения требует соблюдения условий:

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

b) для множества сравниваемых объектов ("альтернатив") может быть выстроена общая система критериев;

c) оценки по «негативным» критериям не находятся в опасной близости к ограничениям.

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

Алгоритм метода анализа иерархий

Мы рассмотрим самый простой, базовый вариант МАИ, он имеется в СППР NooTron (http://nootron.net.ua).

Этапы метода анализа иерархий:

1.Представление исходной проблемы в виде иерархической структуры «цель – критерии – альтернативы» (рис. 2.1). Такая структура называется трёхуровневой полной доминантной иерархией. Полная: все объекты нижнего уровня зависят от каждого объекта соседнего верхнего уровня (доминируется им). Доминантная: в такой иерархии нет горизонтальных и обратных связей, т.е. критерии не зависят друг от друга, равно как и альтернативы, цель не зависит ни от альтернатив, ни от критериев.

Цель составляет высший уровень иерархии (уровень 1). На этом уровне может находиться лишь один объект. На следующем "вниз" уровне 2 находятся критерии. По системе этих критериев оцениваются сравниваемые объекты (называемые обычно "альтернативами"). Альтернативы – на самом нижнем уровне 3.

Рисунок 2.1 – Трёхуровневая иерархия «цель – критерии – альтернативы»

2.Вынесение экспертных суждений на каждом уровне иерархии по парным сравнениям: критерии сравниваются попарно по отношению к цели, альтернативы – попарно по отношению к каждому из критериев и заполнение матриц парных сравнений (МПС). Одна МПС – для критериев, n таких матриц – для альтернатив; здесь n – количество критериев (таб. 2.2).

Таблица 2.2. – Матрица парных сравнений (МПС)

Таблица 2.3. – Шкала Саати

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

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

Если критерий не имеет принятой меры, то сравнение в МАИ проводится с использованием специальной «шкалы Саати» (таб. 2.3). Другие названия: «шкала 1-9», «шкала относительной важности», «шкала кратности предпочтений». Эта шкала имеет 9 степеней предпочтения, выбраных с учетом экспериментально установленных психофизиологических особенностей человека, выполняющего сравнение. Шкалу Саати рекомендуется применять и в «смешанном случае», когда в иерархии есть как количественные, так и качественные критерии. Т.е. в МАИ шкала Саати является основной. Числа из этой шкалы используются, чтобы показать, во сколько раз элемент с большей оценкой предпочтительности превосходит элемент с меньшей оценкой относительно общего для них объекта (рис. 2.1).

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

Таким образом, матрица парных сравнений – это квадратная обратно симметричная матрица с положительными элементами. На её главной диагонали находятся единицы (объект сравнивается с собой), а размерность матрицы равна количеству сравниваемых объектов. Так, для иерархии с тремя критериями и пятью альтернативами надо заполнить экспертными оценками одну МПС критериев относительно цели (её размерность 3x3) и три МПС альтернатив относительно критериев размерностью 5x5 каждая.

Размерность матрицы парных сравнений не должна превышать 10х10 исходя из математики метода. Алгоритм метода и примеры решения задач приведены в Справке СППР NooTron (http://nootron.net.ua).

3.Математическая обработка матриц парных сравнений включает 2 этапа: нахождение локальных приоритетов (ЛП) и нахождение глобальных приоритетов (ГП). Вектор локальных приоритетов количественно ранжирует объекты данной матрицы парных сравнений, т.е. устанавливает их линейный порядок с указанием количественной меры предпочтительности. Векторов ЛП столько сколько матриц парных сравнений, т.е. n+1: одна цель и n критериев. Локальный приоритет критерия в МКА называют его весом (weight). Вес показывает важность критерия, вектор ЛП критериев – вектор их весов. Вектор глобальных приоритетов всегда один. Он количественно ранжирует альтернативы относительно цели; вектор ГП и есть решение задачи МАИ в математическом смысле.

При точном процессе определения вектора локальных приоритетов задача сводится к нахождению главного собственного вектора МПС:

где A – матрица парных сравнений (МПС), X – n-мерный вектор, составленный из искомых приоритетов, λ – главное (наибольшее) собственное число МПС;

и последующего нормирования этого вектора на 1:

Нахождение собственных чисел и собственных векторов рассматривается в любом курсе линейной алгебры. Все математические пакеты (MATLAB, Maple, Mathematica, SciLab…) содержат средства нахождения собственных чисел и векторов, также – и СППР NooTron.

Для МПС небольшой размерности (не выше 4х4) вектор локальных приоритетов может быть приближенно вычислен при помощи калькулятора:

1) Для каждой строки матрицы парных сравнений находим среднее геометрическое ее элементов:

2) Находим сумму всех этих средних геометрических.

3) Делим каждое среднее геометрическое строки на их сумму (п. 2). Это даёт нормировку на единицу. Результат - вектор локальных приоритетов данной матрицы парных сравнений.

В МАИ есть возможность проверки согласованности экспертных оценок, т.е. чисел в каждой матрице парных сравнений. Для контроля согласованности этих оценок вводятся две связанные характеристики - индекс согласованности (CI) и отношение согласованности (CR):

где P_n – это индекс согласованности для положительной обратно симметричной матрицы случайных оценок размера ; элементы этой матрицы получены случайным выбором из множества допустимых оценок, т.е. из чисел ряда {1/9, 1/8, 1/7, 1/6, 1/5, 1/4, 1/3, 1/2, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Таблица 2.4 – Значения индекса согласованности

Допустимым считается отношение согласованности (CR), не превышающее 10 - 20%. Если CR выходит из этих пределов, то экспертам необходимо исследовать задачу и проверить свои оценки.

4.Глобальный приоитет альтернативы определяется как скалярное произведение вектора локальных приоритетов критериев на профильальтернативы – вектор, составленный из локальных приоритетов (т.е. оценок) данной альтернативы по критериям. Размерности этих векторов совпадают и равны m (m - число критериев), а всего имеем n профилей (n - число альтернатив). Вектор глобальных приоритетов альтернатив по отношению к цели составляется из ГП альтернатив и имеет размерность n.