Si une chaîne de Markov a

1: [5 points]

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?

Plusieurs classes finales apériodiques
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 = ∑_k a_j,kp_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
π_j = ∑_k π_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
∑_k π_k = 1
pour donner un système non-singulier.

Une classe finale périodique
Réponse
Dans ce cas il y a une limite pour chaque état de départ et chaque entier j (0 ≤ j < λ) (λ est la période) qui est valable pour les temps t congruents à j (modulo λ). Pour calculer ces limites, il faut
- calculer la période λ
- trouver les sous-classes
- trouver la distribution limite dans chaque sous-classe pour la chaîne dont la matrice est a^λ
- calculer la probabilité limite d'être dans chaque sous-classe pour les temps t congruents à j (modulo λ).
Les sous-classes et la période se trouvent facilement à partir d'une grande (par exemple n²) 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 λ) est calculée par le premier algorithme cité appliqué à a^λ ; ensuite la probabilité d'être dans la sous-classe numéro i à temps congruent à j est la probabilité d'être dans i-j (modulo λ) à 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.

Dans chaque cas, expliquez les principales étapes du calcul des limites qui existent.

2: [5 points]

Dans les trois jeux donnés, la première matrice est celle des gains du premier joueur qui choisit la ligne.

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?
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.

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?
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).

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.)
Réponse
Pour le jeu 2, si le premier joueur a une stratégie mixte optimale avec probabilités x₁, x₂, x₃ de choisir chaque ligne, on sait qu'il a le même gain pour chaque stratégie de l'autre. Donc,
5x₁+4x₂+6x₃ = 4x₁+7x₂+6x₃ = 8x₁+7x₂+4x₃. Avec la troisième équation x₁+x₂+x₃ = 1, ça suffit pour calculer les x.
Pour l'autre c'est pareil. 5y₁+7y₂+5y₃ = 8y₁+6y₂+4y₃ = 6y₁+5y₂+7y₃ et y₁+y₂+y₃ = 1.

(

7
2
7

4
6
8

6
9
4
)(

7
8
4

4
3
5

8
2
6
)

(

5
4
8

4
7
7

6
6
4
)(

5
7
5

8
6
4

6
5
7
)

(

6
8
2

4
5
3

8
10
1
)(

2
5
4

9
8
7

5
10
9
)

3: [5 points]

Pour le programme linéaire
Maximiser -1x₁+2x₂+3x₃-3x₄ sous les contraintes :

5x₁+4x₂ -3x₃ +2x₄

≤

3x₁+0x₂ +6x₃ +4x₄

≤

-3x₁+2x₂ +6x₃ +8x₄

≤

(x₁, x₂, x₃, x₄

≥

la matrice des coefficients et les deux vecteurs après l'ajout des variables d'écart sont

-3

-1

-3

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.
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

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

-1
2
3
-3
0
0
0

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.

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

2
0
-3
-11
0
0
-1

Solution de base (0,1,0,0,4,1,0)
Les variables de la base sont x₂, x₅ et x₆ ; 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₅, x₆ et x₂ respectivement.

4: [5 points]

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.
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

Y n'est pas déjà dans l'arbre

soit un lien X→ Y n'est pas saturé, soit il existe un flot non-nul Y→ X.

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
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→ A→ B→ D de 3 unités.

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

et pourquoi le flot trouvé est forcément maximum quand le processus s'échoue.
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

chaque lien P1→ P2 est saturé

aucun lien P2→ P1 n'a un flot non-nul

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.

File translated from T_EX by T_TH, version 3.05.
On 24 Jan 2008, 11:20.