13. Принятие решений в условиях неопределенности. Постановка задачи. Виды неопределенности. Критерий Сэвиджа. Минимаксный. Критерий Гурвица.

Принятие решений в условиях неопределенности.

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

Пример:оценивание вариантов ИС(инф-ых систем).

-Коэф-т готовности ИС.

-время восстановления ИС.

-Время установления соединения при передаче инф-ии.

-зависят от степени загружности ИС.-неопред-сть.

Постановка задачи:

1)имеется некот.мн-ва аль-тив или решений.Х={x₁,…,xⁿ}

2)мн-во состояний среды.Y={y₁,…,y_m}

3)известны распределение оприорных вероятностях состояний среды.

P={p₁,…,p_m} с вероятностьюp_iсреда примет состояниеy_i.

4)критерий zоценки альтернатив описывается с помощью матрицы полезностиU={u_ij(x_iy_j)}_i=1,n;j=1,m или матрицы потерь.

V={V_ij(x_i y_j)}_i=1,n;j=1,m.

U	y1	y2	…	ym
x1	U(x1,y1)	U(x1,y2)	…	U(x1,ym)
…	…	…	…	…
xn	U(xn,y1)	…	…	U(xn,ym)

Возможны 3 вида оприорной информированности лица принимающего решения(ЛПР):

1)известно оприорное распределение p_i

2)известно,что среда противодействует ЛПР.

3)промежуточный между 1 и 2 ЛПР известно приблизительная инф-ия о состоянии среды.

Минимаксный(максиминный)

z(x)=

z(x)=

Пример: таблица*.

Ответ:x*=x₃

Пример:V==>

4)Критерий Сэвиджа

1)r(x_i,y_i)={}

2)К {r(x_i,y_j)} применяют минимаксный критерий.

Пример:

V=(

r=(}min=1000=>x^*=x₁

Пример:

	y1	y2	y3	y4
x1	5	10	18	25
x2	8	7	8	23
x3	21	18	12	21
x4	30	22	19	15
min	5	7	8	15

r=}min=8=>x^*=x₂

5)Критерий Гурвицаa€[0,1]

Z(x,y)=a

X^*-наилучшая,еслиz(x^*,y)=

a-1=>среда противодействует

a=0=>-среда содействует

a=1/2=>среда либо сод-ет,либо против-ет

a-показатель оптимизма.

V(x_i,y_j)

Z=min(a

Пример:

max	min
25	5
23	7
21	12
30	15

a=1/2

a min+(1-a)max
15
15	}min=15=>x*=x1 илиx2
16,5
22,5

3 возможных ситуаций оприорной информированности

1)p_i=>Байес-ЛаплассаB(x,p) ср.квадратич. ᵴ(x,p)

2)среда противод.=>минимакс(максимин).крит.Сэвиджа.

3)крит.Гурвица a.

14. Построение критерия оценки и выбора решений для разных ситуаций априорной информированности ЛПР.

1) p_iнеизвестны

Кр Гурвица z₁(x,y)= λ₁minU(x_i,y_j)+(1-λ₁)maxU(x_i,y_j)

Z₁(x,y)= λ₁minV(x_i,y_j)+(1- λ₁)maxV(x_i,y_j)

2) p_iизвестны

Комбинированный критерий для U(x_i,y_j)

Z₂(x,p)= λ₂B(x,p)

Z₂(x,p)= λ₂B(x,p)-(1- λ₂)σ(x,p)

B(x,p) критерий Байса-Лапласа

σ(x,p)-сред. квадратич. отклонение

для V:z₂(x,p)= λ₂B(x,p)+(1- λ₂)σ(x,p)

3) Строим универсальный критерий

Z(x,y,p)=Bz₁(x,y)+(1-B)z₂(x,p)

Для U(x_i,y_j)z(x^*,y,p)=minz(x,y,p)

λ ₁, λ₂ ,Bвходят [0,1]

B=0 =>z(x,y,p)=z(x,p) => 1я ситуация априорной информ-ти

λ ₂ входит {0, 0.1,…,1}

B=1 =>z(x,y,p)=z(x,y) => 2я ситуация априорной информ-ти

λ ₁входит {0;0.1;0.2;…;1}

B≠0;1

B=0;0,1;…

Λ₁=0;0,1;… λ₂=0;0,1;….

Пример

Сравниваются 4 варианта ИС. X={x1,x2,x3,x4}

S1-низкий уровень загрузки.S2-ниже среднего.S3- сред. уровень загрузки.S4- выше среднего.S5-сверхвысокий уровень загрузки.

P={0.2,0.2,0.4,0.15,0.05}

V	S1	S2	S3	S4	S5	B(x,p)	σ(x,p)
X1	0.1	0.4	0.5	0.8	1	0.47	0.243
X2	0.3	0.5	0.6	0.8	0.9	0.565	0.156
X3	0.1	0.3	0.5	1	1.1	0.485	0.309
X4	0.2	0.3	0.4	1	1.2	0.470	0.302

