Файл: М.А. Тынкевич Многошаговые процессы принятия решений (динамическое программирование).pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 01.06.2024
Просмотров: 70
Скачиваний: 0
15
или в более изящной форме:
P1 R1 |
X = |
P2 R2 |
Y |
( 4 ) |
||
1− |
P |
1− |
P |
|||
|
1 |
|
|
2 |
|
|
Отсюда возникает простой путь решения. На первом шаге проверяем исходное состояние (точку) на положение относительно граничной линии
(4) и запоминаем соответствующий выбор. Отыскиваем координаты очередной точки в соответствии со сделанным выбором и проводим аналогичные действия. На последнем шаге (в оставшемся одношаговом процессе) суждение о выборе определяется линией (3).
4.2. Пример решения задачи
Пусть N=5, X=10, Y=20, P1 =1/3, P2 =1/2, R1 =3/4, R2 =2/3.
Уравнение ( 4 ) граничной линии при k>1 имеет вид
Y = |
9 |
X . |
|
|
|||
|
16 |
|
|
Точка (10,20) лежит выше граничной линии, что отвечает выбору B. Этот |
|||
выбор порождает точку ( 10 , (1-2/3)× |
20), т.е. ( 10 , 20/3), принадлежащую |
||
области B. Этот выбор, в свою очередь, порождает точку (10,20/9), при- |
|||
надлежащую области А. Выбор А |
порождает точку (10/4,20/9), лежа- |
||
щую в области B. |
|
|
|
В итоге проделанных четырех выборов к последнему шагу возникает |
|||
точка (10,20/27 ), для которой |
|
|
|
F ( 10, 20 ) = max [ |
1 |
|
3 |
|
10 |
, |
1 |
|
2 |
|
20 ] = 5 , |
|
||||
|
4 |
|
3 |
|
||||||||||||
1 |
27 |
|
3 |
4 |
|
2 |
|
|
27 |
8 |
|
|||||
что соответствует выбору А. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом, |
оптимальная |
последовательность |
выборов |
имеет |
||||||||||||
вид {B B A B A}. Что касается значения F5(10,20), то |
его можно найти |
|||||||||||||||
обратным ходом по ранее найденным состояниям: |
|
|
|
|
||||||||||||
A : F1(10/4,20/27) = 0.625 , |
|
|
|
|
|
|
|
|
|
|
||||||
B : F2(10/4,20/9) =1/2× |
[ 2/3× |
20/9 + F1(10/4,20/27)]=1.05, |
||||||||||||||
A : F3(10,20/9) |
= 1/3× |
[ 3/4× |
10 |
+ F2 (10/4,20/9)] = 2.85, |
||||||||||||
B : F4 (10,20/3) |
= 1/2× |
[ 2/3× |
20/3 + F3 (10,20/9) ] |
= 3.65, |
||||||||||||
B : F5(10,20) |
= 1/2× |
[ 2/3× |
20 |
|
+ F4 (10,20/3) ] = 8.49 . |
|||||||||||
В случае бесконечношагового процесса соответствующее |
||||||||||||||||
функциональное уравнение имеет вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
A : P1 { R1X + F( ( 1 − R1)X ,Y ) } |
|
||||||||||||||
F(X,Y) = max B : P { R Y + |
F( X ,( 1 − R |
2 |
)Y ) |
} |
( 5 ) |
|||||||||||
|
|
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналогичными рассуждениями можно показать, что области A и B первого выбора разделяются линией (4), и тем самым c легкостью делать очередной выбор по заданному соотношению запасов.
К сожалению, малейшее усложнение задачи многократно увеличивает трудоемкость решения [1]
16
4.3. Контрольные задания
4.3.1. Требования
1. Ознакомьтесь с постановкой задачи и подходом к ее решению методом рекуррентных соотношений.
2.Выберите вариант контрольного задания и выполните его решение. Оцените полученное оптимальное решение с позиций здравого смысла.
3.Как изменится математическая постановка задачи, если допустить, что машина выходит из строя не навсегда, а допускает ремонт к следующему сезону ?
4.Как вы подойдете к решению рассмотренной задачи в случае процесса бесконечной длительности ?
4.3.2.Варианты заданий
№ |
X |
Y |
P1 |
P2 |
R1 |
R2 |
N |
№ |
X |
Y |
P1 |
P2 |
R1 |
R2 |
N |
1 |
40 |
70 |
0.6 |
0.7 |
0.3 |
0.1 |
7 |
2 |
50 |
70 |
0.6 |
0.7 |
0.3 |
0.3 |
7 |
3 |
10 |
15 |
0.7 |
0.6 |
0.2 |
0.4 |
7 |
4 |
15 |
15 |
0.7 |
0.6 |
0.3 |
0.4 |
7 |
5 |
55 |
33 |
0.2 |
0.6 |
0.8 |
0.4 |
7 |
6 |
45 |
33 |
0.2 |
0.6 |
0.8 |
0.5 |
7 |
7 |
80 |
20 |
0.3 |
0.9 |
0.7 |
0.5 |
7 |
8 |
60 |
80 |
0.3 |
0.8 |
0.7 |
0.5 |
7 |
9 |
20 |
25 |
0.5 |
0.7 |
0.7 |
0.5 |
7 |
10 |
20 |
25 |
0.5 |
0.7 |
0.7 |
0.5 |
7 |
11 |
65 |
50 |
0.1 |
0.4 |
0.7 |
0.3 |
7 |
12 |
65 |
50 |
0.1 |
0.4 |
0.7 |
0.3 |
7 |
13 |
100 |
75 |
0.7 |
0.9 |
0.6 |
0.5 |
7 |
14 |
100 |
75 |
0.7 |
0.8 |
0.6 |
0.5 |
7 |
15 |
55 |
20 |
0.3 |
0.5 |
0.6 |
0.3 |
7 |
16 |
50 |
20 |
0.2 |
0.5 |
0.6 |
0.3 |
7 |
17 |
15 |
50 |
0.1 |
0.3 |
0.6 |
0.5 |
7 |
18 |
15 |
40 |
0.2 |
0.3 |
0.6 |
0.5 |
7 |
19 |
45 |
70 |
0.8 |
0.9 |
0.5 |
0.4 |
7 |
20 |
60 |
70 |
0.8 |
0.9 |
0.5 |
0.4 |
7 |
21 |
120 |
100 |
0.4 |
0.3 |
0.5 |
0.7 |
7 |
22 |
120 |
90 |
0.4 |
0.3 |
0.5 |
0.7 |
7 |
23 |
33 |
40 |
0.9 |
0.7 |
0.5 |
0.7 |
7 |
24 |
50 |
40 |
0.9 |
0.7 |
0.5 |
0.7 |
7 |
25 |
20 |
15 |
0.5 |
0.6 |
0.3 |
0.2 |
7 |
26 |
30 |
15 |
0.5 |
0.3 |
0.3 |
0.8 |
7 |
27 |
90 |
50 |
0.5 |
0.6 |
0.4 |
0.4 |
7 |
28 |
90 |
60 |
0.5 |
0.7 |
0.4 |
0.4 |
7 |
29 |
150 |
200 |
0.6 |
0.5 |
0.7 |
0.9 |
7 |
30 |
150 |
200 |
0.6 |
0.5 |
0.7 |
0.8 |
7 |
31 |
100 |
100 |
0.4 |
0.3 |
0.5 |
0.7 |
7 |
32 |
50 |
100 |
0.3 |
0.3 |
0.5 |
0.7 |
6 |
33 |
60 |
40 |
0.9 |
0.7 |
0.5 |
0.7 |
7 |
34 |
75 |
40 |
0.8 |
0.7 |
0.5 |
0.7 |
6 |
35 |
20 |
25 |
0.5 |
0.6 |
0.3 |
0.2 |
7 |
36 |
25 |
25 |
0.5 |
0.6 |
0.3 |
0.2 |
6 |
37 |
80 |
50 |
0.5 |
0.6 |
0.5 |
0.4 |
7 |
38 |
60 |
50 |
0.5 |
0.6 |
0.5 |
0.4 |
6 |
39 |
50 |
200 |
0.6 |
0.5 |
0.6 |
0.9 |
7 |
40 |
75 |
100 |
0.6 |
0.5 |
0.6 |
0.8 |
6 |
41 |
60 |
50 |
0.4 |
0.3 |
0.5 |
0.7 |
6 |
42 |
50 |
100 |
0.4 |
0.4 |
0.5 |
0.7 |
6 |
43 |
35 |
40 |
0.8 |
0.7 |
0.5 |
0.7 |
6 |
44 |
75 |
40 |
0.9 |
0.7 |
0.5 |
0.7 |
6 |
45 |
20 |
45 |
0.5 |
0.8 |
0.3 |
0.2 |
6 |
46 |
25 |
25 |
0.5 |
0.8 |
0.3 |
0.2 |
6 |
47 |
80 |
50 |
0.6 |
0.6 |
0.4 |
0.4 |
6 |
48 |
60 |
50 |
0.4 |
0.5 |
0.5 |
0.4 |
6 |
49 |
150 |
100 |
0.6 |
0.5 |
0.7 |
0.5 |
6 |
50 |
75 |
100 |
0.5 |
0.4 |
0.6 |
0.8 |
6 |
17
5.Лабораторная работа 5.
Марковские процессы принятия решений
5.1. Постановка задачи и описание метода решения
Пусть некоторая система (сбыт, потребление, здоровье, плодородие, комнатная температура и пр.) в любой фиксированный момент t может находиться в одном из n состояний и перейти из этого состояния в любое
другое. Пусть вероятность Pt(i,j) перехода в момент t из i-го состояния в j-е не зависит от предыстории системы. Такая система называется мар-
ковской.
Если вероятности перехода не зависят от времени, марковская система обладает свойством стационарности, т.е. функция Xt(j) вероятности
нахождения системы в момент t в j-ом состоянии при t→∞ асимптотически сходится к функции X(j), удовлетворяющей уравнениям:
X ( j ) = ∑n |
P( i, j ) X ( i ), |
j = 1 . . n . |
i= 1 |
|
|
Это позволяет предсказать вероятность того или иного состояния на дальнюю перспективу без каких-то трудоемких вычислений.
Предположим, что вероятности перехода зависит от некоторой политики (выбора) q и переход сопровождается получением некоторого
благоприятного эффекта Ri j(q).
Обозначим через Fk(i) ожидаемый эффект функционирования системы, находившейся в начальный момент в i-м состоянии, за k периодов при использовании оптимальной политики. Руководствуясь принципом оптимальности, требующим независимо от начального состояния i и от начального выбора q далее действовать оптимально, т.е. гарантировать мак-
симум ожидаемого эффекта |
в последующем процессе, приходим к |
ре- |
|||||
куррентным соотношениям вида: |
|
|
|
|
|||
Fk(i) = max ∑n |
P |
( q ) [ R |
( q ) + F |
k − 1 |
( j ) ] , i = 1 . . n , k ≥ |
1; |
( 1 ) |
q j = 1 i j |
i j |
|
|
|
|
||
|
|
F0( i ) = 0 , |
i = 1 . . n . |
|
|
||
Для процессов большой длительности использование (1) требует существенных затрат времени даже при машинной реализации процесса вычислений. Если учесть, что при независимости значений вероятностей и эффектов от времени процесс обладает свойством стационарности, то в предположении регулярности (возможности прямого или опосредствованного перехода из любого состояния в любое) полагаем для больших k
Fk (i) = Fi + k G , |
( 2 ) |
где G - средний эффект за период и Fi -составляющая суммарного эффек-
18
та, определяемая начальным состоянием. Подставляя (2) в (1) и учитывая
|
|
∑n |
Pi j( q ) = 1, |
|
|
|
j= |
1 |
|
получаем систему функциональных уравнений |
|
|||
Fi |
+ G = max ∑n |
Pi j ( q ) [ Ri j ( q )+ F j ] , i = 1 . . n , |
( 3 ) |
|
|
q j= |
1 |
|
|
которую можно решать приближением в поведениях. Приведенную систему можно получить, если записать уравнение для бесконечношагового процесса с учетом дисконтирования, положить величину дисконтирован-
ного эффекта равной Fi + G/(1-α ) и принять α = 1 .
Для иллюстрации марковского процесса принятия решений рассмотрим "задачу о такси" .
Таксист обслуживает окрестности трех городов и может руководствоваться одним из трех выборов: ездить по городу в поисках случайного пассажира, ждать вызова по радио или поехать на стоянку и стать там в очередь.
Для каждого города ( i ) и каждого выбора ( q ) известны вероятности поездки в тот или иной город и соответствующие доходы, сведенные в таблице:
Город |
Выбоp |
Вероятности перехода |
Значения дохода |
||||
i |
q |
j=1 |
j=2 |
j=3 |
j=1 |
j=2 |
j=3 |
1 |
1 |
1/2 |
1/4 |
1/4 |
10 |
4 |
8 |
|
2 |
1/16 |
3/4 |
3/16 |
8 |
2 |
4 |
|
3 |
1/4 |
1/8 |
5/8 |
4 |
6 |
4 |
2 |
1 |
1/2 |
0 |
1/2 |
14 |
0 |
18 |
|
2 |
1/16 |
7/8 |
1/16 |
8 |
16 |
8 |
3 |
1 |
1/4 |
1/2 |
1/4 |
10 |
2 |
8 |
|
2 |
1/8 |
3/4 |
1/8 |
6 |
4 |
2 |
|
3 |
3/4 |
1/16 |
3/16 |
4 |
0 |
8 |
Возьмем за начальное поведение q0 = (1, 1, 1), т.е. во всех городах будем придерживаться первого выбора. Для выбранного поведения строим систему n уравнений с n+1 неизвестными
Fi + G = ∑n Pi j( q |
0 ) [ Ri j( q0 ) + F j ] , i = 1 . . n, |
j = 1 |
|
разрешимую с точностью до константы. Для нашего примера :
F1 + G = 1/2 [ 10 + F1 ] + 1/4 [ 4 + F2 ] + 1/4 [ 8 + F3]
F2 + G = 1/2 [ 14 + F1] + + 1/2 [18 + F3]
F3 + G = 1/4 [ 10 + F1 ] + 1/2 [ 2 + F2 ] + 1/4 [ 8 + F3 ]
Полагая, например, F3 = 0, получаем F1 = 4/3, F2 = 7.47 и G = 9.2, т.е. выбранная политика дает средний доход за одну поездку, равный 9.2.
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
Вычисляем |
|
∑n |
|
|
|
|
|
|
|
|
|
|||
|
|
Ti(q) = |
Pi |
j ( q ) [ Ri j ( q )+ F j ] |
|
|
||||||||
|
|
|
|
j= |
1 |
|
|
|
|
|
|
|
|
|
при всех i и q |
и найденных значениях Fi: |
|
|
|
|
|||||||||
|
|
|
T1(1) = |
1/2 |
[10+4/3 ] + |
1/4 |
[ 4+7.47 ] + 1/4 |
[ 8+0 ] |
||||||
|
|
|
T1(2) |
= |
1/16 [ |
8+4/3 ] + |
3/4 |
[ 2+7.47 ] + 3/16 [ 8+0 ] |
||||||
|
|
|
T1(3) |
= |
1/4 |
[ |
4+4/3 ] + |
1/8 [ 6+7.47 ] + 5/8 |
[ 4+0 ] |
|||||
|
|
|
T2(1) |
= |
1/2 |
[14+4/3 ] + |
|
|
|
+ 1/2 |
[18+0 ] |
|||
|
|
|
T2(2) |
= |
1/16 [ |
8+4/3 ] + |
7/8 [16+7.47 ] + 1/16 [ 8+0 ] |
|||||||
|
|
|
T3(1) |
= |
1/4 |
[10+4/3 ] + |
1/2 |
|
[ 2+7.47 ] + |
1/4 |
[ 8+0 ] |
|||
|
|
|
T3(2) |
= |
1/8 |
[ |
6+4/3 ] + |
3/4 |
|
[ 4+7.47 ] + |
1/8 |
[ 2+0 ] |
||
|
|
|
T3(3) |
= 3/4 |
[ |
4+4/3 ] + |
1/16 [ 0+7.47 ] + 3/16 [ 8+0 ]. |
|||||||
Выбирая максимальное из значений Ti(q) |
по q, получаем улучшенное по- |
|||||||||||||
ведение q =(1, 2, 2). Строим и решаем систему уравнений: |
|
|||||||||||||
|
|
F1 + G = 1/2 [ 10 + F1] + 1/4 [ 4 + F2 ] + 1/4 [ 8 + F3 ] |
||||||||||||
|
|
F2 + G = 1/16 [ |
8 + F1] + 7/8 [16 + F2 ] |
+ 1/16 [ 8 + F3] |
||||||||||
|
|
|||||||||||||
|
|
F3 + G = 1/8 [ |
6 + F1] + 3/4 [ 4 + F2 ] |
+ 1/8 [ 2 + F3] |
, |
|||||||||
получая F3 = 0, |
F2 = -3.88, F1 = 12.85, |
G = 13.15. |
q =(2, 2, 2), для |
|||||||||||
Попытка |
дальнейшего улучшения |
дает политику |
||||||||||||
которой F3 = 0, |
F2 = -1.18, |
F1 = 12.86, |
G = 13.34. Очередная попытка |
|||||||||||
улучшения приводит к той же политике, |
откуда напрашивается вывод о |
|||||||||||||
том, что оптимальная политика состоит в использовании второго выбора во всех городах и обеспечивает средний ожидаемый доход за одну поездку, равный 13.34.
2.3. Контрольные задания
2.3.1. Требования
1. Выберите вариант контрольного задания и выполните его решение в предположении процесса большой длительности. Оцените полученное оптимальное решение с позиций здравого смысла.
2.Как вы будете решать задачу, если процесс не будет длительным ?
3.Как получить систему функциональных уравнений (3) на основе интегрального дисконтированного эффекта ?
4.Что характерно для стационарного процесса ?