- •1.1. Методы искусственного интеллекта в прикладных системах и системах принятии решений
- •1.2. Интеллектуальные информационные технологии в прикладных системах и системах принятия решений
- •1.3. Типология задач интеллектуализации систем
- •Лекция 2. Представление знаний в интеллектуальных системах
- •2.1. Модели представления знаний
- •2.2. Системы, основанные на правилах
- •2.3. Системы, основанные на автоматическом доказательстве теорем
- •2.4. Системы, основанные на автоматическом порождении (выдвижении) гипотез
- •Лекция 3. Структура и основные компоненты прикладных интеллектуальных систем
- •3.1. Прикладные системы, основанные на знаниях
- •3.2. Структура системы управления, основанной на знаниях
- •3.3. Структура интеллектуальных систем поддержки принятия решения
- •3.4. Обобщенная структура экспертной системы
- •Лекция 4. Классификация прикладных интеллектуальных систем
- •4.1. Классификация экспертных систем
- •4.2. Примеры прикладных интеллектуальных систем
- •Лекция 5. Основные понятия и определения теории принятия решений
- •5.1. Роли людей в процессе принятия решений
- •5.2. Альтернативы
- •5.3. Критерии
- •5.4. Основные этапы процесса принятия решений
- •5.5. Математические методы теории принятия решений
- •Лекция 6. Принятие решений с помощью статистической проверки гипотез
- •6.1. Статистические решения
- •6.2. Основные задачи статистических решений
- •6.3. Статистическая проверка гипотез
- •6.4. Ошибки решения
- •6.5. Решающее правило при проверке гипотез
- •Лекция 7. Байесовская и последовательная процедуры принятия решения.
- •7.1. Байесовские процедуры принятия решения
- •7.1.1. Байесовская процедура при проверке простой гипотезы
- •7.1.2. Байесовские процедуры в задаче классификации
- •7.2. Принятие решения с помощью последовательной процедуры Вальда
- •Лекция 8. Принятие решения методом дискриминантнного анализа
- •8.1. Классификация в случае, когда распределения классов определены полностью
- •8.1.1. Модель двух нормальных распределений с общей ковариационной матрицей (модель Фишера)
- •8.1.2. Модель двух нормальных распределений с разными ковариационными матрицами
- •8.1.3. Модель нескольких нормальных распределений с общей ковариационной матрицей
- •8.2. Классификация при наличии обучающих выборок
- •8.2.1. Подстановочный алгоритм в модели Фишера
- •8.2.3. Правила классификации
- •8.3. Ошибка решающего правила
- •Лекция 9. Древообразные классификаторы
- •9.1. Назначение древообразных классификаторов
- •9.1. Структура дерева классификации
- •9.3. Вычислительные задачи древообразных классификаторов
- •9.3.1. Определение качества предсказания
- •9.3.2. Выбор разбиений
- •9.3.3. Определение правила прекращения разбиения
- •Лекция 10. Деревья решений
- •9.1. Характеристики дерева решений
- •9.2. Построение дерева решений
- •Лекция 11. Методы прогнозирования
- •11.1. Анализ временных рядов
- •11.1.1. Модель временного ряда
- •11.1.2. Тренд, сезонная и циклическая компоненты
- •11.1.3. Декомпозиция временного ряда
- •11.1.4. Экспоненциальное сглаживание
- •11.2. Каузальные методы прогнозирования
- •11.3. Качественные методы прогнозирования
- •Лекция 12. Основная задача линейного программирования
- •12.1. Математическая модель основной задачи линейного программирования
- •12.2. Задача линейного программирования с ограничениями-неравенствами
- •12.3. Примеры задач линейного программирования
- •12.3.1. Транспортная задача
- •12.3.2. Задача о назначениях
- •Лекция 13. Симплекс-метода решения задачи линейного программирования
- •13.1. Характеристика симплекс–метода
- •13.2. Табличный алгоритм замены базисных переменных
- •13.3. Отыскание опорного решения основной задачи линейного программирования
- •13.4. Отыскание оптимального решения основной задачи линейного программирования
- •Лекция 14. Многокритериальные методы принятия решений при объективных моделях
- •14.1. Объединение критериев
- •14.2. Метод главного критерия
- •14.3. Метод последовательных уступок
- •14.4. Метод целевого программирования
- •14.5. Метод, использующий принцип гарантированного результата
- •14.6. Метод равных наименьших относительных отклонений
- •14.7. Процедура STEM поиска удовлетворительных значений критериев
- •Лекция 15. Выбор Парето–оптимальных решений
- •15.1. Основные определения
- •15.2. Графическая интерпретация
- •15.3. Постановка задачи
- •Лекция 16. Оценка многокритериальных альтернатив с помощью теории полезности
- •16.1. Теория полезности
- •16.2. Принятие решения на основе значения ожидаемой полезности
- •16.3. Многокритериальная теория полезности (MAUT)
- •Лекция 17. Сравнение альтернатив методом аналитической иерархии
- •17.1. Основные этапы метода аналитической иерархии
- •17.2. Декомпозиция задачи
- •17.3. Попарное сравнение критериев и альтернатив
- •17.4. Свойства идеальной матрицы сравнений
- •Лекция 18. Приоритеты для критериев и альтернатив и выбор наилучшей альтернативы в методе анализа иерархий
- •18.1. Вычисление собственных характеристик обратно симметричной матрицы
- •18.2. Вычисление величины приоритетов
- •18.3. Определение наилучшей альтернативы
- •18.4. Проверка согласованности
- •18.5. Пример применения метода анализа иерархий
- •Лекция 19. Оценка многокритериальных альтернатив методами ELECTRE
- •19.1. Этапы подхода, направленного на разработку индексов попарного сравнения альтернатив
- •19.2. Свойства бинарных отношений
- •19.3. Метод ELECTRE I
- •19.4. Метод ELECTRE II
- •19.5. Метод ELECTRE III
- •Лекция 20. Основные понятия и математическая модель игровых методов обоснования решений
- •20.1. Основные понятия теории игр
- •20.2. Математическая модель игры
- •20.3. Нижняя и верхняя цена игры. Принцип минимакса
- •Лекция 21. Методы решения игр
- •21.1. Решение игры в чистых стратегиях
- •21.2. Решение игры в смешанных стратегиях
- •21.3. Упрощение игр
- •21.4. Решение игры 2х2
- •21.5. Графический метод решения (2х2)-игр
- •Лекция 22. Игры 2 х п
- •Лекция 23. Решение игр т х 2 и т х п
- •23.1. Решение игр т х 2
- •23.2. Решение игр т х п
- •Лекция 24. Критерии принятия решений в условиях риска и неопределенности
- •24.1. Основные понятия. Математическая модель
- •24.3. Максиминный критерий Вальда
- •24.4. Критерий минимаксного риска Сэвиджа
- •24.5. Критерий пессимизма-оптимизма Гурвица
- •Литература
признать этот критерий имеющим удовлетворительное значение: Ci ≥ li. Это условие
добавляется к совокупности линейных равенств и неравенств, определяющих область D допустимых значений переменных. Таким образом, возникает уже новая область допустимых значений. Следующий шаг начинается с расчетов при новой области допустимых значений и т.д. При достижении удовлетворительных для ЛПР значений по всем критериям процедура поиска решения останавливается.
Лекция 15. Выбор Парето–оптимальных решений
15.1. Основные определения
Метод основан на выделении из области допустимых решений D области компромиссов, в которой невозможно одновременное улучшение всех критериев.
Приведем необходимые определения.
Точка у D доминирует (улучшает) х D, если Ci (у) ≥ Ci (х), i = 1,..., m, и существует i0
= {1,..., m}, такое, что Ci0 (у) > Ci0 (х).
Точка х D называется оптимальной по Парето (эффективной), если не существует у D, улучшающей х.
Область согласия Dс D не содержит недоминируемых точек (любая точка из Dс может быть улучшена).
Эффективная область (область компромисса) Dэ D содержит все эффективные точки. В этой области ни один критерий не может быть улучшен без ухудшения хотя бы одного из других.
15.2. Графическая интерпретация
Рассмотрим на плоскости (U, V) множество Ω (рис.15.1) [28]. Каждая его точка обладает одним из следующих свойств:
1)все точки, ближайшие к этой точке, принадлежат множеству Ω (такая точка называется внутренней точкой множества Ω),
2)сколь угодно близко от этой точки расположены как точки множества Ω, так и точки, множеству Ω не принадлежащие (такие точки называются граничными точками множества Ω).
Граничная точка может как принадлежать, так и не принадлежать множеству Ω. Мы будем рассматривать только такие множества, которым принадлежат все точки границы. Множество всех граничных точек множества называется его границей ∂Ω.
76
V
.
.
U
Рис. 15.1. Множество точек, соответствующих области допустимых решений
Пусть М – произвольная точка множества Ω, внутренняя или граничная, и (U, V) – ее координаты. Можно ли, оставаясь в множестве Ω, переместиться из точки М в близкую точку так, чтобы при этом увеличились обе ее координаты? Если М – внутренняя точка, то это возможно. Если же М – граничная точка, то такое возможно не всегда (рис.15.2). Из точек М1, М2 и М3 это сделать возможно, но уже из точек вертикального отрезка АВ можно переместиться, увеличивая лишь координату V (координата U при этом остается неизменной). Перемещая точку горизонтального отрезка PQ вправо, мы увеличиваем координату U (координата V при этом сохраняет свое значение). Перемещение вдоль дуги BQ способно лишь увеличить одну из координат при одновременном уменьшении другой.
V
|
P . |
. Q |
M3 . |
. |
. |
|
||
. |
M1 |
. |
|
||
M2 |
|
. |
|
|
B
A
M4
O
U
Рис.15.2. Три класса точек множества Ω
Тем самым точки множества Ω можно разбить на три класса.
1. К первому классу относятся точки, которые можно сдвинуть так, чтобы одновременно увеличились обе координаты и при этом точки оставались в множестве Ω (в этот класс попадают все внутренние точки множества Ω и часть его граничных точек).
77
2.Второй класс образуют точки, перемещением которых по множеству Ω можно увеличить только одну из координат при сохранении значения второй (вертикальный отрезок АВ и горизонтальный отрезок PQ на границе множества Ω).
3.В третий класс попадут точки, перемещение которых по множеству Ω способно лишь уменьшить хотя бы одну из координат (дуга BQ границы ∂Ω).
Множество точек третьего класса называется границей (множеством) Парето данного множества Ω.
15.3. Постановка задачи
Пусть на плоскости (х, у) задано множество ω (рис. 15.3) и в каждой точке этого множества определены две непрерывные функции U = Ф(х, у) и V = Ψ (х, у).
Рассмотрим следующую задачу [28]. На множестве ω найти точку (х0, у0), в которой Ф (х0, у0) = max и Ψ (х0, у0) = max.
Обычно это записывается так:
Ф(х, у) → max и Ψ (х, у) → max, (х, у) ω.
В общем случае поставленная задача решения не имеет.
Изобразим на плоскости (U, V) все точки, координаты которых вычисляются по формулам
U = Ф(х, у) и V = Ψ (х, у), (х, у) ω.
Y
X
Рис. 15.3. Множество ω исходных точек на плоскости (х, у)
Обозначим полученное множество через Ω. Из рис. 15.4 видно, что наибольшее значение U (Umax) и наибольшее значение V (V max) достигаются в разных точках, а точка с координатами (Umax, V max) лежит вне множества Ω.
78
V
Vmax
Umax U
Рис. 15.4. Множество Ω точек на плоскости (U, V)
Тем самым в исходной постановке задача неразрешима – удовлетворить обоим требованиям одновременно невозможно. Следовательно, нужно искать компромиссное решение. Среди известных нам (см. лекц. 14) следует отметить два:
1)метод уступок,
2)метод идеальной точки.
Оба метода используют множество Парето, составленное в данном случае из допустимых точек задачи, которые не могут быть сдвинуты в пределах допустимого множества с улучшением сразу по двум критериям. Улучшая значения одного из критериев, мы неизбежно ухудшаем значения другого.
Метод последовательных уступок заключается в том, что ЛПР, работая в режиме диалога со специалистом, анализирует точки на границе Парето до тех пор, пока не согласится с некоторой компромиссной точкой.
Метод идеальной точки состоит в отыскании на границе Парето точки, ближайшей к точке утопии, задаваемой ЛПР. Обычно ЛПР формулирует цель в виде желаемых значений показателей, и часто в качестве координат целевой точки выбирается сочетание наилучших значений всех критериев. Обычно эту точку невозможно реализовать при заданных ограничениях, поэтому ее называют точкой утопии.
Мы рассмотрели задачу, в которой Ф(х, у) → max, Ψ (х, у) → max.
На практике встречаются случаи, когда требования задаются по иному:
Ф(х, у) → max, Ψ (х, у) → min
или
Ф(х, у) → min, Ψ (х, у) → min.
В этих случаях удобно поступать следующим образом. Принимаем во внимание, что функция Θ = – Ψ обладает следующим свойством: она достигает наибольшего значения в точности в тех точках, где функция Ψ принимает наименьшее значение, и наоборот. Иными словами, условия
Ψ → min и Θ → max
Равносильны. Поэтому, поменяв в случае необходимости знак у критерия на противоположный, мы можем свести любую двухкритериальную задачу к уже рассмотренной:
Ф(х, у) → max, Ψ (х, у) → max.
79