MIAGe Master 1: Recherche Opérationnelle I TD1: le 9/9/2009

1. Dans la chaîne de Markov, dont la matrice de probabilités de transitions est don née, quelles sont les classes de passage et les classes finales ?

(Numérotez les états à partir de 1.) ( \begin{matrix}0.5 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 \\ 1.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.4 & 0.0 & 0.0 & 0.0 & 0.0 & 0.3 & 0.0 & 0.3 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.6 & 0.0 & 0.0 & 0.0 & 0.0 & 0.4 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.5 & 0.5 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.5 & 0.5 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.2 & 0.0 & 0.0 & 0.0 & 0.8 \\ 0.3 & 0.0 & 0.7 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.1 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.9 \end{matrix} )

Réponse {6, 7} classe finale {1, 2, 3, 9} classe finale {5} classe de passage {4, 8, 10} classe de passage

2. Dans cette chaîne il y a une seule classe finale et cette classe est périodique. Quelle est sa période λ et quelles sont les sous-classes ?

( \begin{matrix}0.0 & 0.0 & 0.0 & 0.1 & 0.0 & 0.0 & 0.3 & 0.0 & 0.0 & 0.3 & 0.0 & 0.0 & 0.3 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.1 & 0.3 & 0.6 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 & 0.0 \\ 0.2 & 0.0 & 0.0 & 0.3 & 0.1 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.3 & 0.0 & 0.0 & 0.1 \\ 0.1 & 0.2 & 0.2 & 0.0 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.4 & 0.3 & 0.3 \\ 0.0 & 0.0 & 0.3 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.2 & 0.3 & 0.2 \\ 0.0 & 0.0 & 0.7 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.3 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.3 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.4 & 0.3 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.3 & 0.7 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.3 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.7 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.3 & 0.7 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.7 & 0.3 & 0.0 & 0.0 & 0.0 \end{matrix} )

Réponse Période 4 {2, 10}, {6, 7, 8, 9}, {3, 13, 14, 15}, {11, 12}

3. On considère la chaîne de la compagnie de livraison décrite dans le cours:

(a) Compléter la matrice de probabilités de transition:

( \begin{matrix}a_{0} & a_{1} & a_{2} & a_{3} & a_{4} \\ a_{0}(b_{1} + b_{2} + b_{3} + b_{4}) & a_{0}b_{0} + a_{1}(b_{1} + b_{2} + b_{3} + b_{4}) & a_{1}b_{0} + a_{2}(b_{1} + b_{2} + b_{3} + b_{4}) & a_{2}b_{0} + (a_{3} + a_{4})(b_{1} + b_{2} + b_{3} + b_{4}) & (a_{3} + a_{4})b_{0} \\ a_{0}(b_{2} + b_{3} + b_{4}) & a_{0}b_{1} + a_{1}(b_{2} + b_{3} + b_{4}) & a_{0}b_{0} + a_{1}b_{1} + (a_{2} + a_{3} + a_{4})(b_{2} + b_{3} + b_{4}) & a_{1}b_{0} + (a_{2} + a_{3} + a_{4})b_{1} & (a_{2} + a_{3} + a_{4})b_{0} \\ a_{0}(b_{3} + b_{4}) & a_{0}b_{2} + (a_{1} + a_{2} + a_{3} + a_{4})(b_{3} + b_{4}) & a_{0}b_{1} + (a_{1} + a_{2} + a_{3} + a_{4})b_{2} & a_{0}b_{0} + (a_{1} + a_{2} + a_{3} + a_{4})b_{1} & (a_{1} + a_{2} + a_{3} + a_{4})b_{0} \\ b_{4} & b_{3} & b_{2} & b_{1} & b_{0} \end{matrix} )

(b) Vérifier que la somme de chaque ligne est égale à 1.

Manipulation simple en utilisant a_{0} + a_{1} + a_{2} + a_{3} + a_{4} = 1 et b_{0} + b_{1} + b_{2} + b_{3} + b_{4} = 1.

(c) Calculer les valeurs numériques de la matrice si a_{0} = 0.1, a_{1} = 0.2, a_{2} = 0.3, a_{3} = 0.3, a_{4} = 0.1 b_{0} = 0.1, b_{1} = 0.1, b_{2} = 0.4, b_{3} = 0.2, b_{4} = 0.2

