Année 2005-2006 Session de première session

GU : Master 1 MIAGe UE : MIG715 Épreuve de : Recherche Opérationnelle Date : 21 Décembre 2005, 14h Durée : 1h30

Documents autorisés

Épreuve de Monsieur Robson

1 [6 points]

i. [2 points] La chaîne de Markov, dont la matrice de probabilités de transitions est donnée, 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} )

ii. [4 points] Décrivez une méthode qui permet de calculer exactement la probabilité asymptotique que le système se trouve dans un état donné après un nombre de transitions 1 + kλ quand k tend vers l’infini étant donné qu’il commence dans l’état 1.

2 [6 points]

Dans l’exécution de l’algorithme du simplexe, on a à chaque itération un ensemble de contraintes dans la forme des équations qu’on peut exprimer dans la forme Ax = b où A est une matrice et b le vecteur de parties droites.

i. [2 points]

Expliquez pourquoi le vecteur b ne doit jamais avoir aucun élément négatif. ii. [4 points]

Pourquoi, avec le bon choix d’un pivot, l’opération de pivotage est-elle garantie de ne pas introduire d’éléments négatifs en b?

1/2 3 [8 points]

Trois voyageurs veulent aller de la ville 1 à la ville n par une route qui passe par les villes 2, 3, ..., n − 1 ; il existe un nombre m de billets disponibles, un seul de chaque type, où billet numéro i permet d’aller d’une ville de départ dep_{i} à une destination dest_{i} (dest_{i} > dep_{i}) à un prix de prix_{i}, les valeurs dep, dest et prix étant stockés dans trois tableaux. Une personne utilisant un billet i doit commencer son trajet à dep_{i} et continuer jusqu’à dest_{i}. On veut calculer si le voyage est possible et le coût total minimal des billets.

i. [6 points] Expliquer comment ce calcul peut être exprimée comme un Programme Linéaire en Nombres Entiers ou comme un programme dynamique.

ii. [2 points] Laquelle des deux formulations donnerait le calcul le plus efficace ?

2/2