Выбрать лучший вариант проекта

z(x.y,p)=Bz₁(x,y)+(1-B)z₂(x,p)

B=0

z₂(x,p)= λ₂B(x,p)+(1- λ₂)σ(x,p)

B(x,p)=

σ(x,p)=(∑(V(x_i,y_j)*B(x,p))²p_j)^1/2

	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
X1	0.447	0.425				0.334
X2	0.524	0.483				0.319
X3	0.467	0.450				0.379
X4	0.453	0.436				0.373

Min x1 x1 x1 x1 x1 x2 x2 x2 x2

14. Марковские модели принятия решений.

S-динамическая.S1,S2,…,Sm

Система изменяет свои состояния мгновенно. t1<t2<…<tl<…

Марковость процесса заключается в том, что вер-ть перехода Sв какое либо состояние в моментеt(i) зависит только от состояния системы в моментt(i-1) и не зависит от того, как система в это состояние пришла заi-1 шаг.

Обозначим событие S_kⁱ – в момент времениt_i система приняла состояниеS_kк=1,m,i=0 начальное состояние системы,p(S_kⁱ) вероятность, что наi-м шаге система примет состояниеS_k.

=1

Решение-стратегия. G={X_li} –мн-во допустимых решений.

P_jk(i/X_li-1)-вер-ть перехода изS_j в S_k при условии, что наi-1 шаге приняли решениеX_li-1

P_jk(i/X_li-1)=p(S_kⁱ/S_j^i-1,X_l,i-1)

p(i/X_li-1)={p_jk(i/X_li-1)}^m_j,k-1 матрица переходных вероятностей сi-1 наi-й шаг.

Пример. Садовник, проводя хим. анализ почвы каждый год в начале сезона, оценивает состояние почвы как хорошее, удовлетворит., или плохое. Это позволяет ему принять одно из допустимых решений: 1) не вносить удобрения; 2) вносить удобрения. Садовник планирует проработать еще Nлет и его интересует оптимальная стратегия.

Состояния

S1 хорошее

S2 удовлетворительное

S3 плохое

X₁-не удобрять почву.

P₁₌

P₁(S₁ⁱ|S₃^i-1)=0

X₂-вносить удобрения.

P₂=

Матрица дохода R(i|X_li-1)={r_jk(i|X_li-1)}

U_j(X_li-1)==ожидаемый доход при доходе из состоянияS_j.

Задача максимизировать доход за Nшагов. ЕслиNконечное, то с конечным горизонтом планирования. ЕслиNбесконечная, то с бесконечным горизонтом планирования.

Если ЛПР решает, что после i-1 этапа если система находится в состоянииS_jнужно принимать решениеX^* независимо от состояния наi-м этапе, то говорят, что процесс принятия решений описывается стационарными стратегиями.

Пример.

P1=p2=

Стационарная стратегия- вносить удобрения тогда и только тогда, когда состояние почвы плохое S3.

P=

R=

Обозначим f_i(j)-оптимальный ожидаемый доход за этапыi,i+1,…,Nпри условии, что после (i-1) шага система находится в состоянииS_j,j=1,m

Будем считать, что N<бесконечности.

S_N+1(j)=0

U_j(X_li-1))=

f_i(j) зависит также от того, какой оптимальный ожидаемый доходf_i+1(к)k=1,m

был получен на шаге i+1.

f_i(j)=max{U_j(X_li-1)+∑p_jk(i|X_li-1)*f_i+1(k)} f_N+1(j)=0

Пример. Метод итерации по стратегиям.

Выбрать оптимальную стратегию поведения садовника при N=3.

f₄(j)=0

U1(X1)=0.2*7+0.5*6+0.3*3=5.3

U2(X1)=0*0+0.5*5+0.5*1=3

U3(X1)=0*0+0*0+1*(-1)=-1

U1(X2)=0.3*6+0.6*5+0.1*(-1)=4.7

U2(X2)=0.1*7+0.6*4+0.3*0=3.1

U3(X2)=0.05*6+0.4*3+0.55*(-2)=0.4

S	Ui(xk)		f3(j)	Опт решение
	X1	X2
1	5,3	4,7	5,3	X1
2	3	3,1	3,1	X2
3	-1	0,4	0,4	X2

S	Uj(Xli-1)+∑pjk(i|Xli-1)*fi+1(k)		f2(j)	Опт решение
	X1	X2
1	5.3+0.2*5.3+0.5*3.1+0.3*0.4=8.03	4.7+0.3*5.3+0.6*3.1+0.1*0.4=8.19	8.19	X2
2	4.75	5.61	5.61	X2
3	-0.6	2.125	2.125	X2

S	Uj+∑pjk*f2(k)		f1(j)	Опт решение
	X1	X2
1	10.38	4.7+0.3*8.19+0.6*5.61+0.1*2.125=10.74	10.74	X2
2	6.87	7.92	7.92	X2
3	1.13	4.23	4.23	X2