( \begin{matrix}0.1 & 0.2 & 0.3 & 0.3 & 0.1 \\ .09 & 0.19 & 0.29 & 0.39 & 0.04 \\ 0.08 & 0.17 & 0.59 & 0.09 & 0.07 \\ 0.04 & 0.4 & 0.37 & 0.1 & 0.09 \\ 0.2 & 0.2 & 0.4 & 0.1 & 0.1 \end{matrix} )

(d) Quelle est la probabilité de changer de l’état 2 à l’état 3 en deux transitions ? (Ici je numérote les états selon le nombre de camions à Bordeaux, c’est-à-dire de 0 à 4.) 0.08 ∗ 0.3 + 0.17 ∗ 0.39 + 0.59 ∗ 0.09 + 0.09 ∗ 0.1 + 0.07 ∗ 0.1 = 0.1594

(e) Ecrire un programme pour calculer P^{(2)}

main()
{ float P[5][5], temp[5][5],s;
        int i,j,k,m;
        P[0][0]=0.1;P[0][1]=0.2;P[0][2]=0.3;P[0][3]=0.3;P[0][4]=0.1;
        P[1][0]=0.09;P[1][1]=0.19;P[1][2]=0.29;P[1][3]=0.39;P[1][4]=0.04;
        P[2][0]=0.08;P[2][1]=0.17;P[2][2]=0.59;P[2][3]=0.09;P[2][4]=0.07;
        P[3][0]=0.04;P[3][1]=0.4;P[3][2]=0.37;P[3][3]=0.1;P[3][4]=0.09;
        P[4][0]=0.2;P[4][1]=0.2;P[4][2]=0.4;P[4][3]=0.1;P[4][4]=0.1;
        for (i=0;i<5;i++)
                for(j=0;j<5;j++)
                {s=0;
                        for (k=0;k<5;k++) s+= P[i][k]*P[k][j];
                        temp[i][j]=s;
                }
        for (i=0;i<5;i++)
        {
                for(j=0;j<5;j++) printf("%f   ",temp[i][j]);
                printf("\n");
        }

}
0.084000   0.249000   0.416000   0.175000   0.076000
0.072900   0.267400   0.413500   0.170200   0.076000
0.088100   0.198600   0.482700   0.159400   0.071200
0.091600   0.204900   0.419300   0.220300   0.063900
0.094000   0.206000   0.431000   0.194000   0.075000

(f) Modifier votre programme afin de calculer P^{(128)}

main()
{ float P[5][5], temp[5][5],s;
        int i,j,k,m;
        P[0][0]=0.1;P[0][1]=0.2;P[0][2]=0.3;P[0][3]=0.3;P[0][4]=0.1;
        P[1][0]=0.09;P[1][1]=0.19;P[1][2]=0.29;P[1][3]=0.39;P[1][4]=0.04;
        P[2][0]=0.08;P[2][1]=0.17;P[2][2]=0.59;P[2][3]=0.09;P[2][4]=0.07;
        P[3][0]=0.04;P[3][1]=0.4;P[3][2]=0.37;P[3][3]=0.1;P[3][4]=0.09;
        P[4][0]=0.2;P[4][1]=0.2;P[4][2]=0.4;P[4][3]=0.1;P[4][4]=0.1;
        for (m=1;m!=128;m*=2)
        {
        for (i=0;i<5;i++)
                for(j=0;j<5;j++)
                {s=0;
                        for (k=0;k<5;k++) s+= P[i][k]*P[k][j];
                        temp[i][j]=s;
                }
        for (i=0;i<5;i++)
                for(j=0;j<5;j++)
                        P[i][j]=temp[i][j];
        }
        for (i=0;i<5;i++)
        {
                for(j=0;j<5;j++) printf("%f   ",temp[i][j]);
                printf("\n");
        }
}
0.085451   0.219660   0.446916   0.176322   0.071650
0.085451   0.219660   0.446916   0.176322   0.071650
0.085451   0.219660   0.446916   0.176322   0.071650
0.085451   0.219660   0.446916   0.176322   0.071650
0.085451   0.219660   0.446916   0.176322   0.071650

(g) Que remarquez-vous dans la matrice P^{(128)} ? Toutes les lignes sont pareilles. (La distribution limite)