`: `; `! `?  

Figure

    Année 2005-2006 Session de première session
   GU : Master 1 MIAGe UE : MIG715
   Épreuve de : Recherche Opérationnelle
   Date :

Durée : 1h30
   Documents autorisés
   Épreuve de Monsieur Robson

Figure





1
[6 points]

  1. [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?
    (
    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
    )

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

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

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

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 depi à une destination desti (desti > depi) à un prix de prixi, les valeurs dep, dest et prix étant stockés dans trois tableaux. Une personne utilisant un billet i doit commencer son trajet à depi et continuer jusqu'à desti. On veut calculer si le voyage est possible et le coût total minimal des billets.

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

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



File translated from TEX by TTH, version 3.05.
On 14 Dec 2006, 11:22.