Master 1 MIAGe Recherche Opérationnelle I Projet de programmation à faire en groupes de 2 ou 3

1 Amélioration des coûts d’une chaîne de Markov

Ecrire un programme (en C, C++ ou java) qui lit les informations sur deux chaînes de Markov sur les mêmes états, décide laquelle parmi les deux a les moindres coûts asymptotiquement, et détermine si une politique mixte serait meilleur encore.

2 Date d’échéance

Le 24 décembre 2006.

3 Coefficient

75% de la note de Contrôle Continu (ou, si la fonctionnalité facultative est bien traitée, 50% ou 100% selon ce qui vous est plus avantageux.).

4 Il faut

1. Lire les matrices de probabilités de transition et de coûts pour les deux chaînes (exemple du format en proj.dat mais le vrai fichier n’aura pas de commentaires)

2. calculer les coûts asymptotiques (les v_{i} du cours) en utilisant actualisation avec un taux ρ de 0.95

3. afficher ces coûts

4. décider si les coûts de la meilleure des deux chaînes (c’est-à-dire la meilleure selon le v de l’état de départ qui est le premier état) pourraient être améliorés en changeant la stratégie d’un ou plusieurs états à celle de l’autre chaîne.

5 Facultativement

1. Trouver la politique mixte optimale (une politique mixte veut dire une politique qui utilise, pour chaque état, la stratégie de l’une des deux chaînes.

(vous utiliserez, bien sûr, l’algorithme d’améliorations successives de la politique plutôt qu’un algorithme de recherche brute.)

6 Vous pouvez

1. supposer que toute politique a une chaîne avec une seule classe finale et que cette classe ne sera jamais périodique;

2. utiliser des programmes d’analyse des états d’une chaîne ou de résolution d’un système d’équations linéaires vus en TD.

7 A rendre par mail

Les sources et documentation de votre programme, ainsi que le chemin d’accès à un répertoire contenant les sources, une version exécutable et les fichiers sur lesquels vous l’avez testé.