Module C1.7 : Processus stochastique et simulation
Les chaînes de Markov
Les chaînes de Markov avec des coûts associés

Estimation des coûts
Actualisation des coûts
Calcul des coûts
Calcul d'une politique optimale avec actualisation
Le cas sans actualisation
Exemple (exercice corrigé)
Exercices


Auteur(s) : Mike Robson - IUP Miage Bordeaux
Date de dernière modification : 06 octobre 2004

On considère dans cette séquence des chaînes de Markov qui modélisent des phénomènes économiques. Chaque transition du système a un coût associé et on veut se servir du modèle pour analyser et/ou minimiser les coûts moyens à long terme. On ne considèrera que le cas où tous les états sont persistants et apériodiques.

Estimation des coûts

Coût d'une transition

Nous avons vu dans les séquences précédentes que l'on associe à chaque transition d'un état i à un état j une probabilité  . Dans cette séquence nous définissons le coût moyen d'une transition de i à j par un nouveau coefficient   (on suppose que le coût ne dépend ni du temps ni de l'histoire).

Coût moyen d'une transition

Le coût moyen de la première transition de l'état i est :

 .

Le coût moyen par transition tend vers une constante g. Cette constante est le coût moyen d'une transition dans la distribution limite   (cf la séquence précédente).

On peut donc facilement calculer g :

Possibilité de choix

Supposons que dans l'état i on puisse choisir entre plusieurs décisions et que pour la décision d, la probabilité d'aller à l'état j est   avec un coût  .

On peut calculer l'espérance du coût d'une transition :

mais minimiser cette quantité (la politique gloutonne) n'est pas forcément la bonne politique.

De même, le nombre de politiques possibles peut être trop grand et l'on ne peut calculer le coût moyen g de chacune d'elle sans oublier que ce n'est pas forcément la politique possédant le plus petit g qu'il convient de choisir... Comment comparer les coûts que nous devons payer aujourd'hui avec ceux des années futures ?

 

Actualisation des coûts

C'est un compromis entre la politique gloutonne et la minimisation de g. Un euro aujourd'hui est plus utile qu'un euro l'année prochaine; Le coût d'un euro aujourd'hui est plus grand qu'un pareil coût l'année prochaine;

On veut calculer les coûts sur la supposition qu'un euro à l'instant t vaut    euros à l'instant  .

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

 

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é   de transition de l'état i à j. Le coût moyen actualisé de toutes les transitions à partir de l'état i, noté vi, est donné par l'équation :

(le coût de la première transition augmenté de l'espérance actualisée des coûts de toutes les transitions après la première)

Ici parce que    nous avons un système non singulier : on peut calculer les vi directement à partir de ces équations.

 

Calcul d'une politique optimale avec actualisation

On considère maintenant le cas où, dans chaque état, on peut choisir entre plusieurs décisions et on veut minimiser le coût total avec actualisation.

Il est évident que la décision optimale pour chaque état ne dépend ni de l'histoire ni du temps.

On peut utiliser l'algorithme d'amélioration d'une politique initiale : calculer le coût total (avec actualisation) vj à partir de chaque état j ; choisir à chaque état i la décision   qui minimise   ; répéter tant qu'il y a une réduction ;
(ce qui équivaut à minimiser le coût qu'on aurait si on choisissait une nouvelle politique pour la première étape et gardait l'ancienne politique après, ce qui explique pourquoi il y a amélioration).

Justification de cet algorithme

Il y a une réduction des coûts à chaque itération.

Le nombre de politiques possibles est fini, donc, il est garanti que l'algorithme se termine.

En principe cette terminaison pourrait être très lente (le nombre de politiques étant très élevé), mais "en pratique" l'algorithme trouve la politique optimale après un nombre raisonnable d'itérations.

Nous donnons une démonstration plus mathématique que l'algorithme réduit les coûts à chaque étape, sauf si on est déjà à une politique optimale :

D'abord avec les décisions d, on a :

On choisit    tel que

(et on continue si on a une réduction pour au moins un i)

Les vrais nouveaux coûts sont donnés par :

Donc :

(et on a une augmentation pour au moins un i)

Considérons l'indice i qui donne le minimum de  : on a

et, donc,   pour tout j

Finalement, le résultat ne peut donc être nul pour tout j, et donc on a une amélioration.

 

Le cas sans actualisation

Ce cas est plus compliqué car les équations :

ne sont pas utilisables si   ; (soit aucune solution, soit plusieurs).

On peut définir    le coût moyen d'une suite de n transitions à partir de l'état i. On trouve que :

où, maintenant, vi est le coût si on commence à l'état i.

On a ,

mais ces équations ne suffisent pas (ajout de la même constante k à chaque vi donne une nouvelle solution). Il faut ajouter :

On peut d'optimiser la politique en utilisant la même idée que dans le cas avec actualisation :

 

Exemple : Assurance d'un véhicule

Le coût de l'assurance d'un véhicule est 100, 200, 400 ou 600.

Après un an sans aucun accident déclaré, le prix est réduit au niveau inférieur.
Après un an avec un accident déclaré, le prix est augmenté au niveau supérieur.
La probabilité d'un accident grave est 5 % par an.
La probabilité d'un accident mineur est 15 % par an et le coût de sa réparation est 500.

Devrait-on déclarer un accident mineur ou payer la réparation ?
(nous prenons  = 0.9 et supposons tous les coûts actualisés au début de l'année).

 

Calcul de la politique optimale

Je commence avec la politique de déclarer tout incident

et je calcule 

Donc une meilleur politique pour les niveau 200 et 400 est de payer les réparations.

Par exemple pour  :

et  .

Maintenant on voit qu'une meilleur politique à v2 est de déclarer l'accident (parce que maintenant  ).

Donc, une troisième politique :

et  .

La solution optimale !

Le modèle n'est pas très réaliste car tous les accidents mineurs n'ont pas le même coût mais ce calcul peut aider à prendre de bonnes décisions, par exemple en l'état 2 déclarer un sinistre si le coût est supérieur à .

 


 

Exercices

Questionnaire de compréhension immédiate