%
\documentclass{article}
\usepackage{isolatin1}
\begin{document}
\begin{center}\Large\bf
Master 1 MIAGe\\Recherche Op\'erationnelle I\\
Projet de programmation\\
\`a faire en groupes de 2 ou 3
\end{center}
\section{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.

\section{Date d'\'ech\'eance}
Le 24 d\'ecembre 2006.

\section{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.).

\section{
Il faut}
\begin{enumerate}
\item 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)
\item calculer les coûts asymptotiques (les $v_i$ du cours) en utilisant actualisation avec un taux
$\rho$ de $0.95$
\item afficher ces coûts
\item 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.
\end{enumerate}

\section{Facultativement}
\begin{enumerate}
\item 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.)
\end{enumerate}

\section{Vous pouvez}
\begin{enumerate}
\item supposer que toute politique a une chaîne avec une seule classe finale et que cette
classe ne sera jamais périodique;
\item 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.
\end{enumerate}

\section{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é.

\end{document}
