58

Теория Принятия Решений.

Литература.

Классика:

1. Пойя Д. “Математика и правдоподобные рассуждения.” М. Наука. 1975.

2. Нильсон Н. “Искусственный интеллект. Методы решения задач.”

М. Мир. 1973

1. Попов Р. “Искусство решения проблем.” М. Мир. 1982

2. Александров “Основы теории эвристических решений.”

М. Советское радио 1975.

1. Вагин В. Н. “Дедукция и обобщение в системах принятия решений.”

М. Наука 1988.

Современные:

1. Еремеев А. П. “Экспертные модели и методы принятия решений.” М. МЭИ 1995

2. Ларичев О. И. “Теория и методы принятия решений.” М. Логос 2000, 2002

3. Тратенгерц Э. В. “Компьютерная поддержка принятия решений.” М. Синтег. 1998

4. Башлыков А. А. Еремеев А. П. “Проектирование ЭС поддержки принятия решений в энергетике.”

Введение.

Принятие решений (ПР). Задача принятия решений (ЗПР).

Методы теории принятия решений (ТПР).

П ринятие решений

В узком смысле

- построение последовательности действий для достижения поставленной цели.

- выбор некоторой альтернативы из имеющегося множества альтернатив.

В широком смысле

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

Этапы ПР:

1. О смысливание проблемной ситуации.

2. Формулировка задачи принятия решения.

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

1. Поиск (построение) множества альтернатив.

2. Оценка и выбор альтернатив для реализации.

3. Применение (реализация) альтернатив.

4. Оценка результата.

( Подключается множество критериев оценок. Если результат удовлетворяет оценке, то он принимается в качестве решения. В противном случае возможен возврат на любой из этапов ПР. Чем выше этап, тем больший объём работы необходимо выполнять заново)

- + конец

Задача ПР = T = T(G, A, R, ) , где:

G – цели, A – альтернативы, R – результат, критерии.

З адача принятия решения

В замкнутой форме

- нет необходимости в дополнительной информации в процессе решения задачи

В открытой форме

- при наличии различного типа

НЕ-факторов (неполнота знаний, нечёткость критериев и т.д.)

В замкнутой форме Оптимальное решение

З ПР

В открытой форме Приближённое решение

(размерногсть велика, наличие НЕ-факторов)

F(x) = ext

Задача поиска в пространстве состояний.

(Задача эвристического поиска).

С

Пример: Шахматы.

S - все состояния.

S* - разрешённые состояния.

S\S*- король под ударом.

P – мн. ходов, которые можно делать.

p_i – ладья не может ходить через фигуры.

- поставить мат за минимальное количество ходов

читается, что любое состояние системы можно описать.

T = (S, S*, S_н, S_к, P, )

S - множество состояний задачи (проблемной области)

- множество допустимых состояний.

- множество запрещённых состояний.

- множество

преобразований состояний

p_i , S_pi – множество состояний, в которых

можно делать преобразования.

- множество критериев.

S_н - множество начальных состояний.

S_к - множество конечных состояний.

Задача:

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

Композиция определяется следующим образом:

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

Любую задачу можно привести и решить как задачу поиска в пространстве состояний.

Sн

S¹₁ … S¹₂₀

S²₁ … S²₂₀ … S²₁ … S²₂₀

П ример: Шахматы.

Метод перебора.

После первого хода

получаем 400 вершин

Партия длится в среднем

40 ходов и на каждом

ходу 20 возможностей.

Следовательно, полное дерево перебора будет иметь 40⁴⁰⁰ вершин.

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

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

Методы Теории Принятия Решений.

Строгие методы

Ориентированы на поиск оптимального решения.

ЗПР в замкнутой форме.

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

Решение оптимально 



Дедуктивный вывод.

(от общего к частному)

A B

A

B

Системы Принятия Решений

(Decision Making )

Эвристические методы

Поиск приемлемого (удовлетворяющего, допустимонго) решения.

ЗПР в открытой форме.

НЕ-факторы.

- множество возмущений.

Решение оптимально 



- функция допустимости.

R - отношение допустимости.

Обычно это отношение нестрогого порядка .

Свойства:

1. Рефлексивность a r a

2. Транзитивность arb & brc => arc

1. Асимметричность

a r b & b r a =>a=b



Если в силу природы задачи не возможно отыскать оптимальное решение, то ищется приближённое.

Индуктивный вывод.

(от частного)

A B

B

A

Это правдоподобные методы, следовательно необходимо оценивать степень правдоподобия.

Обобщённый modus ponens

A B

A*

B* B*=A* (A B)

A R1 A ~ a0

T R2 T ~ t0

(t - a0) (t - t0) => выбираем R1

Условия принятия решений.

1.Условия определенности.

S – состояния.

A(R) – альтернативы (частичное решение)

 S  aA

2.Условия риска.

Существуют ситуации, которым соответствует ряд возможных решений и их вероятности:

а1,p1

S а2,p2

… Pi=1.0

an,pn

3.Условия неопределенности.

Неполнота или противоречивость.

Формализация цели в ЗПР.

1. Количественное задание цели ( с помощью целевой функции)

Сведение ЗПР к задаче математической оптимизации.

2. Качественное задание цели.

Выделяется 2 подзадачи:

1). Цель достигнута или цель не достигнута.

Определяется целевое множество Xц

2). С помощью отношения предпочтения ( ) на множестве

альтернатив A .

Пример.

Задача сортировки (классы эквивалентности). Их частичный порядок можно задавать деревом или звездой.

K1 K2

Спецификация плохо формализованных ЗПР.

1.Отсутствие явно (или количественно) выраженной целевой функции.

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

3.Алгоритм существует, но его реализация очень сложна.

4.Существенная комбинаторность процесса поиска решения.

5.Диапазон данных и знаний, используемых в процессе решения задачи.

6.Возможность диалогового поиска решения (обращение к ЛПР в процессе решения).

Пункты 1-6 влияют на процесс решения и мешают использовать методы оптимизации.

Спецификация человеческого мышления при поиске решения.

1. Л.П.- рациональное мышление = дедукция + классическая аргументация.

(-> A, A->B, |-B).

В этом случае гипотеза принимается, если

S аргументов “за” - S аргументов “против” q,

где q – некоторое пороговое значение.

2. П.П. – образное мышление (правдоподобный вывод).=

индукция + абдукция + аргументация(justification)

A->B

B___

A?

Аргументация:

Пусть есть аргументы “за” и аргументы “против”

- веса, значения которых устанавливаются в зависимости

от важности гипотез.

3. Case-based reasoning (рассуждение на основе здравого смысла).

4. Belief (вера, убеждение(мнение)).

L - Квантор необходимости

- Квантор возможности

p  Lp

Lp  LLp

Mp LMp

Теоретико-игровые модели принятия решения

в конфликтных ситуациях.

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

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

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

Результатом партии являются платежи (выигрыши, проигрыши игроков)

Игра состоит из ходов, то есть выборов игроков из множества возможных альтернатив.

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

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

Задача Теории Игр: нахождение оптимальных стратегий игроков (т.е. обеспечение максимизации или минимизации проигрыша) в стратегических играх.

Определение.

Игра n лиц { A₁, … , A₁, H(A₁ , … , A_n)},

где – A_i стратегия i игрока, H – платёж.

Классификация Теоретико-Игровых Моделей.

Дискретные

Конечные