\documentclass{article}
\usepackage[latin1]{inputenc}
\begin{document}


\def\annee{\small 2007-2008}
\def\session{\small Décembre 2007}
\def\GU{\small Master 1 MIAGe }
\def\UE{\small MIG715}
\def\date{\small 11 Décembre 2007, 10h30}
\def\duree{\small 1h30}
\def\epreuve{\small Recherche Op\'erationnelle 1}
\def\documents{\small autorisés}
\def\professeur{\small Monsieur Robson}
\def\nompages{5} %nombre de pages


%%--FORMAT DE LA PAGE----------------------------------------------------------
%\setlength{\oddsidemargin}{0cm}
%%\setlength{\textwidth}{16.5cm}
%\setlength{\evensidemargin}{0cm}
%\setlength{\headheight}{-1cm}
%\setlength{\headsep}{0cm}
%\setlength{\topskip}{-1cm}
%\setlength{\textheight}{25cm}
%%\renewcommand{\baselinestretch}{0.95}
%\pagestyle{empty}
%%-----------------------------------------------------------------------------

\newcounter{probleme}
\newcommand{\probleme}{%
        \stepcounter{probleme}\paragraph{Problème \Roman{probleme} :}}
\newcounter{exercice}
\newcommand{\exercice}{%
        \stepcounter{exercice}\paragraph{Exercice \Roman{exercice} :}}
\newcounter{partie}
\newcommand{\partie}{%
        \stepcounter{partie}\subsection*{Partie \Roman{partie} :}}
\newcounter{question}
\newcommand{\question}[1]{%
        \stepcounter{question}
        \begin{description}
        \item[\textsf{\arabic{question}} ] #1
        \end{description}}
\newcommand{\miniquestion}[1]{%
%  \par\noindent {\bf \thequestion.~} #1 }
  \par\hspace*{0pt} #1 }


\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\ala}[1]{$^{\mbox{\scriptsize #1}}$}

\newcommand{\sautdepage}{\par\mbox{}\vfill\hfill\ldots/\ldots\\\newpage}

\newcommand{\minicadre}{%
  \fbox{\rule{0cm}{2ex}\hspace{30ex}}}
\newcommand{\petitcadre}{%
  \fbox{\rule{0cm}{2ex}\hspace{\linewidth}}}
\newcommand{\cadre}{%
  \fbox{\rule{0cm}{12ex}\hspace{\textwidth}}}
\newcommand{\Cadre}{%
  \fbox{\rule{0cm}{24ex}\hspace{\textwidth}}}
\newcommand{\CADRE}{%
  \fbox{\rule{0cm}{36ex}\hspace{\textwidth}}}
\newcommand{\BIGCADRE}{%
  \fbox{\rule{0cm}{21cm}\hspace{\textwidth}}}


\vspace{1cm}

%\small \renewcommand{\sdim}{1.5\fboxsep}

\vspace{1cm}

\normalsize

\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\thepage}{\arabic{page}/\nompages}

\question{[5 points]} %  chaînes de Markov : tendance vers une limite
Si une chaîne de Markov a une seule classe finale et cette classe est apériodique,
on peut dire que la probabilité d'être dans un état $i$ tend vers une limite qui
ne dépend ni de l'etat initial ni du nombre de transitions. Que peut-on dire de la tendance
dans les cas suivants?
\begin{enumerate}
\item Plusieurs classes finales apériodiques
\\{\bf Réponse}\\
Dans ce cas la probabilité d'être dans un état $i$ tend vers une limite mais cette
limite dépend de l'etat de départ.

Pour un état initial $j$ la limite est donnée par la somme pondérée des distributions
stationnaires de chaque classe finale, le poids pour chaque classe étant la probabilité
de finir dans cette classe si on commence dans l'état $j$. Pour chaque classe finale $C$,
le calcul de ces probabilités $p_j$ pour tous les états $j$ se fait par la résolution
du système d'équations:\\
$p_j~=~1$ pour chaque état $j$ dans la classe $C$\\
$p_j~=~0$ pour chaque état $j$ dans une autre classe finale\\
$p_j~=~\sum_k a_{j,k}p_k$ sinon\\
où $a$ est la matrice de probabilités de transition.
Ce système est forcément non-singulier.

La distribution stationnaire pour chaque classe finale $C$ se fait par l'algorithme standard
de calcul de distribution stationnaire limité aux états de $C$, à savoir la résolution
du système d'équations\\
$\pi_j~=~\sum_k \pi_ka_{k,j}$\\
où $j$ et $k$ sont limités aux états de $C$, avec la suppression d'une de ces équations
et son remplacement par\\
$\sum_k \pi_k~=~1$\\
pour donner un système non-singulier.

\item Une classe finale périodique
\\{\bf Réponse}\\
Dans ce cas il y a une limite pour chaque état de départ et chaque entier $j$ ($0\le j< \lambda$)
($\lambda$ est la période) qui est valable pour les temps $t$ congruents à $j$ (modulo $\lambda$).
Pour calculer ces limites, il faut
\begin{itemize}
\item calculer la période $\lambda$
\item trouver les sous-classes
\item trouver la distribution limite dans chaque sous-classe pour la chaîne dont la matrice est $a^\lambda$
\item calculer la probabilité limite d'être dans chaque sous-classe pour les temps $t$ congruents à $j$ (modulo $\lambda$).
\end{itemize}
Les sous-classes et la période se trouvent facilement à partir d'une grande (par exemple $n^2$) puissance de
la matrice booléenne des possibilités de transition (restreinte aux états de la classe finale) ; en effet deux états
sont dans la même sous-classe si et seulement si leurs lignes dans cette matrice sont identiques. Enfin
la période est le nombre de sous-classes trouvées.

La distribution limite de chaque sous-classe se calcule par l'algorithme standard déjà cité.

La probabilité d'être dans une sous-classe donnée à un temps congruent à $0$ (modulo $\lambda$)
est calculée par le premier algorithme cité appliqué à $a^\lambda$ ; ensuite la probabilité d'être
dans la sous-classe numéro $i$ à temps congruent à $j$ est la probabilité d'être dans $i-j$ (modulo $\lambda$)
à temps congruent à $0$.

Enfin la probabilité d'être dans un état $X$ à temp est le produit de la probabilité d'être
dans la sous-classe de $X$ avec la probabilité de $X$ dans la distribution limite de cette sous-classe.
\end{enumerate}
Dans chaque cas, expliquez les principales étapes du calcul des limites qui existent.


\question{[5 points]} % 3 jeux (3 par 3) : domination, équilibre en stratégies pures, calcul de Nash
Dans les trois jeux donnés, la première matrice est celle des gains du premier joueur qui choisit
la ligne. 
\begin{enumerate}
\item Dans un cas il y a une stratégie pour un joueur qui en domine une autre :
quel jeu, quel joueur et quelle stratégie en  domine quelle autre? Comment sait-on que la stratégie domine l'autre?\\
{\bf Réponse}\\
En le jeu $3$, pour le second joueur la deuxième stratégie domine la troisième.\\
Les gains de la deuxième sont $5,~8,~10$ selon la stratégie du premier ; ceux de la
troisième sont $4,~7,~9$. Donc le deuxième stratégie a un meilleur gain pour
chaque action de l'autre joueur.
\item Dans un autre cas, il y a un équilibre avec une stratégie pure de chaque joueur :
quel jeu et quelle stratégie pour chaque joueur? Comment sait-on que c'est un point d'équilibre?\\
{\bf Réponse}\\
Dans le premier jeu, un équilibre est donné par les stratégies $2$ pour le premier joueur et $3$
pour l'autre.\\
Pour le premier joueur, son gain ($8$) est le meilleur possible avec cette stratégie du deuxième
(élément maximum de la colonne $3$) ;
pour le second son gain ($5$) est le meilleur possible avec cette stratégie du premier
(élément maximum de la ligne $2$).
\item Dans le dernier cas il y a un équilibre avec une stratégie mixte pour chaque joueur :
en supposant que pour chaque joueur chacune de ses trois actions est dans le support de sa stratégie,
expliquez comment calculer la probabilité avec laquelle chacun devrait jouer chaque action.
(On ne vous demande pas d'effectuer le calcul.) \\
{\bf Réponse}\\
Pour le jeu $2$, si le premier joueur a une stratégie mixte optimale avec probabilités $x_1,~x_2,~x_3$
de choisir chaque ligne, on sait qu'il a le même gain pour chaque stratégie de l'autre. Donc,\\
$5x_1+4x_2+6x_3~=~4x_1+7x_2+6x_3~=~8x_1+7x_2+4x_3$. Avec la troisième équation $x_1+x_2+x_3~=~1$,
ça suffit pour calculer les $x$.\\
Pour l'autre c'est pareil.
$5y_1+7y_2+5y_3 ~=~8y_1+6y_2+4y_3~=~6y_1+5y_2+7y_3$ et $y_1+y_2+y_3~=~1$.
\end{enumerate}
\begin{enumerate}
\item 
$\left(\begin{array}{rrr}
7 &2 &7 \\
4 &6 &8 \\
6 &9 &4 \end{array}\right)
\left(\begin{array}{rrr}
7 &8 &4 \\
4 &3 &5 \\
8 &2 &6 \end{array}\right)$
\item 
$\left(\begin{array}{rrr}
5 &4 &8 \\
4 &7 &7 \\
6 &6 &4 \end{array}\right)
\left(\begin{array}{rrr}
5 &7 &5 \\
8 &6 &4 \\
6 &5 &7 \end{array}\right)$
\item 
$\left(\begin{array}{rrr}
6 &8 &2 \\
4 &5 &3 \\
8 &10 &1 \end{array}\right)
\left(\begin{array}{rrr}
2 &5 &4 \\
9 &8 &7 \\
5 &10 &9 \end{array}\right)$
\end{enumerate}

\newpage

\question{[5 points]} % Prog Lin : algo du simplexe : une itération expliquée + solution trouvée
Pour le programme linéaire\\
Maximiser $-1x_1+2x_2+3x_3-3x_4$ sous les contraintes :
\begin{eqnarray*}
 5x_1+4x_2 -3x_3 +2x_4 & \le & 8\\
 3x_1+0x_2 +6x_3 +4x_4 & \le & 1\\
 -3x_1+2x_2 +6x_3 +8x_4 & \le & 2\\
 (x_1,~x_2,~x_3,~x_4 & \ge & 0)
\end{eqnarray*}
la matrice des coefficients et les deux vecteurs après l'ajout
des variables d'écart sont\\
$\begin{array}{rrrrrrr|r}
5 & 4& -3& 2& 1 & 0&0 & 8\\
3& 0& 6& 4& 0&1&0&1\\
-3&2&6&8&0&0&1&2\\ \hline
-1 & 2& 3& -3 &0&0&0&
\end{array}$

Expliquez en détail les calculs de la première itération de l'algorithme du simplexe
sur ce programme. Quelle est la solution de base trouvée par cette itération?
Expliquez comment on trouve directement cette solution des matrice et vecteurs transformés.\\
{\bf Réponse}\\
D'abord on choisit la colonne du pivot en choisissant un coefficient positif de la fonction objective :
je choisis la colonne $2$ (coefficient $+2$).\\
Ensuite on choisit la ligne du pivot en ragardant les éléments positifs de la colonne $2$ et choisissant
le rapport minimum $constante/element.de.la.colonne$ dans ces lignes : je choisis la ligne $3$ parce que $2/2<8/4$.\\
Les opérations de pivotage : d'abord diviser la ligne du pivot par la valeur du pivot ($2$)
pour remplacer le pivot par $1$\\
$\begin{array}{rrrrrrr|r}
5 & 4& -3& 2& 1 & 0&0 & 8\\
3& 0& 6& 4& 0&1&0&1\\
-1.5&1&3&4&0&0&0.5&1\\ \hline
-1 & 2& 3& -3 &0&0&0&
\end{array}$

ensuite soustraire un multiple de la ligne du pivot de chaque autre ligne de façon à remplacer les éléments
de la colonne du pivot par $0$.\\
$\begin{array}{rrrrrrr|r}
11 & 0& -15& -14& 1 & 0&-2 & 4\\
3& 0& 6& 4& 0&1&0&1\\ 
-1.5&1&3&4&0&0&0.5&1\\ \hline
2 & 0& -3& -11 &0&0&-1&
\end{array}$

Solution de base $(0,1,0,0,4,1,0)$
\\Les variables de la base sont $x_2,~x_5$ et $x_6$ ; donc, les autres variables sont nulles.

En effaçant les variables nulles, les lignes $1,~2$ et $3$ (interprétées comme des équations) donnent
les valeurs de $x_5$, $x_6$ et $x_2$ respectivement.
\newpage
\question{[5 points]} % PLNE : calcul d'un chemin augmentant; pourquoi possibilité de réduire un flot;
% pourquoi optimum trouvé si échec
Dans l'algorithme de Ford et Fulkerson pour un flot maximum dans un réseau, décrivez le processus de recherche
d'une chaîne augmentante.\\
{\bf Réponse}\\
On commence la construction d'un arbre qui contiendra tous les sommets du réseau vers lesquels un flot
peut être ajouté sans violer les contraintes. Au départ cet arbre ne contient que la source.
Quand on considère un sommet $X$, on peut ajouter $Y$ à l'arbre si
\begin{itemize}
\item $Y$ n'est pas déjà dans l'arbre
\item soit un lien $X\rightarrow Y$ n'est pas saturé, soit il existe un flot non-nul
$Y\rightarrow X$.
\end{itemize}
Si la destination est ajoutée à l'arbre, on s'arrête : une chaîne a été trouvée.

Expliquez, avec des exemples, pourquoi ce processus peut réduire le flot dans un arc\\
{\bf Réponse}\\
Réseau $S source),A,B,D~(destination)$, arêtes (bidirectionnelles) avec capacités en crochets :
$(SA~[3]),~(SB~[2]),~(AD~[2]),~(BD~[3]),~(AB~[3])$\\
flot actuel $S\rightarrow A\rightarrow B\rightarrow D$ de $3$ unités.

A la prochain itération, on va ajouter un flot $S\rightarrow B\rightarrow A\rightarrow D$ de $2$ unités,
ainsi réduisant le flot total $A\rightarrow B$ de $3$ unités à $1$.

et pourquoi le flot trouvé est forcément maximum quand le processus s'échoue.\\
{\bf Réponse}\\
Si le processus échoue, on a trouvé une partition du réseau en deux parties, le premier ($P1$)
(tous les sommets dans l'arbre) contenant la source et le second ($P2$) (tous les autres) contenant
la destination, telle que
\begin{itemize}
\item chaque lien $P1\rightarrow P2$ est saturé
\item aucun lien $P2\rightarrow P1$ n'a un flot non-nul
\end{itemize}
Donc le flot trouvé a le transfert maximum possible de $P1$ à $P2$ mais tout flot de $S$ à $D$
doit transférer de $P1$ à $P2$ au moins le total du flot.





\end{document}
