Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема 2. Моделирование задачи принятия решения в условиях неопределённости с помощью стратегических игр.
2.1 Постановка задачи принятия решения в условиях неопределённости
Рассмотрим задачу принятия решения, когда на стадии принятия решения ЛПР знает:
а) возможные состояния среды: у1, у2,..уn Є Y – множество состояний окружающей среды.
б) результат, к которому приведёт выбор альтернативы х Є Х для каждого возможного состояния среды: у1, у2,..уn, т. е. знает функцию выигрыша (проигрыша): f(х,y) для всех х Є Х, у = Y, где Х – множество альтернатив, Y – множество состояний среды. Функция двух переменных f(х,y) называется оценочной функцией.
При этом ЛПР не располагает информацией о том, как распределены вероятности состояний среды и даже не знает, какие из этих состояний более вероятны. Такая ситуация принятия решений определяется как структурная неопределённость.
Задача выбора «наилучшего» решения требует определить критерий оптимальности. Критерий оптимальности представляет собой правило выбора «наилучшего» решения.
Очевидно, что широкое разнообразие жизненных и экономических ситуаций не может быть описано с помощью единственного критерия оптимальности, в математических моделях принятия решения предложены и исследованы несколько критериев оптимальности. Выбор того или иного критерия оптимальности основан на определённых предположениях (гипотезах) о поведении окружающей среды
Таким образом, критерий оптимальности – это правило выбора «наилучшего» решения в условиях неопределённости, основанное на определённых предположениях относительно поведения окружающей среды и предпочтений ЛПР.
При этом желательно, чтобы критерий оптимальности обладал свойствами, согласующимися со здравым смыслом и рациональностью. Чтобы пояснить, в чем состоит в данном случае рациональный подход, вспомним понятие доминируемости.
2.1.1 Доминируемые и доминирующие альтернативы
Пусть задача принятия решения характеризуется n-состояниями среды: у1, у2,..уn и предусматривает выбор из m-альтернатив: х1, х2,..хm. Причём для каждой пары (хi, yj) определено значение функции f(хi, yj).
Тогда задачу принятия решения можно описать с помощью платёжной матрицы:
Таблица 1.
|
Состояния среды Альтернативы |
y1 |
y2 |
… |
yj |
… |
yn |
|
x1 |
f(x1,y1) |
f(x1,y2) |
… |
f(x1,yj) |
… |
f(x1,yn) |
|
x2 |
f(x2,y1) |
f(x2,y2) |
… |
f(x2,yj) |
… |
f(x2,yn) |
|
… |
… |
… |
… |
… |
… |
… |
|
xi |
f(xi,y1) |
f(xi,y2) |
… |
f(xi,yj) |
… |
f(xi,yn) |
|
… |
… |
… |
… |
… |
… |
… |
|
xm |
f(xm,y1) |
f(xm,y2) |
… |
f(xm,yj) |
… |
f(xm,yn) |
Предположим, что для некоторых целых чисел i и k Є [1,m] выполняется условие: для любого j f(xi,yj) ≥ f(xk,yj).
В строке i результаты больше, чем в строке k. Следовательно, стратегия xi доминирует стратегию xk, xk – доминируемая стратегия.
Очевидно, что доминируемые стратегии (или альтернативы) заведомо хуже других, а доминирующие заведомо лучше. Если существует стратегия, доминирующая все остальные, то рациональный выбор остановится именно на этой стратегии. Так же понятно, что любой критрий оптимальности должен отвергать доминируемые стратегии. Отсюда следует первый принцип, которому должен удовлетворять критерий оптимальности.
2.1.2 Принципы, которым должен удовлетворять критерий оптимальности.
a) Принцип доминирования:
- если существует доминирующая стратегия, то критерий оптимальности должен обеспечивать выбор именно этой стратегии;
- если существуют доминируемые стратегии, то их удаление и введение не должно влиять на выбор наилучшей стратегии.
Так же очевиден смысл двух других принципов:
b) Перенумерация альтернатив (нумерация строк) и/или состояний среды (нумерация столбцов) не должна влиять на выбор наилучшей стратегии.
c) Предположим, что ко всем значениям функции выигрыша добавлено число а: f(xi,yj) + a. Очевидно, что критерий оптимальности должен обеспечивать выбор наилучшей стратегии, которая не зависит от аддитивной постоянной к функции выигрыша.
Существуют и другие принципы критериев оптимальности, но они применяются редко.
Рассмотрим наиболее часто применяемые критерии оптимальности.
2.2 Критерий Лапласа
Критерий Лапласа основан на гипотезе, согласно которой все состояния среды реализуются с одинаковыми вероятностями.
Если возможна реализация 2-х состояний А и В и нет никакой информации об их вероятностях, то естественно предполагать, что:
Р(А) = Р(В) = ½.
Если среда может принимать состояния у1, у2,..уn и нет информации о вероятностях этих значений, то естественно предполагать:
Р(у1) = Р(у2) = ...= Р(уn) = 1/n.
Пусть для задачи принятия решения, заданной Таблицей 1, принята гипотеза равной возможности. Для каждой стратегии xi определим значение функции L (xi):
L (xi) = 1/n*∑ f(xi,yj) (1)
Получим L(x1), L(x2),.. L(xn) – среднеарифметические выигрыши для каждой стратегии.
Выбираемая стратегия xi: L(xl) ≥ L(xi) (2)
Пример 1: Найти наилучшую стратегию по критерию Лапласа для задачи принятия решения, заданной платёжной матрицей:
|
у1 |
у2 |
у3 |
L (xi) |
|
|
х1 |
92 |
0 |
4 |
96/3=32 |
|
х2 |
30 |
50 |
10 |
90/3=30 |
*
Легко показать, что критерий Лапласа удовлетворяет всем 3-м условиям, определённым в пункте 2.1.1.
Тем не менее, у критерия Лапласа есть недостаток: по критерию Лапласа может быть выбрана рискованная стратегия.
Маленькие значения выигрыша при нахождении среднего перекрываются большими – эффект компенсации.
2.3 Критерий Вальда (максиминный критерий)
Выбор критерия Вальда основан на гипотезе, согласно которой ЛПР стремится получить гарантированный результат при любом состоянии среды.
Пример 2: Найти наилучшую стратегию по критерию Вальда для задачи принятия решения, заданной платёжной матрицей:
|
у1 |
у2 |
у3 |
у4 |
у5 |
аi |
|
|
х1 |
1 |
3 |
2 |
4 |
5 |
1 |
|
х2 |
0 |
6 |
8 |
10 |
12 |
0 |
*
Решение. Найдём выбор по принципу максимина:
для любого i min f(xi,yj) = ai – худший результат при выборе i.
maxmin f(xi,yj) = max ai = K.
Легко показать, что критерий Вальда удовлетворяет всем 3-м условиям, определённым в пункте 2.1.1.
Недостаток этого критерия: критерий Вальда отвергает хорошие варианты решения из-за своего крайнего пессимизма.
2.4 Критерий Гурвица (критерий взвешенного оптимизма/пессимизма)
В основе этого критерия лежит гипотеза о том, что уровень пессимизма ЛПР принимает некоторое значение α: 0 ≤ α ≤ 1. Чем больше α, тем пессимистичнее настроен ЛПР. Для каждой строки xi определяется:
- число аi = min f((xi,yj);
- число bi = max f((xi,yj).
Затем для каждого значения xi и α рассчитывается число:
H(xi, α ) = α* аi + (1- α)* bi
и выбирается max H(xi, α ) = h(α).
Пример 3: Для Примера 2 найти наилучшую стратегию по критерию Гурвица, при значении α = ½.
|
у1 |
у2 |
у3 |
у4 |
у5 |
аi |
bi |
Hi(1/2) |
|
|
х1 |
1 |
3 |
2 |
4 |
5 |
1 |
5 |
1*1/2+5*1/2=3 |
|
х2 |
0 |
6 |
8 |
10 |
12 |
0 |
12 |
0*1/2+12*1/2=6 |
*
Очевидно, что если α = 1, то критерий Гурвица превращается в критерий Вальда.
Докажем, что критерий Гурвица удовлетворяет принципу доминирования.
Доказательство. Пусть стратегия xi является доминирующей. Это значит, что для всех j, 1 ≤ j ≤ n и для всех k, 1 ≤ k ≤ m, k ≠ j, выполняется неравенство:
f(xi,yj) ≥ f(xk,yj). (d)
Из этого следует, что:
max f(xi,yj) ≥ max f(xk,yj). (*)
Докажем выполнение неравенства (*) подробнее:
max f(xi,yj) = f(xi,yp)
max f(xk,yj) = f(xk,yq)
f(xi,yj) ≤ f(xi,yp)
f(xk,yj) ≤ f(xk,yq)
Из (d) следует, что f(xk,yq) ≤ f(xi,yq) ≤ f(xi,yp).
Таким образом, получается bk ≤ bi.
Введём обозначения: min f(xi,yj) = аi = f(xi,yl),
min f(xk,yj) = ak = f(xk,yr)
Из неравенства доминирования (d) следует, что f(xk,yp) ≤ f(xi,yr)
аi = f(xi,yl) ≥ f(xk,yl) ≥ min f(xk,yl) = ak
аi ≥ ak
Так как α ≥ 0, 1- α ≥ 0, то:
α * аi ≥ α * аk
(1- α)* bi ≥ (1- α)* bk
Выполнение условий перестановки и аддитивной постоянной достаточно очевидно.
Недостаток критерия Гурвица: недостаточная обоснованность выбора α (оценочное число).
2.5 Критерий Сэвиджа (критерий наименьших сожалений)
Критерий основан на гипотезе, что ЛПР предпочитает такое решение, при реализации которого у него возникают наименьшие сожаления.
Рассмотрим матричные игры, заданные Таблицей 1.
Допустим, ЛПР знает, что среда примет состояние yj, он выберет такое значение xi, что f(xi,yj) = max f(xi,yj).
Если ЛПР не знает истинного состояния среды, он выберет какую-то стратегию хk. Предположим он выбрал стратегию хk и реализовалось состояние среды yj.
? Как оценить сожаление ЛПР?
Он сравнивает f(xk,yj) c f(xij,yj):
f(xij,yj) ≥ f(xk,yj).
Таким образом, критерий Сэвиджа даёт следующий алгоритм выбора наилучшего решения:
сj = max f(xi,yj)
rij = сj - f(xi,yj)
R = || rij ||
4) для каждой альтернативы находят наибольшее сожаление:
Si = max rij
Sk ≤ Si
minmax rij
Пример 4: Найти решение оптимальное по критерию Сэвиджа для матрицы:
|
у1 |
у2 |
у3 |
у4 |
у5 |
|
|
х1 |
1 |
3 |
2 |
4 |
5 |
|
х2 |
0 |
6 |
8 |
7 |
9 |
|
maxi |
0 |
6 |
8 |
7 |
9 |
1-1 6-3 8-2 7-4 9-5
cij =
1-0 6-6 8-8 7-7 9-9
0 3 6 3 4 6
cij =
1 0 0 0 0 1
max cij = 6 – наибольшее сожаление.
Можно показать, что критерий Сэвиджа удовлетворяет принципу доминирования, инвариантности при перестановке, инвариантности при добавлении аддитивной постоянной.
Критерий Сэвиджа отличается от критерия Вальда тем, что для критерия Сэвиджа реализуется принцип minmax для матрицы потерь, а для критерия Вальда - maxmin для матрицы выигрышей.
Таким образом, критерий Сэвиджа тоже можно отнести к разновидности пессимистических критериев.