Les chaînes de Markov
265
Ce principe va nous permettre de résoudre le problème posé. Supposons en effet que, à
la date
on connaisse les sous-politiques optimales de
pour chaque état
On a donc calculé :
)
(
=
)
(
1
1
0
=
1
1
k
k
k
i
k
i
i
x
x
v
Min
x
V
2
2
1
...
,
i
x
x
x
avec
)
(
1
k
k
x
x
Pour un
donné, d'après le principe d'optimalité, on a alors, si
est l'application
inverse de :
)]
(
)
(
[
=
)
(
1
1
1
1
i
i
i
i
i
i
i
x
V
x
x
v
Min
x
V
(14)
)
(
1
1
i
i
x
x
Cette formule fondamentale permet de proposer l'algorithme suivant :
Phase 1
Phase 2
)]
(
)
(
[
=
)
(
1
1
2
1
1
2
2
x
V
x
x
v
Min
x
V
)
( 2
1
1
x
x
Phase i
)]
(
)
(
[
=
)
(
1
1
1
1
i
i
i
i
i
i
i
x
V
x
x
V
Min
x
V
)
(
1
1
i
i
x
x
Phase T
)
(
1
1
T
T
x
x
est alors la valeur de l'optimum cherché. Pour trouver la politique optimale, il suffit
de remonter le temps : la dernière équation, par laquelle on calcule
permet en
même temps d'avoir
qui assure le minimum de
. L'avant dernière équation,
par laquelle on calcule
permet de repérer
etc.
)]
(
)
(
[
=
)
(
1
1
1
1
T
T
T
T
T
T
T
x
V
x
x
V
Min
x
V
)
,
(
=
)
(
1
0
0
1
1
x
x
v
x
V