- •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. Критерий пессимизма-оптимизма Гурвица
- •Литература
C(Ai , Aj ),если dk (Ai , Aj ) ≤ C(Ai , Aj ), k;
δ(Ai Aj ) = C(Ai , Aj ) ∏ 1−dk (Ai , Aj ); j I * 1−Ck (Ai , Aj )
Здесь I* – множество критериев, для которых dk (Ai , Aj ) > C(Ai , Aj ) .
Величину δ(Ai Aj ) можно интерпретировать как меру уверенности в справедливости
гипотезы о том, что Аi предпочтительнее Аj. |
На этом этапе сначала определяется |
Этап исследования альтернатив [12]. |
|
λ = max δ(Ai Aj ) . Устанавливается достаточно |
близкий к λmax уровень, при котором |
Ai , Aj |
|
принимается гипотеза о превосходстве альтернативы Аi над Аj. Далее для каждой альтернативы Аi подсчитываются два индекса:
•индекс «силы» – число альтернатив, доминируемых Аi;
•индекс «слабости» – число альтернатив, доминирующих Аj.
Альтернативе Аi присваивается характеризующее ее число, равное разности индексов «силы» и «слабости».
Затем строится сверху вниз первый полный порядок альтернатив, аналогично тому, как делается в методе ELECTRE II. Альтернативы с наибольшим значением λ удаляются, для оставшихся опять выделяется ядро на основе подсчета тех же числе и т.д. Другой порядок определяется при подходе снизу вверх. На основе полных двух порядков строится средний, аналогично тому, как делается в методе ELECTRE II.
Лекция 20. Основные понятия и математическая модель игровых методов обоснования решений
20.1. Основные понятия теории игр
В практической деятельности часто приходится рассматривать явления и ситуации, в которых участвуют две или более стороны, имеющие различные цели и обладающие возможностями применять для достижения своих целей разнообразные действия. Такие ситуации принято называть конфликтными (или конфликтами).
Типичный конфликт характеризуется тремя основными составляющими:
1)заинтересованными сторонами,
2)возможными действиями сторон,
3)интересами сторон.
Примеры конфликтных ситуаций весьма многообразны: военные действия, экономика, судопроизводство, спорт и т.д.
Необходимость изучения и анализа таких ситуаций, представляемых в виде упрощенных математических моделей, вызвала к жизни специальный математический аппарат – теорию игр. Теория игр – это математическая теория конфликтных ситуаций.
Опишем некоторые понятия, используемые в этой теории.
Игра – это математическая модель конфликтной ситуации, возникающей при взаимодействии двух или более оперирующих сторон, которые имеют несовпадающие интересы. Заинтересованные стороны называются игроками, исход конфликта (результат игры) – выигрышем.
От реальной конфликтной ситуации игра отличается тем, что ведется по вполне определенным правилам. Правила – это система условий, которые определяют:
•возможные варианты действий игроков,
96
•объем информации каждой стороны о поведении другой,
•результат (исход) игры, к которому приводит каждая совокупность действий.
Игра носит название антагонистической, если число игроков равно двум, а выигрыш одного из игроков равен проигрышу другого (игра с нулевой суммой).
Ходом в теории игр называется выбор одно из предусмотренных правилами игры действий и его осуществление.
Стратегия игрока – это совокупность правил, определяющих выбор варианта действий при каждом ходе игрока в зависимости от ситуации, сложившейся в ходе игры.
Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры обеспечивает игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш).
20.2. Математическая модель игры
Рассмотрим игру, в которой игрок А имеет т стратегий: А1, А2,…, Ат, а игрок В – п стратегий: В1, В2,…, Вп.
Пусть игрок А выбрал стратегию Аi, а игрок В – стратегию Вk. Будем считать, что выбор игроками стратегий Аi и Вk однозначно определяет исход игры – выигрыш аik игрока А и выигрыш bik игрока В, причем эти выигрыши связаны равенством
bik = –аik.
Последнее условие показывает, что выигрыш одного из игроков равен выигрышу другого, взятому с противоположным знаком. Поэтому при анализе такой игры можно рассматривать выигрыши только одного из игроков. Пусть это будут выигрыши игрока А.
Если нам известны значения аik выигрыша при каждой паре стратегий {Аi, Вk}, i = 1, 2,... m, k = 1, 2, …, п, то их удобно записывать
или в виде прямоугольной таблицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В,
|
|
|
|
|
|
|
|
|
В1 |
В2 |
… |
Вп |
|
|
|
|
|
|
|
А1 |
|
а11 |
а12 |
… |
а1п |
|
|
|
|
|
|
|
А2 |
|
а21 |
а22 |
… |
а2п |
|
|
|
|
|
|
|
… |
|
. . . . |
. . . . . . . . . . . . |
||
|
|
|
|
|
|
|
Ат |
|
ат1 |
ат2 |
… |
атп |
или в виде матрицы |
|
|
|
|
|
|
||||||
|
a11 a12 |
... a1n |
|
|
|
|
||||||
А = |
a |
21 |
a |
22 |
... a |
2n |
|
|
|
|
||
|
|
|
|
. |
|
|
|
|||||
|
..................... |
|
|
|
|
|
||||||
|
am1 am2 ... amn |
|
|
|
Полученная матрица имеет размер т х п и называется матрицей игры или платежной матрицей. Рассматриваемую игру называют т х п или т х п – игрой.
Пример 20.1. Каждый из двух игроков А и В одновременно и независимо записывают на листе бумаги любое целое число. Если записанные числа имеют разную четность, то игрок А получает от игрока В 1 руб., а если одинаковую, то, наоборот, игрок А платит игроку
В1 руб.
Уигрока А две стратегии: А1 – записать четное число и А2 – записать нечетное число.
У игрока В такие же две стратегии: В1 – записать четное число и В2 – записать нечетное число.
97
Выбор игроками соответственно стратегий Аi и Вk однозначно определяет исход игры:
аik – выигрыш игрока А.
Матрица (2 х 2)-игры имеет следующий вид:
−11 −11 .
В этой матрице строки соответствуют стратегиям игрока А, а столбцы – игрока В.
20.3. Нижняя и верхняя цена игры. Принцип минимакса
Рассмотрим произвольную матричную игру:
a11 a12 ... a1n
А= a21 a22 ... a2n
.....................
am1 am2 ... amn
иопишем алгоритм, с помощью которого можно определить наилучшую стратегию [5,28]. В теории игр предполагается, что оба игрока действуют разумно, т.е. стремятся к
получению максимального выигрыша, считая, что соперник действует наилучшим для себя образом.
Действия игрока А.
1-й шаг. В каждой строке матрицы А находится минимальный элемент
αi = min аik, i = 1, 2,... m.
k
Полученные числа
α1, α2,…, αт
приписываются к заданной таблице в виде правого добавочного столбца:
|
|
а11 |
а12 |
… |
а1п |
α1 |
|
|
|
а21 |
а22 |
… |
а2п |
α2 |
|
|
|
. . . |
. . . |
. . . |
. . . |
. . . |
|
|
|
ат1 |
ат2 |
… атп |
αт |
|
|
Выбирая стратегию Аi, игрок |
А должен рассчитывать на то, что в результате разумных |
||||||
действий игрока В он выиграет не меньше, чем αi. |
|
|
|
||||
2-й шаг. Среди чисел |
|
|
|
|
|
||
α1, α2,…, αт |
|
|
|
|
|
||
выбирается максимальное число |
|
|
|
|
|
||
α = max αi, |
|
|
|
|
|
||
|
i |
|
|
|
|
|
|
или α = max min аik. |
|
|
|
|
|
||
i |
k |
|
|
|
|
|
Выбранное число α является одним из элементов заданной матрицы А.
Действуя наиболее осторожно и рассчитывая на наиболее разумное поведение противника, игрок А должен остановиться на той стратегии Аi, для которой число αi является максимальным.
Если игрок А будет придерживаться стратегии, выбранной описанным выше способом, то при любом поведении игрока В игроку А гарантирован выигрыш, не меньший α.
Число α называется нижней ценой игры.
Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина, а выбираемая в соответствии с эти принципом стратегия Ai0 – максиминной стратегией игрока А.
98
Действия игрока В.
1-й шаг. В каждой строке матрицы А находится максимальный элемент
βk = max аik, k = 1, 2, …, п.
i
Полученные числа
β1, β2,…, βп
приписываются к заданной таблице в виде нижней добавочной стоки:
а11 |
а12 |
… |
а1п |
α1 |
а21 |
а22 |
… |
а2п |
α2 |
. . . |
. . . |
. . . |
. . . |
. . . |
ат1 |
ат2 |
… атп |
αт |
|
β1 |
β2 |
… |
βп |
|
Выбирая стратегию Вk, игрок В должен рассчитывать на то, что в результате разумных
действий игрока А он проиграет не больше, чем βk. 2-й шаг. Среди чисел
β1, β2,…, βп
выбирается минимальное число
β = min βk, k
или β = min max аik. k i
Выбранное число β является одним из элементов заданной матрицы А.
Действуя наиболее осторожно и рассчитывая на наиболее разумное поведение противника, игрок В должен остановиться на той стратегии Вk, для которой число βk является минимальным.
Если игрок В будет придерживаться стратегии, выбранной описанным выше способом, то при любом поведении игрока А игроку В гарантирован выигрыш, не больший β.
Число β называется верхней ценой игры.
Принцип построения стратегии игрока В, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с эти принципом стратегия Вk 0 – минимаксной стратегией игрока В.
Нижняя цена игры α и верхняя цена игры β всегда связаны неравенством α ≤ β. Если α = β, или
max min аik = min max аik. |
|
i k |
k i |
то ситуация ( Ai0 , Вk 0 ) оказывается равновесной и ни один из игроков не заинтересован
втом, чтобы ее нарушить.
Втом случае, когда нижняя цена игры равна верхней цене игры, их общее значение называется чистой ценой игры и обозначается через ν.
Цена игры совпадает с элементом aiok o матрицы игры А, расположенным на пересечении io-й строки (стратегия Ai0 игрока А) и ko-го столбца (стратегия Вk 0 игрока В), –
минимальным в своей строке и максимальным в своем столбце.
Этот элемент называют седловой точкой матрицы А или точкой равновесия, а про игру говорят, что она имеет седловую точку.
Стратегии Ai0 и Вk 0 , соответствующие седловой точке, называются оптимальными, а
совокупность оптимальных ситуаций и цена игры – решением матричной игры с седловой точкой.
99