Chaînes de Markov avec coûts associés
(tous les états persistants et apériodiques)

Coût d'une transition: Ai,j pour la transition de i à j (ne dépend pas du temps ni de l'histoire)

Coût moyen d'une transition: de l'état i:
ai  =  N
å
j=1 
Pi,jAi,j

Tendance vers la moyenne:

Le coût moyen par transition tend vers g où g est le coût moyen d'une transition dans la distribution limite P

On peut facilement calculer g:

N
å
i=1 
Pi ai = g

Décisions qui peuvent changer
les probabilités de transition

La possibilité de choix: supposons que dans l'état i on peut choisir entre plusieurs décisions et que pour la décision d, la probabilité d'aller en état j est Pdi,j avec un coût adi,j

on peut calculer l'espérance du coût d'une transition:
adi  =  N
å
j=1 
Pdi,j adi,j
mais minimiser ca (la politique gloutonne) n'est pas forcément la bonne politique

Le nombre de politiques possibles peut être trop grand pour permettre de calculer le g de chacune
et peut-être ce n'est pas la politique possédant le plus petit g qu'il convient de choisir...

Actualisation des coûts

Un compromis entre la politique gloutonne et minimiser g

Actualisation: Un euro aujourd'hui est plus utile qu'un euro l'année prochaine;
Un coût d'un euro aujourd'hui est plus grave qu'un pareil coût l'année prochaine;

On veut calculer les coûts sur la supposition qu'un euro au temps t vaut r euros au temps t+1; 0 < r < 1.

Rapport avec le taux d'intérêt: si le taux réel d'intérêt (payé ou reçu) est t, on a
r = 1/(1+t).

Calcul des coûts

Les équations pour les coûts totaux: On a toujours un coût immédiat (moyen) en l'état i de ai et une probabilité Pi,j de transition de l'état i à j:


vi  =  ai + r N
å
j=1 
Pi,j vj

Système non singulier: on peut calculer les vi de ces équations parce que r < 1.

Le coût dans la distribution limite: Si le coût moyen d'une transition dans la distribution limite (sans actualisation) est g, le coût (total) si on commence dans cette distribution est g(1+r+r2 +r3 ¼) =  g/(1-r). Donc g rt /(1-r) est une approximation au coût à partir de temps t (t grand et la chaîne régulière).

Optimisation des coûts

Selon notre point de vue nous voulons choisir une politique de façon à minimiser

Existence d'algorithmes assez efficaces qui convergent sur une politique optimale.


File translated from TEX by TTH, version 3.05.
On 24 Sep 2004, 17:49.