\include{header}

\begin{slide}{}
\heading{
INTRODUCTION
}

%G\'en\'eral: emploi du temps; noms; math; langue.
\begin{itemize}
\item Nom: J. M. (Mike) Robson;\\robson@labri.fr 
\item Emploi du temps:  2 heures de cours et 2 heures de TD par semaine
\item fichiers de transparents et de TD (et éventuellement des corrigés):\\
\verb+http://dept-info.labri.fr/~robson/RO+\\
Fichiers au cremi \verb+~jrobson/RO/+
\item contr\^ole continu: projet de programmation et\\
\'eventuellement
de petites interrogations et note d'assiduité en TD : coefficient 40\%?
\item R.O. branche de math; \`a voir avec d\'ecisions \'economiques
\item trait\'ee ici d'une fa\c{c}on peu rigoureuse mais ...
\item cours (normalement) en français
\item livres:\\
{\em M\'ethodes d'Optimisation Combinatoire:\\Charon et al}\\
{\em Programmation Lin\'eaire: Gu\'eret et al}\\
{\em Exercices et probl\`emes R\'esolus de Recherche Op\'erationnelle
tome 2, Roseaux}\\
Et pour l'histoire\\
{\em La Recherche Op\'erationnelle: Nobert et al}
\end{itemize}
\end{slide}

\begin{slide}{}
\heading{
Mati\`eres: techniques math\'ematiques de d\'ecision;
}
\begin{itemize}
\item o\`u est la difficult\'e de prendre une d\'ecision?
\item  C'est plus difficile quand il s'agit de plusieurs d\'ecisions
d\'ependantes?\\
interaction entre mes d\'ecisions
\item ou de  d\'ecisions de politique \`a appliquer dans le long terme\\
interaction entre mes d\'ecisions d'aujourd'hui et celles de l'avenir
\item  ou de d\'ecisions dans un monde nond\'eterministe\\
interaction entre mes d\'ecisions et la nature
\item ou décisions de moi et une autre personne (un concurrent?); ou plusieurs

\newpage
\item techniques qui d\'ependent de la construction d'un mod\`ele:
la solution donn\'ee par une de ces techniques math\'ematiques n'est plus valable que notre
mod\`ele!
\end{itemize}
\end{slide}


\begin{slide}{}
\heading{
Les Cha\^{\i}nes de Markov\\(3 prochaines  semaines de cours)
}

Mod\`eles de syst\`emes qui \'evoluent dans le temps selon des règles
probabilistes

Exemple: jouer au Pile ou Face\\
D'abord j'ai 3 euros et mon opposant a aussi 3 euros\\
A chaque tour j'ai une probabilit\'e $p$ de gagner un euro et
une probabilit\'e $1-p$ de perdre un  euro mais un joueur sans argent
ne peut plus miser\\
L'``\'etat'' du syst\`eme est combien d'argent j'ai (0,1,2,3,4,5 ou 6)\\
Les transitions possibles sont:
\[1\rightarrow 2, 2\rightarrow 3,3\rightarrow 4,4\rightarrow 5,5\rightarrow 6\]
\[1\rightarrow 0,2\rightarrow 1,3 \rightarrow 2,4\rightarrow 3,5\rightarrow 4\]
\[0\rightarrow 0, 6\rightarrow 6\]

\end{slide}

\begin{slide}{}
\heading{
Les propri\'et\'es g\'en\'erales
}

Un ensemble $E$ d'\'etats possibles

Transitions \`a des moments de temps discrets

Probabilit\'e de transition de l'\'etat $i$ \`a l'\'etat $j$ (\`a moment $t$)
ne d\'epend pas de l'histoire (c-\`a-d des \'etats ant\'erieurs)


Ici on ne consid\`ere que les cha\^{\i}nes finies (nombre d'\'etats fini) et
homog\`enes (probabilit\'e de transition d'\'etat $i$ \`a l'\'etat $j$ ne d\'epend
pas de $t$).

\end{slide}

\begin{slide}{}
\heading{
Un deuxi\`eme exemple: Une petite compagnie de livraison de colis
}
On consid\`ere une compagnie qui poss\`ede 4 camions qui sont utilis\'es
pour des livraisons entre Bordeaux et Paris. Selon les demandes re\c{c}ues
chaque matin $0$, $1$ ou plusieurs camions partent de chaque ville
pour arriver dans l'autre ville le soir. Si la demande d\'epasse
le nombre de camions disponibles, les derniers clients partent.

On veut savoir, par exemple, le pourcentage des demandes qui
\'echouent (faute d'assez de camions dans la ville de la demande).

On suppose $b_i$ la probabilit\'e chaque jour
d'une demande totale qui n\'ecessite
exactement $i$ camions de Bordeaux \`a Paris et $a_i$ la m\^eme
probabilit\'e dans la direction inverse.

Et on suppose que les demandes dans les 2 villes sont ind\'ependantes.

Il y a $5$ \'etats selon le nombre de camions dans les 2 villes (la nuit).

\end{slide}

\begin{slide}{}
La probabilit\'e d'une transition d'un état \`a un autre:

de $(0,4)$ à $(0,4)$: $a_0$

de $(0,4)$ à $(1,3)$: $a_1$

de $(1,3)$ à $(0,4)$: $a_0(b_1+b_2+b_3+b_4)$

de $(1,3)$ à $(1,3)$: $a_0b_0 ~+~ a_1(b_1+b_2+b_3+b_4)$

etc.
\end{slide}

\begin{slide}{}
\heading{
Les matrices de transitions
}

On note $P_{i,j}$ la probabilit\'e d'une transition de l'\'etat $i$ \`a l'\'etat
$j$ \`a un moment et $P$ la matrice de ces probabilit\'es.

Une matrice v\'erifiant les deux propri\'et\'es \'evidentes: $P_{i,j}\geq 0$
pour tout $i,j$ et $\displaystyle \sum_j P_{i,j} = 1$ est une
\begin{center}matrice {\it stochastique}.\end{center}
Toute matrice stochastique est la matrice d'une cha\^{\i}ne de Markov.

On note $P^{(m)}_{i,j}$ la probabilit\'e d'une transition de l'\'etat $i$ \`a l'\'etat
$j$ dans $m$ transitions et $P^{(m)}$ la matrice de ces probabilit\'es.
\end{slide}

\begin{slide}{}
\heading{
Classification des \'etats
}
Un \'etat $i$ est {\it persistant}
ou {\it r\'ecurrent}
si la probabilit\'e d'\^etre une deuxi\`eme fois
en $i$ apr\`es \^etre arriv\'e en $i$ est $1$. (Probabilit\'e $=1$
n'\'equivaut pas \`a {\em certain}!)\\
(Pour les cha\^{\i}nes finies) cel\`a \'equivaut \`a dire que s'il est
possible d'aller de l'\'etat $i$ \`a un autre \'etat $j$
(\'eventuellement en plusieurs \'etapes), il est possible de
rentrer de $j$ \`a $i$.\\
Sinon il est {\it transitoire}

Dans le jeu de Pile ou Face $0$ et $6$ sont des \'etats persistants; les autres
sont transitoires.\\
Dans le syst\`eme des camions \c{c}a d\'epend des probabilit\'es:
si $a_0=b_0=0$ et les autres probabilit\'es sont non-nulles,
$0$ et $4$ sont des \'etats transitoires et tous les autres sont
persistants..

On parle aussi des \'etats {\it ergodiques}, c'est-\`a-dire ceux pour lesquels
le temps moyen du premier retour \`a l'\'etat $i$ apr\`es \^etre
arriv\'e une fois en $i$ est
fini. Pour les cha\^{\i}nes finies il n'y a pas de diff\'erence entre persistant
et ergodique.
\end{slide}

\begin{slide}{}

Un \'etat $i$ est {\it p\'eriodique} avec p\'eriode $\lambda$ si chaque cycle
de $i$ \`a $i$ comporte un nombre de transitions qui est un multiple de
$\lambda$ (et $\lambda$ est l'entier maximum (sup\'erieur \`a $1$)
avec cette propri\'et\'e), c'est-\`a-dire le plus grand diviseur
commun
des longueurs de tous les cycles qui contiennent $i$.
\end{slide}


\begin{slide}{}
\heading{
Le graphe de transitions
}
Le graphe dirig\'e dont les sommets sont les \'etats et les arcs sont les
transitions possibles ($P_{i,j}>0$) permet de trouver les \'etats
persistants etc.

Les chemins dans ce graphe correspondent aux transitions possibles en
plusieurs \'etapes (ou 1 ou 0).

Important: les composants fortement connexes\\
(ensemble maximal de sommets tel qu'il existe un chemin de chacun \`a chaque autre)\\
Le syst\`eme entrera (avec probabilit\'e 1) dans un  composant sans sortie
et ensuite devra y rester;
Les \'etats d'un tel composant constituent une petite cha\^{\i}ne o\`u tous les \'etats
sont persistants (donc ergodiques)\\
S'il y a un seul composant fortement connexe la cha\^{\i}ne est {\it irr\'eductible}\\
Tous les \'etats d'un composant sont du m\^eme type: tous persistants
(une classe {\it finale} d'\'etats) ou tous transitoires (une classe {\it de passage});
\end{slide}


\begin{slide}{}
\heading{
D\'ecomposition en cha\^{\i}nes simples
}

Un autre graphe (sommets les composants du premier; arcs correspondant aux
transitions entre composants) suffit pour montrer dans quels composants
le syst\`eme peut finir \'etant donn\'e un \'etat initial\\
\end{slide}
\begin{slide}{}
Si l'un des \'etats d'un composant est p\'eriodique avec p\'eriode $\lambda$,
c'est vrai pour tous.

En ce cas,
on peut diviser les \'etats en $\lambda$ classes:\\
$C_0,C_1,\cdots C_{\lambda -1}$,
de telle fa\c{c}on que chaque transition est d'une classe $C_i$ \`a $C_{i+1}$
(ou de $C_{\lambda -1}$ \`a $C_0$); les chemins de longueur $\lambda$ donnent
une cha\^{\i}ne \`a l'int\'erieur de chaque $C_i$ o\`u tous les \'etats sont
persistants et ap\'eriodiques.\\
L'\'etude du comportement du syst\`eme a \'et\'e r\'eduite \`a deux questions:
l'\'etude des syst\`emes ergodiques et ap\'eriodiques; et la question de dans
quelle sous-cha\^{\i}ne on peut finir et avec quelle probabilit\'e.


\end{slide}
\end{document}
